Запнулся на такой штуке.
В сканирование по Грехому. Нужно упорядочить точки
по возрастанию полярного угла относительно точки
.
Как найти полярный угол точки
относительно
?
Если
заданы как комплексные переменные, то:
- double angle = arg(p[i]-p[0]);
Если как координаты, то:
- double angle = atan2(y[i]-y[0], x[i]-x[0]);
Его искать из формулы скалярного произведения вектора
и вектора {1,0} ?
Можно это сделать как-нибудь хитрее?
Можно и похитрее, избежав медленных операций типа арктангенса. Только произведение нужно векторное, и код будет сложнее.
Знак векторного произведения показывает, справа или слева находится другой вектор. К сожалению, круг у нас замкнут, поэтому надо сначала разбить все точки на две половины относительно, например, оси X, а потом каждую половину отсортировать используя знак векторного произведения как оператор сравнения.
Ещё надо будет учесть возможность совпадения углов. Полностью сейчас писать лень.