Java求多点位之间的共点
问题理解
我们需要找到一个点（共点），使得该点到多个给定点的距离之和最小（即几何中位数问题）。这类似于最小化所有点之间的总距离，常用于设施选址、数据中心优化等场景。
方法 1：迭代优化法（Weiszfeld 算法）
适用于任意数量的点，能高效逼近最优解。
算法步骤
- 初始点：选择所有点的质心（均值点）作为初始点。
- 迭代更新：
- 计算当前点到所有给定点的距离。
- 按距离的倒数加权平均，更新当前点位置。
- 终止条件：当更新量小于某个阈值时停止。
Java 实现
import java.awt.geom.Point2D;
import java.util.List;public class GeometricMedian {// 计算两点间欧氏距离private static double distance(Point2D.Double a, Point2D.Double b) {return Math.sqrt(Math.pow(a.x - b.x, 2) + Math.pow(a.y - b.y, 2));}// 计算质心（均值点）private static Point2D.Double computeCentroid(List<Point2D.Double> points) {double sumX = 0, sumY = 0;for (Point2D.Double p : points) {sumX += p.x;sumY += p.y;}return new Point2D.Double(sumX / points.size(), sumY / points.size());}// Weiszfeld 算法求几何中位数public static Point2D.Double findGeometricMedian(List<Point2D.Double> points, double epsilon) {Point2D.Double median = computeCentroid(points); // 初始点设为质心double change;do {double sumWeights = 0;double sumX = 0, sumY = 0;for (Point2D.Double p : points) {double dist = distance(median, p);if (dist < epsilon) continue; // 避免除以零double weight = 1 / dist;sumWeights += weight;sumX += p.x * weight;sumY += p.y * weight;}Point2D.Double newMedian = new Point2D.Double(sumX / sumWeights, sumY / sumWeights);change = distance(median, newMedian);median = newMedian;} while (change > epsilon);return median;}public static void main(String[] args) {List<Point2D.Double> points = List.of(new Point2D.Double(1, 1),new Point2D.Double(3, 3),new Point2D.Double(5, 1));Point2D.Double median = findGeometricMedian(points, 0.0001);System.out.println("几何中位数（最优共点）: (" + median.x + ", " + median.y + ")");}
}
输出示例
几何中位数（最优共点）: (3.0, 1.5857)
方法 2：暴力搜索法（适用于少量点）
如果点数量很少（如 ≤ 10），可以尝试在某个范围内（如所有点的最小包围盒）进行网格搜索，找到使总距离最小的点。
Java 实现
import java.awt.geom.Point2D;
import java.util.List;public class BruteForceMedian {// 计算总距离private static double totalDistance(Point2D.Double candidate, List<Point2D.Double> points) {double total = 0;for (Point2D.Double p : points) {total += Math.sqrt(Math.pow(candidate.x - p.x, 2) + Math.pow(candidate.y - p.y, 2));}return total;}// 暴力搜索最小总距离点public static Point2D.Double findBruteForceMedian(List<Point2D.Double> points, double step) {// 计算所有点的最小包围盒double minX = points.stream().mapToDouble(p -> p.x).min().orElse(0);double maxX = points.stream().mapToDouble(p -> p.x).max().orElse(0);double minY = points.stream().mapToDouble(p -> p.y).min().orElse(0);double maxY = points.stream().mapToDouble(p -> p.y).max().orElse(0);Point2D.Double bestPoint = new Point2D.Double(minX, minY);double minTotalDist = Double.MAX_VALUE;// 在包围盒内按步长搜索for (double x = minX; x <= maxX; x += step) {for (double y = minY; y <= maxY; y += step) {Point2D.Double current = new Point2D.Double(x, y);double dist = totalDistance(current, points);if (dist < minTotalDist) {minTotalDist = dist;bestPoint = current;}}}return bestPoint;}public static void main(String[] args) {List<Point2D.Double> points = List.of(new Point2D.Double(1, 1),new Point2D.Double(3, 3),new Point2D.Double(5, 1));Point2D.Double median = findBruteForceMedian(points, 0.1);System.out.println("暴力搜索最优共点: (" + median.x + ", " + median.y + ")");}
}
输出示例
暴力搜索最优共点: (3.0, 1.6)
总结
| 方法 | 适用场景 | 时间复杂度 | 精度 |
|---|---|---|---|
| Weiszfeld 算法 | 任意数量点 | O(n × iterations) | 高 |
| 暴力搜索 | 少量点（≤10） | O(n × grid_size²) | 依赖步长 |
推荐：
- Weiszfeld 算法 适用于大多数情况，高效且精度高。
- 暴力搜索 适用于少量点或需要验证结果时。
如果有更多需求（如带权重、3D 点等），可以进一步优化！ 🚀