Register or Login to browse without ads

Tue 22 Jul 2014 - 9:15 am UTC

Home | Ask a Question | Browse Questions

ANSWERED on Tue 22 Feb 2011 - 2:19 pm UTC by mathtalk

Question: Shortest distance between two rectangles?

Please carefully read the Disclaimer and Terms & conditions.
Priced at $50.00
The customer tipped the researcher $40.00

Actions: Add Comment

Mon 14 Feb 2011 - 6:03 am UTC

Question

j_philipp
Customer

In pseudo code (or Lua) how do I calculate the shortest distance between the outlines of two rotated rectangles? Each of my two rectangles has a given center x, center y, width, height in pixels and a rotation angle in degrees.

My goal, and some background: In a game with gravity written in Lua/ Corona, I want to tell if a ball with a given radius can pass between two stones (the rectangles), or if there's an at least theoretical chance the ball could get stuck (i.e. when the two stone rectangles are too close to each other)... if the ball could get stuck, I want to remove one of the stones. Note the stones are randomly positioned and they are always rotated at least a bit, and also note that speed doesn't matter much here as it's a single pre-level calculation step.

Thanks!!

 
 

Mon 14 Feb 2011 - 11:32 pm UTC

Comment

myoarin
User

Greetings,

For sure, I hardly understand the problem, but I really don't understand what you mean with "the stones are randomly positioned".
I was assuming that the stones have the same dimensions and that their axes of rotation are on a horizontal plane.

