9 Replies - 1034 Views - Last Post: 19 December 2012 - 01:09 PM Rate Topic: -----

#1 qkrtjdwls91  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • 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  Icon User is online

  • Fire giant boob nipple gun!
  • member icon

Reputation: 3336
  • View blog
  • Posts: 11,303
  • 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..
Was This Post Helpful? 1
  • +
  • -

#3 anonymous26  Icon User is offline

  • D.I.C Lover

Reputation: 0
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#4 qkrtjdwls91  Icon User is offline

  • New D.I.C Head

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

Re: Distance between two 2D squares

Posted 19 December 2012 - 12:21 PM

View Postandrewsw, 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
Was This Post Helpful? 0
  • +
  • -

#5 qkrtjdwls91  Icon User is offline

  • New D.I.C Head

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

Re: Distance between two 2D squares

Posted 19 December 2012 - 12:54 PM

View Postqkrtjdwls91, on 19 December 2012 - 12:21 PM, said:

View Postandrewsw, 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
Was This Post Helpful? 0
  • +
  • -

#6 andrewsw  Icon User is online

  • Fire giant boob nipple gun!
  • member icon

Reputation: 3336
  • View blog
  • Posts: 11,303
  • 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 :bigsmile:/> 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!

Attached image(s)

  • Attached Image

Was This Post Helpful? 0
  • +
  • -

#7 qkrtjdwls91  Icon User is offline

  • New D.I.C Head

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

Re: Distance between two 2D squares

Posted 19 December 2012 - 01:03 PM

View Postandrewsw, on 19 December 2012 - 12:59 PM, said:

I haven't done any maths for years :bigsmile:/>/> 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
Was This Post Helpful? 0
  • +
  • -

#8 andrewsw  Icon User is online

  • Fire giant boob nipple gun!
  • member icon

Reputation: 3336
  • View blog
  • Posts: 11,303
  • Joined: 12-December 12

Re: Distance between two 2D squares

Posted 19 December 2012 - 01:04 PM

More complicated than I first thought!
Was This Post Helpful? 0
  • +
  • -

#9 qkrtjdwls91  Icon User is offline

  • New D.I.C Head

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

Re: Distance between two 2D squares

Posted 19 December 2012 - 01:08 PM

View Postqkrtjdwls91, on 19 December 2012 - 01:03 PM, said:

View Postandrewsw, on 19 December 2012 - 12:59 PM, said:

I haven't done any maths for years :bigsmile:/>/>/> 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
Was This Post Helpful? 0
  • +
  • -

#10 andrewsw  Icon User is online

  • Fire giant boob nipple gun!
  • member icon

Reputation: 3336
  • View blog
  • Posts: 11,303
  • 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.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1