Qual è il modo più veloce per creare l'unione di molti boost :: poligoni?

Question

Devo unire molti boost :: polgons, ma il mio approccio non sembra molto performante (> 15 min), specialmente con un numero maggiore di poligoni (> 2000).
Spingo tutti i poligoni voglio unione in un multipoligono e poi unire il multipoligono,
vedere il mio codice:

BOOST_FOREACH(polygon, multipolygon) 
{ 
    boost::geometry::clear(tmp_union); //tmp_union is a multipolygon 
    boost::geometry::union_(result, poly, tmp_union); 
    result = tmp_union; 
} 

Il risultato sarà presumibilmente non conterrà moltissimi poligoni, perché la maggior parte dei poligoni a Unione intersecano.

C'è un modo per rendere questo più performante, come ordinare i poligoni in un ordine specifico o un approccio completamente diverso?

Grazie

Answer 1

Si potrebbe desiderare di guardare a come CGAL sta facendo le cose. Almeno hanno a function per unirsi a più di un poligono. Guardando il codice, noto una chiamata a una funzione _devide_and_conquer. Il che dovrebbe tradursi in boost: dividi l'elenco di poligoni in due, calcola l'unione per ciascuno e poi l'unione di entrambi. Almeno se il poligono risultante è ancora più complesso di quelli originali, questo dovrebbe dare qualche miglioramento.

Se non è ancora abbastanza, si può dare a CGAL una prova per vedere se c'è qualche altra magia che lo rende più veloce di boost. In caso contrario, potrebbe essere necessario implementare il calcolo da soli.

Immagino di dover ordinare i bordi dei poligoni in ordine crescente del valore x dell'endpoint sinistro. Quindi puoi scorrere i bordi di tutti i poligoni in parallelo mentre tieni traccia dei confini esterni della tua unione fino ad ora. Eventuali bordi che si trovano completamente all'interno dei limiti attuali dell'unione potrebbero essere omessi abbastanza rapidamente. Ma rendere l'implementazione solida di fronte alla inesattezza numerica è probabilmente un grosso problema se si affronta questo problema. Potresti voler dare un'occhiata a robust predicates per questo.

Answer 2

È difficile dare consigli a terra senza vedere come appaiono i poligoni.

L'intuizione mi dice che dovresti migliorare la località e unire poligoni che potrebbero interferire, in modo bottom-up.

Per questo, trovare l'ascissa mediana dei centri dei poligoni e dividerli in entrambi i lati della mediana; per ogni metà, ripetere con l'ordinata; e così via ricorsivamente. Questo è come costruire l'albero dei centri kD (http://en.wikipedia.org/wiki/Kd_tree).

Quando si finisce con due poligoni, unirli. Quindi, sulla struttura ricorsiva, unisci i poligoni a coppie.

Answer 3

Si può anche provare l'implementazione di unione Boost.Polygon dalla classe property_merge http://www.boost.org/doc/libs/1_55_0/libs/polygon/doc/gtl_property_merge.htm.

In sostanza, si crea un oggetto con una proprietà property_merge intero banale:

namespace bgp = boost::polygon; 
typedef int property_type; 
typedef int coordinate_type; 
const property_type FAKE_PROPERTY = 99; 

typedef std::map<std::vector<property_type>, bpg::polygon_set_data<coordinate_type> > merge_result; 
//in fact, merge_map will have 1 element only 

merge_map merger; 
for (polygon: my_polygons) 
    merger.insert(polygon, FAKE_PROPERTY); 

merge_result mresult; 
merger.merge(mresult); 

//now use the only element result should have 
assert(mresult.size()<=1); 
if (mresult.empty()) 
{ 
    //use empty bpg::polygon_set_data() 
} 
else 
{ 
    //use 
    const bpg::polygon_set_data & result = mresult.begin()->second; 
    ... 
}