Obtener los puntos de esquina de un polígono definido por ecuaciones lineales.
Digamos que tenemos una lista de n ecuaciones m * x = b
Quiero obtener todos los puntos de esquina del polígono que tiene el eje x, el eje y y las líneas rectas como caja delimitadora.
Los círculos rojos en la imagen de abajo muestran los puntos que quiero.
¿Cómo puedo obtenerlos si tengo una lista de tuplas (m, b)?
La complejidad temporal no importa.
davy.ai
Para obtener los puntos de esquina del polígono, necesitamos resolver los puntos de intersección de las ecuaciones dadas. Aquí están los pasos para lograr esto:
m * x = ba partir de las parejas dadas(m, b).A continuación, podemos resolver los puntos de intersección de cualquier par de ecuaciones para obtener los vértices del polígono.
Para obtener todos los puntos de esquina del polígono, necesitamos resolver las intersecciones de todas las posibles parejas de ecuaciones. Esto se puede hacer utilizando un bucle anidado para iterar sobre todas las parejas de ecuaciones.
Una vez que hayamos obtenido todos los puntos de intersección, podemos filtrar los puntos que se encuentren dentro del cuadro delimitador definido por los ejes x e y.
Los puntos restantes son los puntos de esquina del polígono.
Tenga en cuenta que el cálculo del punto de intersección de dos líneas
y = m1*x + b1yy = m2*x + b2implica resolver el sistema de ecuaciones:lo cual nos da:
Podemos usar estas ecuaciones para calcular el punto de intersección de cualquier par de líneas dadas sus pendientes e intersecciones en y.
La complejidad temporal de este método dependerá del número de ecuaciones y del algoritmo específico utilizado para resolver el sistema de ecuaciones y obtener los puntos de intersección. Dado que la complejidad temporal no es una restricción, podemos utilizar fuerza bruta para calcular todas las intersecciones posibles de pares de líneas.