Алгоритм числа обмоток и точка на границе / краю выпуклой

Мне нужен алгоритм, который может определить, находится ли точка внутри / снаружи или на границе (краю) выпуклой оболочки (C / C ++).

Выпуклая оболочка описывается как массив точек X, Y, целое число, соединение от i до i + 1.

В настоящее время я использую алгоритм извилистых чисел, описанный здесь: http://geomalgorithms.com/a03-_inclusion.html Это функция "wn_PnPoly ()".

Можно ли и как сделать так, чтобы алгоритм числа витков определял, лежит ли точка точно на границе (ребре) выпуклости? Есть ли другой алгоритм для этого? (Необходимо работать над целыми числами).


c++ algorithm point-in-polygon convex
person user3157855    schedule 08.06.2016    source источник
comment
Просто прочтите реализацию функции. Вы найдете тест, находится ли точка слева / справа / слева от края.   -  person    schedule 08.06.2016

Ответы (2)


arrow_upward
7
arrow_downward

Нашел решение:

int wn_PnPoly2(Point P, vector<Point> V, int n)
{
    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
            {
                int l = isLeft(V[i], V[i + 1], P);
                if (l > 0)  // P left of  edge
                    ++wn;            // have  a valid up intersect
                else if (l == 0) // boundary
                    return 0;
            }
        }
        else {                        // start y > P.y (no test needed)
            if (V[i + 1].Y <= P.Y)     // a downward crossing
            {
                int l = isLeft(V[i], V[i + 1], P);
                if (l < 0)  // P right of  edge
                    --wn;            // have  a valid down intersect
                else if (l == 0)
                    return 0;
            }
        }
    }
    return wn;
}
person user3157855    schedule 08.06.2016
comment
Отсутствует функция isLeft (), но ее можно найти и в других источниках. Например, здесь: forum.codeguru.com/ - person st6mm; 23.04.2017

arrow_upward
-1
arrow_downward

Я не знаю алгоритма числа обмоток, но чтобы определить, лежит ли точка на одном из краев, вы можете просто пропустить все края выпуклой оболочки и выполнить следующую проверку:

Если точки u, v являются последовательными точками на выпуклой оболочке, а p - рассматриваемая точка, то ли,

p - u = lambda*(v - u), где lambda - любой скаляр от 0 до 1.

person Abhishek Bansal    schedule 08.06.2016