Определение вхождения точки в полигон

Определение принадлежности точки полигону — одна из базовых геометрических операций в геоинформационных системах, картографических приложениях и сервисах пространственного анализа. Задача заключается в проверке, находится ли заданная точка внутри контура полигона, на его границе или за его пределами.

В экосистеме MapLibre GL JS такая операция часто требуется при:

  • обработке кликов пользователя по карте;
  • определении административной зоны по координатам;
  • проверке попадания объекта в выделенную область;
  • пространственной фильтрации данных;
  • реализации геозон и геофенсинга;
  • анализе пользовательских маршрутов.

Поскольку MapLibre GL JS отвечает главным образом за визуализацию карты, для геометрических вычислений обычно используются собственные алгоритмы или дополнительные библиотеки, работающие с форматом GeoJSON.

Постановка задачи

Имеется полигон:

const polygon = [
    [30, 10],
    [40, 40],
    [20, 40],
    [10, 20],
    [30, 10]
];

И точка:

const point = [25, 25];

Необходимо определить:

  • находится ли точка внутри полигона;
  • лежит ли она на границе;
  • находится ли вне полигона.

Графически задача выглядит следующим образом:

      *
     / \
    /   \
   /  •  \
  /       \
 *---------*

где:

  • вершины образуют полигон;
  • символ • представляет тестируемую точку.

Представление полигона в GeoJSON

В большинстве случаев данные в MapLibre GL JS представлены в формате GeoJSON.

Полигон описывается объектом типа Polygon.

const polygonFeature = {
    type: "Feature",
    geometry: {
        type: "Polygon",
        coordinates: [[
            [30, 10],
            [40, 40],
            [20, 40],
            [10, 20],
            [30, 10]
        ]]
    }
};

Точка:

const pointFeature = {
    type: "Feature",
    geometry: {
        type: "Point",
        coordinates: [25, 25]
    }
};

Координаты полигона всегда содержат массив колец.

Для простого полигона структура выглядит так:

coordinates: [
    [
        [x1, y1],
        [x2, y2],
        ...
    ]
]

Первое кольцо является внешним контуром.

Алгоритм Ray Casting

Самый распространённый способ проверки попадания точки внутрь полигона — алгоритм пересечения лучей (Ray Casting Algorithm).

Основная идея:

  1. Из точки проводится горизонтальный луч вправо.
  2. Подсчитывается количество пересечений луча с рёбрами полигона.
  3. Если число пересечений нечётное — точка внутри.
  4. Если число пересечений чётное — точка снаружи.

Пример:

        *
       /|
      / |
     /  |
 •------|-------->
     \  |
      \ |
       \|
        *

Луч начинается в тестируемой точке и продолжается бесконечно вправо.

Реализация Ray Casting на JavaScript

Простейшая реализация:

function isPointInsidePolygon(point, polygon) {
    const [x, y] = point;

    let inside = false;

    for (
        let i = 0, j = polygon.length - 1;
        i < polygon.length;
        j = i++
    ) {
        const xi = polygon[i][0];
        const yi = polygon[i][1];

        const xj = polygon[j][0];
        const yj = polygon[j][1];

        const intersect =
            ((yi > y) !== (yj > y)) &&
            (
                x <
                ((xj - xi) * (y - yi)) /
                (yj - yi) +
                xi
            );

        if (intersect) {
            inside = !inside;
        }
    }

    return inside;
}

Использование:

const result = isPointInsidePolygon(
    [25, 25],
    polygon
);

console.log(result);

Результат:

true

Разбор алгоритма

Каждое ребро полигона проверяется на пересечение с горизонтальным лучом.

Условие:

(yi > y) !== (yj > y)

означает, что горизонтальная линия точки проходит между вершинами ребра.

Затем вычисляется координата пересечения:

((xj - xi) * (y - yi)) /
(yj - yi) +
xi

Если пересечение находится справа от точки:

x < intersectionX

счётчик пересечений изменяет состояние переменной:

inside = !inside;

