Cómo determinar una diagonal se encuentra dentro o fuera de un polígono cóncavo?

Question

La diagonal (diagonal es un segmento que conecta los vértices no adyacentes) de un cóncavo (no convexa) polígono puede ser completamente dentro o fuera del polígono(o puede intersectar con los bordes del polígono).Cómo determinar si se encuentra completamente en el polígono?(un método sin punto en el polígono de prueba).

Answer 1

Si la diagonal tiene al menos una intersección con los ejes, es parcialmente dentro y parcialmente fuera del polígono, sin embargo, Si la diagonal no tiene intersección con ellos, sólo hay dos estados:es compeletely o completamente fuera del polígono.

Para determinar si se encuentra dentro o fuera del polígono:

Supongamos polígono de vértices están ordenados en sentido antihorario.Considerar uno de los extremos de la diagonal que se encuentra en el vértice denominado P[i] (el otro extremo es p[j]).A continuación, Hacer tres vectores cuyos primeros puntos p[i] :

V1 :p[i+1] - p[i]

V2 :p[i-1] - p[i]

V3 :p[j] - p[i]

La diagonal es completamente en el polígono si y sólo si V3 es entre V1 y V2 cuando se mueve alrededor de la izquierda de V1 a V2.

Cómo determinar si la V3 es entre V1 y V2 cuando vamos de V1 a V2 en sentido antihorario?ir a aquí.

He escrito un programa utilizando este método y funciona de manera efectiva .

Answer 2

  

Cómo determinar si es completamente en el polígono?

Si desea determinar si una diagonal que nunca deja los límites del polígono, simplemente determinar si es o no cruza ninguna línea entre dos vértices adyacentes.

• Si lo hace, es parcialmente dentro y parcialmente fuera del polígono.

• Si no, es ya sea totalmente o completamente fuera del polígono. A partir de ahí, el método más simple es utilizar el punto en el polígono en cualquier punto de la diagonal, pero si usted no quiere hacer eso, utilice el devanado algoritmo .

Answer 3

Creo que la respuesta de Juan pierde un caso importante: cuando la diagonal es completamente fuera del polígono desde el primer momento. Imagínese haciendo que el "puente" diagonal de las dos torres de la "U" en forma de polígono.

he tenido que resolver este hace varios años, así que por favor perdone si mi recuerdo es un poco irregular.

La forma Solucioné esto fue para realizar pruebas de intersección línea de la diagonal en contra de cada borde en el polígono. A continuación, tiene dos casos posibles: o se tenían al menos una intersección, o que no tenía intersecciones. Si obtiene algún intersecciones, la diagonal no está dentro del polígono.

Si usted no recibe ninguna intersección, es necesario determinar si la diagonal es completamente dentro o completamente fuera del polígono. Digamos que la diagonal es unirse p [i] para p [j], que i

Una vez hecho esto, el ángulo 2D de la diagonal será positiva si la diagonal fuera del polígono, o negativo si es dentro del polígono.

Answer 4

En lo que respecta a la comprobación de intersecciones entre segmentos de línea (que es el primer paso que probablemente tendría que hacer), me encontré con las indicaciones de la SoftSurfer para ser útil. Usted tendría que comprobar si hay una intersección entre la diagonal y cualquiera de los bordes del polígono. Si está utilizando MATLAB, usted debería ser capaz de encontrar una forma eficaz para comprobar las intersecciones para todos los bordes con forma simultánea operaciones matriciales y vectoriales (He tratado con puntos de intersección de cómputo de esta manera por intersecciones ray-triángulo ).

Answer 5

respuesta de Juan es impecable:

  

Si desea determinar si una diagonal que nunca deja los límites del polígono, simplemente determinar si es o no cruza ninguna línea entre dos vértices adyacentes. Si es así, se deja el polígono.

Una forma eficiente de hacer esta comprobación es ejecutar el algoritmo sweepline Bentley-Ottman en los datos. Es fácil de aplicar, pero difícil de hacer estable numérica. Si tiene menos de ... digamos ... 20 bordes en sus polígonos una búsqueda de fuerza bruta será probablemente más rápido.