Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Oh wise ones, I'm new to the programming scene and have an interest in perl. What I'm trying to accomplish is check if two squares intersect.
The dataset has (x,y) for each corner of the squares (eg 3x3inch squares). So as an example, the input would be:
square #1: 1,1;1,4;4,4;4,1<br>
square #2: 5,2;5,5;8,5;8,2<br>

[download]
Obviously the two do not intersect in the above example. But this is what the dataset would look like.
Any help would be greatly appreciated.

thanks,
Total Newbie

Replies are listed 'Best First'.
Re: Checking if squares intersect
by ikegami (Patriarch) on Oct 14, 2009 at 18:37 UTC

    [ This posts assumes the squares exist on the same plane. ]

    Start by listing all the different circumstances where the two squares intersect:

    • One corner of one square is inside the other
    • Two adjacent corners of one square is inside the other
    • Four corners of one square is inside the other

    Then further refine those conditions to use definite articles:

    • The TR corner of the first square is inside the other
    • The BR corner of the first square is inside the other
    • The TL corner of the first square is inside the other
    • The BL corner of the first square is inside the other
    • The TR corner of the second square is inside the other
    • The BR corner of the second square is inside the other
    • The TL corner of the second square is inside the other
    • The BL corner of the second square is inside the other
    • ...

    Then express them in terms of functions or X and Y.

    On second thought, it might be easier to to check if two squares *don't* intersect, then negate the result

    Start by listing all the different circumstances where the two squares don't intersect:

    • One square is completely above the other
    • One square is completely to the left of the other

    Then further refine those conditions to use definite articles:

    • The first square is completely above the other
    • The first square is completely below the other
    • The first square is completely to the left the other
    • The first square is completely to the right the other

    Then express them in terms of functions or X and Y.

[reply]
      Actually i came up with the following:

      I done this by negation and using the values for the upper left lower right respectively for both sqares.

      square #1: upper left= x1,y1 ; lower right= x2,y2
square #2: upper left= x3,y3 ; lower right= x4,y4

return !(x2 < x3 || x1 > x2 || y2 > y3 || y1 < y4)

      [download]
      Hope my logic is right...can someone confirm?

      Thanks,
      Total Newbie
[reply]
[d/l]

        x4 is absent, so there's surely an error

        Adjacent squares don't intersect, so
        < should be <=
        > should be >=

        You didn't indicate whether lower "y" values are located higher (that's what you used) or lower (cartesian), so I can't verify the if you are comparing the "y"s properly.

[reply]
[d/l]
[select]
        Your logic only holds with the additional property that the squares have their edges parallel to the x and y axis. If that isn't the case, your logic fails.
[reply]
Re: Checking if squares intersect
by gmargo (Hermit) on Oct 14, 2009 at 20:13 UTC
[reply]
Re: Checking if squares intersect
by Bloodnok (Vicar) on Oct 14, 2009 at 18:21 UTC
    Hmmmm, anyone else's homework detector triggered by this ?

    Show us what you've got thus far...

    A user level that continues to overstate my experience :-))
[reply]
Re: Checking if squares intersect
by JavaFan (Canon) on Oct 20, 2009 at 09:36 UTC
    Two squares intersect if and only if one square has at least one vertex inside the other square. (Whether two squares intersect if they only share part of an edge, have a single vertex on an edge of the other, or share only a vertex is something you have to decide, and code for). This property holds even if the squares aren't axis parallel. However, the property doesn't hold for rectangles, even if they are axes parallel.
[reply]

Back to Seekers of Perl Wisdom