Use of Status structure in Plane sweep Algorithm for line Segment Intersection

Question

I want to implement status structure in Plane Sweep algorithm. My sweep line is moving in y-direction from top to bottom.

Currently i am using set(predefined one in c++) for storing segments according to their x values.

When sweep line moves down the x values of each segment changes and hence ordering in set should change, But in set search key once added can not be modified so my x values once assigned are not changed so everytime i move to next eventpoint i have to delete complete tree and create new with new x-values.

My segment structure is:

struct Segment
{
    double x1;
    double x2;
    double y1;
    double y2;
    int name;
    double x;
    double y;
};

How do i update x values in the set?

Answer 1

I have figured out the solution to the problem. Just used orientation to construct AVL tree insted of x-coordinate.

Here is my full source code.

#include <string>
#include <queue>
#include <iostream>
#include<stdlib.h>
#include<stdio.h>
#include <set>
using namespace std;  
struct Point {
double x;
double y;
int segment;
int segid1;
int segid2;
};
typedef struct Point point;

struct Segment{
double x1;
double x2;
double y1;
double y2;
int name;
double x;
double y;
 };
 typedef struct Segment segment;
 struct classcomp {
  bool operator() (const segment& lhs,const segment& rhs) 
  {//return lhs.x>rhs.x;
   if(rhs.x==lhs.x && rhs.y==lhs.y)
       return ((rhs.x1 - lhs.x2) * (rhs.y2 - lhs.y2) - (rhs.y1 - lhs.y2) *     (rhs.x2 - lhs.x2))<0;
   else
       return ((rhs.x1 - lhs.x1) * (rhs.y2 - lhs.y1) - (rhs.y1 - lhs.y1) * (rhs.x2 - lhs.x1))<0;
   }
    };

class CompareEventPoint {
public:
bool operator()(point& t1, point& t2) // Returns true if t1 is earlier than t2
{
   if(t1.y<t2.y)return true;
   return false;
}
 };


 point checkIntersection(segment a,segment b)
 {
point p;
p.segment=-1;
double num=(a.y1-b.y1)*(b.x2-b.x1)-(a.x1-b.x1)*(b.y2-b.y1);
double den=(a.y1-a.y2)*(b.x2-b.x1)-(a.x1-a.x2)*(b.y2-b.y1);
double s=num/den;
if(s>0 && s<1)
{
    double t=((1-s)*a.x1+s*a.x2-b.x1)/(b.x2-b.x1);
    if(t>0 && t<1)
    {
        p.segment=0;
        if(a.x1>b.x1)
        {
        p.segid1=a.name;
        p.segid2=b.name;
        }
        else
        {
        p.segid1=b.name;
        p.segid2=a.name;    
        }
        p.x=(1-s)*a.x1+s*a.x2;
        p.y=(1-s)*a.y1+s*a.y2;
        return p;
    }
}
return p;

 }

