Создать непересекающийся многоугольник, проходящий через все заданные точки
Предположим, у меня есть массив точек в случайном порядке, и мне нужно найти многоугольник (сортируя их так, чтобы каждая соседняя пара представляла сторону), который проходит черезвсе из точек, и его стороны, конечно, не пересекаются.
Я попытался сделать это, выбрав точку и добавив все точки к окончательному массиву, который находится под ним, отсортированный слева направо. Затем, добавляя все точки над ним, сортируем справа налево.
Мне сказали, что я могу добавить дополнительную точку и сортировать естественным образом, чтобы избежать самопересечения. Хотя я не могу понять это. Какие'простой способ сделать это?