Алгоритм полиномиальной дуги?

Question

В классе мы видели проблему followin, но я didnt undestand решение. Кто-нибудь может объяснить мне более подробно процедуру решения этой проблемы или дать мне лучшее решение ?:

Предположим, что указаны n точек в плоскости. Найдите многоугольную дугу с n-1 сторонами, вершины которых заданы точками и стороны которых не пересекаются. (Смежные стороны могут образовывать угол 180). Количество операций shold должно быть порядка n log n.

Решение учитель:

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

Answer 1

Решение вашего учителя (к счастью) хорошее. Я попытаюсь представить это для вас.

Просто нарисуйте точки на участке. Затем вы можете нарисовать линию от самой левой точки до следующей точки. Таким образом, соедините все точки, идущие вправо.

Если все точки имеют разные координаты х, что будет работать, и никакие линий не пересекутся:

Для точек с одинаковыми координатами х, мы сначала перейти к наименьшая (наименьшая y-координата), а затем вверх. Там тоже нет пересечения.