[Math] How to detect if a circle overlaps with a polygon or not

algorithmscollision detectionpolygons

I have a polygon on earth described by a set of latitude and longitude points. I have following list of points that construct my polygon:

(lat1 , long1)
(lat2 , long2)
...
(latn , longn)

And I have a circle on earth that described by a center and radius(meters).My circle determined by following latitude and longitude and radius :

center = (latc , longc)
radius = r

I want an algorithm to find whether the circle overlaps with the polygon? There exist three states.

  1. The circle is completely outside the polygon
  2. The circle is completely inside the polygon
  3. The circle overlaps with the polygon

I want to detect states 2 , 3 that the circle is inside or overlaps with the polygon.Anyone has idea that solve this problem? I want an algorithms that gets polygon vertex points and circle parameters(center and radius) and outputs a boolean that if the circle overlaps with polygon or not.

Update:

I assume the polygon defined on a small area on earth such as a house or club . and circle is output of android location service . center of circle is output latitude and longitude and radius of circle is upper bound error of location service.I assume my area covering polygon and circle is flat and not forming a part of sphere and keep problem simple!

Best Answer

As long as the polygon is reasonably small (under, say, a few hundred miles at typical latitudes) and not near a pole, we can simplify to the euclidean case. Then it is possible to use the Separating Axis Theorem to solve the problem.

Convert to distances

First things first, since our radius is in a distance measure (meters maybe?), We need to convert our lat/long coordinates into distance-type values as well.

This can get quite distorted far from our chosen meridian, so we will first subtract our center's longitude from the longitude of each of our polygon's vertices. Then to make the numbers less terrible we'll move the whole thing so our center is at $(0,0)$ in our euclidean space:

$$(x,y)=(\cos(\phi)(\theta-\theta_C), \phi-\phi_C)\cdot R$$

Where $(x,y)$ are the euclidean coordinates, $\theta$ is the longitude, $\phi$ is the latitude, $?_C$ denotes that this value comes from the center, and $R$ is the radius of the Earth in the same units as the uncertainty radius. Note: all angles are assumed to be radians; you may need to convert to get there.

Convexity

Next, because SAT requires convex polygons, we'll need to make sure we only give it convex polygons. The typical way of going about this is to use triangulation. There's lots of algorithms for that.

While you're doing this, you want to maintain the same winding for all your polygons - if one polygon has its vertices listed in clockwise order, so too must all other polygons, and vice versa. To maintain winding while breaking a polygon along an internal edge, the two new vertex lists should keep their order and simply remove the vertices that are exclusive to the other polygon: splitting $ABCDEFG$ along $CF$ should give $ABCFG$ and $CDEF$. Note that this makes one polygon have $CF$ as an edge and the other have $FC$; this is intentional.

Lines and Separation

Finally, given our convex polygons, we will generate lines that enclose each polygon; a point that's inside the polygon will be on the same side of every enclosing line. To make the results as convenient as possible, our goal should be Hesse Normal Form for the lines; this form gives, conveniently, the distance of the line from the origin with little hassle.

Given two points $A$ and $B$, a line through them can be expressed as: $$\vec n =\frac{\perp(A-B)}{|A-B|}$$ $$\vec n \cdot x = \vec n \cdot A$$ where $\perp (x,y) = (y,-x)$, a perpendicular vector.

This constant on the right is the distance between the line and the origin; this is convenient because we moved our center to the origin! The only thing left to consider is the radius.

If every line constant for a given polygon is less than the uncertainty radius, (or, depending on winding, more than the negative of the uncertainty radius), then the circle may intersect with that polygon. If even one exceeds that, then they do not intersect.

May

There is however one situation where all the lines say our circle is partly inside but we're not: these lines define a somewhat bigger polygon, but the envelope of locations where the circle and polygon collide is a rounded polygon. We need to figure out when that happens.

It only happens when the center is outside the polygon - when the highest (winding: lowest) line constant is positive (winding: negative). In addition, the center must be closer to a vertex than to a segment. That will happen if, with regards to the line with the highest constant, either $\angle ABC$ or $\angle BAC$ are obtuse, that is, if $(A-B)\cdot(C-B) < 0$ or $(B-A)\cdot(C-A) < 0$. Whichever one is true, we must check the distance between the center and the point; if it's greater than the radius then the circle and polygon don't collide.

In Summary

  1. Convert the polygon into Euclidean coordinates.
  2. Break the polygon into convex components.
  3. Turn each convex polygon into a set of lines.
  4. Test each convex polygon for collision.

If any convex polygon collides with the circle, then the circle and overall polygon collide.

Related Question