@Dave.Thanks, I got your counter-example. And the Separating Axis test is the way to go for finding the intersection of any two polygons.
The Separating Axis test does not apply if one of the polygons is not convex. Thanks, Immanuel On Sun, Aug 7, 2011 at 12:18 AM, Dave <[email protected]> wrote: > @Immanuel: First, TopLeft and BottomRight or the alternative are > insufficient to specify non-axis-aligned rectangles. > > Second, what we can say is that if the rectangles overlap then the > shadows will overlap, but we cannot say that if the shadows overlap > then the rectangles overlap; e.g., take the rectangles [(0,0), (0,3), > (3,3), (3,0)] and [(2,5), (5,2), (7,4), (4,7)]. > > The standard test is the Separating Axis Test. You can find this with > google. > > Dave > > On Aug 6, 11:38 am, immanuel kingston <[email protected]> > wrote: > > Algo goes something like this. > > > > Rectangles are represented by two points TopLeft and bottomRight or > > BottomLeft and TopRight > > > > 1. Choose Xmin and Xmax from Rectangle A. Check if any of the > x-coordinates > > of rectangle B fall in between Xmin and Xmax of A. > > 2. choose Ymin and Ymax from Rectangle A. Check if any of the > y-coordinates > > of rectangle B fall in between Ymin and Ymax of A. > > > > If both the above conditions are satisfied, then the rectangles intersect > > else not. > > > > Basically the above algo is based on Shadow of a rectangle on the x and y > > axes. > > If the rectangles intersect, then the shadows on the x and y axes > overlay. > > > > code as follows: > > > > class Rectangle{ > > Point topRight; > > Point bottomLeft;} > > > > class Point{ > > int x; > > int y; > > > > } > > > > boolean isIntersecting(Rectangle A, Rectangle B){ > > int x0 = Math.min(A.topRight.x, A.bottomLeft.x); > > int x1 = Math.max(A.topRight.x, A.bottomLeft.x); > > int y0 = Math.min(A.topRight.y, A.bottomLeft.y); > > int y1 = Math.max(A.topRight.y, A.bottomLeft.y); > > return ((x0 < B.topRight.x && b.topRight.x < x1) || (x0 < > B.bottomLeft.x > > && b.bottomLeft.x < x1)) && ((y0 < B.topRight.y && b.topRight.y < y1) || > (y0 > > < B.bottomLeft.y && b.bottomLeft.y < y1))} > > > > boolean intersects(Rectangle A, Rectangle B) { > > return isIntersecting(A,B) || isIntersecting(B,A); > > > > } > > > > Pls correct me if i am wrong. > > > > Thanks, > > Immanuel > > > > On Sat, Aug 6, 2011 at 9:26 PM, Aditya Virmani <[email protected] > >wrote: > > > > > > > > > compare the relative positions of the coordinates > > > > > On Sat, Aug 6, 2011 at 9:10 PM, Algo Lover <[email protected]> > wrote: > > > > >> Given 2 rectangles not necessary parallel to co-ordinate axis. How > > >> would you find if the rectangles intersect and if they do find the > > >> intersection points > > > > >> -- > > >> You received this message because you are subscribed to the Google > Groups > > >> "Algorithm Geeks" group. > > >> To post to this group, send email to [email protected]. > > >> To unsubscribe from this group, send email to > > >> [email protected]. > > >> For more options, visit this group at > > >>http://groups.google.com/group/algogeeks?hl=en. > > > > > -- > > > You received this message because you are subscribed to the Google > Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to [email protected]. > > > To unsubscribe from this group, send email to > > > [email protected]. > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
