Сортировка списка координат

-1

У меня проблема: У меня есть список всех x, y координат точек многоугольника. Теперь мне нужно отсортировать их таким образом, чтобы получить очки в по часовой стрелке.Сортировка списка координат

В настоящее время у меня есть 6 координат, чтобы нарисовать многоугольник, но не в порядке.

Кто-нибудь знает, как это осуществить?

Входные координаты:

координаты: 506.6609866568262, 673.970398950142

координаты: 505.34898334317376, +682,8179210498581

координаты: 502.0723751660178, 680,523615304454

координаты: 534.3026433431738, +682,736131049858

координаты: 535,6146466568263 , 673,8886089501419

координат: 538,8912548339822, +676,1829146955461

Выходных координаты:

координаты: 506.6609866568262, 673.970398950142

координаты: 502.0723751660178, 680,523615304454

координаты: 505.34898334317376, +682,8179210498581

координаты: 534.3026433431738 , 682,736131049858

координаты: +538,8912548339822, +676,1829146955461

координаты: 535.6146466568263, 673.8886089501419

Спасибо заранее,

источник

2015-06-20 Shiladittya Chakraborty

Какой язык? что ты уже испробовал? Можете ли вы привести пример формата ввода/вывода? – depperm

Thanx для быстрого ответа. Я делаю эту программу на Java. Я попытался проверить каждую координату по сравнению x, а также y. Но я не смог вычислить правильный порядок. –

Что вы знаете о выходном полигоне? У вас есть набор ребер? Или вам нужно создать простой полигон из этих точек? Если он второй, то возьмите экстремальную точку, возможно, одну из них больше всего, т. Е.ваша первая точка, затем отсортируйте точки радиально вокруг нее, и это даст вам точки простого полигона по часовой стрелке или против часовой стрелки в зависимости от того, как вы определяете больше. Взгляните на [Graham's scan] (https://en.wikipedia.org/wiki/Graham_scan), он сортирует точки по часовой стрелке вокруг самой низкой точки на своем первом шаге. –

Используйте полярные координаты:

найти внутреннюю точку на полигон в качестве ссылки , скажем (c, d);
atan2(x-c, y-d) для каждой вершины (x, y) многоугольника, чтобы получить полярные углы от этой внутренней точки; затем
сортировать по углам, которые вы получаете.

Если многоугольник выпуклый, то усреднение значений max и min x, а также для y должно получить внутреннюю точку. В противном случае у вас будет больше работы.

источник

2015-06-20 03:56:49 Lawrence

Внутренняя точка полигона означает центральную точку многоугольника? –

Не обязательно точная середина; любая точка, находящаяся внутри многоугольника. Подумайте о «часовой стрелке», проходящей от контрольной точки, - вы хотите, чтобы она касалась вершин в требуемом порядке, когда она размахивала вокруг. Если точка была вне полигона, она может ударять по вершинам в другом порядке. – Lawrence

Если два угла одинаковы, то как обрабатывать этот случай? –

ответ

Смежные вопросы