Come faccio a trovare l'area di sovrapposizione tra i due poligoni arbitrari

Question

Sto cercando di creare un metodo che si terrà in due liste arbitrarie di nodi, per un soggetto e un poligono di ritaglio, e l'uscita sia:

a) l'area della sovrapposizione
b) una lista di nodi per la risultante (ritagliato) poligono in modo che possa calcolare l'area

ho trovato molti esempi che clip in un poligono arbitrario utilizzando rettangolare finestra (che è abbastanza standard nella grafica) ma non è quello che mi serve. Capisco che è abbastanza complesso, in particolare quando si ottengono buchi, poligoni convessi e simili. L'unica supposizione semplificante che posso fare è che i poligoni arbitrari non contengono buchi.

Non sono affatto un esperto in questo campo, quindi funzionerebbe qualcosa come l'algoritmo Sutherland-Hodgman? Ci sono delle librerie là fuori che già fanno questo, o è la mia migliore scommessa per implementare semplicemente l'algoritmo come descritto in pseudo-codice su Wikipedia?

Grazie per l'aiuto!

Answer 1

Ho scoperto che l'utilizzo della libreria JavaGeom funzionava molto bene. Integra il codice dalla porta Java di GPC (che non è più disponibile) e quindi consente operazioni poligonali arbitrarie. Usando SimplePolygon2D e Polygon2DUtils.intersection() sono stato in grado di ottenere l'operazione desiderata.

Answer 2

Ci sono delle librerie là fuori che già fanno questo ...

poligono di ritaglio è un compito complesso. Non raccomanderei di provare a farlo da soli, a meno che non vogliate trascorrere molti mesi su di esso. Wikipedia elenca una serie di clipping librerie (e IIRC in tale elenco solo Clipper è gratuito per uso in applicazioni commerciali): http://en.wikipedia.org/wiki/Boolean_operations_on_polygons#External_links

ps: ammetto di un pregiudizio personale per Clipper dato che sono l'autore :) maggiori informazioni qui: http://angusj.com/delphi/clipper.php

Answer 3

Suona come Weiler-Atherton è quello che vi serve:

l'algoritmo richiede poligoni di essere in senso orario e non rientrante (auto intersezione) . L'algoritmo può eseguire i fori di supporto (come poligoni poligoni in senso antiorario ), ma richiede ulteriori algoritmi per decidere quali poligoni sono fori.

I poligoni corrispondono a questi criteri, giusto? Non so sulle implementazioni, ma sembra che sarebbe meglio implementare W-A che S-H se uno dei poligoni potrebbe essere concavo.

Answer 4

Prova gpc.

Answer 5

Ho provato molte librerie diverse e quella che ha funzionato meglio è stata la JTS Topological Suite che è in licenza Java e LGPL2.