Compruebe si el polígono convexo está completamente contenido dentro de otro polígono convexo.

¿Cómo puedo determinar si un polígono convexo está completamente contenido dentro de otro polígono convexo donde la velocidad es crítica? He pensado en hacer esto, que solo usará desigualdades:

pcp = polígono potencialmente contenido

  1. Iterar a través de cada uno de los puntos de pcp, comparando cada uno con cada uno de los puntos del polígono contenedor.
  2. Determine si el punto de pcp está a la izquierda/derecha y en la parte inferior/superior del primer punto.
  3. Compruébalo con cualquier otro punto del polígono contenedor. Si el punto del pcp no tiene la misma orientación horizontal y vertical que la primera verificación en el paso 2, entonces el punto del pcp no está contenido, por lo tanto, el pcp completo no está contenido.

¿Estoy en el camino correcto? No he implementado esto, así que no tengo idea de si funcionará. ¿Hay métodos más rápidos o mejoras que se podrían hacer?

Respuestas (1)

Un polígono convexo puede estar dado por sus vértices o, a menudo más adecuadamente, por desigualdades a i X + b i y ≥ C i describiendo los semiplanos cuya intersección es el polígono. Con la última forma, un punto del plano está dentro del polígono si y solo si todas las desigualdades se cumplen para sus coordenadas (o posiblemente en el límite si tenemos igualdad en al menos una de las desigualdades). Por lo tanto, si tenemos los vértices del polígono potencialmente contenido y las desigualdades del polígono potencialmente contenido, solo necesita comparar cada uno de los vértices con cada una de las desigualdades. esto toma O ( norte metro ) tiempo si norte , metro son el número de vértices. (Tenga en cuenta que no hicimos uso del hecho de que el polígono potencialmente contenido es convexo)

Gracias por la respuesta, pero su explicación fue demasiado sofisticada para mí. ¿Qué representan aix, biy y ci? Además, ¿cómo se relaciona el medio plano con la verificación de contención?
@ JPtheK9 Un polígono convexo es la intersección de un número finito de semiplanos. Un punto está dentro del polígono si y solo si está dentro de todos estos semiplanos.
Ah, claro. Si ese es el caso, ¿debería hacer Dot ( pcp*[i], (*cp*[i] - *cp*[i-1]).Right) >= 0 para encontrar si el punto está debajo del semiplano , donde *cp = Polígono Contenedor ? Supongo que si los vértices fueran en sentido contrario a las agujas del reloj, tendría que cambiar la desigualdad a <= pero eso es solo una cuestión de desigualdades.
Compruebe si el polígono convexo está completamente contenido dentro de otro polígono convexo.
RespuestasAquíPolítica de privacidad1y, 0v