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

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

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

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

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

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

Ответ 1

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

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

Ответ 2

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

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

Ответ 3

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

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

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