Trova la linea di separazione tra due poligoni

Question

Esiste un semplice algoritmo che trova una linea di separazione tra due poligoni in modo tale da trovarsi su entrambi i lati della linea? O preferibilmente qualcuno sa di una biblioteca che fa questo genere di cose? Qualsiasi aiuto sarebbe apprezzato

EDIT:

La mia soluzione:

ho usato JTS: http://www.vividsolutions.com/jts/JTSHome.htm

Creato due poligoni che usano questa libreria e corse DistanceOp per trovare i due punti più vicini tra i poligoni (non necessariamente i vertici). Quindi calcola semplicemente una linea perpendicolare alla linea che li connette.

Answer 1

Lasciate A e B essere i vostri due poligoni. Innanzitutto trovare lo convex hull di ciascuno, C (A) e C (B). Chiaramente una linea che separa A da B separa anche C (A) da C (B). Lasciare a un punto su C (A) e b un punto su C (B). Si può camminare un e b intorno i confini fino a quando una linea di separazione tramite un e b è trovato. Questo può essere compiuto in tempo lineare, ma non lo descriverò ora.

Answer 2

Supponiamo di avere un poligono A con i punti A1, B2, A3, ..., AN e un poligono B con i punti B1, B2, B3, ..., BN.

Che cosa si potrebbe fare è di descrivere una linea dal punto di AX per BX per ogni possibile combinazione (A1 & B1, B2 A1 &, ... AN & BN).

Tale riga può essere descritta nel formato parametrico: SomePoint = InicialPoint + Direction * t e sarà un possibile candidato in una "linea di separazione". Tienilo!

Ora quello che devi fare è DESCRIVERE UN ALTRO vettore da ogni punto di ogni poligono a questa linea di candidati. Ciascuna di quelle linee avrà il suo vettore di direzione.

Se il prodotto incrociato del vettore di direzione di ciascuna linea con il vettore di direzione del candidato ha la stessa direzione (Z-positivo o Z-negativo), significa che i punti si trovano nello stesso lato della linea di separazione (ancora candidato).

Ora controlla tutte le linee che hai descritto per ogni punto di ogni poligono. Puoi capire se tutti i punti del poligono A sono in un lato e tutti i punti nel poligono B sono nell'altro lato ... quindi hai trovato la linea che desideri. Altrimenti, devi provare una nuova linea candidata (AX-BX). Se non trovi nessuna di queste combinazioni con tutte le possibili linee candidate, significa che hai un'intersezione tra i poligoni.

Non sono sicuro che sia l'algoritmo migliore/più veloce ma sono sicuro che funzioni.