Учитывая большой набор вершин в невыпуклом полигоне, как я могу найти края?
У меня есть ряд вершин (названный A), и я хочу найти все вершины границы таким образом, что этот набор вершин границы является схемой формы.
Многие вершины в A избыточны, потому что они в форме, я хочу избавиться от этих вершин.
Мой вопрос подобен Лучшему Алгоритму для нахождения краев (полигон) вершин, но мне нужен он для работы на невыпуклый случай полигона.
Править: Разъяснение: ниже изображения вогнутый полигон. Это - то, под чем я подразумевал невыпуклый. Если бы я выполняю алгоритм выпуклой оболочки на нем, это не сохранило бы вогнутую часть полигона. (если я не ошибаюсь).
У меня есть ряд вершин внутри и на границе полигона: [[x1, y1], [x2, y2]...] я хочу уменьшить набор так, чтобы вершины были просто схемой границы формы.
2 ответа
Ваше описание несколько расплывчато, но возможно, что вы ищете алгоритм для построения Выпуклой оболочки набора точек. Проще говоря, выпуклая оболочка - это форма, которую вы получите, если обернуть резинкой все вершины.
Написать алгоритм выпуклой оболочки в 2D не так уж и сложно, и есть некоторые библиотеки, которые делают это, например qhull
(этот ответ также дается в вопросе, на который вы ссылаетесь, кажется, это частный случай вашего вопроса)
Это старый, возможно, заброшенный вопрос, но он заставил меня задуматься об этом. Вы не ищете выпуклый корпус, вы хотите сохранить форму многоугольника, но избавиться от точек, которые лежат между "краями" вдоль линии.
Решением может быть проход по соседним точкам и вычисление линейного наклона первой и второй, затем, сохраняя значение наклона, вычисление наклона второй и третьей, если наклон pt1-pt2 равен наклону pt2-pt3, то pt2 является лишней в формировании линии и поэтому может быть удалена. Продолжайте двигаться по кругу, пока не вернетесь к pt1.
Таким образом, вогнутая форма сохранится, но лишние точки будут удалены.