N-wymiarowe biblioteki oprogramowania Delaunay Tesselation

10

Mam zestaw znanych punktów / węzłów rozmieszczonych nieregularnie w przestrzeni N-wymiarowej (N> = 2) i chciałbym sposobu na wygenerowanie triangulacji Delaunaya tych punktów i zwrócenie odpowiednich elementów.

Czy istnieją jakieś biblioteki siatki, które wykonają triangulację ND Delaunay?

(Robię to, ponieważ chcę użyć elementów siatki jako podstawy interpolacji liniowej w dowolnym punkcie przestrzeni. Mój wymiar jest obecnie obsługiwany przez klasę C ++ wzorowaną na wymiarze, jeśli ma to znaczenie dla sugestii ...)

computational-geometry high-dimensional mesh-generation delaunay-triangulation unstructured-mesh miramy
źródło
Cześć mirams i witamy w Scicomp! Możesz być zainteresowany tym pytaniem: scicomp.stackexchange.com/questions/770/…
Paul
Dzięki za link, miałem nadzieję uniknąć pisania własnego meshera. Tetgen (dla 3D) działa na wiele linii kodu. Wygląda na to, że problem musiał zostać rozwiązany wiele razy.
mirams
popularne pytanie ... także scicomp.stackexchange.com/questions/7664/…
clipper
Triangulacja Delaunaya zazwyczaj pochodzi z wypukłego kadłuba w przestrzeni o większych wymiarach. Zobacz uwagę qhull poniżej.
meawoppl,
3D nie jest takie trudne, ale dla 4D jest bardzo trudne podczas rafinacji, zadałem pytanie na MathOverflow, ale jeszcze nie ma odpowiedzi: mathoverflow.net/questions/130878/…
Shuhao Cao

Odpowiedzi:

4

Myślę, że możesz to zrobić za pomocą oprogramowania wypukłego kadłuba (np. QHull) za pomocą algorytmu podnoszenia. Przynajmniej dokumentacja polecenia „delaunayn” Matlaba wydaje się wskazywać tyle samo.

rchilton1980
źródło
2
Przetestowano 4D i wydaje się, że działa poprawnie w QHull (używam go przez scipy.spatial w python).
Ethan Coon,
1
Nie pokonasz kadłuba. Użyłem również przez Scipy w maksymalnie 6 wymiarach.
meawoppl,
Hmmm - to z qhull.org/news/qhull-news.html nie jest idealne: „Wszyscy użytkownicy w wersji 3-d i wyższej opcja„ Qt ”nie wytwarza zgodnych triangulacji dla sąsiednich, niełatwych aspektów. Na przykład jeśli masz regularny, trójwymiarowy układ miejsc wejściowych, ich triangulacja Delaunaya składa się z kostek. Opcja „Qt” spowoduje triangulację każdej kostki w czworościany. W obrębie każdej kostki triangulacja jest spójna, ale niekoniecznie jest spójna między sąsiednimi kostkami [C. Bertoglio; C. de Visser]. Sposób rozwiązania tego problemu jest nieznany. ” Warto jednak spróbować, zobaczę, jak sobie radzę.
mirams
5

Ta funkcja wydaje się być dostępna w CGAL

Juan M. Bello-Rivas
źródło
To też wygląda dobrze. Spróbuję zarówno Qhull, jak i tego. Dziękuję za sugestie.
mirams
0

Znalazłem także distmesh w Matlabie, który wydaje się być w stanie to zrobić:

Strona internetowa Distmesh

Robi teselacje dla siatek elementów skończonych (poprzez QHull), ale z ładnym interfejsem do definiowania obszarów / powierzchni na podstawie funkcji odległości. Lepiej w przypadkach, w których chcesz zdefiniować powierzchnię matematycznie i nie przejmuj się, gdzie są wewnętrzne węzły.

miramy
źródło