寻找算法来确定一个点是否指向圆弧的 left/right
Looking for algorithm that will determine if a point is to the left/right of an arc
我目前需要找到一个算法来确定一个点是在圆弧的右边还是左边。
这是以下算法的扩展以包括弧：
// isLeft(): tests if a point is Left|On|Right of an infinite line.
// Input: three points P0, P1, and P2
// Return: >0 for P2 left of the line through P0 and P1
// =0 for P2 on the line
// <0 for P2 right of the line
// See: Algorithm 1 "Area of Triangles and Polygons"
inline int
isLeft( Point P0, Point P1, Point P2 )
{
return ( (P1.x - P0.x) * (P2.y - P0.y)
- (P2.x - P0.x) * (P1.y - P0.y) );
}
//===================================================================
此代码是从站点检索到的：
http://geomalgorithms.com/a03-_inclusion.html
这是用于绕数算法的。我的目标是扩展此算法以包括弧线而不仅仅是线。
这里不太像post：How to determine whether a point (X,Y) is contained within an arc section of a circle (i.e. a Pie slice)?
在提到的post中，作者试图判断该点是否位于圆弧的中心角内。我的有点不同，因为一个点可以超出半径但弧仍然包含有问题的点。
我创建了一张我试图描述的图片。请注意，我无论如何都不是抽屉。无论如何，有问题的弧线是绿色的。我创建了两条平行线，分别在起点和终点节点与圆弧相交。这些线是红色的。请原谅我的绘画技巧。尽管图中的红线看起来不平行，但它们应该是平行的。该图仅供参考。我在此 post 中定义线是平行的。这个 post 取代了图中的任何内容。这意味着即使图中没有表示线相互平行，但实际上它们应该是相互平行的，因为我在 post 中已经说明了这一点。我需要帮助来提出一种算法来确定一个点是否位于蓝色区域内。请注意，红线可以无限延伸。为了便于讨论，我在任意点结束线条以在蓝色区域着色。
如果该点位于蓝色区域内，我认为这是包含该点的弧。作为旁注，我正在用 C++ 编写此算法（因此使用 c++ 标记）
我说的圆弧类型是圆的圆弧，有起点和终点节点，圆弧角度，圆心和半径。
编辑：
Yves 和 MBo 的两个答案在我试图解释的内容中包含了更好的图片。请参考这些图片。 MBo 包含更好的图片。
正如 Yves 所描述的，我正在尝试测试一个点是否位于由圆弧和两条平行线分隔的半无限平板内。这些线与起始节点和结束节点相交。请参阅 MBo 图以获得更清晰的图片。 Yves第一张画的也是一张清晰的图。我正在测试该点是否位于阴影区域。
我使用术语左和右作为视角。很抱歉，我在第一次创建 post 时没有清楚地解释这一点。想象一下，您正以逆时针方向沿着这条弧线行进。第一个节点将是最右边的节点，结束节点将是最左边的节点。从旅行者的角度来看，此弧（或半无限平板）包含的点将位于弧的左侧。右边的任何点都在弧线之外。
提示：
如果您的最终目标是实现加宽数算法，那么您要测试的是该点是否位于由两条平行线（比如水平线，这样 Yb < Y < Ye ) 和圆弧。
圆的等式为 (X - Xc)² + (Y - Yc)² = R²，从中得出条件 X < Xc + √(R²-(Y - Yc)²)。为了方便起见，您可以拆分所有弧线，使它们只与水平线相交一次。
在其他配置中，您将不得不考虑另一侧的交叉路口，X < Xc - √(R²-(Y - Yc)²)，但我将完整的讨论留给您。
让你有圆心C，半径R，端点A和B。
如果我理解正确的话：
如果P点和C点相对于AB线在同一个半平面内：
检查点P在AB线上的投影是否在AB线段的界限内
else（如果点P和中心C在不同的半平面）：
检查 P 到 C 的距离不超过 R
if Sign(CrossProduct(P-A,B-A)) = Sign(CrossProduct(C-A,B-A))
Result = DotProduct(P-A, B-A) / DotProduct(B-A, B-A) in range 0..1
else
Result = DotProduct(P-C, P-C) <= R^2
例如K点和H点符号条件为真，H点结果为真。I和J点符号条件为假，J点结果为真
我目前需要找到一个算法来确定一个点是在圆弧的右边还是左边。 这是以下算法的扩展以包括弧：
// isLeft(): tests if a point is Left|On|Right of an infinite line.
// Input: three points P0, P1, and P2
// Return: >0 for P2 left of the line through P0 and P1
// =0 for P2 on the line
// <0 for P2 right of the line
// See: Algorithm 1 "Area of Triangles and Polygons"
inline int
isLeft( Point P0, Point P1, Point P2 )
{
return ( (P1.x - P0.x) * (P2.y - P0.y)
- (P2.x - P0.x) * (P1.y - P0.y) );
}
//===================================================================
此代码是从站点检索到的： http://geomalgorithms.com/a03-_inclusion.html
这是用于绕数算法的。我的目标是扩展此算法以包括弧线而不仅仅是线。
这里不太像post：How to determine whether a point (X,Y) is contained within an arc section of a circle (i.e. a Pie slice)?
在提到的post中，作者试图判断该点是否位于圆弧的中心角内。我的有点不同，因为一个点可以超出半径但弧仍然包含有问题的点。
我创建了一张我试图描述的图片。请注意，我无论如何都不是抽屉。无论如何，有问题的弧线是绿色的。我创建了两条平行线，分别在起点和终点节点与圆弧相交。这些线是红色的。请原谅我的绘画技巧。尽管图中的红线看起来不平行，但它们应该是平行的。该图仅供参考。我在此 post 中定义线是平行的。这个 post 取代了图中的任何内容。这意味着即使图中没有表示线相互平行，但实际上它们应该是相互平行的，因为我在 post 中已经说明了这一点。我需要帮助来提出一种算法来确定一个点是否位于蓝色区域内。请注意，红线可以无限延伸。为了便于讨论，我在任意点结束线条以在蓝色区域着色。
如果该点位于蓝色区域内，我认为这是包含该点的弧。作为旁注，我正在用 C++ 编写此算法（因此使用 c++ 标记）
我说的圆弧类型是圆的圆弧，有起点和终点节点，圆弧角度，圆心和半径。
编辑：
Yves 和 MBo 的两个答案在我试图解释的内容中包含了更好的图片。请参考这些图片。 MBo 包含更好的图片。
正如 Yves 所描述的，我正在尝试测试一个点是否位于由圆弧和两条平行线分隔的半无限平板内。这些线与起始节点和结束节点相交。请参阅 MBo 图以获得更清晰的图片。 Yves第一张画的也是一张清晰的图。我正在测试该点是否位于阴影区域。
我使用术语左和右作为视角。很抱歉，我在第一次创建 post 时没有清楚地解释这一点。想象一下，您正以逆时针方向沿着这条弧线行进。第一个节点将是最右边的节点，结束节点将是最左边的节点。从旅行者的角度来看，此弧（或半无限平板）包含的点将位于弧的左侧。右边的任何点都在弧线之外。
提示：
如果您的最终目标是实现加宽数算法，那么您要测试的是该点是否位于由两条平行线（比如水平线，这样 Yb < Y < Ye ) 和圆弧。
圆的等式为 (X - Xc)² + (Y - Yc)² = R²，从中得出条件 X < Xc + √(R²-(Y - Yc)²)。为了方便起见，您可以拆分所有弧线，使它们只与水平线相交一次。
在其他配置中，您将不得不考虑另一侧的交叉路口，X < Xc - √(R²-(Y - Yc)²)，但我将完整的讨论留给您。
让你有圆心C，半径R，端点A和B。
如果我理解正确的话：
如果P点和C点相对于AB线在同一个半平面内：
检查点P在AB线上的投影是否在AB线段的界限内
else（如果点P和中心C在不同的半平面）：
检查 P 到 C 的距离不超过 R
if Sign(CrossProduct(P-A,B-A)) = Sign(CrossProduct(C-A,B-A))
Result = DotProduct(P-A, B-A) / DotProduct(B-A, B-A) in range 0..1
else
Result = DotProduct(P-C, P-C) <= R^2
例如K点和H点符号条件为真，H点结果为真。I和J点符号条件为假，J点结果为真