optimalPointInside method

List<double> optimalPointInside({ double resolution = 2.0, })

Calculates the optimal point within a complex polygon using a custom grid-based search algorithm.

This method determines an ideal point for label placement within a polygon to ensure maximum visibility and minimal obstruction by the polygon's edges. It employs a grid-based search algorithm developed specifically for this package, which involves creating a grid over the polygon and evaluating potential points based on their distance to the nearest edge.

The complex polygon can include holes, and the point will not be placed inside any of these holes.

resolution allows you to adjust the granularity of the grid search for the optimal point. A higher resolution increases the computation time but may result in a more precise location.

Returns a List<double> representing the optimal point's longitude and latitude coordinates.

While this method is based on a grid search, it is a unique implementation designed for the specific needs of geospatial analysis within this package and may not directly correspond to any single established grid-based search algorithm in the literature.

Implementation

List<double> optimalPointInside({double resolution = 2.0}) {
  // Calculate the distance between two points in WebMercator coordinates
  double distance(List<double> point1, List<double> point2) {
    return sqrt(
        pow(point1[0] - point2[0], 2) + pow(point1[1] - point2[1], 2));
  }

  /// Calculates the perpendicular distance from a point to a line segment.
  ///
  /// This method finds the closest point on the line segment to the given point and calculates the
  /// distance between these two points in WebMercator coordinates.
  ///
  /// [point] is the point from which the distance is measured.
  /// [lineStart] and [lineEnd] define the line segment's endpoints.
  ///
  /// Returns the perpendicular distance as a double.
  double perpendicularDistance(
      List<double> point, List<double> lineStart, List<double> lineEnd) {
    double dx = lineEnd[0] - lineStart[0];
    double dy = lineEnd[1] - lineStart[1];
    if (dx == 0 && dy == 0) {
      return distance(point, lineStart);
    }
    double t =
        ((point[0] - lineStart[0]) * dx + (point[1] - lineStart[1]) * dy) /
            (dx * dx + dy * dy);
    t = max(0, min(1, t));
    double nearestPointX = lineStart[0] + t * dx;
    double nearestPointY = lineStart[1] + t * dy;
    return distance(point, [nearestPointX, nearestPointY]);
  }

  var coords = <List<List<double>>>[];
  for (final ring in coordinates) {
    final transformedRing = <List<double>>[];

    for (final point in ring) {
      final List<double> transformedPoint =
          convertToWebMercator(point[0], point[1]);
      transformedRing.add(transformedPoint);
    }

    coords.add(transformedRing);
  }

  List<double> labelPoint = [];
  double maxDistance = 0.0;

  // Determine the boundary of the rectangle that covers the outer polygon
  double minX = coords[0].reduce((a, b) => [min(a[0], b[0]), a[1]])[0];
  double maxX = coords[0].reduce((a, b) => [max(a[0], b[0]), a[1]])[0];
  double minY = coords[0].reduce((a, b) => [a[0], min(a[1], b[1])])[1];
  double maxY = coords[0].reduce((a, b) => [a[0], max(a[1], b[1])])[1];

  // Calculate grid size
  int gridSize = (sqrt(coordinates[0].length) * resolution).ceil();
  double deltaX = (maxX - minX) / gridSize;
  double deltaY = (maxY - minY) / gridSize;

  // Browse through the point grid
  for (int i = 0; i <= gridSize; i++) {
    for (int j = 0; j <= gridSize; j++) {
      List<double> gridPoint = [minX + i * deltaX, minY + j * deltaY];
      var gridPointLonLat =
          convertFromWebMercator(gridPoint.first, gridPoint.last);
      if (isPointInsideComplex(gridPointLonLat)) {
        double minDistance = double.infinity;
        // Calculate the distance from the point to each edge of the outer polygon and the holes
        for (var polygon in coords) {
          for (int k = 0; k < polygon.length; k++) {
            List<double> currentVertex = polygon[k];
            List<double> nextVertex = polygon[(k + 1) % polygon.length];
            double distance =
                perpendicularDistance(gridPoint, currentVertex, nextVertex);
            if (distance < minDistance) {
              minDistance = distance;
            }
          }
        }
        if (minDistance > maxDistance) {
          maxDistance = minDistance;
          labelPoint = gridPoint;
        }
      }
    }
  }

  return convertFromWebMercator(labelPoint.first, labelPoint.last);
}