@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 <kingston.imman...@gmail.com>
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
> <virmanisadi...@gmail.com>wrote:
>
>
>
> > compare the relative positions of the coordinates
>
> > On Sat, Aug 6, 2011 at 9:10 PM, Algo Lover <algolear...@gmail.com> 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 algogeeks@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com.
> >> 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 algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > 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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
