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

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

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

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

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

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

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

Источник

4 ответа

Решение

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

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

Источник

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

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

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

Источник

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

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

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

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

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

Источник
Другие вопросы по тегам