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);
  }
}