Триангуляция Делоне из выпуклой оболочки

Question

Мне нужно написать несколько кодов по вычислительной геометрии и распараллелить их, используя openMP. До сих пор я закончил выпуклую оболочку и ближайшую пару точек. Мне нужно написать код дележа триангуляции Делона и победить код. Но у меня не так много времениЯ где-то читал, что триангуляция Делоне может быть легко реализована, если можно вычислить выпуклую оболочку. Так что, если кто-нибудь может предоставить мне серийный код для DT или, по крайней мере, дайте мне знать, как я могу создать триангуляцию Делоне из выпуклой оболочки, я мог бы написатькод и распараллелить его как можно скорее.

Answer 1

Я где-то читал, что триангуляция Делоне может быть легко реализована, если вычислить выпуклую оболочку.

Это правда, но точное утверждение состоит в том, что 2D триангуляция Делоне может быть легко построена, если доступна реализация 3D выпуклой оболочки . Знание 2D корпуса не очень помогает в построении триангуляции Делоне (DT), кроме того, что дает вам несколько ребер DT (каждый ребро корпуса является ребром DT).

Если вы не реализовали 3D-корпус (что довольно сложно), то вам нужно атаковать триангуляция Делоне отдельно.

Answer 2

QHull - это стандартная библиотека, которую используют многие люди: http://www.qhull.org/html/qhull.htm Возможно, вы можете использовать его в качестве эталонной реализации, если вы действительно хотите переопределить это.