Comments 17
Чуть больше бы картинок на шаге 4 и 5, а то не совсем понятно.
Спасибо, да вы правы сейчас попробую добавить
Очень жаль, что я не видел этот метод, когда помогал делать свою первую игру на Юнити... Там была как раз подобная ситуация -- надо было триангулировать и оптимизировать здоровенные контурные рисунки (4000х4000 пикселей), чтобы игрушка влазила по памяти в отведенные 50 мб. И при этом -- не нарушить уже существующую анимацию. В общем, выкрутился, но пришлось попотеть.
Есть такой алгоритм "триангуляция Делоне", на мой взгляд там проще (и да я ее реализовывал когда-то давно), кроме того нужно раскрыть момент большого количества точек (там затраты времени растут непропорционально), что-бы избежать этого есть разные стратегии, например "строй и перестраивай", "разделяй и властвуй" и тд
Комментарий ваш имеет несколько очень грубых ошибок и заблуждений. Как-будто вы погуглили ключевые слова и первое попашееся потащили в комментарий даже не вчитываясь.
Во-первых, та задача триангуляции в "триангуляции делоне" и задача из статьи - совсем разные. В первой надо выпуклую оболочку точек разбить на треугольники на заданных точках, чтобы треугольники были достаточно остроугольные. Во второй задаче надо разбить на треугольники заданную невыпуклю фигуру с дырками. При этом, теоретичесски, можно треугольники стороить на любых точках, а не только из заданных. Соотвественно, алгоритмы там весьма разные и притаскивать тот суда - весьма наивно.
Во-вторых, вы упомянули затраты времени, но даже не смогли назвать термин - "ассимтотическая сложность" или хотя бы О-большое. Более того, приведенный в статье алгоритм работает за O(n log n), что нисколько не уступает самым быстрым алгоримам по построению триангуляции Делоне.
В-третьих, триангуляция Делоне тоже может строиться алгоритмом заметающей прямой, как в статье, "разеляй и властвуй" не единственный возможный подход.
Почему ваш алгоритм работает за n log n? Когда вы проверяете треугольники на условие Делоне, ваш алгоритм может очень долго сходиться.
Оно сходится достаточно быстро. За 
, где 
- количество ребер в графе.
Во-первых, я - не автор. Я просто мимо проходил и заметл ваш комментарий.
Во-вторых, эта часть работает вообще за O(n). После каждой операции количество тупых углов уменьшается. Всего углов во всех треугольниках - O(n), а тупых из них и того меньше. Надо только аккуратно реализовывать и не проверять все ребра после каждой замены. Надо добавлять соседние ребра в очередь на проверку при изменении треугольников.
подозреваю что вдохновение частично отсюда?
https://www.angusj.com/clipper2/Docs/Overview.htm
Вы про iOverlay я полагаю. Clipper очень известная библиотека и для меня она больше как старший брат с которым ты себя сравниваешь и с которого берёшь пример. Но как она реализована я до конца так и не понял. Polybooljs вот кто открыл мне глаза. Если кто сможет объяснить принцип работы Clipper я с удовольствием послушаю.
когда то давно на шарпе заюзал клиппер в самодельном алгоритме разделения видимого/невидимого контура сцены(без триангуляции - т.е. потенциально можно будет графику на cpu, думал тогда я)
https://mysimpleengeneeringsolutions.blogspot.com/2013/10/msf-to-be-continue.html
https://mysimpleengeneeringsolutions.blogspot.com/search/label/MainProject
вот здесь ангус дает ссылку на статью ваати про то как это все работает
https://www.angusj.com/delphi/clipper/documentation/Docs/Overview/_Body.htm
ну и сама реализация емнип 2000 строк хорошо структурированного кода, правда я не вникал, заюзал как черный ящик.
Это у вас какая прикладная область была? 3D-принтер?
Я хорошо погружён во все эти алгоритмы — iOverlay — не первый мой заход на эту территорию. Были и другие: например, я очень долго пытался реализовать рабочее решение, используя алгоритм Greiner-Hormann.
Clipper, как он сам пишет, использует алгоритм Vatti Clipping.
Проблема всех этих алгоритмов в том, что они дают лишь общее направление — там очень много подводных камней, о которые и разбиваются все эти решения.
И на продвинутом уровне интересен не сам базовый алгоритм, а то, как были решены все эти трудности.
И да читать 2000 строк очень сложно, я сам честно пробовал несколько раз, как раз на C#
хотел вот такое сделать, чтобы потом автоматом чертежи генерить как в tekla
https://mysimpleengeneeringsolutions.blogspot.com/2013/11/blog-post_24.html
саму идею описывал здесь
https://forum.dwg.ru/showthread.php?t=95740
я кстати щас тоже в раст ударился(python | c# | some Nim )
Как грится сделать это ладно, а вот сделать на Rust )))
(с удовольствием попрепарирую Ваши репки.)
С трудом но нашел.
оказалось timo23414 впоследствии запилил полноценный проект от сlipper.
https://sourceforge.net/projects/jsclipper/
live:
https://jsclipper.sourceforge.net/6.4.2.2/main_demo.html
помню чтобы посмотреть на стабильность работы я брал этот js качал нужный clipper
вращал тестовые сцены и смотрел на корректность / наличие артефактов
плюс в самом релизе клиппера тоже есть gui демка на шарпе - которая всегда была ОК (в отличии от тестов timo23414),
Clipper прошел большой путь, ангус буквально в ручном режиме, оч. оперативно откликался на все баги(я вот даже один ему накинул https://sourceforge.net/p/polyclipping/discussion/1148419/thread/69c942c8/
)
...я правда давно уже не слежу, но думаю что "второй подход", к-й уже на гитхабе - лишен "детских болячек"(стабилен).
https://github.com/AngusJohnson/Clipper2
iOverlay тоже очень стабилен. Я бы не стал разгонять шум вокруг неё, если бы не был в ней так уверен.
Rust — как раз тот язык, который поощряет писать тесты на код, и мне это прям сильно зашло.
Попробуйте запустить cargo test — там уже, наверное, ближе к двумстам тестам.
И часть из них — рандомные. Если честно, я думаю, что она более стабильна, чем Clipper.
Полгода назад iOverlay вошёл в состав GeoRust. Первое время, да, мне насыпали ошибок, но все они были ошибками имплементации, а не подхода как такового.
Так что пробуйте смело, а если найдете баг, тоже хорошо.
)
у меня щас нет задач связанных с геометрией.
На раст пишу просто всякую дичь(пробую на вкус)
https://github.com/BakinSergey/quadric-equation
https://github.com/BakinSergey/unit-converter
так что буду препарировать с т.з. просто кода на rust
Триангуляция по косточкам