Saludos,Segmento-polígono intersección
Me gustaría detectar si un segmento solo 'toca' un polígono o lo cruza.
La Figura
explica mi duda. ¿Cómo saber la diferencia entre los casos A y B? Tenga en cuenta que en ambas situaciones, la línea roja cruza los polígonos en dos vértices, uno que toca por fuera y otro que cruza por dentro. Tengo un algoritmo de intersección segmento segmento, pero no sé cómo usarlo correctamente. Cualquier ayuda es apreciada.
Creo que puede que no haya un enfoque mucho más fácil que el cálculo de los detalles en un nivel bajo. Primero, necesitará un código robusto para calcular la intersección entre dos segmentos. Esto se discute (con el código) here. Una vez que tenga los puntos de intersección, necesita para calcular cómo el límite del polígono interactúa con su segmento en las cercanías de esos puntos de intersección . Esto es esencialmente cálculos repetidos LeftOf(), usando la notación en mi libro. En su imagen, el segmento pasa a través de vértice b, mientras que los vértices adyacentes un y c (en una secuencia consecutiva (a, b, c)) son ambos al mismo lado de b. Por lo tanto, el segmento no penetra en el interior del polígono en el entorno de b. Pero si a y c estaban en lados opuestos del segmento, entonces debe penetrar.
Muchas gracias Prof. O'Rourke. La idea detrás de 'LeftOf' resuelve el problema cuando el segmento intersecta el polígono en los vértices. – ricfow
Generalizando, una intersección puede comprender muchos puntos. Por ejemplo, vea http://cagd.cs.byu.edu/~557/text/ch7.pdf que discute cómo se cruzan las curvas planas, y dice que las curvas tangentes se cruzan en dos puntos "contados correctamente", lo cual es contrario a la intuición. En el caso de un polígono convexo con una línea de pastoreo, ¿la intersección tiene dos puntos "contados correctamente"? En su caso, ¿hay dos intersecciones con dos puntos cada una?
Así que el Prof. O'Rourke proporciona un algoritmo para calcular el número de puntos en la intersección, por así decirlo. Pragmáticamente, ¿debería un paquete para calcular intersecciones devolver el conteo de puntos en cada intersección?
¿Son sus polígonos siempre simples, o también pueden ser complejos? –
Polígonos cóncavos sin bordes autointersecantes. Los agujeros pueden existir. – ricfow
no estoy seguro si todavía tiene una pregunta o no. Tu comentario a la respuesta del profesor O'Rourke parece indicar que no, pero no has aceptado su respuesta (todavía). –