问题
给出n条由[起点，终点]表示的线段，判断线段间的交点个数（要求O(nlogn)）
对于这一问题，可以分解为两个任务：
①快速判断两线段是否相交的方法
②优化的执行n条线段判断的方法
①线段相交判断
为了优化线段相交的判断，同样可分为两步：快速排斥实现和跨立实验
![[图像处理] 计算n条线段的交点个数](https://johngo-pic.oss-cn-beijing.aliyuncs.com/articles/20230619/c88048d8981a40e28ac7f5e845c5731f.png)
![[图像处理] 计算n条线段的交点个数](https://www.johngo689.com/wp-content/themes/justnews/themer/assets/images/lazy.png)
; 快速排斥实验
我们很容易得到这样一个结论： 当两条线段相交时，以两个线段作为对角线的矩形必定相交
这类似碰撞检测时的一个预先的粗糙判断，具体实现也比较简单，即满足：
bool quick_check = min(p1.x, p2.x) < max(L.p1.x, L.p2.x) &&
min(L.p1.x, L.p2.x) < max(p1.x, p2.x) &&
min(p1.y, p2.y) < max(L.p1.y, L.p2.y) &&
min(L.p1.y, L.p2.y) < max(p1.y, p2.y);
跨立实验
我们又有一个结论： 当两条线段相交时，这两条线段必定相互跨立对方
以下图举例，此处的 跨立意为：一条线段的两端点在另一条线段的两侧，如P1、P2分别在线段Q的两侧，Q1、Q2分别在线段P的两侧，此时P、Q即为相互跨立的关系，也一定满足相交关系
![[图像处理] 计算n条线段的交点个数](https://johngo-pic.oss-cn-beijing.aliyuncs.com/articles/20230619/d1c5e6a9bb894b87b0e05b95fb8fc69d.png#pic_center)
具体计算为：当P跨立Q时，向量(Q1, P1)和向量(Q1， P2)分别在向量(Q1, Q2)两侧，根据向量运算的关系有：
( ( Q 1 , Q 2 ) × ( Q 1 , P 1 ) ) ∗ ( ( Q 1 , Q 2 ) × ( Q 1 , P 2 ) ) < 0 ((Q1, Q2)\times(Q1, P1)) * ((Q1, Q2)\times(Q1,P2))①叉乘的正负表示叉乘前向量到叉乘后向量的旋转方向+②点乘的正负表示两个向量是否同向
即向量(Q1, Q2)到另外两个向量的旋转方向相反，转换成坐标计算形式为：
( ( Q 2. x − Q 1. x ) ∗ ( P 1. y − Q 1. y ) − ( Q 2. y − Q 1. y ) ∗ ( P 1. x − Q 1. x ) ) ∗ ( ( Q 2. x − Q 1. x ) ∗ ( P 2. y − Q 1. y ) − ( Q 2. y − Q 1. y ) ∗ ( P 2. x − Q 1. x ) ) < 0 ((Q2.x-Q1.x)(P1.y-Q1.y)-(Q2.y-Q1.y)(P1.x-Q1.x))((Q2.x-Q1.x)(P2.y-Q1.y)-(Q2.y-Q1.y)*(P2.x-Q1.x))
![[图像处理] 计算n条线段的交点个数](https://johngo-pic.oss-cn-beijing.aliyuncs.com/articles/20230619/75c4fbf5afc1413c9d98b10c4637f479.png#pic_center)
至此可以完成相交判断的代码，如下：
#include
#include
using namespace std;
struct Point
{
int x, y;
Point(){}
Point(int x, int y):x(x), y(y){}
static int cdot(const Point &p1, const Point &p2){
return p1.x*p2.x + p1.y*p2.y;
}
static int xdot(const Point &p1, const Point &p2){
return p1.x*p2.y-p1.y*p2.x;
}
};
struct Line
{
Point p1, p2;
Point line_vec;
Line(const Point& p1, const Point& p2):p1(p1), p2(p2){
line_vec = Point(p2.x-p1.x, p2.y-p1.y);
}
bool IsInter(const Line &L){
bool quick_check = min(p1.x, p2.x) < max(L.p1.x, L.p2.x) &&
min(L.p1.x, L.p2.x) < max(p1.x, p2.x) &&
min(p1.y, p2.y) < max(L.p1.y, L.p2.y) &&
min(L.p1.y, L.p2.y) < max(p1.y, p2.y);
if(quick_check){
Point p1_Lp1 = Point(L.p1.x-p1.x, L.p1.y-p1.y);
Point p1_Lp2 = Point(L.p2.x-p1.x, L.p2.y-p1.y);
Point Lp1_p1 = Point(p1.x-L.p1.x, p1.y-L.p1.y);
Point Lp1_p2 = Point(p2.x-L.p1.x, p2.y-L.p1.y);
return Point::xdot(line_vec, p1_Lp1) * Point::xdot(line_vec, p1_Lp2)<0 &&
Point::xdot(L.line_vec, Lp1_p1) * Point::xdot(L.line_vec, Lp1_p2)<0;
}
return false;
}
};
class LineVec
{
public:
LineVec(){}
void addLine(const Point &p1, const Point &p2){
mLines.push_back(Line(p1, p2));
}
public:
vector<Line> mLines;
};
int main(){
LineVec line_vec;
line_vec.addLine(Point(0, 0), Point(1, 1));
line_vec.addLine(Point(1, 0), Point(0, 1));
cout << line_vec.mLines[0].IsInter(line_vec.mLines[1]) << endl;;
return 1;
}
②n条线段相交判断
暂时没想到nlogn的做法，感觉是从排序的方法中借鉴思路？
Original: https://blog.csdn.net/qq_41265365/article/details/126318490
Author: 感天动地大白狗
Title: [图像处理] 计算n条线段的交点个数
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/645529/
转载文章受原作者版权保护。转载请注明原作者出处！