Largest circle inside a non-convex polygon

by

The key to solving this problem is first making an observation: the center of the largest circle that will fit inside an arbitrary polygon is the point that is:

  1. Inside the polygon; and
  2. Furthest from any point on the edges of the polygon.

Why? Because every point on the edge of a circle is equidistant from that center. By definition, the largest circle will have the largest radius and will touch the polygon on at least two points so if you find the point inside furthest from the polygon you’ve found the center of the circle.

This problem appears in geography and is solved iteratively to any arbitrary precision. Its called the Poles of Inaccessibility problem. See Poles of Inaccessibility: A Calculation Algorithm for the Remotest Places on Earth.

The basic algorithm works like this:

  1. Define R as a rectilinear region from (xmin,ymin) to (xmax,ymax);
  2. Divide R into an arbitrary number of points. The paper uses 21 as a heuristic (meaning divide the height and width by 20);
  3. Clip any points that are outside the polygon;
  4. For the remainder find the point that is furthest from any point on the edge;
  5. From that point define a new R with smaller intervals and bounds and repeat from step 2 to get to any arbitrary precision answer. The paper reduces R by a factor of the square root of 2.

One note, How to test if a point is inside the polygon or not: The simplest solution to this part of the problem is to cast a ray to the right of the point. If it crosses an odd number of edges, it’s within the polygon. If it’s an even number, it’s outside.

Also, as far as testing the distance to any edge there are two cases you need to consider:

  1. The point is perpendicular to a point on that edge (within the bounds of the two vertices); or
  2. It isn’t.

(2) is easy. The distance to the edge is the minimum of the distances to the two vertices. For (1), the closest point on that edge will be the point that intersects the edge at a 90 degree angle starting from the point you’re testing. See Distance of a Point to a Ray or Segment.

More Related Contents:

  1. An algorithm for inflating/deflating (offsetting, buffering) polygons
  2. How do I efficiently determine if a polygon is convex, non-convex or complex?
  3. How can I create an internal spiral for a polygon?
  4. Sort points in clockwise order?
  5. What is the fastest algorithm to calculate the minimum distance between two sets of points?
  6. How to check if line segment intersects a rectangle?
  7. Polygon enclosing a set of points
  8. What is the most efficient algorithm to find a straight line that goes through most points?
  9. Find if a point is inside a convex hull for a set of points without computing the hull itself
  10. Compute the area of intersection between a circle and a triangle?
  11. Location of highest density on a sphere
  12. Circle line-segment collision detection algorithm?
  13. Algorithm for finding the fewest rectangles to cover a set of rectangles without overlapping
  14. How do I calculate the area of a 2d polygon?
  15. Algorithm to detect intersection of two rectangles?
  16. Simple calculations for working with lat/lon and km distance?
  17. Finding whether a point lies inside a rectangle or not
  18. How do you calculate the average of a set of circular data? [closed]
  19. What is an Efficient algorithm to find Area of Overlapping Rectangles
  20. How to Compute OBB of Multiple Curves?
  21. Puzzle: Find largest rectangle (maximal rectangle problem)
  22. robust algorithm for surface reconstruction from 3D point cloud?
  23. Calculate largest inscribed rectangle in a rotated rectangle
  24. Shortest distance between points algorithm
  25. Sort Four Points in Clockwise Order
  26. Create non-intersecting polygon passing through all given points
  27. Circular approximation of polygon (or its part)
  28. How do you find a point at a given perpendicular distance from a line?
  29. Random points inside a parallelogram
  30. Distance from a point to a polygon

Leave a Comment