c++ - 寻找算法来确定一个点是否在圆弧的左侧/右侧

Question

我目前需要找到一个算法来确定一个点是在圆弧的右侧还是左侧。 这是以下算法的扩展以包含弧:

 // 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

这是用于绕组数算法。我的目标是扩展此算法以包括弧线而不仅仅是线。

这里的帖子不太像:How to determine whether a point (X,Y) is contained within an arc section of a circle (i.e. a Pie slice)?

在提到的帖子中，作者试图确定该点是否位于圆弧的中心角内。我的略有不同，因为点可以超出半径但弧仍然包含所讨论的点。

我创建了一张我试图描述的图片。请注意，我无论如何都不是抽屉。无论如何，有问题的弧线是绿色的。我创建了两条平行线，分别在起点和终点节点与圆弧相交。这些线是红色的。请原谅我的绘画技巧。尽管图中的红线看起来不平行，但它们应该是平行的。该图仅供引用。我在这篇文章中定义线是平行的。此处的帖子将取代图中的任何内容。这意味着即使绘图没有表明这些线彼此平行，但实际上它们应该是彼此平行的，因为我在帖子中已经说明了这一点。我需要帮助来提出一种算法来确定一个点是否位于蓝色区域内。请注意，红线可以无限延伸。为了便于讨论，我在任意点结束线条以在蓝色区域着色。

如果该点位于蓝色区域内，我认为这是包含该点的弧。作为旁注，我正在用 C++ 编写此算法(因此使用 c++ 标记)

我说的圆弧类型是圆的圆弧，有起点和终点节点、弧角、圆心和半径。

编辑:

Yves 和 MBo 的两个答案在我试图解释的内容中包含了更好的图片。请引用这些图片。 MBo 包含更好的图片。

正如 Yves 所描述的，我正在尝试测试一个点是否位于由圆弧和两条平行线分隔的半无限平板内。这些线与起始节点和结束节点相交。请参阅 MBo 图以获得更清晰的图片。 Yves第一张画的也是一张清晰的图。我正在测试该点是否位于阴影区域。

我使用术语左和右作为视角。很抱歉，我第一次创建帖子时没有清楚地解释这一点。想象一下，您正以逆时针方向沿着这条弧线行进。第一个节点将是最右边的节点，结束节点将是最左边的节点。从旅行者的角度来看，此弧(或半无限平板)包含的点将位于弧的左侧。右边的任何点都在圆弧之外。

Answer 1

提示:

如果您的最终目标是实现加宽数算法，那么您要测试的是该点是否位于由两条平行线(例如水平线，即 Yb < Y < Ye )和圆弧分隔的半无限平板内.

圆的方程是(X - Xc)² + (Y - Yc)² = R² , 从中得出条件 X < Xc + √(R²-(Y - Yc)²) .为方便起见，您可以拆分所有弧线，使它们只与水平线相交一次。

在其他配置中，您将不得不考虑另一侧的交叉路口，X < Xc - √(R²-(Y - Yc)²) ，但我将完整的讨论留给您。