我有一个问题，我已经尝试解决了几天。我想知道我是否能够从社区获得一些帮助。
为了检测一个点是否在多边形中，我使用了绕组数方法。该算法基于我在此站点上找到的内容：http: //geomalgorithms.com/a03-_inclusion.html。简而言之，该算法将返回一个结果，该结果将指示该点位于线段的左侧还是右侧。对于直线的逆时针方向，正值表示该点位于直线的左侧，负值表示该点位于直线的右侧。符号切换为顺时针方向。如果“lefts”的数量大于“rights”的数量，则该点位于多边形内部。仅考虑端点在点之间的线以加快算法速度。
现在我的多边形（我松散地使用这个术语）由弧和线段组成。这些多边形很简单，不会自行循环。多边形可以是凸的或凹的。作为旁注，我的程序中的弧表示为圆弧。
绕组数算法非常适用于线段。但是当我们谈到弧线时，事情可能会稍微复杂一些。我目前的实现是考虑弧线下方的任何点都在弧线内。（注：我的算法实现源码在文末给出）
这种实现大部分都有效，但从下图中，红点将被视为误报。缠绕数算法将指示红点在多边形内部，而它显然不在多边形内部。
从算法中，第 1 行表示该点位于左侧，第 4 行表示该点位于右侧。但是弧段 2 将指示该点也在左侧，因此该点位于多边形内部。
现在，使用弧的实现有另一个错误，算法将返回假阴性。下面是几何图形，其中中心的点位于多边形的外部，而侧面的点位于多边形内部。
该多边形仅由弧组成。
几天来，我一直在考虑不同的实现，但到目前为止，还没有任何结果。关于弧的另一件事是它们都处于逆时针方向。圆弧是凹的还是凸的取决于选择哪个节点作为第一个节点。
我正在考虑回到光线交叉算法，但我想看看我是否可以先让它工作。如果我有两种不同的直线和圆弧算法，我很好（事实上，我认为我会的）。理想情况下，我想使用缠绕数算法，但我愿意接受其他解决方案。
代码：
如果您想查看更完整的解决方案，我将发布代码源文件的链接。我还发布了与说服相关的片段。如果您对代码有任何疑问，请随时提出。谢谢
多边形测试点：https ://github.com/philm001/Omni-FEM/blob/master/Include/common/ClosedPath.h
bool pointInContour(wxRealPoint point)
{
int windingNumber = 0;
bool isFirstRun = true;
bool reverseWindingResult = false;
double additionTerms = 0;
double subtractionTerms = 0;
// First, the algorithm will need to ensure that all of the lines are oriented in either CCW or CW.
// Each contour, the order of the lines is CCW or CW but the order of the nodes is different.
// For example, the start node of the 1st line could be "connected" to the end node of the next line.
// In which case, we need to swap the nodes of the 1st line.
for(auto lineIterator = p_closedPath.begin(); lineIterator != p_closedPath.end(); lineIterator++)
{
auto nextLineIterator = lineIterator + 1;
if(nextLineIterator == p_closedPath.end())
nextLineIterator = p_closedPath.begin();
if(isFirstRun)
{
if(*(*lineIterator)->getSecondNode() != *(*nextLineIterator)->getFirstNode())
{
if(*(*lineIterator)->getFirstNode() == *(*nextLineIterator)->getFirstNode())
(*lineIterator)->swap();
else if(*(*lineIterator)->getFirstNode() == *(*nextLineIterator)->getSecondNode())
{
(*lineIterator)->swap();
(*nextLineIterator)->swap();
}
else if(*(*lineIterator)->getSecondNode() == *(*nextLineIterator)->getSecondNode())
(*nextLineIterator)->swap();
}
isFirstRun = false;
}
else
{
if(*(*lineIterator)->getSecondNode() == *(*nextLineIterator)->getSecondNode())
(*nextLineIterator)->swap();
}
/*
* This is the actual shoelace algorithm that is implemented. In short, we have two terms, addition terms
* and subtraction terms. THe addition terms are the summation of the Xpoint of the first node multiplied by
* the Ypoint of the second node for all edges (arcs are a special case)
*
* The subtraction term is the summation of the Xpoint of the second node multiplied by the
* Ypoint of the first node (arcs are a special case)
*/
if((*lineIterator)->isArc())
{
/* This algorithm is not being used to accurately determine the arc within a closed contour
* with that said, we only need to approximately determine the area. For arcs, we shall draw
* a line from the first node to the mid point and then from the mid point to the second node.
* We will use these two lines as the calculation for the shoelace algorithm.
*/
additionTerms += ((*lineIterator)->getFirstNode()->getCenter().x) * ((*lineIterator)->getMidPoint().y);
subtractionTerms += ((*lineIterator)->getMidPoint().x) * ((*lineIterator)->getFirstNode()->getCenter().y);
additionTerms += ((*lineIterator)->getMidPoint().x) * ((*lineIterator)->getSecondNode()->getCenter().y);
subtractionTerms += ((*lineIterator)->getSecondNode()->getCenter().x) * ((*lineIterator)->getMidPoint().y);
}
else
{
additionTerms += ((*lineIterator)->getFirstNode()->getCenter().x) * ((*lineIterator)->getSecondNode()->getCenter().y);
subtractionTerms += ((*lineIterator)->getSecondNode()->getCenter().x) * ((*lineIterator)->getFirstNode()->getCenter().y);
}
}
// Next, we need to run the shoe-lace algorithm to determine if the ordering is CCW or CW. If CW, then we will need to swap
// the start node and end node of all of the edges in order to ensure the polygon edge is in CCW
double shoelaceResult = additionTerms - subtractionTerms;
if(shoelaceResult < 0)
reverseWindingResult = true;
// Now we can perform the winding number algorithm
for(auto lineIterator = p_closedPath.begin(); lineIterator != p_closedPath.end(); lineIterator++)
{
if((*lineIterator)->isArc() && (*lineIterator)->getSwappedState())
(*lineIterator)->swap();
double isLeftResult = (*lineIterator)->isLeft(point);
if(!(*lineIterator)->isArc())
{
if(reverseWindingResult)
isLeftResult *= -1;
if((*lineIterator)->getFirstNode()->getCenterYCoordinate() <= point.y)
{
if((*lineIterator)->getSecondNode()->getCenterYCoordinate() > point.y)
{
if(isLeftResult > 0)
windingNumber++;
else if(isLeftResult < 0)
windingNumber--;
}
}
else if((*lineIterator)->getSecondNode()->getCenterYCoordinate() <= point.y)
{
if(isLeftResult < 0)
windingNumber--;
else if(isLeftResult > 0)
windingNumber++;
}
}
else
{
if((*lineIterator)->getSwappedState())
{
isLeftResult *= -1;
// For arcs, we need to preserve the orientation of the first and second
// node for drawing purposes. Lines do not matter as much for drawing but arcs,
// it matters
(*lineIterator)->swap();
}
if(isLeftResult > 0)
windingNumber++;
else
windingNumber--;
}
}
if(windingNumber > 0)
return true;
else
return false;
}
IsLeft 函数植入（代码从第 896 行开始）：https ://github.com/philm001/Omni-FEM/blob/master/Include/UI/geometryShapes.h
double isLeft(wxRealPoint point)
{
if(!p_isArc)
{
return ((_secondNode->getCenterXCoordinate() - _firstNode->getCenterXCoordinate()) * (point.y - _firstNode->getCenterYCoordinate())
- (point.x - _firstNode->getCenterXCoordinate()) * (_secondNode->getCenterYCoordinate() - _firstNode->getCenterYCoordinate()));
}
else
{
double result = 0;
if(isSameSign(crossProduct(point - _firstNode->getCenter(), _secondNode->getCenter() - _firstNode->getCenter()),
crossProduct(this->getCenter() - _firstNode->getCenter(), _secondNode->getCenter() - _firstNode->getCenter())))
{
result = dotProduct(point - _firstNode->getCenter(), _secondNode->getCenter() - _firstNode->getCenter()) /
dotProduct(_secondNode->getCenter() - _firstNode->getCenter(), _secondNode->getCenter() - _firstNode->getCenter());
if(result >= 0 && result <= 1)
return 1.0;
else
return -1.0;
}
else
{
result = dotProduct(point - this->getCenter(), point - this->getCenter());
if(result <= pow(_radius, 2))
return 1.0;
else
return -1.0;
}
}
}