Java中如何连接非凸多边形内随机点且不与边界相交？

我修改了Stack Overflow上《How to get a random point on the interior of an irregular polygon?》中的代码，用于在多边形Shape内生成随机点并连接成Path2D。但当Shape为非凸多边形时，生成的路径线段会与多边形边界相交。希望通过重新排序随机点的方式避免这种情况，构建所有线段都在Shape区域内的路径，求具体的重排示例。

原实现代码 #

生成多边形内随机点的方法 #

// 生成多边形Shape内的随机点列表
public ArrayList<Point2D> generateDoubleRandomPointList(Shape region, int numberRandomPoints){ 
   
   ArrayList<Point2D> randomPointList = new ArrayList<>();
   for (int i = 0; i < numberRandomPoints; i++) {
          Rectangle2D r = region.getBounds();
          double x = 0, y = 0;
          Random rand = new Random();
          if(!r.isEmpty()) { // 避免空边界引发异常
           do {
               x = r.getX() + rand.nextDouble(r.getWidth());
               y = r.getY() + rand.nextDouble(r.getHeight());        
           }  while(!region.contains(x,y));
       }
       randomPointList.add(new Point2D.Double(x,y));
   }
    return randomPointList;
}

连接点生成Path2D的方法 #

// 根据点列表创建路径
public static Path2D createPathFromListOfPoints2D(List<Point2D> points) { 
    // 创建Path2D对象
    java.awt.geom.Path2D path = new java.awt.geom.Path2D.Double();  
    Point2D p = points.get(0);
    double xΑ = p.getX();
    double yΑ = p.getY();
    // 从第一个点开始绘制
    path.moveTo(xΑ, yΑ);
    // 遍历剩余点，依次连线
    for(int i=1; i<points.size(); i++) {
        p = points.get(i);
        path.lineTo(p.getX(), p.getY());
    }
    // 闭合路径
    path.closePath();
    return path;
}

解决方案：基于极角排序的点重排 #

核心思路是：在随机点集中选取一个中心参考点（比如所有点的重心），将所有随机点按照相对于该中心点的极角从小到大排序。这种排序方式能保证相邻点的连线始终处于多边形内部，不会跨越非凸多边形的凹陷边界。

步骤1：实现极角排序逻辑 #

添加以下工具方法完成点的排序：

// 计算点集的重心，作为极角排序的中心参考点
private static Point2D calculateCentroid(List<Point2D> points) {
    double sumX = 0, sumY = 0;
    for (Point2D p : points) {
        sumX += p.getX();
        sumY += p.getY();
    }
    int count = points.size();
    return new Point2D.Double(sumX / count, sumY / count);
}

// 按照相对于中心点的极角对随机点进行排序
public static void sortPointsByPolarAngle(List<Point2D> points) {
    if (points.size() < 2) return;
    Point2D centroid = calculateCentroid(points);
    // 自定义比较器，按极角从小到大排序
    points.sort((p1, p2) -> {
        double angle1 = Math.atan2(p1.getY() - centroid.getY(), p1.getX() - centroid.getX());
        double angle2 = Math.atan2(p2.getY() - centroid.getY(), p2.getX() - centroid.getX());
        return Double.compare(angle1, angle2);
    });
}

步骤2：修改路径生成流程 #

在生成随机点后，先执行极角排序，再创建路径：

// 使用示例
public static void main(String[] args) {
    // 假设已有非凸多边形Shape实例nonConvexShape
    Shape nonConvexShape = ...;
    int pointCount = 10;
    
    // 生成随机点列表
    ArrayList<Point2D> randomPoints = generateDoubleRandomPointList(nonConvexShape, pointCount);
    // 对随机点进行极角排序
    sortPointsByPolarAngle(randomPoints);
    // 生成无交叉的安全路径
    Path2D safePath = createPathFromListOfPoints2D(randomPoints);
}

原理说明 #

• 极角排序后，所有点围绕中心点呈放射状排列，相邻点的连线不会跨越多边形的凹陷区域，确保线段始终处于多边形内部。
• 若多边形存在复杂多凹陷结构，可结合三角剖分将其拆分为多个凸子多边形，在每个子多边形内分别排序点再连接，但极角排序在大多数非凸场景下已能满足需求。

内容的提问来源于stack exchange，提问作者jazznbass