furthest point inside polygon with orthogonal edges (convex or concave or having holes)

Question

I have a set of non-intersecting rectangles representing a single shape. All the rectangle edges are either vertical or horizontal. Some rectangles are adjacent, others are disjoint. This set was derived by clipping out similarly oriented rectangles from a single other rectangle. How do I find all the points furthest from the new shape's edges?

By furthest, I mean a point A within a given connected polygon P (so we ignore all disjoint polygons that do not contain A; given non-intersection there will only be one) such that there is no point B within P where the minimum distance from B to any point on an edge of P is greater than the same minimum distance with A.

This is what I think I'll have to do:

1. Group adjacent rectangles.

2. Convert multiple adjacent rectangles into a single irregular polygon that is either convex or concave and may contain holes, but having only orthogonal edges. Problems: how to represent holes? Should holes be removed for (3)? How to remove holes while keeping edges orthogonal?

   • Might be easier to do steps 1&2 in parallel.

3. For each polygon, apply an algorithm that returns the point furthest from the edges of that polygon, as well as the minimum distance.

   • Problem: how to test if point is within polygon?

   • Answer: "Wikipedia: Point-in-Polygon"

4. Filter all points having the greatest minimum distance; these are the result.

Assuming this is correct, what is the best algorithm to do (3), and how does it affect the rest of the answer? Is the problem simplified by only having vertical or horizontal edges?

By best, I mean either simplest or fastest.

Illustration:

Edit v1:

So I poked this problem with google to find several approaches

Algorithms

1. Voronoi Diagram -> Medial Axis

   The voronoi diagram of line segments (rather than points) is composed of medial axis segments (lines or parabola arcs), and (reflex) lines from each vertex of the polygon to a vertex of the medial axis. See this stackoverflow answer (#2) for an overview of the relationship between the voronoi diagram, the medial axis, and the maximum inscribed circle problem. Also see below.

   1. Use "A Sweepline Algorithm for Voronoi Diagrams", O[n*log(n)].

      Works with convex or concave polygons irrespective of holes. Construct the voronoi diagram for the edges of the polygon. Unfortunately produces an unorded set of segments (lines or parabolas). Organize the set into a graph structure before determining the maximum inscribed circle. See "Voronoi Diagrams and a Day at the Beach" for a good overview of fortune's algorithm.

   2. Use "Finding the Medial Axis of a Simple Polygon in Linear Time", O(n).

      Works with simple polygons (convex or concave) without holes. It appears very complicated so I decided to skip this.

   3. Use "A Linear time algorithm for computing the Voronoi diagram of a convex polygon", O(n).

      Only works for convex polygons, so not applicable to my problem. See this stackoverflow answer (#1) for more information.

2. Straight Skeleton -> Medial axis

   For convex polygons, the voronoi diagram and straight skeleton are the same. Therefore, these solutions are not applicable to my problem.

   1. Use "STALGO", O[n*log(n)]. See this stackoverflow answer (#1) for more information.

3. Brute Force, O(n^4). See this stackoverflow answer (#3) and this stackoverflow answer (#2).

   1. For all possible three-way combinations (order doesn't matter) of polygon's edges and vertices:

   2. Construct the maximum inscribed circle for each set, i.e. find the center point equidistant to all three.

   3. Discard results if the center lies outside the polygon.

   4. Discard results if any other edge or vertex is within (or intersects) the circle.

   5. Sort by circle radius; return largest circle.

4. Delaunay Triangulation -> Voronoi Diagram -> Medial Axis

   It should be possible to convert from delaunay triangulation to voronoi diagrams... but I haven't looked into this for voronoi diagrams of edges. This approach could be useful if your geometry library only provides delaunay triangulation.

Voronoi Diagram and Maximum Inscribed Circle

Every resource I've seen claims the maximum inscribed circle touches three faces (vertices or edges) of a polygon, and that therefore the center of the maximum circle must be a vertex on the medial axis. But this only represents a subset of the maximum inscribed circles. Consider the medial axis of a rectangle:

Any circle with a center along the horizontal segment of the medial axis is a valid maximum inscribed circle. Therefore, if a medial axis segment separates two nearest neighbor cells, and the corresponding polygon segments of those cells are parallel, then rather than a single point the entire medial axis edge represents the set of maximum inscribed circles.

Intuitively, I think this is how it works, given the possible combinations of polygon edges to the nearest neighbor cells:

• line, line, parallel: The medial axis is a line, which represents the set of possible maximum inscribed circles.

• line, line, not parallel: The medial axis is a line. As usual, the endpoints of this line must have at least two reflex lines connecting back to the polygon. The possible maximum inscribed circle is centered on the endpoint with the longest reflex line.

• line, point: The medial axis is a parabola. As above, use the reflex lines to determine the center of the possible maximum inscribed circle. (*)

• point, point: Same as above. (*)

  Not sure about the last two

And this is why the brute force approach detailed above is incomplete.

Orthogonal Polygons

Despite the orthogonal constraint, I was unable to find any simpler algorithms for constructing the medial axis. One paper used this constraint to provide more stable alternatives to the medial axis: "Skeletal representations of orthogonal shapes".

Edit v2:

I wonder if it is somehow possible to adapt this stackoverflow approach - based on "Poles of Inaccessibility: A Calculation Algorithm for the Remotest Places on Earth" - to my input (green) rectangles (instead of squares) while guaranteeing absolute maximum inscribed circle.