Классификация точек

Классификация точек — это процесс определения принадлежности географической точки к определённой области, объекту или категории на основе её пространственного положения. В геоинформационных системах такая задача возникает постоянно: необходимо определить, находится ли объект внутри административной границы, попадает ли пользователь в зону обслуживания, принадлежит ли координата определённому району или лежит ли она в пределах заданного полигона.

Библиотека Turf.js предоставляет набор функций пространственного анализа, позволяющих выполнять подобные проверки непосредственно в JavaScript без использования специализированных ГИС-серверов.

Основными задачами классификации точек являются:

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

Геометрические объекты, участвующие в классификации

Перед выполнением классификации необходимо понимать типы геометрий GeoJSON.

Точка (Point)

const point = turf.point([37.6176, 55.7558]);

Структура GeoJSON:

{
  "type": "Point",
  "coordinates": [37.6176, 55.7558]
}

Точка представляет собой единственную пару координат.

Линия (LineString)

const line = turf.lineString([
  [37.5, 55.7],
  [37.7, 55.8]
]);

Линия состоит из последовательности точек.

Полигон (Polygon)

const polygon = turf.polygon([
  [
    [37.5, 55.7],
    [37.8, 55.7],
    [37.8, 55.9],
    [37.5, 55.9],
    [37.5, 55.7]
  ]
]);

Полигон описывает замкнутую область.

Мультиполигон (MultiPolygon)

const multiPolygon = turf.multiPolygon([
  [
    [
      [37.5, 55.7],
      [37.6, 55.7],
      [37.6, 55.8],
      [37.5, 55.8],
      [37.5, 55.7]
    ]
  ],
  [
    [
      [37.7, 55.7],
      [37.8, 55.7],
      [37.8, 55.8],
      [37.7, 55.8],
      [37.7, 55.7]
    ]
  ]
]);

Мультиполигон объединяет несколько независимых полигонов.

Проверка принадлежности точки полигону

Наиболее распространённая задача классификации — определение того, находится ли точка внутри полигона.

Для этого используется функция booleanPointInPolygon.

Пример

const point = turf.point([37.65, 55.8]);

const polygon = turf.polygon([
  [
    [37.5, 55.7],
    [37.8, 55.7],
    [37.8, 55.9],
    [37.5, 55.9],
    [37.5, 55.7]
  ]
]);

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

console.log(inside);

Результат:

true

Точка попадает внутрь полигона.

Точка вне полигона

const point = turf.point([38.0, 56.0]);

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

console.log(result);

Результат:

false

Координаты расположены за пределами области.

Алгоритм определения принадлежности

Функция booleanPointInPolygon() реализует модификацию алгоритма Ray Casting.

Суть метода:

Из точки проводится условный луч.
Подсчитывается количество пересечений луча с рёбрами полигона.
Нечётное число пересечений означает нахождение внутри.
Чётное число пересечений означает нахождение снаружи.

Схематично:

Точка внутри

+----------------+
|                |
|      ● ----->  |
|                |
+----------------+

Количество пересечений = 1

Точка снаружи

          ● ----->
+----------------+
|                |
|                |
+----------------+

Количество пересечений = 0

Работа с границей полигона

Особое внимание следует уделять ситуациям, когда точка лежит на границе.

Поведение по умолчанию

const point = turf.point([37.5, 55.8]);

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

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

Игнорирование границы

Для строгой проверки используется параметр ignoreBoundary.

const result =
  turf.booleanPointInPolygon(
    point,
    polygon,
    {
      ignoreBoundary: true
    }
  );

Теперь точка на границе будет считаться внешней.

Это полезно при:

кадастровом анализе;
зонировании территорий;
проверке пересечений объектов.

Классификация относительно мультиполигона

Многие реальные географические объекты представлены несколькими отдельными участками.

Например:

архипелаги;
районы с анклавами;
природные заповедники;
зоны покрытия сетей.

Проверка выполняется аналогично.

const point =
  turf.point([37.55, 55.75]);

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

Если точка находится хотя бы в одном полигоне мультиполигона, результат будет:

true

Массовая классификация набора точек

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

Исходные данные

const points = turf.featureCollection([
  turf.point([37.55, 55.75]),
  turf.point([37.65, 55.82]),
  turf.point([38.0, 55.9])
]);

Обработка массива

const classified =
  points.features.map(feature => ({
    ...feature,
    properties: {
      inside:
        turf.booleanPointInPolygon(
          feature,
          polygon
        )
    }
  }));

Результат:

[
  { inside: true },
  { inside: true },
  { inside: false }
]

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

Пространственное тегирование объектов

Классификация часто используется для присвоения атрибутов.

Предположим, имеется набор районов города.

const districts = [
  {
    name: "Северный",
    polygon: northDistrict
  },
  {
    name: "Южный",
    polygon: southDistrict
  }
];

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

function findDistrict(point) {
  for (const district of districts) {
    if (
      turf.booleanPointInPolygon(
        point,
        district.polygon
      )
    ) {
      return district.name;
    }
  }

  return null;
}

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

const district =
  findDistrict(userPoint);

Результат:

"Северный"

Определение ближайшей категории

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

Для этого используется функция nearestPoint.

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

const stores =
  turf.featureCollection([
    turf.point([37.6, 55.75], {
      name: "Магазин 1"
    }),
    turf.point([37.8, 55.8], {
      name: "Магазин 2"
    })
  ]);

Поиск ближайшего объекта

