Guillermo Garcia wrote: > My proposal: > > - find how many vertices of one rectangle are inside the other one (easy) > - case > * 4 vertices: one rectangle is contained in the other > * 1 vertex: find intersections between the lines going out from this > vertex with the sides of the containing rectangle. Then you have the > intersection > * 2 vertices: find first the line between these two vertices, then find > intersections with the sides of containing rectangle. > * 3 vertices: find first the lines between these three vertices, then > the interesections with the sides of containg rectangle. > > What do you think?
I don't think breaking it down to these cases helps very much. Because each case is as complicated as the original problem. I have since looked at this problem, and I realize that there is a much easier way to do this. A rectangle is equal to the intersection of the four half planes each of which's border is incident with each edge of the rectangle (and which contain the other points) So the critical calculation we need to be able to do is to be able to intersect any arbitrary polygon with a half plane. This, it turns out, is a fairly simple and doable exercise. You simply walk the set of vertices of the polygon and include any point which is in the half plane, plus inserting any points which are created by the intersection of any edge segment with the half plane borderline. So you just take one rectangle to be a polygon, and the other to be four half planes, and do the 4 intersections, and you are done. This generalizes to the intersection of any random polygon with any convex polygon (since only convex polygons are the intersection of half planes.) With two non-convex polygons, I guess you would want to break at least one down into a disjoint union of convex polygons. But I think that's a fairly doable problem as well. -- Paul Hsieh http://www.pobox.com/~qed/ http://bstring.sf.net/ --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
