Circle-poligono intersezioni

Question

Una geometria computazionale problema:
Il punto P0 è scelto a caso su un bordo (ad esempio, EB) di un poligono (ad esempio, BCDE), per trovare possibili punti (cioè, P1,P2,P3,...) su altri bordi basati sulla distanza specificata (es., r). La seguente dimostrazione mostra una soluzione trovando le intersezioni tra il cerchio centrato sul punto P0 e i bordi del poligono. Quindi il problema in sostanza potrebbe essere risolto con l'analisi dell'intersezione Circle--Line-Segment.

Mi chiedo esiste un metodo più efficiente per questo problema molto semplice in termini di costi di calcolo? Il processo sarà valutato diversi million times quindi qualsiasi improvvisazione è di interesse.

• la soluzione finale beneficerà Python potenza;
• il calcolo di base sarà in Fortran se necessario.

Aggiornamenti:
Grazie per i vostri commenti. Si prega di considerare i miei commenti sui commenti che aiutano a chiarire di più la domanda. Non sono disposto a ripeterle qui, incoraggiando a considerare tutti i commenti e le risposte;).

Ho appena implementato il metodo Circle--Line-Segment Intersection in base all'algoritmo trovato [here]. In realtà l'ho adattato per funzionare con segmenti di linea. Il benchmark del algoritmo implementato in Python è il seguente:


il numero di segmenti di linea è: 100,000 e il sistema è usuale desktop. Il tempo trascorso è: 15 seconds. Spero che questi siano utili per dare un'idea del costo del calcolo. L'implementazione di core in Fortan potrebbe migliorare significativamente le prestazioni.
Tuttavia la traduzione è l'ultimo passaggio.

Answer 1

Per intersezione tra line (o line-segment) e un circle (sphere in 3D) c'è un po 'più spiegazione, dettagli di implementazione e anche Python, C ecc codici campione in [this link]. Puoi provarli per il tuo problema.
L'idea è sostanzialmente la stessa che hai già trovato in [here].

Answer 2

Supponendo che il circle--line-intersection è ottimizzato, si potrebbe essere in grado di ottenere qualcosa distinguendo tra i diversi casi:

per il punto A, B:

• Se d (P0, A) < r e d (P0, B) < r: n intersezione

• se d (P0, a) == r: intersezione di un

• se d (P 0, B) == r: Intersezione di B
• Se d (P0, A) < r e d (P0, B)> r: 1 intersezione, eseguire circle--line-intersection

• Se d (P0, A)> r e d (P0, B) < r: 1 intersezione, eseguire circle--line-intersection

• Se d (P0, A)> r e d (P0, B)> r: C'è 0, 1 o 2 intersezioni -> Se il minimum distance in linea (A, B)> r: Nessuna intersezione -> Se il minimum distance in linea (A, B) == r: 1 intersezione -> Se il minimum distance in linea (A, B) < r: 2 intersectio ns