упорядочить список вершин
Дан выпуклый n-угольник. Для каждой вершины заданы координаты, которые храняться в массиве.
Также имеется список(произвольный) индексов вершин из этого массива. Как можно упорядочить их так, чтобы
получить список в котором те же самые индексы будут располагаться по часовой(или против)
стрелке?
Помогите пожалуйста. Заранее благодарен. Дмитрий.
Также имеется список(произвольный) индексов вершин из этого массива. Как можно упорядочить их так, чтобы
получить список в котором те же самые индексы будут располагаться по часовой(или против)
стрелке?
Помогите пожалуйста. Заранее благодарен. Дмитрий.
Цитата:
Originally posted by dima85
Как можно упорядочить их так, чтобы
получить список в котором те же самые индексы будут располагаться по часовой(или против)
стрелке?
Как можно упорядочить их так, чтобы
получить список в котором те же самые индексы будут располагаться по часовой(или против)
стрелке?
Тебе нужен рабочий алгоритм, или просто идеи? :)
Цитата:
Originally posted by kelz
Тебе нужен рабочий алгоритм, или просто идеи? :)
Тебе нужен рабочий алгоритм, или просто идеи? :)
Мне нужны просто идеи, а алгоритм сам разработаю.
Ну, можно использовать произведение векторов по распространенной формуле:
x1*y2 - x2*y1,
что даст отрицательный результат, если два вектора расположены по ЧС; положительный, если против; и ноль, если образуют прямую. К примеру - на рисунке вектор AB(-3,2) и соседний с ним вектор BC(1,3):
-3*3 - 1*2 = -9 - 3 = -12 => вектора обходятся по ЧС. Или тот же вектор AB и вектор BO(-1,0):
-3*0 - -1*2 = 0 + 2 = 2 => против ЧС. Теперь нам необходимо их отсортировать. Для этого сначала предпочтительно выбрать самую нижнюю точку или самую верхнюю точку, т.к. одна из них точно является выпуклой вершиной. Теперь начнем двигаться по ЧС или против. Ясно, что чем больше угол между текущим вектором и следующим за ним, тем лучше. В идеале этот угол доходит до 180 и вектора образуют линию. К примеру, вектор FA и возможные варианты - вектора AB и AC (пока рассмотрим только их). Эти вектора по отношению к вектору FA являются правильнонаправленными, т.е. попадают в обход по ЧС. Теперь необходимо снова рассмотреть векторное отношение. На этот раз образуем какой-либо соседний с вектором FA вектор и обходим все остальные, следя за тем, чтобы направление обхода оставалось прежним относительно взятого вектора. Если условие выполнилось, то взятый вектор образует с вектором FA найбольший угол. Относительно того же АВ все остальные вектора обходятся по ЧС. Вообще-то говоря, алгоретмически может получиться много умножений для каждой из проверок. В принципе, можно реализовать делением на полуплоскости - там теоретически их должно быть меньше, но лучше, как мне кажется, не пытаться - хрен знает какие там подводные камни...
x1*y2 - x2*y1,
что даст отрицательный результат, если два вектора расположены по ЧС; положительный, если против; и ноль, если образуют прямую. К примеру - на рисунке вектор AB(-3,2) и соседний с ним вектор BC(1,3):
-3*3 - 1*2 = -9 - 3 = -12 => вектора обходятся по ЧС. Или тот же вектор AB и вектор BO(-1,0):
-3*0 - -1*2 = 0 + 2 = 2 => против ЧС. Теперь нам необходимо их отсортировать. Для этого сначала предпочтительно выбрать самую нижнюю точку или самую верхнюю точку, т.к. одна из них точно является выпуклой вершиной. Теперь начнем двигаться по ЧС или против. Ясно, что чем больше угол между текущим вектором и следующим за ним, тем лучше. В идеале этот угол доходит до 180 и вектора образуют линию. К примеру, вектор FA и возможные варианты - вектора AB и AC (пока рассмотрим только их). Эти вектора по отношению к вектору FA являются правильнонаправленными, т.е. попадают в обход по ЧС. Теперь необходимо снова рассмотреть векторное отношение. На этот раз образуем какой-либо соседний с вектором FA вектор и обходим все остальные, следя за тем, чтобы направление обхода оставалось прежним относительно взятого вектора. Если условие выполнилось, то взятый вектор образует с вектором FA найбольший угол. Относительно того же АВ все остальные вектора обходятся по ЧС. Вообще-то говоря, алгоретмически может получиться много умножений для каждой из проверок. В принципе, можно реализовать делением на полуплоскости - там теоретически их должно быть меньше, но лучше, как мне кажется, не пытаться - хрен знает какие там подводные камни...