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

Ответ 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.

Ответ 2

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

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

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

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

Ответ 3

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

Ответ 4

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

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

Ответ 5

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

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