Алгоритм числа обмоток не дает ожидаемого результата - PullRequest
Новая
       63

Алгоритм числа обмоток не дает ожидаемого результата

1 голос
/ 27 апреля 2020

Итак, я реализовал очень неоптимизированную версию алгоритмов числа обмотки и числа пересечения, найденных в http://geomalgorithms.com/a03-_inclusion.html, но я сталкивался со случаем, когда алгоритм числа обмоток не дает ожидаемого результат.

Я создал многоугольник и три точки в виде графика здесь . Для 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));
    }

Я что-то упускаю здесь очевидное? Почему алгоритм числа пересечений успешно в этом случае, в то время как число обмоток терпит неудачу?

1 Ответ

0 голосов
/ 27 апреля 2020

Эти два метода не являются одним и тем же критерием.

В ненулевом или правиле намотки направление сегментов линии имеет значение. Алгоритм проверяет, пересекает ли отрезок линии исходящий луч слева или справа, и подсчитывает, как часто происходит каждый случай. Точка считается противоположной только в том случае, если

число пересечений или четно-нечетное правило просто подсчитывает частоту пересечения линии. Каждый раз, когда вы пересекаете линию, вы go либо изнутри наружу, либо наоборот, так что четное число пересечений означает, что точка находится снаружи.

Если вы go справа от P1 в вашем примере, вы пересекайте две линии, поэтому четно-нечетное правило говорит вам, что P1 не находится в многоугольнике. Но эти две линии имеют одинаковую ориентацию: если ваша общая фигура нарисована по часовой стрелке, обе линии нарисованы сверху вниз. По словам статьи, которую вы связали, многоугольник дважды обматывает P1. Согласно правилу намотки, P1 является частью вашего многоугольника. Ваша программа показывает правильное поведение.

Векторные графические программы и форматы различают guish между этими двумя правилами. Например, SVG имеет атрибут fill-rule, где вы можете установить поведение. В Postscript есть операторы fill и eofill для заполнения путей правилом намотки и четно-нечетным правилом соответственно. По умолчанию обычно используется правило намотки, поэтому разработчики должны позаботиться о правильной ориентации своих путей.

...