如何计算覆盖指定圆形地图区域的最小重叠子区域中心经纬度？

Hey there, let's solve this problem of dividing a circular map region into overlapping sub-circles (with minimal overlap) while ensuring full coverage. The most efficient layout for this is a hexagonal grid—it's the tightest arrangement of circles, which minimizes unnecessary overlap. Below is the complete Java implementation, including the missing divideArea method and helper functions for coordinate calculations.

import java.util.ArrayList;
import java.util.List;

public class Main {
    private static final double EARTH_RADIUS_METERS = 6378137.0; // WGS84 equatorial radius

    public static void main(String[] args) {
        // ==== Parameters =====
        /* These are just example values; Should work with any sensible input */
        LatLng outerAreaCenter = new LatLng(40.689259, -74.044538);
        double outerAreaRadiusInMeters = 1000;
        double divisionsRadiusInMeters = 125;
        // ==== Divide area =====
        List<LatLng> divisionCenters;
        divisionCenters = divideArea(outerAreaCenter, outerAreaRadiusInMeters, divisionsRadiusInMeters);
        // ==== Draw large area =====
        drawCircleOnMap(outerAreaCenter, outerAreaRadiusInMeters);
        // ==== Draw division circles within large area =====
        /* These circles should cover the entire surface of the outer area, and
         * may extend a little bit outside of the outer circle if needed */
        for (LatLng divisionCenter : divisionCenters) {
            drawCircleOnMap(divisionCenter, divisionsRadiusInMeters);
        }
    }

    /**
     * Divides a large area into divisions/smaller areas that, together, cover the entire surface of the large area with minimal overlap.
     *
     * @param outerAreaCenter the center coordinates of the area that needs to be divided
     * @param outerAreaRadiusInMeter the radius of the area that needs to be divided
     * @param divisionsRadiusInMeter the maximum radius of each division/smaller area
     *
     * @return a list of center coordinates for each of the smaller areas that, which can be used with {@param divisionsRadiusInMeter} to make new areas that together cover the entire large area surface
     */
    private static List<LatLng> divideArea(LatLng outerAreaCenter, double outerAreaRadiusInMeter, double divisionsRadiusInMeter) {
        // ==== Check preconditions =====
        if (divisionsRadiusInMeter <= 0 || outerAreaRadiusInMeter <= 0) {
            throw new IllegalArgumentException("Radii must be positive values.");
        }
        if (divisionsRadiusInMeter > outerAreaRadiusInMeter) {
            throw new IllegalArgumentException("Divisions radius cannot be larger than radius of outer area.");
        }

        List<LatLng> divisionCenters = new ArrayList<>();

        // Calculate spacing between sub-circle centers for hexagonal grid (minimizes overlap)
        double centerSpacingLat = metersToLatitudeOffset(divisionsRadiusInMeter * Math.sqrt(3));
        double centerSpacingLonHalf = metersToLongitudeOffset(divisionsRadiusInMeter * 1.5, outerAreaCenter.latitude);
        double centerSpacingLonFull = centerSpacingLonHalf * 2;

        // Calculate how far we need to extend the grid to fully cover the outer circle (including edges)
        double maxLatOffset = metersToLatitudeOffset(outerAreaRadiusInMeter + divisionsRadiusInMeter);
        double maxLonOffset = metersToLongitudeOffset(outerAreaRadiusInMeter + divisionsRadiusInMeter, outerAreaCenter.latitude);

        int numRows = (int) Math.ceil(maxLatOffset * 2 / centerSpacingLat) + 1;
        int numCols = (int) Math.ceil(maxLonOffset * 2 / centerSpacingLonFull) + 1;

        // Generate all candidate sub-circle centers in hexagonal grid pattern
        for (int row = 0; row < numRows; row++) {
            double currentLat = outerAreaCenter.latitude - maxLatOffset + row * centerSpacingLat;

            // Offset every other row by half a column to form the hexagonal layout
            double lonStartOffset = (row % 2 == 1) ? centerSpacingLonHalf : 0;
            double currentLon = outerAreaCenter.longitude - maxLonOffset + lonStartOffset;

            for (int col = 0; col < numCols; col++) {
                LatLng candidateCenter = new LatLng(currentLat, currentLon);

                // Only keep centers that can contribute to covering the outer area
                double distanceToOuterCenter = calculateDistance(candidateCenter, outerAreaCenter);
                if (distanceToOuterCenter <= outerAreaRadiusInMeter + divisionsRadiusInMeter) {
                    divisionCenters.add(candidateCenter);
                }

                currentLon += centerSpacingLonFull;
            }
        }

        return divisionCenters;
    }

    /**
     * Converts a distance in meters to a latitude offset (degrees)
     */
    private static double metersToLatitudeOffset(double meters) {
        return Math.toDegrees(meters / EARTH_RADIUS_METERS);
    }

    /**
     * Converts a distance in meters to a longitude offset (degrees) at a given latitude
     */
    private static double metersToLongitudeOffset(double meters, double latitude) {
        double latRad = Math.toRadians(latitude);
        return Math.toDegrees(meters / (EARTH_RADIUS_METERS * Math.cos(latRad)));
    }

    /**
     * Calculates the distance (in meters) between two LatLng points using the Haversine formula
     */
    private static double calculateDistance(LatLng point1, LatLng point2) {
        double lat1Rad = Math.toRadians(point1.latitude);
        double lon1Rad = Math.toRadians(point1.longitude);
        double lat2Rad = Math.toRadians(point2.latitude);
        double lon2Rad = Math.toRadians(point2.longitude);

        double deltaLat = lat2Rad - lat1Rad;
        double deltaLon = lon2Rad - lon1Rad;

        double a = Math.sin(deltaLat / 2) * Math.sin(deltaLat / 2)
                + Math.cos(lat1Rad) * Math.cos(lat2Rad)
                * Math.sin(deltaLon / 2) * Math.sin(deltaLon / 2);
        double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));

        return EARTH_RADIUS_METERS * c;
    }

    private static void drawCircleOnMap(LatLng circleCenter, double radiusInMeters) {
        /* Some code to draw this circle on a map (not relevant to the question) */
        // To visualize points, add a new layer on https://mapmakerapp.com by pasting the console output
        System.out.println(circleCenter.latitude + "," + circleCenter.longitude + ",,#FF0000");
    }

    private static class LatLng {
        private final double latitude;
        private final double longitude;

        private LatLng(double latitude, double longitude) {
            this.latitude = latitude;
            this.longitude = longitude;
        }
    }
}

Key Details Explained: #

• Hexagonal Grid Layout: This pattern ensures minimal overlap between adjacent sub-circles. Adjacent centers are spaced divisionsRadiusInMeter * sqrt(3) apart latitudinally, and every other row is offset by half a longitudinal spacing to form the hexagonal shape.
• Coordinate Conversion Helpers: These functions account for the Earth's curved surface—longitude offsets vary with latitude, while latitude offsets are consistent globally.
• Full Coverage Guarantee: We extend the grid slightly beyond the outer circle's radius to ensure no edge areas are left uncovered. Any candidate centers that can't contribute to covering the original area are filtered out.
• Precondition Checks: Added extra validation to ensure input values are sensible (positive radii, sub-circle radius not larger than outer radius).

内容的提问来源于stack exchange，提问作者Rolf W.