compute method
void
compute()
Implementation
void compute() {
initBoundary();
// if boundaryPtLocater is not present then result is degenerate (represented as zero-radius circle)
// if (boundaryPtLocater == null) {
// Coordinate? pt = obstacles.getCoordinate();
// centerPt = pt!.copy();
// centerPoint = factory.createPoint(pt);
// radiusPt = pt.copy();
// radiusPoint = factory.createPoint(pt);
// return;
// }
// Priority queue of cells, ordered by decreasing distance from constraints
PriorityQueue cellQueue = PriorityQueue();
//-- grid covers extent of obstacles and boundary (if any)
createInitialGrid(gridEnv, cellQueue);
// use the area centroid as the initial candidate center point
farthestCell = createCentroidCell(obstacles);
//int totalCells = cellQueue.size();
/**
* Carry out the branch-and-bound search
* of the cell space
*/
int maxIter = MaximumInscribedCircle.computeMaximumIterations(bounds, tolerance);
int iter = 0;
while (! cellQueue.isEmpty() && iter < maxIter) {
iter++;
// pick the cell with greatest distance from the queue
CellLEC cell = cellQueue.poll() as CellLEC;
//System.out.println(iter + "] Dist: " + cell.getDistance() + " Max D: " + cell.getMaxDistance() + " size: " + cell.getHSide());
// update the center cell if the candidate is further from the constraints
if (cell.getDistance() > farthestCell.getDistance()) {
farthestCell = cell;
}
/**
* If this cell may contain a better approximation to the center
* of the empty circle, then refine it (partition into subcells
* which are added into the queue for further processing).
* Otherwise the cell is pruned (not investigated further),
* since no point in it can be further than the current farthest distance.
*/
if (mayContainCircleCenter(cell)) {
// split the cell into four sub-cells
double h2 = cell.getHSide() / 2;
cellQueue.add( createCell( cell.getX() - h2, cell.getY() - h2, h2));
cellQueue.add( createCell( cell.getX() + h2, cell.getY() - h2, h2));
cellQueue.add( createCell( cell.getX() - h2, cell.getY() + h2, h2));
cellQueue.add( createCell( cell.getX() + h2, cell.getY() + h2, h2));
//totalCells += 4;
}
}
// the farthest cell is the best approximation to the LEC center
centerCell = farthestCell;
// compute center point
centerPt = new Coordinate(centerCell.getX(), centerCell.getY());
centerPoint = factory.createPoint(centerPt);
// compute radius point
List<Coordinate?>? nearestPts = obstacleDistance.nearestPoints(centerPoint);
if(nearestPts != null) {
radiusPt = nearestPts[0]!.copy();
radiusPoint = factory.createPoint(radiusPt);
}
}