Algoritmo per verificare se un Cerchio è totalmente contenuto nell'area di altri cerchi

Question

Quale sarebbe l'algoritmo per verificare se un cerchio come quello blu in basso è TOTALMENTE contenuto nell'area di altri cerchi (i cerchi del tempo). Voglio un VERO per il cerchio blu e un FALSO per il cerchio rosso

L'input per tutti i cerchi è le loro coordinate e il loro raggio.

Answer 1

Questo sembra semplice (EDIT: ma non è): se ogni punto di ogni arco di cerchio dato è contenuto in almeno uno degli altri cerchi, allora l'intero cerchio è contenuto. Dovresti quindi trovare tutte le intersezioni (algorithm to detect if a Circles intersect with any other circle in the same plane) e fare un controllo per tutti gli archi specificati da questi incroci. Se qualsiasi punto "interno" di un arco A1-A2 del cerchio A per le due intersezioni date con il Cerchio B (arco B1-B2, dove i punti A1 = B1 e A2 = B2) è contenuto nel cerchio B, allora l'intero arco è contenuto nel cerchio B e viceversa. Perfavore, correggimi se sbaglio.

MODIFICA: Ok, lo so già, che ho sbagliato, come ha mostrato maxim1000. Questo è più complicato di quanto pensassi. Penso di aggiungere qualcosa alla mia risposta, ma non sono sicuro, se questa è una soluzione. Spero che aiuti, comunque. Vale a dire: penso a determinare l'area totale delle intersezioni tra il nostro cerchio in mente e tutti gli altri. Troviamo tutte le intersezioni separate all'interno del nostro cerchio - tutte le parti che includono gli stessi punti, che sono separati da tutti gli archi intersecanti - e trovano le loro aree. Wu riassumili. Se è uguale all'area del nostro cerchio, allora il nostro cerchio è contenuto in altri cerchi. Determinare quest'area può essere un problema da solo, ma come ho detto, può portare nella giusta direzione. Fammi pensare troppo ..

EDIT: Dopo un po 'di pensiero. Determinare tutte le aree in (più) cerchi intersecanti è solo questione di aggiungere o sottrarre triangoli o ... hmmm ... come chiamarli? ... parti gialle come qui sull'immagine :)

Answer 2

Io non credo che ci sia una soluzione facile.

Vorrei rispondere prendendo ogni cerchio a turno e eseguendo una sottrazione booleana di tutti gli altri cerchi. (I cerchi che sono abbastanza lontani - R0 + R1 < D12 - non interferiranno.)

Dopo che i pezzi sono stati mangiati, un cerchio diventa un poligono curvilineo fatto di archi circolari, o un insieme di tali poligoni, come può la connessione essere rotto. Un poligono può essere rappresentato dall'elenco di cerchi che contribuiscono con un arco del suo contorno e i punti finali degli archi sono definiti dall'intersezione comune di due vicini consecutivi o del cerchio di destinazione e di un vicino. Si noti che lo stesso vicino può apparire più volte.

Per rendere le cose un po 'più cruente, i poligoni possono avere buchi, che è necessario rappresentare anche.

Quindi un'operazione cruciale è la sottrazione di un cerchio da un poligono curvilineo. È necessario rilevare gli archi che si trovano interamente all'interno del nuovo cerchio e quelli che lo attraversano. Dopo aver ottenuto le parti rimanenti degli archi, è necessario riorganizzare gli archi rimanenti e quelli nuovi.

Immagino che tutte queste operazioni possano essere costruite da una singola primitiva che trova la parte di un arco (definito da tre cerchi) all'interno di un disco.

Answer 3

Ecco una soluzione grezza:

• prendere tutti i circoli e trovare tutti i punti di di intersezione che sono sia sopra o all'interno il test cerchio T. Split i bordi corrispondenti e costruire un grafico del bordo:

Per ciascun bordo, tenere traccia del cerchio che lo ha creato.

• individuare tutte le non sovrapposti regioni all'interno del cerchio, usando il minimo ciclo algoritmo (Find all non-overlapping polygons in a list of edges/vertices).

• Per ogni delimitazione bordo e di ogni regione R a trovare, prendere la Circle C che E appartiene. Se C è non T (rosso) - cioè E è blu, controllare se i punti sugli altri bordi R sono all'interno C:

  • Se sono poi C copre R. Continuare sulla regione successiva .
  • Se non lo sono, allora R è non comprese C. loop sugli altri bordi blu delimitano R.
  • Se alla fine R è ancora non coperto, allora T non è completamente coperto - ritorno falso.

nello schema precedente, C contiene B, quindi R è coperto; ma C non contiene A, in modo da non coprire S

• Se non si è ancora tornato in questa fase per poi tornare vero.

---

casi collaterali:

• Se un determinato cerchio contiene T, allora l'ignorano.
• Se T contiene è, quindi differire il test di intersezione memorizzandolo in un elenco. Alla fine, rifai il test e dividi i bordi.

Questo algoritmo è altamente inefficiente, e non sono sicuro al 100% se ci sono casi più degeneri; se qualcuno ha qualche suggerimento per favore fatemelo sapere.