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 ...)

— 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

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