2

我有一个问题，我需要验证一个点是否越过线路径，
线路径是线（y = ax + b）的集合。
有谁知道一些已知的算法？

所以我这样解决它：我在路径的起点和终点添加了 2 个点 - 所以现在它是一个多边形，我将 90 度的 2 个点添加到固定距离的点上。我使用了射线算法。

4

4 回答 4

1

有一些简单的算法可以知道一个点是在多边形内部还是外部：http ://en.wikipedia.org/wiki/Point_in_polygon 这可以通过将多边形的某些边缘推到无穷大来适应线路径设置（实际上，你可以把你的线路径放在一个大盒子里，然后把由盒子的右边（或左边，如你所愿）边的部分形成的多边形放在一边）。

于 2013-07-24T14:25:47.590 回答
1

给定一个输入点 (x_1, y_1) ，并且您的直线的形式为y = ax + b，那么您可以通过将 x_1 放入直线方程来判断输入点的位置：

if y_1 == a * x_1 + b then (x_1, y_1) is on the line
if y_1 < a * x_1 + b then (x_1, y_1) locates below the line
if y_1 > a * x_1 + b then (x_1, y_1) locates above the line

因此，您可以通过跟踪该点的上述结果来判断该点是否已越线。

于 2013-07-24T16:29:38.583 回答
0

所以我这样解决它：我在路径的起点和终点添加了 2 个点 - 所以现在它是一个多边形，我将 90 度的 2 个点添加到固定距离的点上。我使用了射线算法。

编辑：它并不总是 90 度，它取决于点起点和终点之间的角度

于 2013-07-25T13:23:57.523 回答
0

我知道两种方法：

  1. 在多边形算法中使用适应点
    • 你必须知道哪条路是哪边（交叉/非交叉边）
    • 所以创建一个从线补丁指向交叉侧的向量目录
    • 它可以是平均法线（或起点线的法线）
    • 从测试点向dir方向投射光线
    • 计算与线补丁的交叉点
    • 如果相交恰好发生在两条线的连接点上，则只计算一次
    • 最后，如果计数为非零且奇数，则点已越线补丁
    • 这很容易出错，但有点慢
    • 见左图
  2. 如果您的线补丁不是太复杂的形状，请使用缠绕规则（标量向量乘法）
    • 线补丁线必须在一个方向从开始到结束！
    • 从补丁中选择接近您的点的行（1-5 应该足够了）
    • 理想情况下在右图的相同高度
    • 当然实际上它可以旋转，所以按距离选择线（不需要sqrt它）
    • 计算选定行的点积，如下所示：
    • 线 P0,P1，点 P -> 点积 = ((P1-P0).(P-P1))
    • 2个向量的点积((x0,y0,z0).(x1,y1,z1))=(x0*x1+y0*y1+z0*z1)
    • 结果的极性表示绕线方向 CW/CCW
    • 如果所有绕组都正确，则该点不交叉
    • 如果线块形状很复杂，那么如果点太靠近它就会出现问题
    • 在这种情况下，仅测试具有相同“高度”的行或使用方法 1。
    • 获取“高度”计算点与线方向起点之间的距离
    • 如果它从零到行的大小，则可以，否则不要使用它
    • 也可以用法向量到线方向的点积来完成

线补丁交叉

于 2013-10-05T08:10:08.143 回答