c++ - 是否有一种算法可以通过多组平行线段构建矩形

Question

我试图找到一个算法来通过多组平行线构建所有矩形。给出了所有线的方程式。举个例子说明一下，两组平行线相互垂直:((a)组中的红线平行，(b)组中的绿线也平行。)

矩形应受制于一个约束，即其边的最小长度必须大于 d_min，见图。并且矩形可以相互重叠。

Line equation: y = kx + b
struct sLine 
{
  float k;
  float b;
}
// Input
vetor<sLine> vecLineGroupA;
vetor<sLine> vecLineGroupA;

// Output
struct sRectangle
{
  // 4 edges of a rectangle
  sLine  Line1;
  sLine  Line2;
  sLine  Line3;
  sLine  Line4;
}

是否有解决这个问题的算法，或者有人对此有想法？

Answer 1

假设你有这样的东西:

// line: y = ax + b;
struct line {double a; double b;};

vector<line> groupA = {....};     
vector<line> groupB = {.....};

你需要像这样的伪代码:

sort_with_smallest_b_first(groupA);
sort_with_smallest_b_first(groupB);

for (int n1=0; n1 < groupA.size()-1; ++n1)
{
   for (int n2=n1+1; n2 < groupA.size(); ++n2)
   {
       for (int j1=0; j1 < groupB.size()-1; ++j1)
       { 
           for (int j2=j1+1; j2 < groupB.size(); ++j2)
           { 
               // Now you have the recatangle between the lines
               // groupA[n1], groupA[n2]
               // groupB[j1], groupB[j2]
               double d1 = distance(groupA[n1], groupA[n2]);
               double d2 = distance(groupB[j1], groupB[j2]);
               if (d1 >= dmin && d2 >= dmin)
               {
                   // Add rectangle to output
               }
           }
       }
   }
}

要计算线之间的距离，请参阅:https://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line

如果性能是一个问题，您可以通过首先计算所有非重叠矩形然后从非重叠矩形组中创建重叠矩形来提高性能。它将为您节省一些距离计算，即当您简单地添加与非重叠矩形的距离而不是总是使用“复杂”公式重新计算时。