CG2017 PA2 Segment Intersection Reporting （多线段求交）

标签：求交 PA2 right return AVLTreeNode Reporting key root left

Description (描述)

邓俊辉老师的学堂在线计算几何课堂第二章提到了Segment Intersection Reporting的BO算法，简单实现了一下。

Input (输入)

第一行整数N，表示线段总数

后面N行，每行4个整数，格式为a,b,c,d，表示线段的起点(a,b)和终点(c,d)，不保证起点在终点左边。

Output (输出)

输出所有交点的坐标及交点所在的两个线段，格式为

( a, b ) n1 n2

(a,b)是交点坐标，n1和n2是所在的线段编号

Sample Input (输入样例)

Sample Output (输出样例)

/*
( -6 , 4 ) 1    LEFT
1
( -4 , 0 ) 2    LEFT
2 1
( -4 , 5 ) 6    LEFT
2 1 6
( -3 , 2 ) 5    LEFT
2 5 1 6
( -3 , 3 ) 3    LEFT
2 5 3 1 6
( -3 , 3 ) 4    LEFT
2 5 4 3 1 6
( -3 , 3 ) 0    INTX
2 5 4 3 1 6
( -2.66667 , 3.33333 ) 0    INTX
2 5 4 3 6 1
( -2.5 , 2.5 ) 0    INTX
2 4 5 3 6 1
( -2.33333 , 2.66667 ) 0    INTX
2 4 3 5 6 1
( -2.33333 , 2.66667 ) 0    INTX
( -2.22222 , 2.77778 ) 0    INTX
2 4 3 6 5 1
( -2 , 2 ) 4    RIGHT
2 3 6 5 1
( -2 , 2.5 ) 0    INTX
2 6 3 5 1
( -2 , 2.5 ) 0    INTX
( -2 , 3 ) 5    RIGHT
2 6 3 1
( -1 , 2 ) 3    RIGHT
2 6 1
( 0 , 0 ) 6    RIGHT
2 1
( 1.14286 , 2.57143 ) 0    INTX
1 2
( 1.14286 , 2.57143 ) 0    INTX
( 4 , 2 ) 1    RIGHT
2
( 4 , 4 ) 2    RIGHT
*/
 ( -3 , 3 ) 4 3
 ( -2.66667 , 3.33333 ) 1 6
 ( -2.5 , 2.5 ) 5 4
 ( -2.33333 , 2.66667 ) 5 3
 ( -2.22222 , 2.77778 ) 5 6
 ( -2 , 2.5 ) 3 6
 ( 1.14286 , 2.57143 ) 2 1

Limitation (限制)

2 <= N <= 10^5

保证无竖直线段，保证线段间的交点只有一个

题解

按照邓老师课上讲的方法和数据结构，利用AVL存储当前状态，优先队列存储当前事件。

参考资料为

数据结构图文解析之：AVL树详解及C++模板实现 - 腾讯云开发者社区-腾讯云 (tencent.com)

二叉查找树的前驱后继 - 范仁义 - 博客园 (cnblogs.com)

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<set>

using namespace std;

#define EPS 1e-8

//#define DEBUG

enum TYPE{
    NONE, LEFT, RIGHT, INTX
};

struct Point2{
    double x;
    double y;
    // 点所在的线段编号
    long long int n;
    // 左右端点、或者交点
    TYPE type;
    // 交点所在的线段编号
    long long int n1;
    long long int n2;

    Point2(double xx, double yy, long long int nn, TYPE e) : x(xx), y(yy), n(nn), type(e){
        n1 = 0;
        n2 = 0;
    }

    Point2() : x(0),y(0),n(0),type(NONE),n1(0),n2(0){}

    bool operator== (const Point2& p) const{
        return abs(x - p.x) < EPS  && abs(y - p.y) < EPS && type == p.type && n == p.n && n1 == p.n1 && n2 == p.n2;
    }

    //需要最大堆，对小于号重载
    
    bool operator < (const Point2& p) const{
        return (x < p.x) || (abs(x - p.x) < EPS && (y < p.y || (abs(y - p.y) < EPS && (type < p.type || type == p.type && n < p.n))));
    }
    

    // 需要最小堆，对大于号重载
    friend bool operator > (const Point2& p1, const Point2& p2) {
        return (p1.x > p2.x) || (abs(p1.x - p2.x) < EPS && (p1.y > p2.y || (abs(p1.y - p2.y) < EPS && (p1.type > p2.type || (p1.type == p2.type && p1.n > p2.n)))));
    }

