Как я могу разделить полигон по линии?

Question

Как показано ниже,

Answer 1

Я должен был сделать это недавно. Простая ходьба многоугольника не будет работать для вогнутых многоугольников, как на вашей диаграмме. Ниже приведен набросок моего алгоритма, вдохновленного алгоритмом отсечения полигонов Greiner-Hormann . Расщепление легче и сложнее, чем вырезание полигонов. Проще, потому что вы только обрезаете линию вместо прямоугольника или другого многоугольника; сложнее, потому что нужно держать обе стороны.

Create an empty list of output polygons
Create an empty list of pending crossbacks (one for each polygon)
Find all intersections between the polygon and the line.
Sort them by position along the line.
Pair them up as alternating entry/exit lines.
Append a polygon to the output list and make it current.
Walk the polygon. For each edge:
    Append the first point to the current polygon.
    If there is an intersection with the split line:
        Add the intersection point to the current polygon.
        Find the intersection point in the intersection pairs.
        Set its partner as the crossback point for the current polygon.
        If there is an existing polygon with a crossback for this edge:
            Set the current polygon to be that polygon.
        Else
            Append a new polygon and new crossback point to the output lists and make it current.
        Add the intersection point to the now current polygon.

Answer 2

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

Обойти ребра полигонов и для каждого ребра определить, пересекает ли он линию.Найдите первое такое ребро, которое делает это.Продолжайте движение, пока не найдете другой такой край, но добавьте каждый, с которым вы столкнулись по пути, к новому многоугольнику (включая часть первого края, которая была разделена линией, которая находится на «этой стороне», и аналогично для последнего края).Наконец, добавьте закрывающий край к новому многоугольнику.Теперь продолжите обработку ребер - на другой стороне линии, создавая другой многоугольник таким же образом.Теперь у вас есть два полигона, разделенных по линии.Если вы будете осторожны, тот же метод будет работать с разбиением невыпуклого многоугольника на несколько многоугольников.

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

Редактировать: Как указывает Ксан, это не будет правильно обрабатывать все невыпуклые случаи.Это можно исправить с помощью небольшой модификации алгоритма.Прежде чем добавить закрывающий край, как описано выше, вы должны сначала проверить, пересекает ли какой-либо дополнительный край исходного многоугольника этот закрывающий край;если это так, вы закрываете только до этого ребра и продолжаете обработку дальнейших ребер с этой точки.

Answer 3

Все, что вам нужно, это обрезка полигонов алогритом.Вы можете увидеть обзор здесь: Обрезка полигонов Я думаю, что есть пять реализаций, из которых можно извлечь уроки.

Answer 4

В 1994 году Джордж Ванечек разработал решение для этого в 3D и опубликовал решение в Graphic Gems V "Пространственное разбиение многоугольника плоскостью".Исходный код все еще доступен в репозитории Graphic Gems .

. Недавно Дэвид Гейер опубликовал 2D-реализацию алгоритма Ванечека с объяснением этого алгоритма.См. Блог Дэвида: разбиение произвольного многоугольника на линию

Answer 5

Это вполне возможно.Я предполагаю, что вы используете Java2d для этого.Вы нашли в нем метод, который называется пересекающимся.Используя это, вы можете сделать это.

Возможно, вам придется изменить эту реализацию полигона и написать еще один метод пересечения, который передает объект Line2D, и настраивает его так, чтобы он передавал полигоны массива (возможно, поскольку один и тот же отрезок может привести к образованию бесконечных многоугольников - предположим, зигзагообразный многоугольник) или ноль.