If you are measuring in pixels, there are differences in the horizontal and vertical formats:
http://www.mevicom.de/download/Digitale%20Bildformate.pdf
(Maybe that doesn't matter, but it would seem to complicate things.)

It seems to me that the ball could get stuck if the distance between the centers X and Y is less than sum of half the diagonals of stones and the diameter of the ball.

Try to be polite about telling me that I really don't understand.

Myo

 

Wed 16 Feb 2011 - 10:20 am UTC

Question clarification

j_philipp
Customer

Hi Myo,

the stones x and y coordinates are random pixel values (but within the screen dimensions), and the rotation is also a randomized angle (but never zero).

Hope that explains it more!

cheers
Philipp

 

Wed 16 Feb 2011 - 3:01 pm UTC

Uclue Researcher Request for clarification

mathtalk
Researcher

Let me ask a few things to narrow my answers as much as possible.

How do you represent the rectangles/stones?  I get that you are using screen coordinates, but presumably this is for the center of each figure, and in addition you have a rotation (degrees? radians?) and a notion of width and height of the "unrotated" rectangle.

Are all the rectangles congruent (up to translation/rotation)?

Is it known a priori that rectangles do not intersect, or is it not a problem if they do?  If the test needs to include intersection cases, I'd give more detail about that.

Also, are we dealing with static rectangles (but a moving circle)?  I got that impression from the remark about doing the tests once per level.

regards, mt

 

Wed 16 Feb 2011 - 3:47 pm UTC

Question clarification

j_philipp
Customer

Hi Mathtalk,

thanks for the followup, here are the answers to your questions:

- the rectangles are represented as center x and y in pixels (say 50, 400), and the original width and height in pixels of the zero-rotated rectangle. Then I'm applying a rotation in degrees (think something like -50 to 50). So for an unrotated rectangle the left-top edge would be something like x - width / 2, y - height / 2.

- sidenote: actually, the Lua/ Corona framework says they can also give me the minX, minY, maxX, maxY bounding box, but this doesn't seem useful for my needs, as I'm rotating the rectangles (I also haven't tested if the bounding box values are correct, just saying, as their could be an exotic bug in it).

- all stone rectangles are rotated a bit, so they're never zero rotation (I'm doing this so the ball will not rest on them and never roll sideways) In my current code, but this may change, the most drastic rotation angles in degrees are -50 to 50, but this limit could change in the future, so best not include this as a fixed limit in a solution.

- it is not known before whether rectangles overlap. They often do overlap (I'm removing as many as I can find using Corona's collision detection, but there are currently flaws in it that prevent me from making full use of it; my first try was to overlay the main rectangles with larger checker rectangles, but there's problems in certain cases with what the physics engine reports back here; I'm having an 80% working solution but looking to make it to 100%).

- all rectangles are static, non-moving. Think of something below 100 rectangles randomly dropped on a 1024*7678 pixels screen; these rectangles are concrete stones that only I can remove before the game starts, the player cannot change or remove them. The level is generated before each play, so it shouldn't be super slow to generate it but a couple of microseconds more won't hurt the framerate either.

thanks!
Philipp

 

Thu 17 Feb 2011 - 3:53 pm UTC

Uclue Researcher Request for clarification

mathtalk
Researcher

You don't say the rectangles are or are not congruent, so I'll assume they are not (i.e. possibly different shapes).

In various places where there might be a minor "optimization" for the special case of all rectangles "equal", I'll try and point that out.

I'm not familiar with Lua, so bear with my attempts to use its syntax for the time being.  Basically we have two problems to solve. (1) Do a given pair of rectangles intersect? (2) If not, what is the minimum distance between a pair of such non-intersecting rectangles?

The short answers to these questions are:

(1) A pair of rectangles intersect if no line separates the plane into two parts, with one rectangle on either side of that line.  We can narrow the candidates for a possible "separating axis" to just lines that extend edges of the rectangles, provided we allow one rectangle to be adjacent to that line (obviously) and the other rectangle to be on the other side of the line and not touching it.  Cf.

[Separating Axis Theorem -- codezealot]
http://www.codezealot.org/archives/55

(2) The minimum distance between a pair of non-intersecting rectangles is attained at a vertex of one rectangle.  So it suffices to find the distance from a point to a rectangle and evaluate this eight times (all four vertices of both rectangles).  We can narrow these candidates if we know an edge of one rectangle "separates" as in the answer to (1).

I see you posted the question at stackoverflow.  I recall that there was a very nice formulation of the distance calculation there or at math.stackexchange, but I haven't been able to pull it up with the right search terms yet.  I'm sure I can reconstruct it, but I'd love to give the guy who wrote it up (last Dec.?) credit.  I was surprised by the compactness of his logic.

regards, mt

 

Thu 17 Feb 2011 - 3:57 pm UTC

Question clarification

j_philipp
Customer

"You don't say the rectangles are or are not congruent, so I'll assume they
are not (i.e. possibly different shapes)."

To answer your request for clarification: The rectangles at this moment are all the same width and height.

Thanks, and looking forward to an answer!

Philipp

 

Thu 17 Feb 2011 - 3:59 pm UTC

Question clarification

j_philipp
Customer

PS: If you email me at [...email deleted by uclue admin...], I can furthermore send you an image of a formula my grandfather gave to me when I asked him about this, he says it can be used to solve my problem.

 

Thu 17 Feb 2011 - 4:25 pm UTC

Uclue Researcher Request for clarification

mathtalk
Researcher

Hey,

Here's a very similar stackoverflow answer to the one (I think) I remember:

[Circle-Rectangle collision detection (intersection) -- stackoverflow]
http://stackoverflow.com/questions/401847/circle-rectangle-collision-detection-intersection

Perhaps the other (should have been fairly recent) got deleted for being a duplicate (they are fairly aggressive about that sort of thing).

Anyway, the powers that be have asked you to post the formula at Google Docs or Tinypic.url.

Here's the gist of the idea.  Given a vertex of one rectangle, any ball (disk) that touches that vertex can only extend toward the other rectangle by the diameter of the ball.  So if you consider the circle around the vertex of radius equal to the diameter of the ball, and ask if it intersects with the other rectangle, you get the answer, at least if you do this up to eight times.

Of course we don't want to do unnecessary work, so I'll detail how knowing a separating edge reduces the work.

-mt

 

Thu 17 Feb 2011 - 4:34 pm UTC

Question clarification

j_philipp
Customer

( Well, here's what my grandfather scribbled down in German: http://i.imgur.com/smTPB.jpg )

 

Mon 21 Feb 2011 - 8:00 am UTC

Question clarification

j_philipp
Customer

Hi, this question has been locked for several days, may I ask when I can expect the answer? It's slightly urgent as the game this is about happily waits for its submission now...

cheers
Philipp

 

Mon 21 Feb 2011 - 1:58 pm UTC

Uclue Researcher Request for clarification

mathtalk
Researcher

Hi, Philipp:

Here's what I have so far, I'm filling in the blanks on the coding, but certainly you can look over the framework and narrative, and then the code will be added today.

Representation of stones
------------------------

Here's my pigeon-Lua description of intrinsic attributes for the stones.
Since these are "rotated boxes", a natural way to represent them is with
an array (table) called rox.

However suppressing any indexing of array entries, let's work with object
roxA (resp. roxB) having assigned attributes as follows:

roxA.x   \    center of
roxA.y   /    rectangle

roxA.dx  :  half width
roxA.dy  :  half height

roxA.theta : angle of rotation in degrees

Given approximately 100 such stones, there will be about 5,000 pairs of
distinct stones whose separation by distance dBall (diameter of ball)
is to be proven.  For the sake of discussion we propose a function call
separate(roxA,roxB,dBall) returning true or false accordingly as the
two stones do not intersect and have the required separation.  This
arrangement entails two auxiliary functions, step1(roxA,roxB,dBall)
and step2(roxA,roxB,dBall), which also return true or false and whose
semantics are detailed below.

I've used some semicolons to clarify what are putative lines of code,
knowing that they are not required in Lua.

Step 0:  Bounding circles test
------------------------------

As our colleague eiffel immediately noticed, the diagram drawn by your
grandfather gives a quick test that proves in many cases that stones
are separated by the requred distance, or if not that much, that they
do not intersect.

The idea is to subtract from the stones' center-to-center distance the
sum of the bounding circles' radii.  If this difference exceeds dBall,
then the required separation of these rectangles is proven.  If not,
but the difference is nonetheless positive, then at least we know that
the rectangles do not intersect (and we can skip to Step 2).

This top-level test does not use the rotations of the rectangles and
is inconclusive to the extent that rotations can prevent the required
separation.  Accordingly a final determination may depend on calls to
the auxiliary functions step1 and/or step2.

The function step1 tests the stones for intersection, and returns
false if they do intersect.  Otherwise step1 returns the result of
step2.  Function step2 assumes non-intersecting stones and returns
true or false accordingly as their separation exceeds dBall.

First we compute the radius of each bounding circle:

radiusA = math.sqrt( roxA.dx^2 + roxA.dy^2 );
radiusB = math.sqrt( roxB.dx^2 + roxB.dy^2 );

dCtr2Ctr = math,sqrt( (roxA.x - roxB.x)^2 + (roxA.y - roxB.y)^2 );

dCircles = dCtr2Ctr - ( radiusA + radiusB );

if dCircles > dBall then return true
elseif dCircles > 0 then return step2(roxA,roxB,dBall)
else return step1(roxA,roxB,dBall);

Step 1:  Ruling out intersection
--------------------------------

A definitive way to rule out intersection of two rectangles checks
to see if an edge of one rectangle "separates" it from the other
rectangle, in the sense that all the vertices of the latter lie on
the opposite side of the given edge from the center of the first
rectangle.  It may be that only one of the rectangles has such an
edge, and the code below may try all eight edges before reaching
any conclusion about intersection.

If the rectangles intersect, we return false since obviously they do
not have the required separation.  Otherwise step1 should call step2
to determine whether the required separation exists.

Finding the vertices and edges of a stone uses its rotation for the
evaluation of trigonometric functions sine and cosine, stuff we did
not need in Step 0.  Note that Lua assumes trigonometric arguments
in radians and provides math.rad( ) to convert degrees to radians.

An "unrotated" box (never used in your app) is determined by its
projections on the x/y-axes, [x - dx,x + dx] and [y - dy,y + dy]
resp., because the box is the Cartesian product of the intervals.
Once it has been rotated, the same information is obtained by
projection onto a rotated pair of mutually perpendicular axes.

ASSUMPTION

I don't know whether in your environment positive angles correspond
to clockwise or counterclockwise rotations.  I'm going to pick one
formula and go with it, namely that the rotated box's vertices are:

(x + dx, y + dy) |->
(x + cos(theta)*dx - sin(theta)*dy, y + sin(theta)*dx + cos(theta)*dy)

(x - dx, y + dy) |->
(x - cos(theta)*dx - sin(theta)*dy, y - sin(theta)*dx + cos(theta)*dy)

(x - dx, y - dy) |->
(x - cos(theta)*dx + sin(theta)*dy, y - sin(theta)*dx - cos(theta)*dy)

(x + dx, y - dy) |->
(x + cos(theta)*dx + sin(theta)*dy, y + sin(theta)*dx - cos(theta)*dy)

If it turns out I've guessed wrong, then what needs to be changed
are the signs of the sine terms.  Likely you can check correctness
by printing vertex coordinates of a stone rotated 30 degrees.

PROJECTION

Given the above assumption, we would recover the width and height of
the rotated rectangle by projecting it onto the rotated axes.  For
consistency we translate the center of the rectangle to the origin,
subtracting (x,y) from every pair of coordinates to be projected,
and then dot product the results with these unit vectors:

( cos(theta), sin(theta) )   : the rotated unit vector along x-axis

(-sin(theta), cos(theta) )   : the rotated unit vector along y-axis

which gives a pair of values for each projected vertex after rotation:

unrotated vertex         on rotated x-axis         on rotated y-axis
----------------         -----------------         -----------------
  (x+dx,y+dy)                     dx                        dy
  (x-dx,y+dy)                    -dx                        dy
  (x-dx,y-dy)                    -dx                       -dy
  (x+dx,y-dy)                     dx                       -dy

Projecting the vertices of roxA onto its corresponding rotated axes
is therefore not necessary to compute; we know the answer.  What is
necessary is the same computations for the vertices of roxB onto the
rotated axes of roxA.

NONINTERSECTION

Let xmin_B and xmax_B be the least and greatest projections of roxB's
vertices onto the rotated x-axis of roxA.  Let ymin_B and ymax_B be
the least and greatest projections of roxB's vertices onto the rotated
y-axis of roxA.

Then rectangles roxA and roxB have empty intersection if the intervals
[-dx,dx] and [xmin_B,xmax_B] have empty intersection, or the intervals
[-dy,dy] and [ymin_B,ymax_B] have empty intersection.

In other words, a sufficient condition for nonintersection of roxA and
roxB is any one of the following:

    xmin_B  >  dx
    xmax_B  < -dx
    ymin_B  >  dy
    ymax_B  < -dy

Likewise if we project the vertices of roxA onto rotated axes of roxB,
exchanging the roles of roxA and roxB, we get four more sufficient
conditions for nonintersection of roxA and roxB.

Combining all eight conditions in a disjunction (OR) gives a necessary
and sufficient condition for nonintersection.  In other words if none
of the eight conditions is true, then none of the eight edges separate
the rectangles, and the rectangles do intersect.

IMPLEMENTATION

function step1(roxA,roxB,dBall)

Step 2: Distance between rectangles
-----------------------------------

Once the nonintersection of rectangles is known, the distance between
them will be the minimum distance of a vertex of one rectangle to the
other rectangle.  In general we must check vertices of both rectangles.

 

Mon 21 Feb 2011 - 2:07 pm UTC

Question clarification

j_philipp
Customer

Looks excellent so far, I'll hang in there, thanks!

> I don't know whether in your environment positive
> angles correspond to clockwise or counterclockwise rotations.

In my framework, positive = clockwise.

In your pseudo-code answer, it would be cool if you could separate code from explanation, or keep the explanation in // comments (or as it's in Lua: -- comments), so that I could quickly have a run with it to see if I can get it to work.

cheers!
Philipp

 

Mon 21 Feb 2011 - 2:22 pm UTC

Uclue Researcher Request for clarification

mathtalk
Researcher

Yes, I'll post just some code in the answer (with comments, although from Lua's manual I was under the impression comments start with double hyphens "--").

I'm a little leery about the clockwise/counterclockwise thing, as the screen coordinates probably have x increasing left to right and y increasing top to bottom, so that things are "reflected" vertically.  Anyway there are only two possibilities and I'm going to stick with what I guessed for now (unless you tell me I'm wrong about screen coordinates), and we can check it in practice.

--mt

 

Mon 21 Feb 2011 - 3:23 pm UTC

Question clarification

j_philipp
Customer

> although from Lua's manual I was under the impression comments
> start with double hyphens

You're exactly right, they do.

 

Mon 21 Feb 2011 - 5:51 pm UTC

Uclue Researcher Request for clarification

mathtalk
Researcher

-- Code for the distance squared from a point (tx,ty) to
-- an unrotated origin-centered box [-dx,dx] X [-dy,dy].
-- To be called with dx,dy positive integer half-width &
-- half-height of such box.

function dsqr2box(tx,ty,dx,dy)

    tx = math.abs(tx);

    if tx > dx then tx = (tx - dx)^2 else tx = 0;

    ty = math.abs(ty);

    if ty > dy then ty = (ty - dy)^2 else ty = 0;

    return tx + ty; -- distance squared to box

end

 

Mon 21 Feb 2011 - 7:56 pm UTC

Uclue Researcher Request for clarification

mathtalk
Researcher

This is something I just read about on an programming language newsgroup, an idea that seems it might be useful for threads like the current one:

[Pastebin -- Wikipedia]
http://en.wikipedia.org/wiki/Pastebin

Basically that there are (free) Web-based services where syntax-highlighted text can be cut and pasted, scaling up in some cases (I think) to actually running/debugging of code.

Seems like an idea whose cloud-time has come!

--mt

 

Tue 22 Feb 2011 - 10:25 am UTC

Question clarification

j_philipp
Customer

Hi MathTalk,

You posted a request for clarification but I am not sure what your question is. My question is unlocked now, does that mean you don't want to post an answer? Either way, no problem, please let me know.

cheers
Philipp

 

Tue 22 Feb 2011 - 2:19 pm UTC

Uclue Researcher Answer

mathtalk
Researcher

-- Compute distance squared from point (tx,ty) to an
-- unrotated box centered at origin [-dx,dx] X [-dy,dy]

function dsqr2box(tx,ty,dx,dy)

    tx = math.abs(tx);
   
    if tx > dx then tx = (tx - dx)^2 else tx = 0;
   
    ty = math.abs(ty);
   
    if ty > dy then ty = (ty - dy)^2 else ty = 0;
   
    return tx + ty;
   
end

-- Check if rotated rectangles roxA,roxB are separated enough for
-- ball of diameter dBall to pass between them.  Object roxA (resp.
-- object roxB) has assigned attributes as follows:
--
--   roxA.x   \    center of
--   roxA.y   /    rectangle
--
--   roxA.dx  :  half width
--   roxA.dy  :  half height
--
--   roxA.theta : angle of rotation in degrees

function separate(roxA,roxB,dBall)

-- bounding circle test

    radiusA = math.sqrt( roxA.dx^2 + roxA.dy^2 );
    radiusB = math.sqrt( roxB.dx^2 + roxB.dy^2 );
   
    diffABx = roxA.x - roxB.x
    diffABy = roxA.y - roxB.y
    dCtr2Ctr = math,sqrt( diffABx^2 + diffABy^2 );
   
    dCircles = dCtr2Ctr - ( radiusA + radiusB );
   
    if dCircles > dBall then return true;

    if dCircles > 0 then nonintersectAB = true;

-- distance from vertices of one rectangle to other rectangle

    dBall = dBall^2;  -- use diameter dBall squared henceforth

-- distance from vertices of roxB to rectangle roxA

    rAth = math.rad(roxA.theta);
    cosA = math.cos(rAth);
    sinA = math.sin(rAth);
   
    tx = roxB.dx - diffABx;
    ty = roxB.dy - diffABy;
    xBne = cosA*tx + sinA*ty;
    yBne = -sinA*tx + cosA*ty;
    if dsqr2box(xBne,yBne,roxA.dx,roxA.dy) <= dBall then return false;
   
    tx = -roxB.dx - diffABx;
    ty = roxB.dy - diffABy;
    xBnw = cosA*tx + sinA*ty;
    yBnw = -sinA*tx + cosA*ty;
    if dsqr2box(xBnw,yBnw,roxA.dx,roxA.dy) <= dBall then return false;

    tx = -roxB.dx - diffABx;
    ty = -roxB.dy - diffABy;
    xBsw = cosA*tx + sinA*ty;
    yBsw = -sinA*tx + cosA*ty;
    if dsqr2box(xBsw,yBsw,roxA.dx,roxA.dy) <= dBall then return false;

    tx = roxB.dx - diffABx;
    ty = -roxB.dy - diffABy;
    xBse = cosA*tx + sinA*ty;
    yBse = -sinA*tx + cosA*ty;
    if dsqr2box(xBse,yBse,roxA.dx,roxA.dy) <= dBall then return false;
   
-- distance from vertices of roxA to rectangle roxB

    rBth = math.rad(roxB.theta);
    cosB = math.cos(rBth);
    sinB = math.sin(rBth);
   
    tx = roxA.dx + diffABx;
    ty = roxA.dy + diffABy;
    xAne = cosB*tx + sinB*ty;
    yAne = -sinB*tx + cosB*ty;
    if dsqr2box(xAne,yAne,roxB.dx,roxB.dy) <= dBall then return false;
   
    tx = -roxA.dx + diffABx;
    ty = roxA.dy + diffABy;
    xAnw = cosB*tx + sinB*ty;
    yAnw = -sinB*tx + cosB*ty;
    if dsqr2box(xAnw,yAnw,roxB.dx,roxB.dy) <= dBall then return false;

    tx = -roxA.dx + diffABx;
    ty = -roxA.dy + diffABy;
    xAsw = cosB*tx + sinB*ty;
    yAsw = -sinB*tx + cosB*ty;
    if dsqr2box(xAsw,yAsw,roxB.dx,roxB.dy) <= dBall then return false;

    tx = roxA.dx + diffABx;
    ty = -roxA.dy + diffABy;
    xAse = cosB*tx + sinB*ty;
    yAse = -sinA*tx + cosB*ty;
    if dsqr2box(xAse,yAse,roxB.dx,roxB.dy) <= dBall then return false;

-- perform nonintersection tests, if needed

    if nonintersectAB then return true;

    if (    xBne > roxA.dx and xBnw > roxA.dx
        and xBsw > roxA.dx and xBse > roxA.dx )
    then return true;

    if (    yBne > roxA.dy and yBnw > roxA.dy
        and yBsw > roxA.dy and yBse > roxA.dy )
    then return true;

    if (    xBne < -roxA.dx and xBnw < -roxA.dx
        and xBsw < -roxA.dx and xBse < -roxA.dx )
    then return true;

    if (    yBne < -roxA.dy and yBnw < -roxA.dy
        and yBsw < -roxA.dy and yBse < -roxA.dy )
    then return true;

    if (    xAne > roxB.dx and xAnw > roxB.dx
        and xAsw > roxB.dx and xAse > roxB.dx )
    then return true;

    if (    yAne > roxB.dy and yAnw > roxB.dy
        and yAsw > roxB.dy and yAse > roxB.dy )
    then return true;

    if (    xAne < -roxB.dx and xAnw < -roxB.dx
        and xAsw < -roxB.dx and xAse < -roxB.dx )
    then return true;

    if (    yAne < -roxB.dy and yAnw < -roxB.dy
        and yAsw < -roxB.dy and yAse < -roxB.dy )
    then return true;
   
    return false;   -- rectangles intersect in criss-cross fashion
   
end

 
 

Wed 23 Feb 2011 - 4:20 am UTC

Accepted and rated

j_philipp
Customer

Works beautifully. Thanks so much MathTalk!!!

 

Actions: Add Comment

 

Frequently Asked Questions | Terms & Conditions | Disclaimer | Privacy Policy | Contact Us | Spread the word!

© 2014 Uclue Ltd