Объединить произвольное количество полигонов вместе

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

введите описание изображения здесь

Каждый гексагон имеет 6 вершин x, y. Вершины известны для всех гексов.

Может ли кто-нибудь указать мне на алгоритм, который объединит все гексы в один многоугольник? По сути, я просто ищу функцию, которая выделяет массив местоположений вершин, упорядоченных таким образом, что при рисовании линий от одной к другой она формирует многоугольник.

Это мой метод:

  1. Создайте массив всех вершин для всех гексов.
  2. Определите, сколько раз вершина встречается в массиве
  3. Если вершина находится в массиве 3+ раза, удалите вершины из массива.
  4. Если вершина находится в массиве 2 раза, удалите одну из них.

Однако следующий шаг непростой. Я использую холст для рисования этих многоугольников, что по сути включает рисование линии от одной вершины к другой. Поэтому порядок вершин в окончательном массиве важен. Его нельзя отсортировать произвольно.

Кроме того, я не ищу алгоритм «выпуклой оболочки», так как он не будет правильно рисовать многоугольник.

Есть ли какие-то функции, которые делают что-то подобное? На правильном ли я пути или есть более эффективный способ?


hex algorithm polygon hexagonal-tiles
person Jake Wilson    schedule 01.12.2012    source источник
comment
Что вы хотите сделать с большим многоугольником с дырой в нем? Подойдет ли два (или более) списка вершин?   -  person Beta    schedule 02.12.2012
comment
Предположим, что все гексы соприкасаются. Никаких дыр.   -  person Jake Wilson    schedule 02.12.2012

Ответы (3)


arrow_upward
5
arrow_downward

Я бы сделал что-то вроде этого:

  1. Перечислите все стороны. Сторона определяется двумя парами координат.
  2. Если какая-либо сторона появляется более одного раза, удалите все экземпляры этой стороны.
  3. Выберите произвольную сторону, а с этой стороны выберите одну из ее точек.
  4. Поместите эту точку в массив.
  5. Следуйте за текущей стороной и поместите другую точку в массив.
  6. Удалите сторону, на которую вы только что подписались.
  7. Затем найдите другую сторону с точкой, которая совпадает с последней точкой в ​​массиве. Такая сторона будет только одна. Если его нет, все готово.
  8. Вернитесь к шагу 5.

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

Просто имейте в виду, что это не справится с дырами. Форма должна определяться одним путем.

person Niet the Dark Absol    schedule 01.12.2012
comment
Как определить, не входит ли сторона в границу? - person Jake Wilson; 03.12.2012
comment
Моя первоначальная идея заключалась в том, чтобы использовать массив вершин и отсортировать их, выясняя, что есть что, и удалить дубликаты и т. Д. Однако использовать стороны вместо вершин намного проще. Спасибо! - person Jake Wilson; 03.12.2012

arrow_upward
0
arrow_downward

без отслеживания пар координат, составляющих линии, было бы невозможно определить внешнюю границу фигуры

если вы знаете пары координат, составляющие линии, ТО

  1. Создайте 2 списка, одну из вершин (список 1), одну из строк (список 2)
  2. Удалите все повторяющиеся вершины из списка вершин
  3. Составьте новый список (список 3) всех вершин, к которым прикреплены 3 линии.
  4. Используя список 3, удалите все строки, которые имеют 2 вершины из списка 3, как их две пары координат.
  5. Пришло время пройти по фигуре, список оставшихся линий должен сформировать форму, которую вы хотите, просто начните с произвольной координаты, а затем для каждой координаты для всех линий, если (x1, y1) = текущая координата, затем добавьте (x2, y2) в стек и удалите эту строку из разрыва списка elseif (x2, y2) = текущая координата, затем добавьте (x1, y1) в стек и удалите эту строку из разрыва списка
person Andy Strackbein    schedule 02.12.2012

arrow_upward
0
arrow_downward

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

Теперь у вас есть набор многоугольников (изначально шестиугольников). Идея состоит в том, чтобы объединить многоугольники до тех пор, пока не останется только один (или как можно меньше).

Выберите край многоугольника и найдите это же ребро (то есть ту же пару вершин) среди других многоугольников. Если есть два экземпляра, объедините два многоугольника на этом краю, например (a, b, c, d, e, f) + (g, h, d, c, i, j) => (a, b, c, i, j, g, h, d, e, f) . (Если две вершины находятся в одном и том же порядке в обоих многоугольниках, или если имеется три или более экземпляров ребра, сообщить об ошибке и прервать выполнение.) Итерировать по всем ребрам. Если гексы действительно образуют непрерывную группу, останется только один многоугольник.

У многоугольника могут быть дублированные края. Если ребро встречается более одного раза, устраните его, разделив список на два, например (a, b, c, d, b, a, e, f, g) => (b, c, d) + (a, e, f, g). Или, если края смежные, удалите их: (a, b, c, b, d, e) => (a, b, d, e). Или, если этот список имеет только этот край, удалите список: (a, b) => ничего.

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

person Beta    schedule 02.12.2012