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

Question

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

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

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

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

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

Answer 1

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

Эта статья кажется лучшей. Duckham, M., Kulik, L., Worboys, M.F., Galton, A. (2008) Эффективная генерация простых полигонов для характеристики формы набора точек на плоскости Распознавание образов v41, 3224-3236

Answer 2

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

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

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

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

---

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

• https://github.com/mapbox/concaveman
• https://gis.stackexchange.com/questions/1200/what-are-definition-algorithms-and-practical-solutions-for-concave-hull
• Вогнутая оболочка: подход к k-ближайшим соседям для вычисления области, занятой набором точек ( ссылка )

Answer 3

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

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

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

Answer 4

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

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