algorithm - 如何判断鼠标指针是否位于贝塞尔曲线和直线定义的路径内？

Question

我有一条由多条贝塞尔曲线和直线段组成的封闭路径。如何判断鼠标指针的当前位置是在路径内部还是外部？

鼠标离开该区域的示例：

鼠标进入区域示例：

Answer 1

首先，您应该检查您正在使用的图形库是否已经提供了这种命中测试。

如果您必须自己编写代码，那么完全精确的答案将需要求解二次或三次方程（取决于贝塞尔曲线的程度）以确定与这些路径的交点。似乎有一篇关于这个问题的论文。

但是，我认为建立对路径的线性近似（即密集地评估路径）然后使用标准的多边形点测试会更明智。这可以精确到您选择的任何容差（例如一个像素）。

Answer 2

If the regions are relatively small, you could run a floodfill starting from the mouse location. If the floodfill goes outside of a bounding box (which you can precompute) then it's outside of the region.

See: http://en.wikipedia.org/wiki/Flood_fill

Answer 3

要测试一个点是在贝塞尔路径的内部还是外部，请从该点沿任意方向画一条线，并计算该线穿过路径的次数。如果数字是奇数，那么你在里面，如果它是偶数，那么你在外面。

因此，内部测试可以重新表示为交叉测试。可以通过多种方式处理交叉路口。一种相对简单的方法是使用 deCasteljau 算法用直线段近似贝塞尔补丁，将贝塞尔线相交测试减少为一系列线线相交测试。

请注意，您可以在计算中采用几种捷径。例如，如果您绘制的线完全位于给定贝塞尔面片控制点的边界框之外，那么您可以假设它不会穿过面片。在使用 deCasteljau 递归分割曲线时，您可以利用此特定快捷方式来丢弃不会与线段相交的分割曲线部分。