intersecciones Circle-Polygon

Question

A Computational Geometry problema:
El punto P0 se elige al azar en un borde (por ejemplo, EB) de un polígono (por ejemplo, BCDE), para encontrar posibles puntos (es decir, P1,P2,P3,...) en otro bordes basados ​​en la distancia dada (es decir, r). La siguiente demostración muestra una solución al encontrar intersecciones entre el círculo centrado en el punto P0 y los bordes del polígono. Entonces el problema básicamente podría resolverse mediante el análisis de intersección Circle--Line-Segment.

Me pregunto ¿Hay algún otro método más eficaz para este problema muy simple en términos de costo de cálculo? El proceso se evaluará varios million times por lo que cualquier mejora es de interés.

• la solución final se beneficiará de Python poder;
• el cómputo central estará en Fortran si es necesario.

actualizaciones:
, gracias por sus comentarios. Por favor, considere mis comentarios sobre los comentarios que ayudan a aclarar la pregunta más. No estoy dispuesto a repetirlos aquí, alentándome a considerar todos los comentarios y respuestas;).

Acabo de implementar el método de Circle--Line-Segment Intersection basado en el algoritmo encontrado [here]. En realidad, lo adapté para trabajar con segmentos de línea. El punto de referencia del algoritmo implementado en Python es como sigue:


El número de segmentos de línea es: 100,000 y el sistema es de escritorio habitual. El tiempo transcurrido es: 15 seconds. Espero que estos sean útiles para dar una idea del costo de cálculo. La implementación de core en Fortan podría mejorar el rendimiento significativamente.
Sin embargo, la traducción es el último paso.

Answer 1

Para intersección entre line (o line-segment) y un circle (sphere en 3D) hay un poco más de explicación, los detalles de implementación y también Python, C etc códigos de ejemplo en [this link]. Puedes probarlos para tu problema.
La idea es básicamente la misma que ya ha encontrado en [here].

Answer 2

Suponiendo que el circle--line-intersection está optimizado, es posible que pueda ganar algo al distinguir entre diferentes casos:

para el punto A, B:

• Si d (P0, A) < ry d (P0, B) < r: No intersección

• si d (P0, a) == r: intersección en a

• si d (P 0, B) == r: Intersección en B
• Si d (P0, A) < r y d (P0, B)> r: 1 intersección, ejecutar circle--line-intersection

• Si d (P0, A)> r y d (P0, B) < r: 1 intersección, ejecutar circle--line-intersection

• Si d (P0, A)> r y d (P0, B)> r: No es 0, 1 o 2 intersecciones -> Si el minimum distance a la línea (A, B)> r: No hay intersecciones -> Si el minimum distance a la línea (A, B) == r: 1 intersección -> Si el minimum distance a la línea (A, B) < r: 2 intersectio ns