Как сформировать общий polygon имея несколько соседних?

Question

[Анатолий]

Доброго времени суток всем!

Может кто сталкивался с задачей/решением вопроса объединения polygon-ов координат?
задача такая, имея N-кол-во полигонов объединить их в один общий, например:
Имея вот такие несколько полигонов


Объединить их в один общий, примерно так:


Простите за корявую обводку, но суть примера думаю понятна)
Может есть какие библиотеки на PHP или на GO

Answer 1

[Владислав Enokin]

На счет php не сталкивался с такой проблемой, но на js можно сделать с помощью библиотеки turfjs

let turf = require('@turf/turf');

let polygon1 = turf.polygon([[[0,0], [0,1], [1,1], [1,0], [0,0]]]);
let polygon2 = turf.polygon([[[0.5,0.5], [0.5,1.5], [1.5,1.5], [1.5,0.5], [0.5,0.5]]]);
// С помощью booleanIntersects можно понять что есть пересечения полигонов
if (turf.booleanIntersects(polygon1, polygon2)) {
    let merged = turf.union(polygon1, polygon2);
    console.log(merged)
} else {
    console.log('Полигоны не пересекаются');
}

Comments

[Анатолий]

А если они не пересекаются, объединить не получится ведь

[Владислав Enokin]

Анатолий, с помощью библиотеки turf можно найти ближайшего соседа и уже их объединять

let turf = require('@turf/turf');

// Задайте ваши полигоны
let poly1 = turf.polygon([[[0, 0], [0, 5], [5, 5], [5, 0], [0, 0]]]);
let poly2 = turf.polygon([[[5, 0], [5, 5], [10, 5], [10, 0], [5, 0]]]);
let poly3 = turf.polygon([[[10, 0], [10, 5], [15, 5], [15, 0], [10, 0]]]);

// Список полигонов
let polygons = [poly1, poly2, poly3];

// Для каждого полигона найдем его ближайшего соседа и объединим их
for (let i = 0; i < polygons.length; i++) {
  let minDistance = Infinity;
  let closestPolygonIndex;

  for (let j = 0; j < polygons.length; j++) {
    if (i !== j) {
      let distance = turf.distance(polygons[i], polygons[j]);
      if (distance < minDistance) {
        minDistance = distance;
        closestPolygonIndex = j;
      }
    }
  }

  if (closestPolygonIndex !== undefined) {
    let unionPoly = turf.union(polygons[i], polygons[closestPolygonIndex]);
    console.log(unionPoly);
  }
}

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

[alexalexes]

Интересно, а как регулируется выпуклость конечной фигуры в зоне, где появляется дополнительная площадь после объединения? Там ведь n*m вариантов, как провести отрезки в таких зонах, где точки образуют вогнутость контура.