Пересечь многоугольник с прямоугольником и создать линии (разрез)

Question

Мне нужен алгоритм для пересечения (потенциально невыпуклого) многоугольника с прямоугольником. Прямоугольник будет параллелен плоскости xy, но многоугольник может иметь любую ориентацию.

Кроме того, мне нужен не только результат true / false, но и точные точки, где многоугольник пересекает прямоугольник, чтобы я мог рисовать линии там, где многоугольник перекрывает прямоугольник. Для невыпуклых многоугольников это может привести к двум или более линиям пересечения.

Это будет для модуля среза, который может разрезать набор многоугольников и создать 2D "разрез", где фигуры пересекают "плоскость", заданную значением z.

Я занимаюсь разработкой на Java, поэтому, если в Java3 (2) D есть какие-то встроенные методы, которые могут помочь, это было бы идеально.

Любая помощь / указатели в правильном направлении будет принята с благодарностью!

Вот картинка ... Я хочу красную линию в результате пересечения:

Answer 1

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

Рассмотрим многоугольник как упорядоченную совокупность ребер AB, BC, CD и т. Д., Где «направление» от первой точки каждого ребра кего вторая точка - «по часовой стрелке».То есть, если мы смотрим на точку A, точка B является следующей точкой при движении по часовой стрелке.

Метод состоит в том, чтобы найти ребро многоугольника, который пересекает плоскость, а затем найти следующий отрезок, двигаясьпо часовой стрелке, которая пересекает исходную сторону плоскости.Две точки, где эти сегменты пересекают плоскость, образуют конечные точки для пересекающегося сегмента.Это повторяется до тех пор, пока не будут проверены все ребра многоугольника.

Имейте в виду, что не все сегменты обязательно находятся внутри многоугольника, если он вогнутый.

   let P be any point on the polygon.

   TOP:
   while (P has not been checked)

       mark P as having been checked.

       let f be the point following P, clockwise.

       if (P and f are on opposite sides of the plane) then

          Continuing from f clockwise, find the next point Y that is on
              the same side of the plane as P.
          Let z be the point counter-clockwise from Y.
              (note - Sometimes z and f are the same point.)

          let S1 be the point where P,f intersects the plane
          let S2 be the point where Y,z intersects the plane

          if (segment (S1,S2) is inside the polygon)
              add (S1,S2) to a 'valid' list.
              let P = Y
          else
              let P = f
          endif    
       else
          let P = f
       endif
   endwhile       

Этот алгоритмстоит того, что вы заплатили за это.: -)