Distance between two 2D squares

Page 1 of 1

9 Replies - 2478 Views - Last Post: 19 December 2012 - 01:09 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=304412&amp;s=024b87bfc26ce0afc70ac1fec159160a&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

#1 qkrtjdwls91

Reputation: 2
• Posts: 15
• Joined: 19-December 12

Distance between two 2D squares

Posted 19 December 2012 - 10:46 AM

How do I find the distance between two 2D squares if I am given x, y, length, and height of two 2D squares?

Current idea I have is to simply brute force it and check the distance from every point in one edge of a square with every point in one edge of the other square and pick the lowest distance of the two. (the edges depending on the location/length of the two squares)

Is there a better way/algorithm for this?
Is This A Good Question/Topic? 0

Replies To: Distance between two 2D squares

#2 andrewsw

Reputation: 5463
• Posts: 21,473
• Joined: 12-December 12

Re: Distance between two 2D squares

Posted 19 December 2012 - 11:23 AM

It depends what determines "distance between". This can mean the distance between the centre-point of each square, or the shortest line that would touch the edge of the two shapes. That is, the "smallest gap" between the two shapes. [You stated squares, but I'm guessing you might mean rectangles?]

The distance between the two centre-points is easier:
dx = ABS((x1 + half * length1) - (x2 + half * length2))
similarly for dy. Then pythagoras:
distance = SQRT(dx^2 + dy^2)

If you are looking for the second option (shortest distance between) then I would treat it separately to find the horizontal and vertical distances.. But my Maths is rusty and, I suppose, there may be a formula that does this(?).

It can also mean the shortest distance between corner-points, rather than just edge-points..

#3 anonymous26

• D.I.C Lover

Reputation: 1
• Posts: 3,638
• Joined: 26-November 10

Re: Distance between two 2D squares

Posted 19 December 2012 - 12:02 PM

The specifics need to be known in order to find the best method.

#4 qkrtjdwls91

Reputation: 2
• Posts: 15
• Joined: 19-December 12

Re: Distance between two 2D squares

Posted 19 December 2012 - 12:21 PM

andrewsw, on 19 December 2012 - 11:23 AM, said:

It depends what determines "distance between". This can mean the distance between the centre-point of each square, or the shortest line that would touch the edge of the two shapes. That is, the "smallest gap" between the two shapes. [You stated squares, but I'm guessing you might mean rectangles?]

The distance between the two centre-points is easier:
dx = ABS((x1 + half * length1) - (x2 + half * length2))
similarly for dy. Then pythagoras:
distance = SQRT(dx^2 + dy^2)

If you are looking for the second option (shortest distance between) then I would treat it separately to find the horizontal and vertical distances.. But my Maths is rusty and, I suppose, there may be a formula that does this(?).

It can also mean the shortest distance between corner-points, rather than just edge-points..

Yes, I meant the 2nd option.. the shortest distance between, I am trying to find the formula for this

#5 qkrtjdwls91

Reputation: 2
• Posts: 15
• Joined: 19-December 12

Re: Distance between two 2D squares

Posted 19 December 2012 - 12:54 PM

qkrtjdwls91, on 19 December 2012 - 12:21 PM, said:

andrewsw, on 19 December 2012 - 11:23 AM, said:

It depends what determines "distance between". This can mean the distance between the centre-point of each square, or the shortest line that would touch the edge of the two shapes. That is, the "smallest gap" between the two shapes. [You stated squares, but I'm guessing you might mean rectangles?]

The distance between the two centre-points is easier:
dx = ABS((x1 + half * length1) - (x2 + half * length2))
similarly for dy. Then pythagoras:
distance = SQRT(dx^2 + dy^2)

If you are looking for the second option (shortest distance between) then I would treat it separately to find the horizontal and vertical distances.. But my Maths is rusty and, I suppose, there may be a formula that does this(?).

It can also mean the shortest distance between corner-points, rather than just edge-points..

Yes, I meant the 2nd option.. the shortest distance between, I am trying to find the formula for this

The data given is the x, y location of both rectangles and their width/height...

I have an idea of how to do it posted in my op, but I am wondering if theres a more efficient/algorithm to solving this problem instead of brute forcing every possible combination to find the lowest number

#6 andrewsw

Reputation: 5463
• Posts: 21,473
• Joined: 12-December 12

Re: Distance between two 2D squares

Posted 19 December 2012 - 01:03 PM

I haven't done any maths for years /> but, following from my previous example which determines the length of the green line in the attached image, I've outlined how the length of the green-line but only between the two shapes, might be determined. This will be the shortest distance according to your description (I believe..). I would not be upset if someone corrects my (poor) Maths.

But, of course, I'm making assumptions about the relative positions of the shapes. It needs to be checked and probably revised to take into account other relative positions.

Mmm scrub that.. it's not the shortest distance as the green line could be tilted from the right to create a shorter line.

Please ignore my attempt - my Maths is letting me down, sorry!

#7 qkrtjdwls91

Reputation: 2
• Posts: 15
• Joined: 19-December 12

Re: Distance between two 2D squares

Posted 19 December 2012 - 01:03 PM

andrewsw, on 19 December 2012 - 12:59 PM, said:

I haven't done any maths for years />/> but, following from my previous example which determines the length of the green line in the attached image, I've outlined how the length of the green-line but only between the two shapes, might be determined. This will be the shortest distance according to your description (I believe..). I would not be upset if someone corrects my (poor) Maths.

But, of course, I'm making assumptions about the relative positions of the shapes. It needs to be checked and probably revised to take into account other relative positions.

I am trying to find something like this http://postimage.org/image/h99o7fn5h/

where the black line would be the shortest distance....

and the light blue lines arent, but are still distance between rectangles

#8 andrewsw

Reputation: 5463
• Posts: 21,473
• Joined: 12-December 12

Re: Distance between two 2D squares

Posted 19 December 2012 - 01:04 PM

More complicated than I first thought!

#9 qkrtjdwls91

Reputation: 2
• Posts: 15
• Joined: 19-December 12

Re: Distance between two 2D squares

Posted 19 December 2012 - 01:08 PM

qkrtjdwls91, on 19 December 2012 - 01:03 PM, said:

andrewsw, on 19 December 2012 - 12:59 PM, said:

I haven't done any maths for years />/>/> but, following from my previous example which determines the length of the green line in the attached image, I've outlined how the length of the green-line but only between the two shapes, might be determined. This will be the shortest distance according to your description (I believe..). I would not be upset if someone corrects my (poor) Maths.

But, of course, I'm making assumptions about the relative positions of the shapes. It needs to be checked and probably revised to take into account other relative positions.

I am trying to find something like this http://postimage.org/image/h99o7fn5h/

where the black line would be the shortest distance....

and the light blue lines arent, but are still distance between rectangles

the graph would be
0 1 2 3 4 5 6 7... x
1
2
3
4
5
6
y

#10 andrewsw

Reputation: 5463
• Posts: 21,473
• Joined: 12-December 12

Re: Distance between two 2D squares

Posted 19 December 2012 - 01:09 PM

If the shapes overlap in their horizontal or vertical positioning then the distance is easy to determine. If they don't overlap then it needs to be the distance between the two nearest corners.