    friend ostream& operator<<(ostream& out, const Point2& p){
        string str[] = {"NONE", "LEFT", "RIGHT", "INTX"};
        out << "( " << p.x << " , " << p.y << " ) " <<  p.n << "    " << str[p.type] << endl;
        return out;
    }
};

struct Segment
{
public:
    Point2 p1;
    Point2 p2;
    long long int n;
    double k;

    Segment(){
        p1 = Point2();
        p2 = Point2();
        k = 0;
        n = 0;
    };

    Segment(Point2 pp1, Point2 pp2, long long int nn){
        p1 = pp1;
        p2 = pp2;
        k = (pp2.y - pp1.y) / (pp2.x - pp1.x);
        n = nn;
    }

    // j 是否在 i左边
    bool toLeftTest(const Point2& s, const Point2& i, const Point2& j) const{
        long long int x1 = i.x - s.x;
        long long int x2 = j.x - s.x;
        long long int y1 = i.y - s.y;
        long long int y2 = j.y - s.y;
    
        long long int res = x1 * y2 - x2 * y1;
        
        //严格控制顶点不在线上
        return res > 0;
    }

    bool isInSegment(const Segment& s) const{
        
        auto xx = (k * p1.x - s.k * s.p1.x - p1.y + s.p1.y ) / (k - s.k);
        
        return ((xx > p1.x || abs(xx - p1.x) < EPS) && (xx < p2.x || abs(xx - p2.x) < EPS)) && 
        ((xx > s.p1.x || abs(xx - s.p1.x) < EPS) && (xx < s.p2.x || abs(xx - s.p2.x) < EPS));
    }

    //  求出线段和扫描线的交点，方便判断
    Point2 intersectionL(const double line) const{
        return move(Point2(line, p1.y + k * (line - p1.x), n, NONE));
    }

    // 判断在 line这条扫描线上谁高谁底
    bool lessS(const Segment& s, const double line){
        auto pp1 = intersectionL(line);
        auto pp2 = s.intersectionL(line);
        // 处理相等的情况，按照线段后面的趋势来判断谁高谁底
        if(abs(pp1.y - pp2.y) < EPS){
            auto ppp1 = intersectionL(p2.x);
            auto ppp2 = s.intersectionL(p2.x);
            return ppp1.y < ppp2.y;
        }
        return pp1.y < pp2.y;
    }

    bool greaterS(const Segment& s, const double line){
        auto pp1 = intersectionL(line);
        auto pp2 = s.intersectionL(line);
        if(abs(pp1.y - pp2.y) < EPS){
            auto ppp1 = intersectionL(p2.x);
            auto ppp2 = s.intersectionL(p2.x);
            return ppp1.y > ppp2.y;
        }
        
        return pp1.y > pp2.y;
    }
    
    bool isIntersectionS(const Segment& s) const{
        // 还要判断线段端点是否在别人的线上, 对于共线问题要特殊判断
        if(isInSegment(s))
            return true;
        return (toLeftTest(p1, p2, s.p1) != toLeftTest(p1, p2, s.p2)) && (toLeftTest(s.p1, s.p2, p1) != toLeftTest(s.p1, s.p2, p2));
    }

    // 求出两个线段的交点
    Point2 intersectionS(const Segment& s) {
        auto res = Point2();
        res.x = (k * p1.x - s.k * s.p1.x - p1.y + s.p1.y ) / (k - s.k);
        res.y = p1.y + k * (res.x - p1.x);

        // 在这里处理交点时，把低线段放在第一个
        if(this->lessS(s, p1.x)){
            res.n1 = n;
            res.n2 = s.n;
        }else{
            res.n1 = s.n;
            res.n2 = n;
        }
        
        res.type = TYPE::INTX;
        res.n = 0;
        return move(res);
    }


    bool operator == (const Segment& s){
        return n == s.n;
    }

    friend ostream& operator<< (ostream& out, const Segment& s) {
        out << s.n << endl;
        return out;
    }
};


struct AVLTreeNode
{
    Segment key;
    int height;
    
    AVLTreeNode* left;
    AVLTreeNode* right;

    AVLTreeNode(Segment s, AVLTreeNode* l, AVLTreeNode* r) : key(s), left(l), right(r){}
    
    ~AVLTreeNode(){}
};


class AVLTree {
public:
    AVLTreeNode* root;

    AVLTree(){ root = nullptr;};
    ~AVLTree(){};

    int getHeight(AVLTreeNode* p_root){
        return !p_root? 0 : p_root->height;
    }

    void updateHeight(AVLTreeNode* p_root){
        p_root->height = max(getHeight(p_root->left), getHeight(p_root->right)) + 1;
    }

