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
    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.2012-01-13
  • 0
    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.2012-01-13
  • 0
    search of 'collision detection' may help : (http://content.gpwiki.org/index.php/Polygon_Collision)2012-01-13
  • 0
    Regular polygons, equivalent orientation. Updating OP to reflect.2012-01-13
  • 0
    If you need 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
    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 ? )2012-01-13
  • 0
    (Assuming Regular Polygons)2012-01-13
  • 0
    @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$.2012-01-13
  • 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