Rectilinear polygon intersection?

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

Thank you. I will look at chapters 2 and 8. I see the term I want is isothetic polygons.

– jedierikb May 21 at 19:32.

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.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.