    // 返回最大节点，最右节点最大
    AVLTreeNode* maximum(AVLTreeNode* p_root) const {
        if(p_root == nullptr) return nullptr;
        while(p_root->right != nullptr) p_root = p_root->right;
        return p_root;
    }

    // 返回最小节点，最左节点最小
    AVLTreeNode* minimum(AVLTreeNode* p_root) const {
        if(p_root == nullptr) return nullptr;
        while(p_root->left != nullptr) p_root = p_root->left;
        return p_root;
    }


    // 左单旋 : 在右子树插入右孩子
    // 对节点y进行向左旋转操作，返回旋转后新的根节点x
    //  p_root                          x
    //  /  \                          /   \
    // T1   x      向左旋转 (p)    p_root  z
    //     / \   - - - - - - - ->   / \   / \
    //   T2   z                    T1 T2 T3 T4
    //       / \
    //      T3 T4
    AVLTreeNode* leftRotation(AVLTreeNode* p_root){
        AVLTreeNode* pr_right = p_root->right;
        p_root->right = pr_right->left;
        pr_right->left = p_root;

        // 注意是先更新子树，再更新根
        updateHeight(p_root);
        updateHeight(pr_right);

        return pr_right;
    }

    // 右单旋 ：在左子树插入左孩子
    // 对节点y进行向右旋转操作，返回旋转后新的根节点x
    //        y                              x
    //       / \                           /   \
    //      x   T4     向右旋转 (y)        z     y
    //     / \       - - - - - - - ->    / \   / \
    //    z   T3                       T1  T2 T3 T4
    //   / \
    // T1   T2
    AVLTreeNode* rightRotation(AVLTreeNode* p_root){
        AVLTreeNode* pr_left = p_root->left;
        p_root->left = pr_left->right;
        pr_left->right = p_root;

        updateHeight(p_root);
        updateHeight(pr_left);

        return pr_left;
    }

    // 先右旋右子树再左旋根节点：在右子树插入左孩子
    AVLTreeNode* rightLeftRotation(AVLTreeNode* p_root){
        p_root->right = rightRotation(p_root->right);
        return leftRotation(p_root);
    }


    // 先左旋左子树再右旋根节点：在左子树插入右孩子
    AVLTreeNode* leftRightRotation(AVLTreeNode* p_root){
        p_root->left = leftRotation(p_root->left);
        return rightRotation(p_root);
    }

    AVLTreeNode* insert(AVLTreeNode* p_root, Segment& key, const double line){
        if(p_root == nullptr){
            p_root = new AVLTreeNode(key, nullptr, nullptr);
        }
        else if(key.greaterS(p_root->key, line)) { // 值比当前值大，在右子树插入
            p_root->right = insert(p_root->right, key, line);
            if(getHeight(p_root->right) - getHeight(p_root->left) == 2) //插入后失衡
            {
                if(key.greaterS(p_root->right->key, line))  // 插入右子树的右节点
                    p_root = leftRotation(p_root);
                else if(key.lessS(p_root->right->key, line)) // 插入右子树的左节点
                    p_root = rightLeftRotation(p_root);
            }
        }
        else if(key.lessS(p_root->key, line)) {     // 值比当前值小，在左子树插入
            p_root->left = insert(p_root->left, key, line);
            if(getHeight(p_root->left) - getHeight(p_root->right) == 2)  // 插入后失衡
            {
                if(key.lessS(p_root->left->key, line))  /// 插入左子树左节点
                    p_root = rightRotation(p_root);
                else if(key.greaterS(p_root->left->key, line))
                    p_root = leftRightRotation(p_root);
            }
        }

        updateHeight(p_root);
        return p_root;
    }

