java - 如何在多条线交叉的矩形内找到区域？

Question

假设您有许多条线(每条线由两个点表示)。您还有一个特定大小的矩形，并且知道其左上角的坐标。现在您必须确定这些线中的哪些线与矩形相交，对于所有相交的线 - 找到由线在矩形内创建的区域并计算这些区域的面积。

Answer 1

这是一个简单的算法，可以通过更深入的思考加以改进:-

在矩形中使用裁线算法。

Line clipping

使用Flood Fill算法获取不同的区域和区域

Flood Fill

对每个区域使用convex hull获取区域的顶点

Graham Scan for convex hull

编辑:-

如果需要避免 floodfill 或坐标系不是离散的，则使用以下:-

1. 通过直线找到矩形内部或矩形上的所有交点。

2. 从交点构造一个图，如果每个交点都存在于矩形中的某条公共(public)线上，则存在从每个交点到其他交点的无向边。以及它们之间的距离作为边缘权重。仅在给定线上的最近对之间构造边。这可以通过对一条线上的所有交点进行排序并在排序序列中的每个点之间添加边来完成。

3. 使用下面的方法得到所有的多边形

   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);