线段在多边形内吗？
Is a line segment within a polygon?
我正在做路径规划，车辆应该沿着一条路径穿过杂乱的环境。我的算法非常宽容，因此我只需要为以下问题提供一个布尔值答案：这条线是否在多边形内（多边形是障碍物）。
当然，要避免多边形和线的任何交集。
我在网上做了研究，但我只找到了类似的东西（以吨为单位）：
wrong cases, valid for points only, more points.
我的算法通过连接两点生成路径，生成时又检查它们不在多边形内。
逐点检查不够精确，因为我不能冒任何碰撞的风险。多边形的相交线和线是我的第一个猜测，但由于每条（无尽的）线都与另一条线相交（平行线除外），我必须检查交点是否在所有其他边缘之外。这对我来说似乎很慢，问题是，有没有更好的方法或者这是 "good" 解决方案？ [或者我如何相互检查有限长度的线段？]
经过好评，归结为：我需要一种快速检查线段与线段相交的方法。 （我知道边界框，我会先做。）
如果重要的话，我正在使用 C++。
我假设它是二维的。
大纲（quick/dirty解决方案）。
- 为直线和多边形计算 axis aligned bounding box。如果这些框不相交，则线不在多边形内。
对于凸多边形：
对于每条边：
2.1 计算它外面的法线指向（在 2d 中，它是将边缘向量旋转 90 度的问题，这是微不足道的 normal = vector2(-edgeVector.y, edgeVector.x))，但是你的边缘应该以统一的顺序排列才能工作（顺时针或逆时针）。
2.2。使用平面方程的二维版本，确定线段的两个 start/end 点是否位于边的 "outside" 处。如果 dotProduct(point - edgeStart, edgeNormal) > 0.
点是 "outside"
2.3。如果两个点都在外面，则终止循环并报告没有碰撞。
2.4。如果两个点都在平面下方，则移动到下一个 plane/edge.
2.5。否则使用插值 (endPos - startPos)* startDistance/(endDistance- startDistance) 计算交点，其中 start/end 距离计算为 distance = dotProduct(point - edgeStart, edgeNormal)
2.6。确定点是否位于边缘 (0 <= dotProduct (intersectionPoint - edgeStart, edgeEnd - edgeStart) <= dotProduct(edgeEnd - edgeStart, edgeEnd - edgeStart))。如果它位于边缘，则会发生碰撞。终止循环并报告冲突。
2.7。完成循环后，如果所有边的 start/end 点都是 "below" 平面，则报告碰撞。
2.8。报告没有碰撞。
对于凹多边形。
(optional) 你可以先计算凸包并检查碰撞。如果凸包不与线段碰撞，则不碰撞。
选取多边形外的任意点，然后（使用 2.3..2.4 步 edge/edge 碰撞）计算它与多边形相交的边数。如果数字不能被 2 整除（(edgeCount % 2) != 0），return 报告碰撞（线段位于多边形内）。不要省略这一步。
使用edge/edge碰撞（在2.2..2.3中概述）确定它是否与任何边缘相交。如果是，报告碰撞。
报告没有碰撞。
要优化 large/complex 多边形上的碰撞查询，请使用 space 分区算法（如 bsp 树、八叉树）或 sweep and prune 方法。
这是 edge/polygon 交集的简要概述（可能偶尔会出现错字）。
可能存在更快的方法并可在网络上获得。
我正在做路径规划，车辆应该沿着一条路径穿过杂乱的环境。我的算法非常宽容，因此我只需要为以下问题提供一个布尔值答案：这条线是否在多边形内（多边形是障碍物）。 当然，要避免多边形和线的任何交集。 我在网上做了研究，但我只找到了类似的东西（以吨为单位）： wrong cases, valid for points only, more points.
我的算法通过连接两点生成路径，生成时又检查它们不在多边形内。
逐点检查不够精确，因为我不能冒任何碰撞的风险。多边形的相交线和线是我的第一个猜测，但由于每条（无尽的）线都与另一条线相交（平行线除外），我必须检查交点是否在所有其他边缘之外。这对我来说似乎很慢，问题是，有没有更好的方法或者这是 "good" 解决方案？ [或者我如何相互检查有限长度的线段？]
经过好评，归结为：我需要一种快速检查线段与线段相交的方法。 （我知道边界框，我会先做。）
如果重要的话，我正在使用 C++。
我假设它是二维的。
大纲（quick/dirty解决方案）。
- 为直线和多边形计算 axis aligned bounding box。如果这些框不相交，则线不在多边形内。
对于凸多边形：
对于每条边：
2.1 计算它外面的法线指向（在 2d 中，它是将边缘向量旋转 90 度的问题，这是微不足道的
normal = vector2(-edgeVector.y, edgeVector.x))，但是你的边缘应该以统一的顺序排列才能工作（顺时针或逆时针）。2.2。使用平面方程的二维版本，确定线段的两个 start/end 点是否位于边的 "outside" 处。如果
点是 "outside"dotProduct(point - edgeStart, edgeNormal) > 0.2.3。如果两个点都在外面，则终止循环并报告没有碰撞。
2.4。如果两个点都在平面下方，则移动到下一个 plane/edge.
2.5。否则使用插值
(endPos - startPos)* startDistance/(endDistance- startDistance)计算交点，其中 start/end 距离计算为distance = dotProduct(point - edgeStart, edgeNormal)2.6。确定点是否位于边缘 (
0 <= dotProduct (intersectionPoint - edgeStart, edgeEnd - edgeStart) <= dotProduct(edgeEnd - edgeStart, edgeEnd - edgeStart))。如果它位于边缘，则会发生碰撞。终止循环并报告冲突。2.7。完成循环后，如果所有边的 start/end 点都是 "below" 平面，则报告碰撞。
2.8。报告没有碰撞。
对于凹多边形。
(optional) 你可以先计算凸包并检查碰撞。如果凸包不与线段碰撞，则不碰撞。
选取多边形外的任意点，然后（使用 2.3..2.4 步 edge/edge 碰撞）计算它与多边形相交的边数。如果数字不能被 2 整除（
(edgeCount % 2) != 0），return 报告碰撞（线段位于多边形内）。不要省略这一步。使用edge/edge碰撞（在2.2..2.3中概述）确定它是否与任何边缘相交。如果是，报告碰撞。
报告没有碰撞。
要优化 large/complex 多边形上的碰撞查询，请使用 space 分区算法（如 bsp 树、八叉树）或 sweep and prune 方法。
这是 edge/polygon 交集的简要概述（可能偶尔会出现错字）。
可能存在更快的方法并可在网络上获得。