    // 删除右子树节点相当于左子树加节点，造成失衡，反之亦然
    AVLTreeNode* remove(AVLTreeNode*& p_root, Segment& key, const double line){
        if(p_root == nullptr) return nullptr;

        if(key == p_root->key){ // 找到删除节点
            // 如果左右都不为空
            if(p_root->left != nullptr && p_root->right != nullptr) {

                if(getHeight(p_root->left) > getHeight(p_root->right)){ // 左子树比右子树高，在左子树寻找节点替换
                    AVLTreeNode* ppre = maximum(p_root->left);      // 左子树最大节点
                    p_root->key = ppre->key;                        // 更换最大值
                    p_root->left = remove(p_root->left, ppre->key, line); // 递归删除最大节点
                }else{
                    AVLTreeNode* psuc = minimum(p_root->right);
                    p_root->key = psuc->key;
                    p_root->right = remove(p_root->right, psuc->key, line);
                }

            }else{
                AVLTreeNode* ptemp = p_root;
                if(p_root->left != nullptr){        // 如果右空，返回左子树
                    p_root = p_root->left;
                }else if(p_root->right != nullptr){ // 如果左空，返回右子树
                    p_root = p_root->right;
                }else {
                    p_root = nullptr;
                }
                delete ptemp;
                return p_root;
            }

        } else if(key.greaterS(p_root->key, line)){  // 在右子树删除

            p_root->right = remove(p_root->right, key, line);
            if(getHeight(p_root->left) - getHeight(p_root->right) == 2){
                // 左子树插入右节点
                if(getHeight(p_root->left->right) > getHeight(p_root->left->left))
                    p_root = leftRightRotation(p_root);
                else
                    p_root = rightRotation(p_root);

            }

        } else if(key.lessS(p_root->key, line)){    // 在左子树删除

            p_root->left = remove(p_root->left, key, line);
            if(getHeight(p_root->right) - getHeight(p_root->left) == 2){
                // 右子树插入左节点
                if(getHeight(p_root->right->left) > getHeight(p_root->right->right))
                    p_root = rightLeftRotation(p_root);
                else
                    p_root = leftRotation(p_root);
            }

        }
        return p_root;
    }

    // 返回key值的node，同时通过指针返回该node的父节点
    // 这里是要改变指针本身的值，而不是指针指向的对象，所以要加引用
    AVLTreeNode* getNodeAndPrecParent(AVLTreeNode* p_root, const Segment& key, const double line, AVLTreeNode*& parent, AVLTreeNode*& firstParent){
        while(p_root){
            if(p_root->key == key)  // 如果找到这个key对应的node返回该node，运行到这里时候parent已经被赋值了
                return p_root;
            
            parent = p_root;        // 记录当前为Parent

            if(p_root->key.greaterS(key, line))
                p_root = p_root->left;
            else{
                firstParent = p_root;  // 记录最近一个右拐的顶点
                p_root = p_root->right;
            }
        }
        return nullptr;
    }


    AVLTreeNode* precursor(AVLTreeNode* p_root, const Segment& key, const double line) {
        if(p_root){
            AVLTreeNode* parent = nullptr;
            AVLTreeNode* firstParent = nullptr;

            auto node = getNodeAndPrecParent(p_root, key, line, parent, firstParent);
            if(node == nullptr)
                return node;

            if(node->left)          // 有左子树
                return maximum(node->left);
            
            if(parent == nullptr || (parent && (nullptr == firstParent))) 
                return nullptr; // 没有前驱节点

            if(node == parent->right)
                return parent;
            else   
                return firstParent;

        }
        return p_root;
    }

    // 返回key值的node，同时通过指针返回该node的父节点
    AVLTreeNode* getNodeAndSuccParent(AVLTreeNode* p_root, const Segment& key, const double line, AVLTreeNode*& parent, AVLTreeNode*& firstParent){
        while(p_root){
            if(p_root->key == key)
                return p_root;
            
            parent = p_root;

            if(p_root->key.lessS(key, line))
                p_root = p_root->right;
            else{
                firstParent = p_root;
                p_root = p_root->left;
            }
        }
        return nullptr;
    }

    AVLTreeNode* succeed(AVLTreeNode* p_root, const Segment& key, const double line){
    if(p_root){
            AVLTreeNode* parent = nullptr;
            AVLTreeNode* firstParent = nullptr;
            
            auto node = getNodeAndSuccParent(p_root, key, line, parent, firstParent);
            if(node == nullptr)
                return node;
            
            if(node->right)
                return minimum(node->right);

            if(parent == nullptr || (parent && (firstParent == nullptr)))
                return nullptr;
            
            if(node == parent->left)
                return parent;
            else
                return firstParent;
            
        }
        return p_root;
    }

    // 遍历查找
    AVLTreeNode* find(AVLTreeNode* p_root, const Segment& key, const double line){
        if(p_root != nullptr) {
            if(p_root->key == key)
                return p_root;

            auto l = find(p_root->left, key, line);
            auto r = find(p_root->right, key, line);
            if(l && l->key == key)
                return l;
            if(r && r->key == key)
                return r;
        }
        return nullptr;
    }



    void inOrder(AVLTreeNode* p_root) const {
        if(p_root != nullptr){
            inOrder(p_root->left);
            cout << p_root->key.n << " ";
            inOrder(p_root->right);
        }
    }

    void preOrder(AVLTreeNode* p_root) const {
        if(p_root != nullptr){
            cout << p_root->key.n << " ";
            preOrder(p_root->left);
            preOrder(p_root->right);
        }
    }

};


