我正在寻找一个算法，找到所有的交点给定n线段。
下面是http://jeffe.cs.illinois.edu/teaching/373/notes/x06-sweepline.pdf中的伪代码
输入s[1..n]是一列直线
部分。
label[i]是第i个最左端点的标签。
sort the endpoints of S from left to right
create an empty label sequence
for i ← 1 to 2n
line ← label[i]
if isLeftEndPoint[i]
Insert(line)
if Intersect(S[line], S[Successor(line)])
return TRUE
if Intersect(S[line], S[Predecessor(line)])
return TRUE
else
if Intersect(S[Successor(line)], S[Predecessor(line)])
return TRUE
Delete(label[i])
return FALSE
将算法应用于下面的直线集，只检查一个交点。我该怎么做才能知道其他2个交点的存在？
行[1]进入
进入第[2]行，勾选第[1]行和第[2]行的交集。
第[3]行进入，勾选第[2]行和第[3]行的交集。
进入第[4]行，勾选第[4]行和第[1]行的交叉点找到交叉口A。
第[4]行离开，未检查任何内容。
行[1]离开，未检查任何内容。
行[2]离开，未检查任何内容。
第[3]行离开，未检查任何内容。
最佳答案
标准线方程
ax+by=c
由方程标准线定义的直线的斜率（m）为
M=—（A/B）
点-坡-线方程
y-y1=m（x-x1）
用m=（-a/b）代入点-坡-线方程
y2-y1=（a/-b）*（x2-x1）
（y2-y1）/（x2-x1）=A/-B
因此：
a=y2-y1
B=x1-x2
C=ax+by
x=（c-by）/a
y=（C-Ax）/B
给定两条带等式的直线
A1x1+B1y1=C1和A2x2+B2y2=C2。
然后指定直线之间的交点
使a1x+b1y-c1=a2x+b2y-c2
A1x+B1y=C1
A2X+B2Y=C2
A1B2x+B1B2y=B2C1（将第一个方程式乘以B2）
A1B2X+B1B2Y-B2C1=0
a2b1x+b1b2y=b1c2（第二个方程乘以b1）
A2B1x+B1B2y-B1C2=0
把这两个方程等同起来
A1B2x+B1B2y-B2C1=A2B1x+B1B2y-B1C2
A1B2X+B1B2Y-B2C1-A2B1X-B1B2Y+B1C2=0
A1B2X-B2C1-A2B1X+B1C2=0
A1B2x-A2B1x=B2C1-B1C2
x（A1B2-A2B1）=B2C1-B1C2
x=（B2C1-B1C2）/A1B2-A2B1
A1X+B1Y=C1
A2X+B2Y=C2
A1A2X+A2B1Y=A2C1（将第一个方程式乘以A2）
A1A2X+A2B1Y-A2C1=0
A1A2X+A1B2Y=A1C2（将第二个方程式乘以A1）
A1A2X+A1B2Y-A1C2=0
把这两个方程等同起来
A1A2X+A2B1Y-A2C1=A1A2X+A1B2Y-A1C2
A1A2x+A2B1y-A2C1-A1A2x-A1B2y+A1C2=0
A1C2-A2C2=A1B2y-A2B1y
A1B2Y-A2B1Y=A1C2-A2C2
Y（A1B2-A2B1）=A1C2-A2C1
Y（A1B2-A2B1）=A1C2-A2C1
Y=（A1C2-A2C1）/（A1B1-A2B1）
y和x的分母是一样的，所以
分母=A1B1-A2B1
因此：
X=（B2C1-B1C2）/分母
Y=（A1C2-A2C1）/分母
这是两条线与点（x1，y1），（x2，y2）和（x3，y3），（x4，y4）相交的x和y坐标
现在对于一条线段，它是相同的，但是我们需要检查x或y坐标是否在两条线段中。也就是说，在两个数值较小的段的x坐标和两个数值较大的段的x坐标之间
这是一个C++程序，如果片段相交并返回假，则返回true。如果片段相交，则在变量i中存储相交点。
struct Point
{
float x, y;
};
//p1 and p2 are the points of the first segment
//p3 and p4 are the points of the second segment
bool intersection(Point p1, Point p2, Point p3, Point p4, Point &i)
{
float max1; //x-coordinate with greater value in segment 1
float min1; //x-coordinate with lesse value in segment 1
float max2; //x-coordinate with greater value in segment 2
float min2; //x-coordinate with lesser value in segment 2
float A1 = p2.y - p1.y;
float B1 = p1.x - p2.x;
float C1 = A1 * p1.x + B1 * p1.y;
float A2 = p4.y - p3.y;
float B2 = p3.x - p4.x;
float C2 = A2 * p3.x + B2 * p3.y;
float denom = A1 * B2 - A2 * B1;
if (denom == 0.0) //When denom == 0, is because the lines are parallel
return false; //Parallel lines do not intersect
i.x = (C1 * B2 - C2 * B1) / denom;
i.y = (A1 * C2 - A2 * C1) / denom;
if (p1.x > p2.x)
{
max1 = p1.x;
min1 = p2.x;
}
else
{
max1 = p2.x;
min1 = p1.x;
}
if (p3.x > p4.x)
{
max2 = p3.x;
min2 = p4.x;
}
else
{
max2 = p4.x;
min2 = p3.x;
}
//check if x coordinate is in both segments
if (i.x >= min1 && i.x <= max1 &&
i.x >= min2 && i.x <= max2)
return true;
return false; //Do no intersect, intersection of the lines is not between the segments
}
现在只需要在循环上比较所有线段并将交点存储在数组中。