[计算机图形学] 二维交互绘图中的线段拣选算法 - EaBIM

交互式流程图绘制工具时，遇到了屏幕二维线段鼠标拣选（用鼠标激活线段）的问题。

当时要求在鼠标接近线段时，鼠标光标要变成手指形状，而且此时如果用户按下鼠标左键，则可以激活该条线段。

问题的核心是，如何判断鼠标接近了线段。很直接的想法是：鼠标移动过程中，计算鼠标点到线段的垂直距离，如果距离小于设定的临界值，则判断为鼠标接近了线段。但是随后又考虑，平面上，计算一个点到直线的垂直距离，稍微有点复杂，想要采用尽量简便，又不影响操作的算法。最后经过思考，我确定了这样一种算法，实践证明，效果还是非常好的。

首先，我们考察鼠标顶点C，与线段端点A、B所构成的三角形：

除了C位于AB线段上，或者位于AB延长线上的时候，这三个点都可以构成一个三角形。并且，根据中学的几何知识，三角形边长之间存在一个定律，就是：任何两边的长度之和都大于第三边长度，也就有

AC + BC > AB

也可以表示为

(AC + BC) – AB = e
// e为变量

再有，也是根据中学的几何知识，对于AB，AC，BC长度确定的情况下，上述公式中的e值是确定的，而且C点距离AB越近，e值就有减小的趋势，其极限值为0。

我们知道，当e值为定值的时候，C点有一个运动轨迹，这个轨迹就是围绕A、B点，以A、B点为原点的椭圆，如下图：

回到前面鼠标拣选线段的话题，如果在鼠标移动时，计算e值，即可判断鼠标点位于以A、B为原点的哪一个椭圆轨迹上。当e值足够小，也就表示椭圆足够“扁”，此时可以认为C点接近了AB线段。

说到这里，有人会问，根据椭圆区域判断鼠标在线段周围的位置，不及矩形区域判断准确，但是，别忘了，我们是考虑e值足够小的情况，如下图：

当椭圆非常“扁”的情况下，其覆盖的区域与一个“扁”的矩形是非常接近的，一般在屏幕象素绘图上，可能只在矩形四个顶点处会有几个象素的差别，而这几个象素，我们是完全可以忽略的。在计算复杂度上，这种算法只需要计算三条线段的长度，再进行一次求和，一次求差值的计算，比计算点到线段的垂直距离要简便得多。