我过去曾在商业产品中解决过这个问题.您已经询问过分析曲线,但我会更一般地解决它至少两次可微分的曲线.将多边形处理为一组单独的线段.无需对曲线进行分段,但如果您愿意,可以稍微调整算法.
此外,您可能希望在Graphics Gems V中查看我的纸张Matrix-Based Ellipse Geometry来查找省略号之间的交叉点.
基本理念:
- 考虑来自测试点的+ x方向的光线.
- 现在考虑从测试点沿着光线行走的蚂蚁.
- 当蚂蚁撞击其中一条曲线的第一个交叉点时,它会使最锋利的线条离开,并在该交点处留下一个箭头,指示它所选择的方向.(如果没有交叉点,那么显然这一点不受限制.)
- 如果它到达曲线的末端,它会自动翻倍.
- 如果在该点处有多条曲线相交,则选择最左侧的曲线.
- 如果一条或多条曲线实际上与交叉处的光线相切,则可以使用更高的导数来决定选择哪条曲线和方向.(这只蚂蚁知道微积分.)
- 现在,当蚂蚁沿着曲线漫步时,它总是像上面那样做出最大的左转.如果交叉点处的曲线之间存在相切,请使用更高的导数来确定"最左边"的曲线.(细节留给蚂蚁).
- 在它的旅行中,蚂蚁可能多次来到射线的起始交叉点.但是一旦它发现自己沿着箭头方向(它在步骤3中离开的那个方向)前进,它的行程就完成了并且它已经遍历了"轮廓".问题减少到决定点是否在该轮廓中.
"轮廓"是拓扑实体.它是在"顶点"处连接的"段"的闭环.
"段"是轮廓在特定方向上使用的曲线的一部分.
"顶点"是段之间的连接.顶点与平面上的(x,y)位置相关联,但是在同一位置可能存在多个顶点,每个顶点对应于该点处的轮廓中的每对线段.每个曲线端点(一个支点顶点)或蚂蚁遇到的曲线 - 交叉点都有一个顶点.
轮廓(在此上下文中)不是几何实体!不要把它想象成飞机上的简单封闭路径.蚂蚁可能沿着一段,走到尽头,然后回到它的方式 - 这被称为"刺",包括两个轮廓段,一个用于任一方向.或者它可能沿着曲线段的一个方向,沿着其他曲线漂移一点,然后沿着该段的另一个方向返回.
因此,即使你的曲线组中只有一条线从A到B(我假设你没有无限线)并且你的光线在P处击中它,你仍然有轮廓V0(P)-V1( A)-V2(P)-V3(B)-V0具有4个区段V0-V1,V1-V2,V2-V3,V3-V0.注意,V0和V2是不同的顶点,都位于P.
现在测试你的点是否在轮廓中.
找到光线的交叉点(源自测试点的任何光线都可以)与轮廓相交.我们只想要与轮廓交叉的数量的奇偶校验(偶数或奇数).如果奇偶校验是奇数,则该点受曲线限制,如果它甚至不是.
由于双向遍历的段对奇偶校验没有贡献,我们可以忽略它们.这是因为在双向遍历的段上总是存在偶数个交叉点,因为它们在轮廓中是两次.
例子:
考虑这个曲线集.我使用线条,所以我不太努力:
案例1 - 这一点没有限制.曲线段的轮廓使用由虚线箭头表示.光线轮廓相交奇偶校验的数量是偶数.
案例2 - 这一点是有限的.光线轮廓相交奇偶校验是奇数.
这可能是错误的:
由于各种数值原因,您无法找到轮廓.例如,您可能会错过交叉点,例如,两条曲线几乎与曲线相切.您可能会将其视为单个交叉点,但是当您执行光线交叉点奇偶校验测试时,您会看到一个交叉点,以便在不应该的情况下翻转奇偶校验.
您可能无法计算足够的导数来做出正确的转弯决策.在分析几何的情况下,情况永远不应该如此.
您的光线会击中轮廓的顶点(线段之间的连接).(请注意,单个(x,y)点可能有多个顶点.每个顶点都必须单独处理.)
在这种情况下,您必须确定顶点的传入和传出段是否位于顶点处光线的同一侧.如果它们位于同一侧,则不会影响奇偶校验.否则,平价翻转.如果其中一条曲线与顶点处的光线相切,则可能必须使用更高的导数来决定这一点.
- 线段与测试光线共线.这实际上是2的特例,但易于处理:忽略它.
有很多细节,但你应该能够处理它们.务必使用空间树来避免计算不必要的交叉点.
第二个问题的答案来自于从轮廓中移除任何双向遍历的段.这可能会产生多个子轮廓.其中一个将包含你的观点.