Как упорядочить вершины в невыпуклом многоугольнике (как найти одно из многих решений)
У меня та же проблема, что и здесь: как упорядочить вершины в простом невыпуклом многоугольнике, но я не могу найти решения.
У меня есть координаты точек, и мне нужно найти многоугольник. Не имеет значения, что есть больше решений для одного списка точек. Мне нужен алгоритм, чтобы найти один из них. Неважно, какой. Я действительно не знаю, как решить это.
(Я сохранил координаты в массиве, и я хочу использовать некоторый алгоритм в Javascript)
Большое спасибо.
1 ответ
Сначала найдите центр ограничительной рамки, в которой находятся все ваши вершины. Мы назовем этот пункт C.
Сортируйте список вершин по углу каждой точки относительно C. Вы можете использовать atan2(point.y - C.y, point.x - C.x) найти угол. Если две или более вершин имеют один и тот же угол, на первом месте должна стоять та, что ближе к С.
Затем нарисуйте ваши точки в порядке их появления в списке. В итоге вы получите шаблон звездообразования, который не пересекается и, вероятно, не является выпуклым. Пример:
