Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a computer program wherein I'd like to determine when two given shapes of equivalent size and orientation are intersecting.

For example: For a given pair of squares, both of side length X, - are the areas of the squares guaranteed to intersect when the distance between the two squares is less than or equal to X?

Distance in this case, being defined as the absolute length between two complementary points making up the two polygons. I.e., the distance between their two centers. Or, in the case of the square, it could be the top left corner point of each of them. (Absolute distance should be the same, since the point in question is simply a transformation from the center point).

Does this hold true for all polygons?

What about circles?

share|improve this question
    
It depends what you mean by "the distance between", and whether you are talking about the distance between centrally symmetric convex shapes, and whether your congruences are allowed to change orientation. –  Mark Bennet Jan 13 '12 at 20:47
    
And whether you are talking about the distance between centres (as seems likely) - the distance between regions is normally thought of as the distance between boundaries. –  Mark Bennet Jan 13 '12 at 20:56
    
search of 'collision detection' may help : (content.gpwiki.org/index.php/Polygon_Collision) –  Raymond Manzoni Jan 13 '12 at 22:08
    
Regular polygons, equivalent orientation. Updating OP to reflect. –  Raven Dreamer Jan 13 '12 at 22:21
    
If you need a general practical solution, you may consider this library: github.com/bjornharrtell/jsts which allows you to calculate the overlap/intersection between arbitrary polygons. –  Erel Segal Halevi Jul 16 at 13:22

2 Answers 2

up vote 1 down vote accepted

Presumably you define a "center" for the polygon to measure this distance. For a square, the center is easy to define and yes, they must intersect if the distance between the centers is less than the side. The easiest way to see it is because a square of side X includes a circle of diameter X and two circles must intersect if the centers are less than a diameter apart.

This gives a hint to the solution. An equilateral triangle does not cover a circle as large as its side. So you can have one triangle $(-1,0), (1,0), (0,\sqrt{3})$ with center $(0,\frac{\sqrt 3}3)$ and side $2$ and another $(-1,2), (1,2), (0,2+\sqrt 3)$ that do not intersect.

If you allow irregular polygons you need to think about what you mean by center and which side to consider. If you allow them not to be oriented the same, think about two pentagrams, one with a point between the points of the other.

share|improve this answer
    
If we assume that both shapes have the same orientation, can we "effectively" treat them like circles? (And say they intersect for all distance < 2r ? ) –  Raven Dreamer Jan 13 '12 at 22:28
    
(Assuming Regular Polygons) –  Raven Dreamer Jan 13 '12 at 22:40
    
@RavenDreamer: You need to define the diameter. Yes, for a given shape in matching orientation you can define a distance that will force an intersection. For side $2$ equilateral triangles, it is $2-\frac{\sqrt 3}3$. –  Ross Millikan Jan 13 '12 at 22:50
    
Oh, wow, that sounds like a much better question to ask. –  Raven Dreamer Jan 14 '12 at 0:42

Two circles of the same size will always intersect if the distance $d$ between their centers is $\leq 2r$, where $r$ is the radius of the circles. They will intersect at a single tangent point in the $d = 2r$ case, at two distinct points in the $0 \neq d < 2r$ case, and at every point in the $d = 0$ case.

For polygons: in your program, are they always regular? If not, are they always convex?

Also, how exactly are you defining distance? It seems that you mean the shortest line that connects two points of the shape. In that case, there is no guarantee that they will intersect. It will always be possible to bring the polygons arbitrarily close to each other before they intersect, so the "distance" between them gives no information about intersection.

Perhaps you mean the distance between their "origins"? A useful definition for "origin" here might be the center of the smallest circle that encloses every point of the polygon.

share|improve this answer
    
I've updated the OP. We can assume regular Polygons, and a common orientation (exact orientation should be irrelevant as long as both have the same, I think). –  Raven Dreamer Jan 13 '12 at 22:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.