Как отсортировать произвольные точки так, чтобы при проведении линии через них последовательно получился многоугольник? Есть несколько точек в двухмерном пространстве, совершенно произвольные могут быть (но не могут совпадать). Нужно отсортировать их так, чтобы при последовательном проведении линии через все эти точки получился - не самопересекающийся многоугольник. Как это сделать? Существует ли вообще алгоритм, который способен на подобное? Ну или подойдёт какая-нибудь библиотека на C# или C++, которая просто возьмёт и сделает это.

Предыдущий
вопрос Следующий
вопрос

Для того чтобы отсортировать произвольные точки так, чтобы при проведении линии через них получился многоугольник, можно воспользоваться алгоритмом Graham scan или алгоритмом Jarvis march (также известным как алгоритм оболочки).

Алгоритм Graham scan:

Найдите точку с самой низкой координатой y (и самой левой, если таких несколько), установите ее как начальную точку.Отсортируйте все остальные точки относительно начальной точки по углу, который они образуют с горизонтальной осью (по направлению против часовой стрелки).Пройдите по отсортированному списку точек, добавляя их в многоугольник, если они образуют поворот влево с предыдущими двумя точками, и удаляя предыдущие точки и добавляемый поворот вправо.Повторяйте шаг 3, пока не вернетесь в начальную точку.

Алгоритм Jarvis march:

Найдите самую левую нижнюю точку и добавьте ее в многоугольник.Найдите следующую точку, образующую самый большой угол с предыдущей точкой и добавьте ее в многоугольник.Повторяйте шаг 2, пока не вернетесь в начальную точку.

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

Также можно воспользоваться библиотеками, например, библиотекой CGAL для C++ или библиотекой Clipper для C#, которые предоставляют инструменты для работы с геометрическими объектами, включая построение многоугольников по точкам.