2d триангуляция с учетом множества граничных точек

Question

Предположим, у меня есть двоичное изображение, и я обнаруживаю границу пикселей. Основываясь на граничных пикселях, я хочу провести триангуляцию, как показано ниже.

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

Эта цифра взята из этой статьи . Они назвали этот «адаптивный три angular me sh» и заявили, что используют CGAL для его генерации, но я погуглил «адаптивный три angular me sh» и просмотрел всю документацию CGAL, но не смог найти ничего подходящего , Может кто-нибудь, пожалуйста, укажите мне правильное направление?

Answer 1

Ну, я начну с того, что указал, что соответствующий CDT - это уже Делоне. Алгоритм уточнения просто улучшает общую форму треугольников. Уточнение имеет преимущества, когда me sh должен использоваться для определенных численных расчетов. Но это не обязательно для каждого приложения. Например, я использую нерафинированное me sh для вычисления объема и площади поверхности озер и водохранилищ, и оно прекрасно работает (см. https://github.com/gwlucastrig/Tinfour/wiki/Using-the-Delaunay-to-Compute-Lake-Volume-Part-1).

Там два основных алгоритма уточнения Делоне: второй алгоритм Рупперта и Чу. Оба работают, вставляя искусственные точки в me sh в благоприятных местах. Рупперт - старший из двух и гарантирует, что критерию Делоне отвечают все треугольники. Chew's производит несколько лучшие треугольники, но, я думаю, не гарантирует Делоне.

Я нашел статью об алгоритме Чу на http://2011.cccg.ca/PDFschedule/papers/paper91.pdf Рисунок 6 дает хорошее визуальное представление о том, что делает уточнение.

У меня есть планы реализовать Delaunay Refinement в моей собственной программной библиотеке с использованием алгоритма Рупперта. Есть некоторые технические проблемы, которые меня тормозят. Я считаю, что если вы ищете действительно превосходный пакет Triangle Джонатана Шевчука, или, возможно, библиотеку CGAL, или Java Topology Suite (https://locationtech.github.io/jts/), вы найдете несколько реализаций.

Answer 2

Я думаю, что вы ищете, это ограниченная триангуляция Делоне (CDT), но вы также можете увидеть ее как соответствующую триангуляцию Делоне (что означает сокращение «согласованное ограничение ...»). Я разместил страницу с описанием CDT на https://github.com/gwlucastrig/Tinfour/wiki/About-the-Constrained-Delaunay-Triangulation. Указанный полигон будет служить ограничением для общего размещения ребер в Делоне. Есть также еще немного информации о том, что вы пытаетесь сделать на https://github.com/gwlucastrig/Tinfour/wiki/Tutorial-Using-Polygon-Based-Constraints. Вторая статья может быть полезна в качестве источника идей, но некоторые ее обсуждения связаны с конкретным c API.

Многоугольник на размещенном вами изображении выглядит выпуклым. Границы Делоне будут выпуклыми. Таким образом, если ваш многоугольник выпуклый, ребра не будут размещены вне вашего многоугольника. Однако, если ваш многоугольник содержит вогнутости, то за пределами многоугольника будут ребра. Любая достойная реализация API Делоне позволит вашему коду различать guish вне зависимости от того, находится ли граница внутри ограничений или нет.

Похоже, что опубликованная вами картинка претерпела какое-то уточнение Делоне, процесс, в котором вершины вставляются в me sh, чтобы создать более устойчивые треугольники. Вы заметите, что на вашей картинке нет "тощих" треугольников и что у границы есть много маленьких треугольников. Эти особенности являются типичными для техники уточнения. Если вы используете API, который не включает метод уточнения, вы все равно получите действительный Делоне, но он может быть не таким приятным в эстетическом смысле. Вместо реализации уточнения вы можете просто заставить свой код искать узкие треугольники и вставлять их центры окружностей в me sh.