rectilinear polygon intersection

9
votes

I am looking for / trying to develop an optimal algorithm for rectilinear polygon intersection with rectangles. The polygons I am testing do not have holes.

Answers like those given here and here are for very general polygons, and the solutions are understandably quite complex.

Hoping that the S.O. community can help me document algorithms for the special cases with just rectilinear polygons.

I am looking for the polygon filled in green in the image below:

rectilinear polygon intersection with a rectangle

2
algorithmmathgeometry
are the edges of the rectilinear polygon and the rectangles parallel to the axes ? – Andre Holzner
@Andre -- yes -- all lines are parallel – jedierikb
As a first thought, storing the rectilinear polygon in a segment tree (for two dimensions) comes to my mind. Assuming that the rectilinear polygons are the ones which do not change and the rectangles vary. – Andre Holzner
Yes, your assumption is correct about what is mutable and what is not. Thanks for the suggestion. – jedierikb

2 Answers

3
votes

The book Computational Geometry: an Introduction by Preparata and Shamos has a chapter on rectilinear polygons.

2
votes

Use a sweep line algorithm, making use of the fact that a rectilinear polygon is defined by its vertices.

Represent the vertices along with the rectangle that they belong to, i.e. something like (x, y, #rect). To this set of points, add those points that result from the intersections of all edges. These new points are of the form (x, y, final), since we already know that they belong to the resulting set of points.

Now:

  • sort all points by their x-value
  • use a sweep line, starting at the first x-coordinate; for each new point:
    • if it's a "start point", add it to a temporary set T. Mark it "final" if it's a point from rectangle A and between y-coordinates from points from rectangle B in T (or vice versa).
    • if it's an "end point", remove it and its corresponding start point from T.

After that, all points that are marked "final" denote the vertices of the resulting polygon.

Let N be the total number of points. Further assuming that testing whether we should mark a point as being "final" takes time O(log(n)) by looking up T, this whole algorithm is in O(N*log(N)).

Note that the task of finding all intersections can be incorporated into the above algorithm, since finding all intersections efficiently is itself a sweep line algorithm usually. Also note that the resulting set of points may contain more than one polygon, which makes it slightly harder to reconstruct the solution polygons out of the "final" vertices.