假设您有许多行（每一行由两点表示）还有一个特定大小的矩形，知道它左上角的坐标。现在，您必须确定这些线中哪些与矩形相交，对于那些确实找到由这些线在矩形内创建的区域并计算这些区域的面积的线。
最佳答案
下面是一个简单的算法，可以通过深入思考加以改进：
在矩形中使用line clipping algorithm。
Line clipping
使用Flood Fill算法获取不同的区域和区域
Flood Fill
对每个区域使用convex hull来获取区域的顶点
Graham Scan for convex hull
编辑：-
如果需要避免floodfill或坐标系不是离散的，则使用以下方法：-
按直线查找矩形内或矩形上的所有交点。
从交集构造一个图，使得每个交点都有一个无向边，如果它们都存在于矩形上的某条公共直线上。以及它们之间的距离作为边权重仅在给定直线上最近的对之间构造边这可以通过对一条线上的所有交点进行排序并在排序序列中的每个点之间添加边来完成。
使用以下命令获取所有多边形
Find_polygon(vertex u,int iter,vertex[] path) {
if(!visited[u]) {
visited[u] = true;
path[iter] = u;
if(iter==1) {
source = u;
for all edge(u,v)
Find_polygon(v,iter+1,path);
}
else {
for all edge(u,v) {
if(slope(u,v)!=slope(path[iter-1],u)) {
Find_polygon(v,iter+1,path);
}
}
}
}
else { //loop
index = findIndex(u,path); // can use array for O(1)
polygons.add(path[index to iteration])
}
}
polygons = [];
for all vertices v in graph :
Find_polygon(v);