Pruebas de polígono en polígono

Question

Tengo una lista de vértices de polígonos simples, y me gustaría comprobar si un polígono está o no totalmente contenido en otro polígono de la lista.

¿Es suficiente con hacer algo como:

Dejemos que $p_0$ sea el polígono candidato.

Dejemos que $r_i, ~le_i, ~u_i, ~l_i$ denotan el vértice más a la derecha, el más a la izquierda, el más arriba y el más abajo del iésimo polígono de la lista.

Para todos los polígonos de la lista, si algún polígono tiene:

• $r_i(x) \ge r_0(x)$ Y
• $le_i(x) \le le_0(x)$ Y
• $u_i(y) \ge u_0(y)$ Y
• $l_i(y) \le l_0(y)$

donde por ejemplo $r_i(x)$ denota el $x$ -coordenada del vértice más a la derecha del $i$ -de un polígono, entonces podemos concluir que $p_0$ está totalmente contenida en $p_i$ .

¿Tiene esto sentido, y hay algún contraejemplo para el que este algoritmo no funcione?

Answer 1

La imagen muestra algunos contraejemplos, incluido uno que demuestra que el problema no es tan fácil como comprobar que todos los vértices de un polígono están dentro del otro.

Un posible enfoque sería comprobar que ninguno de los lados de los dos polígonos se cruza y que un vértice está dentro.

Véase, por ejemplo: https://stackoverflow.com/a/4833823

Answer 2

Dejemos que $p_1$ sea el cuadrilátero con vértices $(1,0), (0,1), (-1,0), (0,-1)$ . Entonces sus condiciones son para el cuadro delimitador $b$ de $p_1$ no para $p_1$ en sí mismo. En particular, un pequeño $p_0$ cabe en una esquina de $b$ pero está completamente fuera $p_1$ .

Ni siquiera es suficiente con utilizar un algoritmo de punto en polígono para comprobar si los vértices de $p_0$ están todos dentro $p_1$ porque $p_1$ puede no ser convexo.

La única forma general es comprobar que su unión es $p_1$ . Para ello puede necesitar una herramienta de recorte de polígonos como gpc . Véase también el Algoritmo de recorte Weiler-Atherton y operaciones booleanas sobre polígonos .

Answer 3

No, esto no funciona en absoluto.

Esta prueba de caja delimitadora garantiza que los polígonos son disjuntos, cuando las cajas son disjuntas. En caso contrario, no dice nada.

---

Una prueba relativamente sencilla y correcta es comprobar que no hay intersecciones de lados por pares, lo que se hace mediante pruebas exhaustivas de intersección segmento-segmento. Entonces, o bien los polígonos son disjuntos o bien uno está totalmente incluido en el otro. La decisión final se toma tomando algún vértice y aplicando una prueba de punto en polígono con respecto al otro polígono.

Si buscas una solución eficiente, puedes recurrir a un algoritmo de línea de barrido, durante el cual barres una línea horizontal a través de todos los vértices y mantienes una lista de los segmentos horizontales que cortan los polígonos. Entonces se reduce a un problema de contención de segmentos 1D.

Answer 4

Si el polígono contenedor es convexo se puede comprobar si los vértices del polígono interior están dentro utilizando algoritmos conocidos para calcular el casco convexo de un conjunto de vértices.

Ver https://en.wikipedia.org/wiki/Convex_hull_algorithms

Editar: Como sus polígonos no tienen por qué ser convexos, sospecho que no hay una respuesta muy fácil. Tal vez puedas mirar los algoritmos de cascos convexos y encontrar una manera de modificar uno para comprobar si cada vértice del polígono interior está en el lado correcto de cada arista del exterior. @lhf apunta a gpc, que parece prometedor.

Answer 5

Su prueba es una condición necesaria, pero no suficiente, para la interioridad.

Aunque esto pueda parecer inútil, puede utilizar su prueba como una primera prueba rápida para excluir la mayoría de las posibilidades, y luego pasar a una prueba más complicada para decidir los casos restantes.

No es conveniente utilizar la complicada prueba en todas las combinaciones posibles, ya que esto podría ser muy lento, dependiendo de $n$ .

Creo que la prueba completa más rápida sería:

Cada vértice de $p_0$ debe estar dentro de $p_i$ y cada vértice de $p_i$ debe estar fuera $p_0$ .

Entonces, ¿cómo se comprueba si un punto está dentro de un polígono?

Se trata de un problema muy estudiado y con muchos recursos disponibles en la web. Empezando por el Página de Wikipedia He encontrado esta página que describe dos algoritmos. Si ese enlace se rompe, un búsqueda en la web le dará muchos otros.