Tengo 2 polígonos Sé las coordenadas de vértice de ambos polígonos. ¿Cuál es la mejor manera de verificar si uno está completamente dentro del otro? Por ejemplo, el algoritmo solo debe reconocer el trapecio negro a continuación como contenido:
collision-detection
vector
geometry
usuario960567
fuente
fuente
Respuestas:
Hay toneladas de fragmentos de código fuente para un método que realiza una prueba de " punto dentro del polígono ". El principio proviene del teorema de la curva de Jordan para polígonos ( http://www-cgrl.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Octavian/compgeom.html ).
La forma ingenua sería: teniendo ese método, llámelo
PointInsidePolygon(Point p, Polygon poly)
:Teóricamente, no debería perderse ningún escenario para sus polígonos, pero no es la solución óptima.
Observaciones del caso "Edge"
PointInsidePolygon(..)
debe devolver verdadero si el punto está en el borde del polígono (ya sea en un borde o es un vértice)EdgesIntersect(..)
debe devolver falso si elinnerEdge
es un subconjunto (geométricamente sabio) delouterEdge
. En este caso, los bordes obviamente se cruzan, pero para el propósito del algoritmo, debemos indicar que la intersección no está rompiendo la semántica detrás de laisInside
variableRemakrs generales :
sin controles de intersección de borde frente a borde, como se señala en los comentarios, el enfoque podría devolver falsos positivos para algunos polígonos cóncavos (por ejemplo, un quad en forma de V y un rectángulo; el rectángulo podría tener todos sus vértices dentro de la forma de V, pero intersecarlo , teniendo así al menos algunas áreas afuera).
después de que uno verifique que al menos uno de los vértices del polígono interno esté dentro del externo, y si no hay bordes de intersección, significa que se cumple la condición buscada.
fuente
Intenta hacer una intersección de línea con cada línea roja. En pseudocódigo:
Sin embargo, como puede ver, esta solución será más lenta a medida que agregue más polígonos para verificar. Una solución diferente podría ser:
Esta solución es muy rápida, pero depende de su implementación (y de lo que quiera hacer con el resultado de su verificación) qué solución funciona mejor para usted.
fuente