如何在被多线分割的多边形中找出面积最大的子多边形？

核心实现步骤 #

1. 完整收集所有顶点与交点

   • 先提取输入中原始多边形的所有顶点，存入顶点集合。
   • 遍历所有分割线段，计算两类交点并加入集合（需做浮点精度去重，比如判断两点距离小于极小值则视为同一点）：
     • 分割线段之间的交点（使用你提供的findIntersection方法，但要额外验证交点是否在两条线段的范围内，而非无限直线的交点）；
     • 分割线段与原始多边形边界的交点（原始多边形的边是首尾相连的线段，需逐个计算交集）。

2. 构建平面细分的有向边图

   • 将每个顶点作为图的节点。
   • 用交点将原始多边形的边、分割线段拆分为若干子线段，每条子线段作为图的有向边（按逆时针方向定义边的方向，确保后续能遍历出闭合的子多边形）。
   • 对每个顶点，将其所有相连的有向边按极角排序，保证遍历子多边形时能找到连续的边。

3. 遍历子多边形并计算面积

   • 维护已访问边的集合，避免重复遍历。
   • 从任意一条未访问的有向边出发，沿着极角排序后的下一条边依次前进，直到回到起点，形成闭合的子多边形顶点序列。
   • 用多边形面积公式计算每个子多边形的面积：

     面积 = 0.5 * |Σ(x_i * y_{i+1} - x_{i+1} * y_i)|
     

     其中序列最后一个顶点的下一个顶点是第一个顶点。
   • 记录所有子多边形的面积，最终取最大值对应的子多边形。

工具代码（你提供的实现） #

计算两点距离：

public static double calcDistanceBetweenPoints(Point a, Point b){
        return Math.sqrt((b.y - a.y) * (b.y - a.y) + (b.x - a.x) * (b.x - a.x));
}

计算直线交点（需补充线段交点的范围验证）：

public static Point findIntersection(Point A, Point B, Point C, Point D){
    // Line AB represented as a1x + b1y = c1
    double a1 = B.y - A.y;
    double b1 = A.x - B.x;
    double c1 = a1*(A.x) + b1*(A.y);
  
    // Line CD represented as a2x + b2y = c2
    double a2 = D.y - C.y;
    double b2 = C.x - D.x;
    double c2 = a2*(C.x)+ b2*(C.y);
  
    double determinant = a1*b2 - a2*b1;
  
    if (determinant == 0)
    {
        // The lines are parallel
        return new Point(Double.MAX_VALUE, Double.MAX_VALUE);
    }
    else
    {
        double x = (b2*c1 - b1*c2)/determinant;
        double y = (a1*c2 - a2*c1)/determinant;
        return new Point(x, y);
    }
}

输入格式说明 #

n m
x1 y1
...
xn yn
x11 y11 x21 y21
...
x1m y1m x2m y2m

• n：原始多边形的顶点数，m：分割线段的数量
• 接下来n行是原始多边形的顶点坐标（按顺序排列）
• 最后m行是每条分割线段的两个端点坐标

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