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

Priced at $50.00

The customer tipped the researcher $40.00

**Actions: **
Add Comment

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!!

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

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

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

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

"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

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.

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

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

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.

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

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

> although from Lua's manual I was under the impression comments

> start with double hyphens

You're exactly right, they do.

-- 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

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

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

-- 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

**Actions: **
Add Comment

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

Fri 23 Jun 2017 - 7:02 pm UTC - © 2017 Uclue Ltd

myoarin

User

14 Feb 2011 23:32 UTCMon 14 Feb 2011 - 11:32 pm UTC

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