Реализация алгоритма триангуляции Шазеля - PullRequest
12 голосов
/ 20 октября 2011

Существует алгоритм для триангуляции многоугольника за линейное время из-за Chazelle (1991), но, AFAIK, нет никаких стандартных реализаций его алгоритма в общих математических библиотеках программного обеспечения.

Кто-нибудь знает о такой реализации?

Ответы [ 2 ]

18 голосов
/ 20 октября 2011

См. ответ на вопрос Мощные алгоритмы, слишком сложные для реализации :

Согласно Скиене (автору Руководства по разработке алгоритмов), «алгоритм совершенно безнадежен».

Я уже искал реализацию, но не смог ее найти. Я думаю, можно с уверенностью предположить, что никто не реализовал его из-за его сложности, и я думаю, что он также имеет довольно большой постоянный коэффициент, поэтому он не преуспел бы против O(n lg n) алгоритмов, которые имеют меньшие постоянные факторы.

1 голос
/ 31 декабря 2018
...