int main()
{
int n,i;
FILE *fp,*f;
priority_queue<point, vector<point>, CompareEventPoint> pq; // Creates a priority queue pq to store strings, and initializes the queue to be empty.
printf("Enter the number of line Segments\n");   
scanf("%d",&n);
segment segArray[n];




point p;
printf("Enter the co-ordinates of End points with top point first and then low  point\n");
  for(i=0;i<n;i++)
  {
    scanf("%lf%lf",&p.x,&p.y);
      p.segment=i+1;
    pq.push(p);
    segArray[i].name=i+1;
    segArray[i].x1=p.x;
    segArray[i].y1=p.y;
    scanf("%lf%lf",&p.x,&p.y);
    p.segment=-(i+1);
    pq.push(p);
    segArray[i].x2=p.x;
    segArray[i].y2=p.y;

}


set<segment,classcomp> tree;
set<segment,classcomp>::iterator itlow,itup;
int segid;
point ptemp;
double lineY;
int iteration=0;
while (!pq.empty()) {

   ptemp=pq.top();
   pq.pop(); 
   iteration++; 
   segid=ptemp.segment;
   lineY=ptemp.y;
   // Case of starting Point

   for (itlow=tree.begin(); itlow!=tree.end();++itlow)
        printf("%d\t",itlow->name);
   printf("\n");



   if(segid>0)
   {

   tree.insert(segArray[segid-1]);
   itlow=tree.lower_bound (segArray[segid-1]);   
   if(itlow!=tree.begin())                                                  //       ^
   {    itlow--;
       p=checkIntersection(segArray[segid-1],segArray[itlow->name-1]);
       if(p.segment==0 && ptemp.y>p.y)
       {
           pq.push(p);

       }
   }

   itup=tree.upper_bound (segArray[segid-1]); 
   if(itup!=tree.end())
   {

           p=checkIntersection(segArray[segid-1],segArray[itup->name-1]);
           if(p.segment==0 && ptemp.y>p.y)
           {
               pq.push(p);
           }
   }
   }


   // Case of intersection Point
   if(segid==0)
   {
       int t1=ptemp.segid1;
       int t2=ptemp.segid2;


       segment s1=segArray[t1-1];
       segment s2=segArray[t2-1];


       tree.erase(s1); 
       tree.erase(s2); 


       segArray[t1-1].x=ptemp.x;
       segArray[t1-1].x1=ptemp.x;
       segArray[t2-1].x=ptemp.x;
       segArray[t2-1].x1=ptemp.x;
       segArray[t1-1].y=ptemp.y;
       segArray[t1-1].y1=ptemp.y;
       segArray[t2-1].y=ptemp.y;
       segArray[t2-1].y1=ptemp.y;

       s1=segArray[t1-1];
       s2=segArray[t2-1];

       tree.insert(s1);
       tree.insert(s2);


       itlow=tree.lower_bound (s1);
       if(itlow!=tree.begin())
       {       itlow--;
               p=checkIntersection(s1,segArray[itlow->name-1]);

               if(p.segment==0 && ptemp.y>p.y)
                  {
                   pq.push(p);
                  }
       }
       itup=tree.upper_bound (s2); 
       if(itup!=tree.end())
       {

           p=checkIntersection(s2,segArray[itup->name-1]);
           if(p.segment==0 && ptemp.y>p.y)
            {
               pq.push(p);
            } 
       }


       printf("Intersection point=%lf %lf\n",ptemp.x,ptemp.y);

   }

   // Case of End point
   if(segid<0)
   {



       segid=-segid;
       if(itlow!=tree.begin() && itup!=tree.end())
       {
       itlow=tree.lower_bound (segArray[segid-1]);
       itlow--;
       itup=tree.upper_bound (segArray[segid-1]); 
       }
       tree.erase(segArray[segid-1]); 
       if(itlow!=tree.begin() && itup!=tree.end())
       {
       p=checkIntersection(segArray[itlow->name-1],segArray[itup->name-1]);
       if(p.segment==0 && ptemp.y>p.y)
       {
           pq.push(p);
       }

       }

   }
}

return 0;
}

Answer 2

std::set is generally implemented as a red-black tree. The ordering of elements in the tree is controlled by passing pairs of elements to a comparison function which is stored in the set; an element's position within the sort order is checked during insertion, and is assumed not to change thereafter. (You probably know all this already... just giving some background.)

Plane-sweep algorithms also commonly use self-balancing trees such as red-black trees for their state structure. However-- that's where the similarity ends. Elements (segments) in the state structure have no inherent overall ordering; the order is defined given a particular y-coordinate, and will change with the y-coordinate. Most importantly, at intersection event points, two segments will swap positions in the ordering, an operation that doesn't even make sense with std::set.

Bottom line: std::set, and other sorted container classes, are generally not appropriate for implementing the sweep state of a plane-sweep algorithm, even though the underlying data structures are appropriate. You should use a lower-level, directly-exposed red-black tree implementation which will allow you to swap elements.