Тема: Сортировка по углам
кто знает как сделать сортировку по углам
если дано N точек (x1,y1; x2,y2; ... ; xn,yn) или вообще зачем нужна сортировка по углам
Re: Сортировка по углам
Сортировка по углам нужна,и нужна довольно часто,например задача о "построении выпуклой оболочки",задача о "поиске всех прямоугольников на наборе точек",их можно решать и по другому но очень удобно сортировать данные по углу.
Как написать сортировку по углу:
# Найдём самую левую-нижнюю точку,и сместим её в (0,0) и остальные координаты (на нужную величину). (Не обязательно делать).
# Теперь допустим есть точка (x,y) тогда угол для неё будет ArcTanges(Y / X).
Re: Сортировка по углам
Если сортировать по arctan(x/y), легко получить проблемы с точностью, т.к. arctan - очень неточная штука, особенно при y->0. acrtan2(y, x) чуть лучше, но на многих задачах все равно не поможет. Гораздо лучше сортировать компаратором на основе векторного произведения. Для начала надо проверить, что вектора a и b находятся в одной полуплоскости. Если это не так, то их легко между собой сравнить. Иначе же считают что a < b если [a x b] > 0. Такой компаратор сравнивает вектора в целых числах и принципиально не может иметь проблем с точностью
Re: Сортировка по углам
Ну ArcTan функция возрастающая,поэтому если сместить точки в плоскости (1,4) - что легко делается,то можно сортировать по x/y,а соотвественно при сравнении углов,можно избавиться от деления,так что тоже получит всё в целых числах.
Re: Сортировка по углам
Это как раз и получится векторное произведение)
Re: Сортировка по углам
:):) Эх Годы )