const user =
  turf.point([37.7, 55.78]);

const nearest =
  turf.nearestPoint(
    user,
    stores
  );

console.log(
  nearest.properties.name
);

Результат:

"Магазин 2"

Такая классификация относится к категории анализа близости.

Классификация по расстоянию

Иногда принадлежность определяется не полигоном, а радиусом.

Создание центра

const center =
  turf.point([37.6176, 55.7558]);

Расчёт расстояния

const point =
  turf.point([37.7, 55.8]);

const distance =
  turf.distance(
    center,
    point,
    {
      units: "kilometers"
    }
  );

Определение зоны

let zone;

if (distance < 5) {
  zone = "A";
} else if (distance < 15) {
  zone = "B";
} else {
  zone = "C";
}

Результат:

"B"

Подобная схема применяется для:

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

Классификация относительно буферных зон

Буфер создаёт область вокруг объекта.

const buffer =
  turf.buffer(
    center,
    10,
    {
      units: "kilometers"
    }
  );

После этого точка классифицируется относительно буфера.

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

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

Проверка принадлежности линии

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

Для этого применяется функция booleanPointOnLine.

Пример

const route =
  turf.lineString([
    [37.5, 55.7],
    [37.8, 55.9]
  ]);

const point =
  turf.point([37.65, 55.8]);

const result =
  turf.booleanPointOnLine(
    point,
    route
  );

Результат:

true

Классификация GPS-треков

Типичная задача транспортных систем — определение нахождения транспортного средства на маршруте.

const onRo ute =
  turf.booleanPointOnLine(
    gpsPoint,
    route
  );

Если результат:

true

транспорт движется по заданному маршруту.

Если:

false

произошло отклонение.

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

Допустим, существуют несколько объектов обслуживания.

const stations = [
  {
    name: "Станция 1",
    point: station1
  },
  {
    name: "Станция 2",
    point: station2
  }
];

Для каждого объекта создаётся буфер.

const serviceArea =
  turf.buffer(
    station.point,
    5,
    {
      units: "kilometers"
    }
  );

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

const covered =
  turf.booleanPointInPolygon(
    userPoint,
    serviceArea
  );

Так реализуются:

зоны доставки;
покрытия базовых станций;
территории обслуживания клиентов.

Оптимизация классификации больших наборов данных

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

Наивный подход:

for (const point of points) {
  for (const polygon of polygons) {
    turf.booleanPointInPolygon(
      point,
      polygon
    );
  }
}

Сложность:

O(n × m)

где:

n — количество точек;
m — количество полигонов.

Предварительная фильтрация по ограничивающему прямоугольнику

Получение границ полигона:

const bbox =
  turf.bbox(polygon);

Проверка попадания в рамку:

const inBox =
  pointLng >= bbox[0] &&
  pointLat >= bbox[1] &&
  pointLng <= bbox[2] &&
  pointLat <= bbox[3];

Только после этого выполняется более дорогая операция:

turf.booleanPointInPolygon(
  point,
  polygon
);

Такой подход существенно ускоряет массовую классификацию.

Типичные сценарии использования

Геомаркетинг

определение района проживания клиента;
анализ зон продаж;
сегментация аудитории.

Логистика

распределение заказов по складам;
контроль нахождения транспорта;
проверка зон доставки.

Геоинформационные системы

кадастровый анализ;
административное деление;
классификация объектов местности.

Телекоммуникации

определение покрытия сети;
анализ сигналов;
классификация абонентов по базовым станциям.

Основные функции Turf.js для классификации точек

Функция	Назначение
`booleanPointInPolygon()`	Проверка нахождения точки внутри полигона
`booleanPointOnLine()`	Проверка принадлежности точки линии
`nearestPoint()`	Поиск ближайшей точки
`distance()`	Вычисление расстояния между объектами
`buffer()`	Создание зон вокруг объектов
`bbox()`	Получение ограничивающего прямоугольника
`pointsWithinPolygon()`	Поиск точек внутри полигона
`collect()`	Сбор атрибутов объектов внутри области

Функция pointsWithinPolygon

Для одновременной классификации множества точек используется функция pointsWithinPolygon.

const result =
  turf.pointsWithinPolygon(
    points,
    polygon
  );

Результатом станет новый набор данных, содержащий только точки, попавшие внутрь области.

Это значительно удобнее и эффективнее ручной фильтрации через цикл при обработке больших коллекций GeoJSON.

Классификация точек

Геометрические объекты, участвующие в классификации

Точка (Point)

Линия (LineString)

Полигон (Polygon)

Мультиполигон (MultiPolygon)

Проверка принадлежности точки полигону

Пример

Точка вне полигона

Алгоритм определения принадлежности

Работа с границей полигона

Поведение по умолчанию

Игнорирование границы

Классификация относительно мультиполигона

Массовая классификация набора точек

Исходные данные

Обработка массива

Пространственное тегирование объектов

Определение ближайшей категории

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

Поиск ближайшего объекта

Классификация по расстоянию

Создание центра

Расчёт расстояния

Определение зоны

Классификация относительно буферных зон

Проверка принадлежности линии

Пример

Классификация GPS-треков

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

Оптимизация классификации больших наборов данных

Предварительная фильтрация по ограничивающему прямоугольнику

Типичные сценарии использования

Геомаркетинг

Логистика

Навигация

Геоинформационные системы

Телекоммуникации

Основные функции Turf.js для классификации точек

Функция pointsWithinPolygon