Come posso determinare se una serie di punti (o poligono) è all'interno di una regione rettangolare?

Question

Ho esaminato i messaggi sul determinare se un punto si trova all'interno di un poligono o meno e le risposte sono troppo vaghe, astratte o complesse per me. Quindi cercherò di porre la mia domanda specifica a ciò che devo fare.

Ho un set di punti che descrivono una linea non retta (a volte un poligono chiuso). Ho una regione rettangolare "vista". Ho bisogno di determinare il più efficiente possibile sia che qualsiasi dei segmenti di linea (o dei bordi poligono) passino attraverso la regione di vista.

Non riesco a testare semplicemente ogni punto per vedere se si trova all'interno della regione di vista. È possibile che un segmento attraversi attraverso la regione senza alcun punto in realtà all'interno della regione (cioè la linea è disegnata attraverso la regione).

Ecco un esempio di ciò che voglio determinare (rosso significa che la funzione dovrebbe restituire true per il set di punti, blu significa che dovrebbe restituire false, l'esempio utilizza linee rette e rettangoli perché non sono un artista). .

Un'altra condizione Voglio essere in grado di spiegare (anche se il metodo / funzione potrebbe essere un separato), è quello di determinare non solo se un bordo di un poligono passa attraverso la regione rettangolare, ma se la regione sia interamente compressa dal poligono. La sfumatura qui è che nella situazione sopra descritta sopra, se sono solo preoccupato per disegnare i confini, il metodo dovrebbe restituire false. Ma nella situazione descritta qui, se ho bisogno di riempire la regione del poligono allora ho bisogno della funzione per restituire true. Attualmente non ho bisogno di preoccuparsi di testare i poligoni a forma di "ciambella" (grazie a Dio!).

Ecco un esempio che illustra la sfumatura (il rettangolo rosso non ha un singolo vertice o segmento di bordo che passa attraverso la regione sullo schermo, ma dovrebbe ancora essere considerata sullo schermo):

Per il "qualsiasi segmento di linea o confine poligonale passano o giacciono sullo schermo?" Problema Lo so che posso trovare una soluzione (anche se forse non è efficiente). Anche se è più verboso, le condizioni sono chiare per me. Ma il secondo "è una regione di Polygon sullo schermo?" il problema è un po 'più difficile. Spero che qualcuno potrebbe avere un buon suggerimento per farlo. E se una soluzione è facilmente implementata in cima all'altra, beh, booya.

Come sempre, grazie in anticipo per qualsiasi aiuto o suggerimento.

PS Ho una funzione per determinare l'intersezione della linea, ma sembra eccessivamente usarlo per confrontare ogni segmento su ciascun lato della regione sullo schermo perché la regione su schermo è sempre una semplice [0, 0, larghezza , altezza] rettangolo. Non c'è qualche tipo di scorciatoia?

Answer 1

.

PS Ho una funzione per determinare intersezione della linea, ma sembra Overkill per usarlo per confrontare ciascuno segmento su ciascun lato dello schermo regione perché la regione sullo schermo è Sempre un semplice [0, 0, larghezza, altezza] rettangolo.Non c'è qualche tipo di Breve-taglio?

Non è un eccessivo eccessivo, il suo neccessario qui.L'unico tipo di scorciatoia a cui posso pensare è di valori hardcode [0, 0, larghezza, altezza] in quella funzione e semplificarlo un po '.

Answer 2

Quello che stai cercando è nominato Algoritmo di rilevamento della collisione Una ricerca Google ti guideràAbbastanza implementazioni in vari linguaggi e molta teoria

Ci sono un sacco di teoria geometrica alle spalle, dal semplice calcolo Bisector per limitare le triangolazioni delaunay e i diagrammi di Voronoi (che sono solo esempi).Dipende dalla forma dell'oggetto, il numero di dimensioni e di sicuro il rapporto tra l'esattezza necessaria e il tempo di calcolo offerto; -)

buona lettura