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