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

Поэтому я реализовал очень неоптимизированную версию алгоритмов 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));
    }

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


person Ian Clayman    schedule 27.04.2020    source источник


Ответы (1)


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

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

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

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

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

person M Oehm    schedule 27.04.2020
comment
Теперь я вижу, что пропустил концепцию двойной обмотки. Однако я заметил еще один пограничный случай, с которым я не уверен, как справиться: точка (10,5), которая будет существовать на самой правой линии многоугольника. Оба алгоритма не могут рассматривать эту точку как содержащуюся внутри многоугольника, но интуитивно так и должно быть. Есть ли материал о том, как улучшить алгоритм для обеспечения надежности, в том числе для случая, когда многоугольник является сплайном Безье? - person Ian Clayman; 27.04.2020
comment
Это также желаемое поведение: правило чет-нечет не учитывает (10, 5), потому что оно пересекает две линии, а правило намотки не учитывает его, потому что две линии пересекают луч в разных направлениях. Если вы рисуете большой внешний квадрат по часовой стрелке, вы также проходите верхний левый внутренний квадрат по часовой стрелке, но нижний правый внутренний квадрат вы проходите против часовой стрелки. - person M Oehm; 27.04.2020
comment
Настоящие крайние случаи - это когда ваш луч и линии коллинеарны, например. (3, 8), или где они просто пересекаются в одном из узлов многоугольника. Это становится еще сложнее, когда вам приходится иметь дело с числами с плавающей запятой. Путь также может содержать кривые, но имейте в виду, что может быть несколько точек, в которых луч пересекает кривую Безье. Эти проблемы лежат в основе всей векторной графики, поэтому термины «точка в полигоне», «рендеринг полигонов», «отсечение полигонов» и т. д. могут оказаться полезными для вашей поисковой системы. - person M Oehm; 27.04.2020
comment
Эта статья - Проблема точки в многоугольнике для произвольных многоугольников - хорошо обсуждается взаимосвязь между четно-нечетными и извилистыми числовыми методами определения внутренней части многоугольника. Усовершенствованный алгоритм вычисления точки в многоугольнике также очень полезен. - person RaffleBuffle; 27.04.2020