Учитывая большой набор вершин в невыпуклом многоугольнике, как мне найти ребра?

У меня есть набор вершин (называемый A), и я хочу найти все граничные вершины, чтобы этот набор граничных вершин был контуром формы.

Многие вершины в A избыточны, потому что они находятся внутри формы, я хочу избавиться от этих вершин.

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

РЕДАКТИРОВАТЬ: Уточнение: изображение ниже представляет собой вогнутый многоугольник. Это то, что я имел в виду под невыпуклостью. Если я запустил на нем алгоритм выпуклой оболочки, он не сохранил бы вогнутую часть многоугольника (если я не ошибаюсь).

вогнутый многоугольник

У меня есть набор вершин внутри и на границе многоугольника: [[x1, y1], [x2, y2] ...] Я хочу уменьшить набор так, чтобы вершины были просто контуром границы фигуры.


outline vertices polygons concave
person tommy chheng    schedule 30.04.2010    source источник
comment
Что вы подразумеваете под работой для случая невыпуклого многоугольника? Вопрос, на который вы ссылаетесь, включает случай, когда входные вершины образуют вогнутый многоугольник, поэтому я не понимаю, чем отличается ваш вопрос.   -  person outis    schedule 30.04.2010
comment
Как отличить вершины внутри многоугольника, а какие - на краю?   -  person Marius Gedminas    schedule 15.07.2010

Ответы (4)


arrow_upward
5
arrow_downward

Кажется, это горячая тема .. https://gis.stackexchange.com/questions/1200/concave-hull-definition-algorithms-and-practical-solutions

Эта статья кажется лучшей. Дакхэм, М., Кулик, Л., Уорбойз, М. Ф., Гальтон, А. (2008 г.) ) Эффективная генерация простых многоугольников для описания формы множества точек на плоскости. Распознавание образов v41, 3224-3236

person TelsaBoil    schedule 02.09.2010

arrow_upward
0
arrow_downward

Ваше описание несколько расплывчато, но возможно, вы ищете алгоритм для построения выпуклой оболочки набора точек. Проще говоря, выпуклая оболочка - это форма, которую вы получите, если обернете резинкой все вершины.
Написать алгоритм выпуклой оболочки в 2D не так уж сложно, и есть некоторые библиотеки, которые делают это как qhull

(Этот ответ также дается в вопросе, на который вы ссылаетесь, который, по-видимому, является частным случаем вашего вопроса)

person shoosh    schedule 30.04.2010
comment
Разве выпуклая оболочка не исключила бы некоторые точки, потому что она будет отслеживать только выпуклый многоугольник? Я добавил изображение к ответу, чтобы уточнить форму. - person tommy chheng; 30.04.2010
comment
Это будет, но как вы могли определить, какое ребро разделить, чтобы добавить эти два дополнительных ребра? - person shoosh; 30.04.2010

arrow_upward
0
arrow_downward

Это старый, возможно, забытый вопрос, но он заставил меня задуматься над ним. Вам не нужна выпуклая оболочка, вам нужно сохранить форму многоугольников, а просто избавиться от точек, лежащих между «краями» на линии.

Решением может быть переход через соседние точки и вычисление линейного наклона первой и второй, затем сохранение этого значения наклона, вычисление наклона второй и третьей, если наклон точки pt1-pt2 равен наклону точки pt2-pt3. тогда точка pt2 является избыточной при формировании линии и, следовательно, может быть удалена. Продолжайте повторять, пока не вернетесь к точке 1.

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

person softwarequestioneer    schedule 10.07.2010

arrow_upward
0
arrow_downward

Вам нужен термин вогнутый корпус.

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

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

Здесь k - ваш гиперпараметр для настройки. Если k слишком велико, вы получите выпуклую оболочку. Если k слишком мало, то полученный многоугольник будет иметь много вогнутостей.

Вот несколько ссылок по теме:

person nimcap    schedule 26.06.2018