priority_queue<Point2, vector<Point2>, greater<Point2>> events;
vector<Segment> segments;
set<Point2> intxPoints;
AVLTree avl;
int N;

int main() {
    cin >> N;
    long long int a,b,c,d;
    segments.push_back(Segment());
    for(long long int i = 1; i <= N; i ++){
        cin >> a >> b >> c >> d;
        if(a < c) {
            auto p1 = Point2(a, b, i, TYPE::LEFT);
            auto p2 = Point2(c, d, i, TYPE::RIGHT);
            events.push(p1);
            events.push(p2);
            segments.push_back(Segment(p1, p2, i));
        }else{
            auto p1 = Point2(a, b, i, TYPE::RIGHT);
            auto p2 = Point2(c, d, i, TYPE::LEFT);
            events.push(p1);
            events.push(p2);
            segments.push_back(Segment(p2, p1, i));
        }
    }

    double L = 0;
    while (!events.empty())
    {
        auto e = events.top();
        events.pop();
        cout << e;
        L = e.x;
        if(e.type == LEFT){

            avl.root = avl.insert(avl.root, segments[e.n], L);

            auto prec = avl.precursor(avl.root, segments[e.n], L);
            auto succ = avl.succeed(avl.root, segments[e.n], L);

            if(prec && segments[e.n].isIntersectionS(prec->key)) {
                auto p = segments[e.n].intersectionS(prec->key);
                // 需要交点在L之后才加入队列，防止重复探测造成 INTX 重复，而导致错误交换seg顺序
                if(p.x > L || abs(p.x - L) < EPS)
                    events.push(p);
            }

            if(succ && segments[e.n].isIntersectionS(succ->key)) {
                auto p = segments[e.n].intersectionS(succ->key);
                if(p.x > L || abs(p.x - L) < EPS)
                    events.push(p);
            }
            avl.inOrder(avl.root);
            cout << endl;
        }else if(e.type == RIGHT){

            auto prec = avl.precursor(avl.root, segments[e.n], L);
            auto succ = avl.succeed(avl.root, segments[e.n], L);

            if(prec && succ && prec->key.isIntersectionS(succ->key)){
                auto p = prec->key.intersectionS(succ->key);
                if(p.x > L || abs(p.x - L) < EPS)
                    events.push(p);
            }

            avl.root = avl.remove(avl.root, segments[e.n], L);
            avl.inOrder(avl.root);
            cout << endl;
        }else if(e.type == INTX){

            //cout << " ( " << e.x << " , " << e.y << " ) " << e.n1 << " " << e.n2 << endl;
            
            // 防止多次判断同一对线段的交点，从而错误的改变该线段的次序
            if(intxPoints.find(e) == intxPoints.end())
                intxPoints.insert(e);
            else
                continue;
            // 此时 e.n1比e.n2低 ，因此找e.n2的后继和e.n1的前驱，交换后重新判断
            auto prec = avl.precursor(avl.root, segments[e.n1], L);
            auto succ = avl.succeed(avl.root, segments[e.n2], L);

            // 但是在交点的横坐标L处，n1和n2实际上用作排序的值已经相等了，想不到什么O(logn)的查找方法，直接遍历吧
            // 或许就是在判断相等的时候，用左端点所在的垂直线判断，这个就不写了，直接遍历完事
            auto s1 = avl.find(avl.root, segments[e.n1], L);
            auto s2 = avl.find(avl.root, segments[e.n2], L);

            // swap，当前走向是 n1 低于 n2，如果未来是n2 低于 n1的话，再交换
            if(s1->key.greaterS(s2->key, s1->key.p2.x)){
                auto tmp = s1->key;
                s1->key = s2->key;
                s2->key = tmp;
            }

            if(prec && segments[e.n2].isIntersectionS(prec->key)) {
                auto p = segments[e.n2].intersectionS(prec->key);
                if(p.x > L || abs(p.x - L) < EPS)
                    events.push(p);
            }

            if(succ && segments[e.n1].isIntersectionS(succ->key)) {
                auto p = segments[e.n1].intersectionS(succ->key);
                if(p.x > L || abs(p.x - L) < EPS)
                    events.push(p);
            }
            avl.inOrder(avl.root);
            cout << endl;
        }
    }
    
    for(auto e : intxPoints)
        cout << " ( " << e.x << " , " << e.y << " ) " << e.n1 << " " << e.n2 << endl;

    return 0;
}

思考不周嗯写的代码，如有纰漏，欢迎指正！！！

标签：求交,PA2,right,return,AVLTreeNode,Reporting,key,root,left
From： https://www.cnblogs.com/HXLGY/p/16832319.html