我在2D空间中有这张边缘和顶点的大图。大图由C ++库中计算的函数返回。我正在阅读此图，并使用它来计算其边缘（线段）的所有交点。我使用扫描算法。为了检测两个边缘的交点，我有一些问题。我有4种不同的方法，根据这些方法，我可以测试两条边是否相交以及是否确定，以计算并保留它们的相交：
一种用于测试两个边缘是否为多边形的对角线。那是
插入到等式中的一条线的边缘的坐标
另一行有不同的标志。
每次计算交集并检查是否
找到的交点在两个线段的端点之间。
其中之一是C ++中实现的this link中的代码。
一个实现了Jason Cohenín提出的第一种方法的方法
this question。
“问题简化为这个问题：从A到B以及从C到D的两条线是否相交？然后您可以问四次（在该线和矩形的四个边之间）。
这是执行此操作的向量数学。我假设从A到B的线是有问题的线，从C到D的线是矩形线之一。我的记法是Ax是“ A的x坐标”，而Cy是“ C的y坐标”。 “ *”表示点积，因此：
A*B = Ax*Bx + Ay*By.
E = B-A = ( Bx-Ax, By-Ay )
F = D-C = ( Dx-Cx, Dy-Cy )
P = ( -Ey, Ex )
h = ( (A-C) * P ) / ( F * P )
这个h数是关键。如果h在0到1之间，则线条相交，否则它们不相交。如果FP为零，则当然无法进行计算，但是在这种情况下，线是平行的，因此仅在明显的情况下相交。
精确的交点为C + Fh。
如果h恰好是0或1，则线条在端点处接触。您可以认为这是一个“交叉点”，也可以认为不是合适的。”
对于我创建的数据（具有双值的小数据），使用所有4种实现的方法均获得了良好的结果。当我对来自大图的数据使用以C ++实现的这些方法中的任何一种时，每次都会得到不同的结果，但效果不好：
方法返回的交叉点更多（我所有的点都在图形上），但是得到的点太多。
无论如何，我总是获得0个交集。
我得到的交集比1多得多。
对于某些示例，我得到的点不在图形上（因此甚至交点也没有）。但是对于某些示例，我得到了交点以及其他一些点。
我不知道问题出在哪里。关于如何计算相交和对其进行测试的任何建议或任何其他想法，都值得欢迎。谢谢你，玛达琳娜
最佳答案
您需要的是对4种方法进行单元测试并对其进行全面测试。尤其是在线段相交处，除了所有常见的公差问题（例如，“等斜率”是什么意思？）之外，还有许多最终情况，例如平行斜率，重合的端点，完全或部分重叠。
如果不将内容分解为更小，更可测试的单元，您将很难将其范围缩小。
关于c++ - 计算两条边的交点，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/707096/