Как вычислить вхождение точек в полигон?

Question

[Роман Андреевич]

Коллеги, доброго времени суток, в продолжении ранней темы, столкнулся, видимо с нехваткой знаний в геометрии. Суть такая, рисую на карте полигон (leaflet), из него получаю углы, получаю bbox полигона, а дальше нужно отсеить точки из bbox, которые не входят в полигон, вот собственно код:

Получаю точки bbox:

return new Promise((resolve, reject) => {

            data.coords = [];

            let RECOMMEND_SIZE = 20; // шаг
            let BIAS_TO_CENTER = 0.5;

            let x_min = data.bounds.nw[0];
            let x_max = data.bounds.se[0];
            let y_min = data.bounds.nw[1];
            let y_max = data.bounds.se[1];

            let x_side_len = x_max - x_min;
            let y_side_len = y_max - y_min;

            let x_total_count = Math.round(data.width / RECOMMEND_SIZE);
            let y_total_count = Math.round(data.height / RECOMMEND_SIZE);

            let x_closest_size = x_side_len / x_total_count;
            let y_closest_size = y_side_len / y_total_count;

            for (let x = 0; x < x_total_count; x++) {

                for (let y = 0; y < y_total_count; y++) {

                    let coord_x = x_min + x_closest_size * (x + BIAS_TO_CENTER);
                    let coord_y = y_min + y_closest_size * (y + BIAS_TO_CENTER);

                    data.coords.push([coord_x, coord_y]);

                }

            }

            resolve(data);

        });

Далее пытаюсь отсеить точки (код взят от сюда ):

return new Promise((resolve, reject) => {

            data.polygonCoords = [];

            data.coords.forEach(item => {

                let x = item[0];
                let y = item[1];

                let xp = data.conners.x;
                let yp = data.conners.y;

                let xLength = xp.length;
                let j = xLength - 1;

                for (let i = 0; i < xLength; i++) {

                    if ((((yp[i]<=y) && (y<yp[j])) || ((yp[j]<=y) && (y<yp[i]))) && (x > (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i])) {

                        data.polygonCoords.push([x,y]);

                    }

                    j = i;

                }

            });

            resolve(data);

        });

Но в итоге, получаю такую картину:



Кто сталкивался с решением таких задач, прошу помощи или совета! заранее благодарю

Comments

[Сергей Соколов]

Аналогичный вопрос на StackOverflow и ответ с реализацией алгоритма прокладки лучей? (ray casting)

Answer 1

[TheRonCronix]

Идея следующая.
1. Обычно, полигон, если он не выпуклый, разбивают на выпуклые (на треугольники, проще говоря). Далее, любой полигон может быть представлен как пересечение трех и более полуплоскостей (смотря соклько сторон у вашего полигона).
2. Вы можете вычислить отношение точки к направленному вектору, т.е. с какой стороны полуплоскости лежит точка: слева или справа, с учетом напрвления вектора, делящего плоскость на две полуплоскости. Т.к. полигон это пересечение полуплоскостей, то определить, попадает ли в него точка, можно убедившись, что точка лежит во всех полуплоскостях образующих полигон.
3. Согласно вышесказанному, мы можем написать функцию, которая определяет, что точка лежит справа от вектора, образующего полуплоскость. Мы представим грани полигона векторами и будем обходить полигон по часовой стрелке, так что "справа от вектора" - это всегда полуплоскость, которая "внутри полигона". Пройдясь по всем граням-векторам и убедившись, что точка лежит "справа" от них всех, мы сделаем вывод, что точка лежит внутри полигона.
4. Отношение "справа/слева" вычисляется векторным произведением (если мне помять не изменяет).