Powiedziałbym, że jesteś na dobrej drodze, ale wymyślenie optymalnego i / lub wydajnego algorytmu to inna sprawa: to trudny problem. Jednak, jeśli twoje zainteresowania nie są akademickie, wystarczające może być wystarczające rozwiązanie.
Po pierwsze, jeśli nie jesteś zainteresowany wymyśleniem własnego rozwiązania, CGAL zawiera już algorytm rozkładu wypukłych wielościanów: http://doc.cgal.org/latest/Convex_decomposition_3/index.html
Teraz metoda; podobnie jak wiele problemów w 3D, często pomocne jest rozważenie problemu 2D, który jest łatwiejszy do zrozumienia. W przypadku 2D zadaniem jest zidentyfikowanie wierzchołków odruchu i podzielenie wielokąta na dwa, tworząc nową krawędź (i ewentualnie nowe wierzchołki) z tego wierzchołka odruchu, i kontynuuj, dopóki nie pozostaniesz bez wierzchołków odruchu (a zatem wielokątów wypukłych) ).
Dekompozycja wielokąta J. Mark Keil zawiera następujący algorytm (w niezoptymalizowanej formie):
diags = decomp(poly)
min, tmp : EdgeList
ndiags : Integer
for each reflex vertex i
for every other vertex j
if i can see j
left = the polygon given by vertices i to j
right = the polygon given by vertices j to i
tmp = decomp(left) + decomp(right)
if(tmp.size < ndiags)
min = tmp
ndiags = tmp.size
min += the diagonal i to j
return min
Zasadniczo porównuje wyczerpująco wszystkie możliwe partycje i zwraca tę z najmniejszą liczbą przekątnych. W tym sensie jest też nieco brutalna i optymalna.
Jeśli chcesz „ładniej wyglądających” rozkładów, czyli takich, które wytwarzają bardziej zwarte kształty niż wydłużone, możesz również rozważyć ten wyprodukowany przez Marka Bayazita , który jest zachłanny (stąd znacznie szybszy) i wygląda ładniej, ale ma kilka wad. Zasadniczo działa, próbując połączyć wierzchołki odruchowe z najlepszym przeciwległym do niego, zwykle z innym wierzchołkiem odruchowym:
Jednym z niedociągnięć jest to, że ignoruje „lepszy” rozkład poprzez tworzenie punktów Steiner'a (punktów, które nie istnieją na istniejącej krawędzi):
Problem w 3D może być podobny; zamiast wierzchołków odruchowych identyfikujesz „krawędzie wycięcia”. Naiwnym wdrożeniem byłoby identyfikowanie krawędzi wycięcia i wielokrotne wykonywanie płaskich cięć na wielościanie, aż wszystkie wielościany będą wypukłe. Sprawdź „Wypukłe partycje wielościanów: algorytm optymalny dolnej granicy i najgorszego przypadku” Bernarda Chazelle, aby uzyskać więcej informacji.
Zauważ, że takie podejście może spowodować w najgorszym przypadku wykładniczą liczbę sub-wielościanów. Wynika to z możliwości zdegenerowania takich przypadków:
Ale jeśli masz nietrywialną siatkę (pomyśl nierówną powierzchnię), i tak otrzymasz słabe wyniki. Jest bardzo prawdopodobne, że zechcesz wcześniej uprościć wiele czynności, jeśli będziesz musiał użyć tego w przypadku skomplikowanych siatek.
