扫掠线算法用实施例

-3

代码Contais 3类：

班线表示水平线：参数：（X1，Y1） - --------（X2，Y2）
类点：
类段，用于在扫描线算法

我尝试使用下面的代码，来计算水平线之间的交叉点，因为你可以从我的线是水平的坐标：坐标：X1，Y1，X2，Y2我X1 < X2，和y 1 = Y

类点：

#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) 
{ 

}

类线

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

类板块：

#ifndef SEGMENT_H 
#define SEGMENT_H 

#include "Point.h" 
#include "Line.h" 

#include <vector> 
#include <set> 
#include <algorithm> 
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 <(const event &b) const 
     { 
      if (x != b.x) return x < b.x; 
      else return type < b.type; 
     } 
    }; 

class Segment 
{ 

    public: 
     Segment(); 
     vector<Point> hv_intersections(const vector<Line> &); 

}; 

#endif // SEGMENT_H 


#include "Segment.h" 

Segment::Segment() 
{ 
    //ctor 
} 

    vector<Point> Segment::hv_intersections(const vector<Line> & lines) 
    { 
     int L = lines.size(); 
     vector<event> events; 
     vector<Point> ans; 

     // Y coordinates of active lines 
     multiset<int> active; 

     // Convert lines into events 
     for (int i = 0; i < 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 <= x2 and y1 <= y2. 
     for (vector<event>::const_iterator e = events.begin(); e != events.end(); ++e) 
     { 
      switch (e->type) 
      { 
       case EVENT_START: 
        active.insert(lines[e->line].y1); 
        break; 

       case EVENT_END: 
        active.erase(active.find(lines[e->line].y1)); 
        break; 

       case EVENT_VERTICAL: 
       { 
        // Iterate over all y values for intersecting horizontal lines 
        multiset<int>::const_iterator first, last, i; 
        first = active.upper_bound(lines[e->line].y1); 
        last = active.lower_bound(lines[e->line].y2); 

        for (i = first; i != last; ++i) 
         ans.push_back(Point(e->x, *i)); 
       } 
       break; 
      } 
     } 

     return ans; 
    }

int main() 
{ 
    vector<Line> v; 
    v.push_back(Line(0, 5, 10, 5)); 
    v.push_back(Line(5, 0, 5, 10)); 
     Segment s; 
     vector<Point> p = s.hv_intersections(v); 
     cout << p.size() << endl; 
    return 0; 
}

来源

2013-10-25 Hani Goc

这是你的整个代码？当我尝试编译它时，我得到了'错误：'复杂'没有命名一个类型'。 – Kevin

是的，它是@Kevin。 –

其实数据中的行之间没有交集。预计什么？ – Sergey