Каждое пересечение переключает значение между:

false

и

true

Проверка клика пользователя на карте

Частый сценарий в MapLibre GL JS — определение области, по которой кликнул пользователь.

Получение координат клика:

map.on("click", (event) => {
    const lng = event.lngLat.lng;
    const lat = event.lngLat.lat;

    console.log(lng, lat);
});

Проверка попадания в полигон:

map.on("click", (event) => {
    const point = [
        event.lngLat.lng,
        event.lngLat.lat
    ];

    const inside =
        isPointInsidePolygon(
            point,
            polygon
        );

    if (inside) {
        console.log("Внутри полигона");
    } else {
        console.log("Снаружи полигона");
    }
});

Использование Turf.js

Для производственных проектов предпочтительнее использовать готовые геометрические библиотеки.

Наиболее популярное решение — Turf.js.

Подключение:

<script src="https://unpkg.com/@turf/turf@latest/turf.min.js"></script>

Создание объектов:

const point = turf.point([25, 25]);

const polygon = turf.polygon([[
    [30, 10],
    [40, 40],
    [20, 40],
    [10, 20],
    [30, 10]
]]);

Проверка:

const result =
    turf.booleanPointInPolygon(
        point,
        polygon
    );

console.log(result);

Результат:

true

Функция корректно обрабатывает:

  • сложные полигоны;
  • внутренние отверстия;
  • мультиполигоны;
  • пограничные случаи.

Работа с GeoJSON-источником MapLibre

Предположим, на карте уже существует источник:

map.addSource("regions", {
    type: "geojson",
    data: regionsGeoJSON
});

Получение объекта:

const source =
    map.getSource("regions");

Если исходный GeoJSON хранится отдельно:

const feature =
    regionsGeoJSON.features[0];

Проверка точки:

const inside =
    turf.booleanPointInPolygon(
        pointFeature,
        feature
    );

Полигоны с отверстиями

GeoJSON поддерживает внутренние кольца.

Пример:

{
    type: "Polygon",
    coordinates: [
        [
            [0,0],
            [10,0],
            [10,10],
            [0,10],
            [0,0]
        ],
        [
            [3,3],
            [7,3],
            [7,7],
            [3,7],
            [3,3]
        ]
    ]
}

Первое кольцо:

+----------+
|          |
|          |
|          |
+----------+

Второе кольцо:

+----+
|    |
+----+

представляет отверстие.

Точка внутри отверстия не считается принадлежащей полигону.

turf.booleanPointInPolygon(
    point,
    polygon
);

вернёт:

false

если точка находится внутри внутреннего кольца.

Поддержка MultiPolygon

Некоторые объекты состоят из нескольких независимых частей.

Например:

  • государства с островами;
  • архипелаги;
  • административные районы.

GeoJSON:

{
    type: "MultiPolygon",
    coordinates: [
        [
            [
                [0,0],
                [10,0],
                [10,10],
                [0,10],
                [0,0]
            ]
        ],
        [
            [
                [20,20],
                [30,20],
                [30,30],
                [20,30],
                [20,20]
            ]
        ]
    ]
}

Turf автоматически проверяет все части:

const inside =
    turf.booleanPointInPolygon(
        point,
        multiPolygon
    );

Проверка нескольких точек

Нередко требуется определить принадлежность большого количества объектов одной области.

Например:

const points = [
    [20, 20],
    [25, 30],
    [80, 50],
    [15, 10]
];

Фильтрация:

const result = points.filter(point =>
    isPointInsidePolygon(
        point,
        polygon
    )
);

Результат:

[
    [20, 20],
    [25, 30]
]

Оптимизация при больших объёмах данных

Если проверяется несколько тысяч точек, полный обход всех рёбер становится дорогой операцией.

Полезно предварительно вычислить ограничивающий прямоугольник.

