Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум на CrossPlatform.RU _ Алгоритмы, задачи по программированию, логические игры _ задачка

Автор: Алексей1153 6.3.2013, 9:57

на 2D :
требуется очертить произвольный набор точек выпуклым полигоном.



Решение в лобище - перебрать все сочетания из 3 точек, все эти треугольники объединить.

Придумайте более оптимальное решение

Автор: lanz 6.3.2013, 10:14

Эээ, спойлер

Раскрывающийся текст
http://en.wikipedia.org/wiki/Graham_scan

Раскрывающийся текст
http://en.wikipedia.org/wiki/Convex_hull_algorithms

:lol:

Автор: Алексей1153 6.3.2013, 10:25

lanz, с обжиманием "эластичной" лентой - это явно неоптимальный по скорости, а вот с правым/левым поворотом - вполне тема )

Форум Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)