Поэтому я реализовал очень неоптимизированную версию алгоритмов Winding Number и Crossing Number, которые можно найти на http://geomalgorithms.com/a03-_inclusion.html, но я столкнулся со случаем, когда алгоритм Winding Number не дал ожидаемого результата.
Я создал многоугольник и три точки, как показано здесь. Для P0 и P2 оба алгоритма ведут себя предсказуемо. Однако для точки P1 (точки, содержащейся в «нулевом пространстве» в границах многоугольника) алгоритм числа пересечений завершается успешно, в то время как алгоритм числа витков не может распознать точку как не содержащуюся в многоугольнике.
Это реализованный алгоритм:
int wn_PnPoly(Vector2 P, Vector2[] V)
{
int n = V.Length - 1;
int wn = 0; // the winding number counter
// loop through all edges of the polygon
for (int i = 0; i < n; i++)
{ // edge from V[i] to V[i+1]
if (V[i].y <= P.y)
{ // start y <= P.y
if (V[i + 1].y > P.y) // an upward crossing
if (isLeft(V[i], V[i + 1], P) > 0) // P left of edge
++wn; // have a valid up intersect
}
else
{ // start y > P.y (no test needed)
if (V[i + 1].y <= P.y) // a downward crossing
if (isLeft(V[i], V[i + 1], P) < 0) // P right of edge
--wn; // have a valid down intersect
}
}
return wn;
}
float isLeft(Vector2 P0, Vector2 P1, Vector2 P2)
{
return ((P1.x - P0.x) * (P2.y - P0.y)
- (P2.x - P0.x) * (P1.y - P0.y));
}
Я пропустил что-то очевидное здесь? Почему в этом случае алгоритм числа пересечений срабатывает, а число намотки терпит неудачу?