function getBoundingBox(polygon) {
    let minX = Infinity;
    let minY = Infinity;

    let maxX = -Infinity;
    let maxY = -Infinity;

    polygon.forEach(([x, y]) => {
        minX = Math.min(minX, x);
        minY = Math.min(minY, y);

        maxX = Math.max(maxX, x);
        maxY = Math.max(maxY, y);
    });

    return {
        minX,
        minY,
        maxX,
        maxY
    };
}

Проверка прямоугольника:

function insideBoundingBox(
    point,
    bbox
) {
    const [x, y] = point;

    return (
        x >= bbox.minX &&
        x <= bbox.maxX &&
        y >= bbox.minY &&
        y <= bbox.maxY
    );
}

Использование:

const bbox =
    getBoundingBox(polygon);

if (
    insideBoundingBox(point, bbox)
) {
    const inside =
        isPointInsidePolygon(
            point,
            polygon
        );
}

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

Проверка попадания в объект карты через queryRenderedFeatures

Если необходимо определить попадание в уже отображаемый полигон, можно использовать механизм выборки объектов карты.

map.on("click", (event) => {

    const features =
        map.queryRenderedFeatures(
            event.point,
            {
                layers: ["regions-layer"]
            }
        );

    if (features.length > 0) {
        console.log(
            "Полигон найден"
        );
    }
});

Преимущества метода:

  • не требуется собственная геометрия;
  • учитываются реальные объекты на карте;
  • работает быстро благодаря внутренним пространственным индексам.

Однако этот способ определяет попадание в визуализированный объект, а не выполняет универсальный геометрический анализ произвольных координат.

Проверка точки на границе полигона

Отдельный случай — точка лежит непосредственно на ребре.

Например:

const point = [20, 40];

Такая точка совпадает с вершиной полигона.

В зависимости от реализации возможны разные результаты:

true

или

false

Для строгого контроля обычно сначала выполняется проверка принадлежности отрезку.

Пример проверки:

function pointOnSegment(
    point,
    start,
    end
) {
    const [px, py] = point;
    const [x1, y1] = start;
    const [x2, y2] = end;

    const cross =
        (py - y1) * (x2 - x1) -
        (px - x1) * (y2 - y1);

    if (Math.abs(cross) > 1e-10) {
        return false;
    }

    const dot =
        (px - x1) * (x2 - x1) +
        (py - y1) * (y2 - y1);

    if (dot < 0) {
        return false;
    }

    const lengthSquared =
        (x2 - x1) ** 2 +
        (y2 - y1) ** 2;

    return dot <= lengthSquared;
}

После проверки границы выполняется стандартный алгоритм определения внутренней области.

Практические сценарии использования

Геозоны

if (
    turf.booleanPointInPolygon(
        userPoint,
        zone
    )
) {
    activateZone();
}

Определение района города

districts.features.find(feature =>
    turf.booleanPointInPolygon(
        point,
        feature
    )
);

Фильтрация объектов

const visibleObjects =
    objects.filter(object =>
        turf.booleanPointInPolygon(
            turf.point(object.coords),
            selectedPolygon
        )
    );

Анализ маршрута

routePoints.forEach(point => {
    const inside =
        turf.booleanPointInPolygon(
            turf.point(point),
            protectedArea
        );

    if (inside) {
        console.log(
            "Вход в охраняемую зону"
        );
    }
});

Интерактивное выделение территории

map.on("click", event => {

    const inside =
        turf.booleanPointInPolygon(
            turf.point([
                event.lngLat.lng,
                event.lngLat.lat
            ]),
            selectedRegion
        );

    if (inside) {
        showInformationPanel();
    }
});

Определение вхождения точки в полигон является фундаментальной операцией пространственного анализа в MapLibre GL JS. На практике используются два основных подхода: собственная реализация алгоритма Ray Casting для максимального контроля над вычислениями и применение Turf.js для работы со сложными геометриями GeoJSON, включая полигоны с отверстиями и объекты типа MultiPolygon. В интерфейсах карт эта операция лежит в основе геозон, выбора объектов, пространственной фильтрации и обработки пользовательских взаимодействий с картой.

Оглавление