#computational-geometry #polyline #convex-hull
#вычислительная геометрия #полилиния #выпуклая оболочка
Вопрос:
Я пытаюсь найти способ создания четкого контура полилинии. Я уже реализовал алгоритм выпуклой оболочки, основанный на подходе сканирования Грэма, но, как вы можете видеть на диаграмме ниже, я хочу добиться более строгой версии этого результата.
Я не уверен, на какие алгоритмы мне следует обратить внимание и существует ли на самом деле обобщенный способ достижения желаемого результата. Любые предложения по конкретным алгоритмам будут высоко оценены.
Правка: здесь еще один набросок, показывающий больше дел, которые следует обработать.
Комментарии:
1. Является ли ваш пример представителем общего случая ?
2. Да, входные полилинии будут иметь либо один цикл (аналогичный желаемому выходу на диаграмме), либо несколько циклов (например. входная ломаная линия на приведенной выше диаграмме будет рассматриваться как 2 петли), соединенные между собой таким же образом, как и на приведенной выше диаграмме.
3. Я говорю, что это репрезентативно. Вам что-то непонятно из того, что я пишу?
4. Я добавил эскиз, который показывает эти случаи, чтобы вам было легче понять.
5. Вы можете взглянуть на так называемые альфа-формы. Другим вариантом было бы найти небольшие «промежутки» между вершинами, которые не связаны ребром. Переключая ребра между четырьмя соседними точками, вы получите независимые полигоны и сможете проверить их внутреннюю целостность.