RomanDillerNsk
@RomanDillerNsk
JavaScript

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

Коллеги, доброго времени суток, в продолжении ранней темы, столкнулся, видимо с нехваткой знаний в геометрии. Суть такая, рисую на карте полигон (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);

        });


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

5cef6d857ad13319012953.jpeg

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы