点交叉路径
Point crossing path
我有一个问题，当一个点（显然在移动中）穿过一条直线路径时我需要发出警报，
线路径是线的复杂集合 (y=ax+b)。
假设-
- 我不知道 "Point" 会从哪一边越线。
- 行路径可能非常复杂并且包含很多行。
例如 -
- 解决这个问题的最佳方法是什么？
- 有人知道是否有算法吗？
要快速检查可能的交叉点，您可以将每个 "line" 的两个端点插入点轨迹方程（大概本身就是一条线段），形式为 px+qy+r= 0。如果 px+qy+r 的符号不同，则可能存在交集。这次预映会很快
为了让它更快，您可以考虑将线条封闭在边界框的层次结构中。一个非常简单的方法是将线的每个边界框两两分组（按遍历顺序），然后将这些组分组到 by to，依此类推。然后通过递归比较轨迹的bounding box和hierarchy中的bounding box，可以快速拒绝无数条线。
查找线/路径截距
考虑到线可以来自任何方向，路径中的线段可以是任何配置，没有简单的解决方案。您需要根据行
检查每个路径段
下图显示了AD、BD、CD三行。线 AD 和 CD 在 3 个位置截取路径，BD 在一个位置截取路径。
对于每条线段，离线段起点最近的点就是您要查找的点。
要找到这些点，我们必须先定义一个点和线段。
// point
p.x = ?
p.y = ?
// line segment contains start and end points p1, p2
l.p1 = {x, y}
l.p2 = {x, y}
寻找线段上的最小单位距离
计算每个路径段截取的线段上的单位距离（如果有）。在最小单位距离 >= 0 处截取线段的路径段将是第一个截取点。您要找的那个。
伪代码
以下显示了所需的步骤。根据线段检查每个路径段。首先检查路径是否与线段不平行。如果是这样，请检查拦截是否在路径段上。如果是这样，请检查截距是否在线段上并且是迄今为止找到的最接近线起点的截距。
// l is line segment
interceptFound = false // Semaphore to indicate point found
minUnitDist = 1 // unit dist of intercept
ix = 0 // intercept point
iy = 0
pathSeg // if needed the path segment that intercepted
vx1 = l.p2.x - l.p1.x // vector of line segment
vy1 = l.p2.y - l.p1.y
for each pathSegment // p path segment
vx2 = p.p2.x - p.p1.x // vector of path segment
vy2 = p.p2.y - p.p1.y
crossProd = vx1 * vy2 - vy1 * vx2
if crossProd != 0 // Check lines are not parallel
vx3 = l.p1.x - p.p1.x // Vector from start of l to start of p
vy3 = l.p1.y - p.p1.y
unit = (vx1 * vy3 - vy1 * vx3) / crossProd // unit dist on path segment
if unit >= 0 && unit <= 1 // Code Point A.
unit = (vx2 * vy3 - vy2 * vx3) / crossProd // unit dist on line segment
if unit >= 0 && unit <= minUnitDist // Is the intercept closest to start
interceptFound = true
minUnitDist = unit
pathSeg = p // store intercepting path segment
if interceptFound // Was a intercept found
ix = l.p1.x + vx1 * minUnitDist // Calculate intercept point
iy = l.p1.y + vy1 * minUnitDist
你可以预先计算每个路径段的矢量vx2，vy2在上面的例子中可以节省一点时间（如果路径不随时间变化）
如果 minUnitDist 为零，您也可以提前退出循环
这个比较快，不需要复杂的数据结构。大多数路径段将在 // Code Point A
处剔除
AABB 检查
如果路径段的数量非常多，您可以执行 AABB 以避免上例中的一些数学运算。如果路径点不随时间变化并且您在开始时为每个路径段计算一次边界框，这只会是一个好处
伪代码AABB校验
// l is a line segment
l.left = min(l.p1.x, l.p2.x)
l.right = max(l.p1.x, l.p2.x)
l.top = min(l.p1.y, l.p2.y)
l.bottom = max(l.p1.y, l.p2.y)
然后检查两个段是否可以拦截
// l and p are line segs with bounding boxes calculated
if l.left > p.right || l.right < p.left || l.top > p.bottom || l.bottom < p.top
// line segments do not intercept
else
// Line segments may intercept
更多边界框和Quad trees
如果您仍然发现解决方案太慢，您可以将路径段分成相关的（紧密相连的）组，并在检查组中的路径段之前对每个组进行 AABB 测试。
此外，您可以考虑使用 quad tree 来存储路径段，以进一步减少您需要测试线路的路径段数量。
我有一个问题，当一个点（显然在移动中）穿过一条直线路径时我需要发出警报， 线路径是线的复杂集合 (y=ax+b)。
假设-
- 我不知道 "Point" 会从哪一边越线。
- 行路径可能非常复杂并且包含很多行。
例如 -
- 解决这个问题的最佳方法是什么？
- 有人知道是否有算法吗？
要快速检查可能的交叉点，您可以将每个 "line" 的两个端点插入点轨迹方程（大概本身就是一条线段），形式为 px+qy+r= 0。如果 px+qy+r 的符号不同，则可能存在交集。这次预映会很快
为了让它更快，您可以考虑将线条封闭在边界框的层次结构中。一个非常简单的方法是将线的每个边界框两两分组（按遍历顺序），然后将这些组分组到 by to，依此类推。然后通过递归比较轨迹的bounding box和hierarchy中的bounding box，可以快速拒绝无数条线。
查找线/路径截距
考虑到线可以来自任何方向，路径中的线段可以是任何配置，没有简单的解决方案。您需要根据行
检查每个路径段下图显示了AD、BD、CD三行。线 AD 和 CD 在 3 个位置截取路径，BD 在一个位置截取路径。
对于每条线段，离线段起点最近的点就是您要查找的点。
要找到这些点，我们必须先定义一个点和线段。
// point
p.x = ?
p.y = ?
// line segment contains start and end points p1, p2
l.p1 = {x, y}
l.p2 = {x, y}
寻找线段上的最小单位距离
计算每个路径段截取的线段上的单位距离（如果有）。在最小单位距离 >= 0 处截取线段的路径段将是第一个截取点。您要找的那个。
伪代码
以下显示了所需的步骤。根据线段检查每个路径段。首先检查路径是否与线段不平行。如果是这样，请检查拦截是否在路径段上。如果是这样，请检查截距是否在线段上并且是迄今为止找到的最接近线起点的截距。
// l is line segment
interceptFound = false // Semaphore to indicate point found
minUnitDist = 1 // unit dist of intercept
ix = 0 // intercept point
iy = 0
pathSeg // if needed the path segment that intercepted
vx1 = l.p2.x - l.p1.x // vector of line segment
vy1 = l.p2.y - l.p1.y
for each pathSegment // p path segment
vx2 = p.p2.x - p.p1.x // vector of path segment
vy2 = p.p2.y - p.p1.y
crossProd = vx1 * vy2 - vy1 * vx2
if crossProd != 0 // Check lines are not parallel
vx3 = l.p1.x - p.p1.x // Vector from start of l to start of p
vy3 = l.p1.y - p.p1.y
unit = (vx1 * vy3 - vy1 * vx3) / crossProd // unit dist on path segment
if unit >= 0 && unit <= 1 // Code Point A.
unit = (vx2 * vy3 - vy2 * vx3) / crossProd // unit dist on line segment
if unit >= 0 && unit <= minUnitDist // Is the intercept closest to start
interceptFound = true
minUnitDist = unit
pathSeg = p // store intercepting path segment
if interceptFound // Was a intercept found
ix = l.p1.x + vx1 * minUnitDist // Calculate intercept point
iy = l.p1.y + vy1 * minUnitDist
你可以预先计算每个路径段的矢量vx2，vy2在上面的例子中可以节省一点时间（如果路径不随时间变化）
如果 minUnitDist 为零，您也可以提前退出循环
这个比较快，不需要复杂的数据结构。大多数路径段将在 // Code Point A
AABB 检查
如果路径段的数量非常多，您可以执行 AABB 以避免上例中的一些数学运算。如果路径点不随时间变化并且您在开始时为每个路径段计算一次边界框，这只会是一个好处
伪代码AABB校验
// l is a line segment
l.left = min(l.p1.x, l.p2.x)
l.right = max(l.p1.x, l.p2.x)
l.top = min(l.p1.y, l.p2.y)
l.bottom = max(l.p1.y, l.p2.y)
然后检查两个段是否可以拦截
// l and p are line segs with bounding boxes calculated
if l.left > p.right || l.right < p.left || l.top > p.bottom || l.bottom < p.top
// line segments do not intercept
else
// Line segments may intercept
更多边界框和Quad trees
如果您仍然发现解决方案太慢，您可以将路径段分成相关的（紧密相连的）组，并在检查组中的路径段之前对每个组进行 AABB 测试。
此外，您可以考虑使用 quad tree 来存储路径段，以进一步减少您需要测试线路的路径段数量。