Ashwin Murthy wrote: > What is the most efficient way to compute the intersecting area of 2 > rectangles? Dont assume anything about the relative postions of the 2 > rectangles. They can be aligned in any manner relative to one another.
This is kind of an annoying to program, but otherwise doable problem. The only thing you really have is that rectangles are convex shapes. What I would do is break everything down into sets of triangles. So first each rectangle is a pair of triangles, then we would need to make a primitive for triangle intersection and another for disjoint triangle union (which just concatenates the triangles.) Then you can make a special function to try to stitch the triangle back into polygons (indentically shared edges lead a pair of triangles to become a quadtrilateral etc, and colinear sequential edges can remove their redundant midpoints.) Keep in mind that a triangle pair intersection algorithm is actually itself kind of annoying to write. In fact I would break *that* down into a triangle, half-plane intersection algorithm (since a filled triangle is equal to the intersection of 3 half-planes.) If the rectangles can be assumed to be orthogonal with the axes, the problem is obviously is a *lot* easier. -- 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.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
