Алгоритм границы полигона?

Question

У меня есть массив значений (x, y), которые определяют многоугольник.Многоугольник рисуется исходя из положения точки * размера карандаша.Дело в том, что я хочу нарисовать границу такой формы, игнорируя внутренние вершины.Посмотрите на этот пример, ЧЕРНЫЕ вершины - это те, которые мне интересны, я хочу избавиться от ЖЕЛТЫХ.

Я хотел бы получить X вдругой массив, упорядоченный по часовой стрелке.Мы думали об оценке каждой точки, чтобы увидеть, есть ли у нее сосед и где (север, юг, восток, запад), но, похоже, слишком много усилий, чтобы проверить каждую вершину, и я считаю, что это должен быть еще один проверенный и более элегантный алгоритм.1007 * Любой совет?

Answer 1

Поскольку ваши "точки" - это просто маленькие квадраты, звучит так, будто ваши внутренние точки (те, которые не влияют на границу фигуры) - это те, где (x-1,y), (x+1,y), (x,y-1) и (x,y+1) также все точки.

Вы можете быстро выполнить этот тест, поместив все свои точки в хеш-таблицу (или одну из многих других проиндексированных структур).

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

Answer 2

Обычно многоугольник определяется контуром. Это неудачный формат, с которым вам приходится иметь дело.

Если они расположены таким образом (в строках с одинаковыми координатами y), вы можете просто отсортировать массив сначала по x, а затем по y, а затем взять первую точку, две точки вокруг любого изменения y и последний пункт, чтобы сформировать ваш контур.

Если реальное положение вещей немного запутано, то вы, возможно, захотите взглянуть на «альфа-фигуры». Некоторые ссылки: http://biogeometry.duke.edu/software/alphashapes/, http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html

Answer 3

Создайте границы спрайтов, разместите их одинаково в каждом квадрате и разместите сортировку за