Как правильно построить многоугольник по точкам?

Question

[Марат Нагаев]

Пользователь щелчком мыши выбирает точки. Точки нужно соединить чтобы получилась фигура.

Как избежать такого?
Можно вывести ошибку, что фигура не может быть построена, только вот как это определить?
Использую Windows forms C++, метод drawPolygon.
UPD: выяснил, что drawPolygon соединяет точки по порядку, а не так, чтобы получалась корректная фигура.

Comments

[Евгений Шатунов]

Марат Нагаев , пока не очень понятно, что именно тебя не устраивает в этой фигуре.
С моей точки зрения с ней все нормально. Обычный невыпуклый многоугольник.
Опиши своими словами, почему таких результатов нужно избегать.

[Марат Нагаев]

Евгений Шатунов, drawPolygon соединяет точки по порядку. Если поставить 4 точки прямоугольника: левую верхнюю, правую верхнюю, потом нижнюю левую и нижнюю правую, то прямоугольник не получится: правая верхняя точка соединится с нижней левой, а не с нижней правой.
Пока что мне кажется, что нужно смотреть на разницу координат.

[Евгений Шатунов]

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

Я пока все еще не понимаю что тебе не нравится в том многоугольнике с изображения. Тебе нужно описать проблему, но пока ты рассказываешь мне свои попытки решения этой проблемы. Я хочу понять проблему.
В частности, я хочу понять, почему ты опираешься на механику работы drawPolygon вместо того чтобы самостоятельно определить порядок следования точек при отрисовке многоугольника.
Ты ведь можешь определить для себя таблицу инцидентности вершин и от этой таблицы линиями рисовать многоугольник.

[Марат Нагаев]

Евгений Шатунов,

Тебе нужно описать проблему, но пока ты рассказываешь мне свои попытки решения этой проблемы. Я хочу понять проблему.

Описываю: лабораторная работа заключается в том, чтобы построить многоугольник по точкам. Точки пользователь вводит кликом. Я использую drawPolygon потому, что прочитал в доках, что он строит многоугольник. Вроде как подходит для решения задачи. В действительности он строит не так, как ожидалось (просто проходит по массиву точек и соединяет их, в результате порядок ввода играет роль). Про таблицу инцидентности вершин не слышал.
Получается, что в общем-то drawPolygon подходящий метод, просто в массиве точек нужно выполнить какие-то перестановки, чтобы линии нормально соединялись. А какие пока не понял.

[Евгений Шатунов]

Марат Нагаев, хорошо, теперь проблема становится понятна. Спасибо.
У многоугольников есть самые разные характеристики. Например - уже обозначенная выпуклость.
Среди свойств выпуклого многоугольника есть одно важное: каждый внутренний угол многоугольника не больше 180°. Руководствуясь уже одним этим свойством можно определить, подходит ли многоугольник тебе или нет. Если хоть один внутренний угол будет больше 180°, многоугольник можно забраковывать.

Wataru дал очень хороший ответ. Мне и добавить нечего.

[Марат Нагаев]

Я посмотрел его ответ. Он подходит, но лишь отчасти.
Мой вопрос можно переформулировать: как можно отсортировать массив вершин так, чтобы если соединить эти вершины получился выпуклый многоугольник.

Answer 1

[Wataru]

Картинка не видна, но по коментариям понятно, что вам хочется получать только выпуклые многоугольники?

Проверить, что что-то не так можно через векторное произведение последовательных сторон.

Для всех 3 подряд идущих вершин a, b и c, то надо проверить, что (b-a)*(c-b) всегда дает одинаковый знак (или всегда <=0 или всегда >=0). Это векторное произведение.
Формула в вашем случае будет (xb-xa)*(yc-yb)-(xc-xb)*(yb-ya).

Еще можно построить выпуклую оболочку (convex hull).
Вот расписан алгоритм, как ее построить по заданным точкам: https://e-maxx.ru/algo/convex_hull_graham

Edit: Еще можно, вместо сортировки точек в выпуклую оболочку, игнорировать клики от пользователя, которые делают текущий многоугольник невыпуклым. Опять же, проверку невыпуколсти можно делать только для новых сторон: В последней, новой и первой точках.

Comments

[Марат Нагаев]

Спасибо. Но еще нужно точки соединять чтобы был выпуклый многоугольник, а не только проверять на выпуклость. Т.е если есть 4 точки, то соединить их можно так, чтобы получился невыпуклый многоугольник. Вопрос только как это сделать. Методу drawPolygon из Windows Forms абсолютно все равно какой многоугольник рисовать, он рисует невыпуклый по 4 точкам.
Т.е вопрос можно переформулировать: как можно отсортировать массив вершин так, чтобы если соединить эти вершины получился выпуклый многоугольник.

[Wataru]

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