title: Sweep Line algorithm
body: <p><strong>SWEEP LINE EXAMPLE WITH EXAMPLE: AFTER CORRECTION</strong></p>
  
  <p>The code Contais 3 classes: </p>
  
  <ol>
  <li>Class Line to represent the Horizontal lines: Parameters:
  (x1,y1)----------(x2,y2) </li>
  <li>Class Point: </li>
  <li>Class segment for the sweep line algorithm</li>
  </ol>
  
  <p>I am trying to use the following code, to compute the intersections between horizontal lines, As you can from the coordinates that My lines are Horizontal:
  Coordinates: <strong>x1,y1,x2,y2</strong> I have x1 &lt; x2, and y1 = y</p>
  
  <hr>
  
  <p>Class Point:</p>
  
  <pre><code>#ifndef POINT_H
  #define POINT_H
  
  
  class Point
  {
      public:
          Point(float, float);
          float x;
          float y;
  
  };
  
  #endif // POINT_H
  
  #include "Point.h"
  
  Point::Point(float xi, float yi):x(xi),y(yi)
  {
  
  }
  </code></pre>
  
  <hr>
  
  <p>Class Line</p>
  
  <pre><code>#ifndef LINE_H
  #define LINE_H
  
  
  class Line
  {
      public:
          Line(int,int,int,int);
          int x1, y1, x2, y2;
  };
  
  #endif // LINE_H
  
  #include "Line.h"
  
  Line::Line(int x_1, int y_1, int x_2,int y_2):x1(x_1),y1(y_1),x2(x_2),y2(y_2)
  {
      //ctor
  }
  </code></pre>
  
  <hr>
  
  <p>Class Segment:</p>
  
  <pre><code>#ifndef SEGMENT_H
  #define SEGMENT_H
  
  #include "Point.h"
  #include "Line.h"
  
  #include &lt;vector&gt;
  #include &lt;set&gt;
  #include &lt;algorithm&gt;
  using namespace std;
  
  
      enum event_type { EVENT_END,EVENT_VERTICAL,EVENT_START};
      struct event
      {
          event_type type;
          int x;
          int line;        // index into list of lines
  
          event() {}
          event(event_type type, int x, int line) : type(type), x(x), line(line) {}
  
          // sort by X then by type
          bool operator &lt;(const event &amp;b) const
          {
              if (x != b.x) return x &lt; b.x;
              else return type &lt; b.type;
          }
      };
  
  class Segment
  {
  
      public:
          Segment();
          vector&lt;Point&gt; hv_intersections(const vector&lt;Line&gt; &amp;);
  
  };
  
  #endif // SEGMENT_H
  
  
  #include "Segment.h"
  
  Segment::Segment()
  {
      //ctor
  }
  
      vector&lt;Point&gt; Segment::hv_intersections(const vector&lt;Line&gt; &amp; lines)
      {
          int L = lines.size();
          vector&lt;event&gt; events;
          vector&lt;Point&gt; ans;
  
          // Y coordinates of active lines
          multiset&lt;int&gt; active;
  
          // Convert lines into events
          for (int i = 0; i &lt; L; i++)
          {
              if (lines[i].y1 != lines[i].y2)
                  events.push_back(event(EVENT_VERTICAL, lines[i].x1, i));
              else if (lines[i].x1 != lines[i].x2)
              {
                  events.push_back(event(EVENT_START, lines[i].x1, i));
                  events.push_back(event(EVENT_END, lines[i].x2, i));
              }
          }
  
          // Sort events by X
          sort(events.begin(), events.end());
  
          // Returns all intersections between lines. The lines must all be either
          // horizontal and vertical, and only horizontal-vertical intersections are
          // counted (i.e. not overlaps). Lines are considered to exclude their
          // endpoints. Also, each line must have x1 &lt;= x2 and y1 &lt;= y2.
          for (vector&lt;event&gt;::const_iterator e = events.begin(); e != events.end(); ++e)
          {
              switch (e-&gt;type)
              {
                  case EVENT_START:
                      active.insert(lines[e-&gt;line].y1);
                      break;
  
                  case EVENT_END:
                      active.erase(active.find(lines[e-&gt;line].y1));
                      break;
  
                  case EVENT_VERTICAL:
                  {
                      // Iterate over all y values for intersecting horizontal lines
                      multiset&lt;int&gt;::const_iterator first, last, i;
                      first = active.upper_bound(lines[e-&gt;line].y1);
                      last = active.lower_bound(lines[e-&gt;line].y2);
  
                      for (i = first; i != last; ++i)
                          ans.push_back(Point(e-&gt;x, *i));
                  }
                  break;
              }
          }
  
          return ans;
      }
  </code></pre>
  
  <hr>
  
  <pre><code>int main()
  {
       vector&lt;Line&gt; v;
      v.push_back(Line(0, 5, 10, 5));
      v.push_back(Line(5, 0, 5, 10));
         Segment s;
          vector&lt;Point&gt; p = s.hv_intersections(v);
          cout &lt;&lt; p.size() &lt;&lt; endl;
       return 0;
  }
  </code></pre>