0
$\begingroup$

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?

  • 0
    If you $n$eed a general practical solution, you may consider this library: https://github.com/bjornharrtell/jsts which allows you to calculate the overlap/intersection between arbitrary polygons.2014-07-16

2 Answers 2

1

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.

  • 0
    Oh, wow, that sounds like a much better question to ask.2012-01-14
1

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.

  • 0
    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).2012-01-13