Cascading/iterated maximum inscribed circle

[micycle1]

In PGS, I offer a "maximum inscribed" circle packing method, which packs a polygon with the N largest non-overlapping inscribed circles, relying on JTS' MaximumInscribedCircle used in a brute-forced iterative way:

for (int i = 0; i < n; i++) {
	final MaximumInscribedCircle mic = new MaximumInscribedCircle(geometry, tolerance);
	final double d, x, y;
	x = mic.getCenter().getX();
	y = mic.getCenter().getY();
	d = mic.getRadiusLine().getLength() * 2;
	shapeFactory.setCentre(new Coordinate(x, y));
	shapeFactory.setSize(d);
	geometry = geometry.difference(shapeFactory.createEllipse());
}

This is a fairly slow method 1) because difference() is expensive and 2) because MIC has to reindex much of the same (remaining) area each time.

it looks like the JTS implementation uses grid-based indexing approach and I wonder whether the following is feasible way to optimise this operation: after the initial MIC is found on the geometry's indexed grid cells, we remove any grid cells that our MIC covers, then simply run the sub-routine that finds the MIC on the remaining grid cells, and repeat this N times.

I suspect the most involved part would be refining/sub-dividing any grid cells the previous MIC partially overlaps to get a more circular cut-out when we remove them. Cell distances would need updating too after each iteration -- could this simply be newCellDistance = min(oldCellDistance, dist(cell, newMIC.center) - newMIC.radius)?

[dr-jts]

As you point out, the need to reconcile the resolution of the grid with the circular constraint(s) feels awkward. I would try and approach of maintaining the removed circles as purely vector constraints (at full accuracy, by representing them as a center point and a radius). The cell distances can be computed based on the original input points/polygon, in combination with the removed circles.

[micycle1]

Rebuilding the whole grid every iteration with respect to the circular constraints has sped things up by ~10x compared the iterated way above.

A slightly more involved approach where each iteration starts from and refines the grid from the previous iteration would speed things up even more.

And accuracy has improved too!

[dr-jts]

Looks great!