Distance between two 2D squares
Page 1 of 19 Replies  1401 Views  Last Post: 19 December 2012  01:09 PM
#1
Distance between two 2D squares
Posted 19 December 2012  10:46 AM
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?
Replies To: Distance between two 2D squares
#2
Re: Distance between two 2D squares
Posted 19 December 2012  11:23 AM
The distance between the two centrepoints 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 cornerpoints, rather than just edgepoints..
#3
Re: Distance between two 2D squares
Posted 19 December 2012  12:02 PM
#4
Re: Distance between two 2D squares
Posted 19 December 2012  12:21 PM
andrewsw, on 19 December 2012  11:23 AM, said:
The distance between the two centrepoints 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 cornerpoints, rather than just edgepoints..
Yes, I meant the 2nd option.. the shortest distance between, I am trying to find the formula for this
#5
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:
The distance between the two centrepoints 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 cornerpoints, rather than just edgepoints..
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
Re: Distance between two 2D squares
Posted 19 December 2012  01:03 PM
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!
Attached image(s)
#7
Re: Distance between two 2D squares
Posted 19 December 2012  01:03 PM
andrewsw, on 19 December 2012  12:59 PM, said:
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
Re: Distance between two 2D squares
Posted 19 December 2012  01:04 PM
#9
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:
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
Re: Distance between two 2D squares
Posted 19 December 2012  01:09 PM
