Сортировка точек

← →
alsov © (2008-02-04 17:29) [0]

Приветствую, Мастера

Помогите пожалуйста в решении задачки.

Есть массив точек, лежащих на окружности.
Как отсортировать их по часовой стрелке?

Точки окружности нахожу по алгоритму Мичнера.
Вот тут описано http://algolist.manual.ru/graphics/painting/circle.php

Заранее спасибо.

← →
хам (2008-02-04 17:30) [1]

Найти центр окружности, дпльшн сортровать по результату функции arctan2

← →
oldman © (2008-02-04 17:33) [2]

Собственно по координатам.
Если принять центр за 0, то х и у становятся очень понятными.
И без всякого arctan2.

← →
TUser © (2008-02-04 17:45) [3]

Переводи в полярные координаты.

← →
ketmar © (2008-02-04 17:49) [4]

>[1] хам (04.02.08 17:30)
не усложняй. сказали же: «на окружности». потому квадрант можно определить и без тригонометрии.

← →
oldman © (2008-02-04 17:57) [5]

> потому квадрант можно определить и без тригонометрии.

+1
что я и сказал в [2]

← →
alsov © (2008-02-04 18:16) [6]

> oldman © (04.02.08 17:33) [2]
>
> Собственно по координатам.
> Если принять центр за 0, то х и у становятся очень понятными.
>

Если я правильно понял то после приведения координат для точек, принадлежащих каждой четверти квадранта нужно отдельную сортировку делать?

← →
oldman © (2008-02-04 18:27) [7]

> alsov © (04.02.08 18:16) [6]

У тебя с математикой ваще хреново?
1 квадрант - x>0, y>0
2 квадрант - x>0, y<0
3 квадрант - x<0, y<0
4 квадрант - x<0, y>0

в чем проблема?
у тебя там что, точек несколько миллионов?
для несколькоих тысяч сортировка занимает несколько секунд.

← →
alsov © (2008-02-04 18:33) [8]

> 1 квадрант - x>0, y>0
> 2 квадрант - x>0, y<0
> 3 квадрант - x<0, y<0
> 4 квадрант - x<0, y>0

Это понятно

> в чем проблема?

набор точек - результат sql запроса
вот и думаю как лучше сделать

>[5] oldman ©(04.02.08 17:57)
ну да, я на твой ответ и намекал.

>[6] alsov ©(04.02.08 18:16)
зачем отдельно? одной функцией и проверяй. «многоуровневая» сортировка: сначала проверяешь квадранты, потом в зависимости от квадранта координаты. несколько простых условий.

>[7] oldman ©(04.02.08 18:27)
>для несколькоих тысяч сортировка занимает несколько секунд.
ты забыл приставку «милли» или «микро»? %-)

Сортировка точек Найти похожие ветки