CODEWITHSUNDEEP
c++algorithmgraph-algorithm
rayallen
rayallen

Reputation: 213

Is there an algorithm to build rectangles by groups of paralle line segments

I try to find an algo to build all the rectangles by groups of paralle lines. The equations for all the lines are given. Here is an example to explain the situation, which shows two groups of parallel lines and they are perpendicular to each other: (the red lines in group(a) are parallel and the green lines in group(b) are also parallel.)

enter image description here

The rectangle should be subject to one constrant, that the minimal length of its edge must be bigger than the d_min, see figure. And the rectangles can overlap to each other.

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

Is there an algo to solve this Problem, or anyone has an idea for that?

Upvotes: 0

Views: 165

Answers (1)

4386427
4386427

Reputation: 44368

Assume you have something like:

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

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

you'll need some thing like this pseudo code:

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
               }
           }
       }
   }
}

For calculating distance between lines see: https://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line

If performance is an issue you can improve performance by first calculating all non-overlapping rectangles and then create the overlapping rectangles from the group of non-overlapping rectangles. It will save you some distance calculations, i.e. as you do a simple add of the distance from the non-overlapping rectangles instead of always recalculating using the "complex" formula.

Upvotes: 1

Related Questions