我正在使用.NET制作具有绘图表面的应用程序，类似于Visio。 UI使用Graphics.DrawLine连接屏幕上的两个对象。这个简单的实现可以很好地工作，但是随着表面变得越来越复杂，我需要一种更健壮的方式来表示对象。这些可靠的要求之一是确定两条线的交点，这样我就可以通过某种图形来指示分离。

所以我的问题是，有人可以建议一种方法吗？也许使用不同的技术(也许是GraphViz)或者算法？

解决方案

问博士数学

y = mx + c表示的线对于计算机图形学是有问题的，因为垂直线要求m为无穷大。

此外，计算机图形中的线具有起点和终点，这与范围无限的数学线不同。如果相交点位于所讨论的两个线段上，通常只对相交感兴趣。

如果有两个线段，一个从向量x1到x1 + v1，另一个从向量x2到x2 + v2，则定义：

a = (v2.v2 v1.(x2-x1) - v1.v2 v2.(x2-x1)) / ((v1.v1)(v2.v2) - (v1.v2)^2)
b = (v1.v2 v1.(x2-x1) - v1.v1 v2.(x2-x1)) / ((v1.v1)(v2.v2) - (v1.v2)^2)

对于向量p =(px，py)，q =(qx，qy)，其中p.q是点积(px * qx + py * qy)。首先检查(v1.v1)(v2.v2)=(v1.v2)^ 2，如果是，则线是平行的并且没有交叉。

如果它们不平行，则如果0 <= a <= 1和0 <= b <= 1，则交点位于两条线段上，并由该点给出

x1 + a * v1

编辑a和b的方程式的推导如下。交点满足矢量方程

x1 + a*v1 = x2 + b*v2

通过将该方程的点积与v1和v2相乘，我们得到两个方程：

v1.v1*a - v2.v1*b = v1.(x2-x1)
v1.v2*a - v2.v2*b = v2.(x2-x1)

形成a和b的两个线性方程。求解该系统(通过将第一个方程式乘以v2.v2，第二个方程式乘以v1.v1并减去或者以其他方式得出)得出a和b的方程式。

如果旋转参照系使其与第一条线段对齐(因此原点现在是第一条线的起点，并且第一条线的矢量沿X轴延伸)，问题就变成了，第二条线在哪里按下新坐标系中的X轴。这是一个容易回答的问题。如果第一条线称为" A"，并且由" A.O"定义为该线的起点，而" A.V"为该线的矢量，则" A.O + A.V"为该线的终点。参照系可以由矩阵定义：

| A.V.X   A.V.Y   A.O.X |
M = | A.V.Y  -A.V.X   A.O.Y |
    |   0       0       1   |

在齐次坐标中，此矩阵为参照系提供了基础，该参照系将线" A"映射到X轴上的0到1. 现在，我们可以将转换后的线" B"定义为：

C.O = M*(B.O)
C.V = M*(B.O + B.V) - C.O

适当地为均匀坐标定义了*操作符(在这种情况下是从3空间到2空间的投影)。现在剩下的就是检查并查看C击中X轴的位置，这与将C的参数方程的Y边求解为t相同：

C.O.Y + t * C.V.Y = 0
     -C.O.Y
t = --------
      C.V.Y

如果t的范围是0到1，则C会撞到线段内的X轴。它在X轴上的位置由C的参数方程的X边给出：

x = C.O.X + t * C.V.X

如果x的范围是0到1，则交点在A线段上。然后，我们可以使用以下命令在原始坐标系中找到该点：

p = A.O + A.V * x

当然，我们必须首先检查任一线段的长度是否为零。同样，如果" C.V.Y = 0"，则我们具有平行的线段。如果" C.V.X"也为零，则我们具有共线线段。