2

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

所以我的问题是，任何人都可以提出一种方法来做到这一点吗？也许使用不同的技术（也许是 GraphViz）或算法？

4

3 回答 3

9

用 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)，pq 是点积 (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 的方程。

于 2008-09-30T16:12:42.057 回答
4

问博士。数学

于 2008-09-30T15:41:56.033 回答
4

如果您旋转参考系以与第一条线段对齐（因此原点现在是第一条线的起点，第一条线的矢量沿 X 轴延伸）问题就变成了，第二条线在哪里击中新坐标系中的 X 轴。这是一个更容易回答的问题。如果第一条线被调用A，它被定义A.O为线的起点，'AV'是线的向量，所以它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 个空间的投影）。现在剩下的就是检查并查看CX 轴的位置，这与求解forY的参数方程的一侧相同：Ct

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

如果t在 0 到 1 的范围内，则C命中线段内的 X 轴。它落在 X 轴上的位置由 的参数方程的 X 侧给出C：

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也为零，则您有共线线段。

于 2008-09-30T18:10:13.913 回答