Алгоритмы, методы, исходники / Форум

Алгоритмы, методы, исходники / Форум (http://forum.algolist.ru/)
-   Вычислительная геометрия (http://forum.algolist.ru/algorithm-geometry/)
-   -   Построение выпуклой оболочки (модификация Quickhull) (http://forum.algolist.ru/algorithm-geometry/4534-postroenie-vypukloi-obolochki-modifikatsiia-quickhull.html)

kon 09.01.2011 23:59

Построение выпуклой оболочки (модификация Quickhull)
 
Есть несколько замечаний по алгоритму Quickhull.

1. Что будет если левая и нижняя точки совпадают? (Так же как и правая верхняя)
Можно упростить алгоритм найдя эти две точки, соединив их, затем поделить оставшиеся точки на 2 подмножества из разных полуплоскостей и для каждой из них решить рекурсивно.

2. При определении расстояния до самой удалённой точки от линии нет смысла делить на sqr(a^2+b^2), можно просто отнормировать вектор нормали (a,b). На самом деле можно обойтись и без этого, ведь в сравнении будут участвовать все точки с одним и тем же коэффициентом. (Единственная проблема может быть в разрядной сетке при представлении чисел).

3. Есть программа (по п.1), но она работает не на всех тестах из acmp.ru (задача 117, только она с дополнением, хотя дополнение прошло проверку на том же сайте - задача 370) :( . На 4 тесте выдаёт неверный ответ. Соответственно, вопрос
Где можно найти набор тестов для проверки решения?
Стандартные варианты с расположением на одной линии, по периметру выпуклого многоугольника и немного произвольных отрабатываются нормально.

Если необходимо код могу выложить здесь же. (Хотя лучше сначала поправить ошибки :) )

lordKelvin 13.01.2011 04:46

1) Тогда теряется сок как раз от того, что мы изначально отбрасываем ту часть точек, которая внутри четырехугольника.
2) Если ты точно уверен, что это константа, то делить на нее перед сравнением действительно не нужно.
3) Если есть вопросы по коду, то его разумно выложить. Тесты - рандом на больших количествах, плюс учет целочисленного переполения.


Часовой пояс GMT +4, время: 07:27.