Как эффективно найти большие пересечения полигонов? - PullRequest
Новая
       82

Как эффективно найти большие пересечения полигонов?

0 голосов
/ 21 июня 2019

У меня есть случай слоя с ~ 5000 полигонов (без отверстий), и мне нужно очистить все пересечения. Это веб-приложение, ориентированное на пользователя, поэтому я предпочитаю JavaScript, но я могу использовать серверные вызовы, если есть лучший инструмент в Python, JVM или чем-то еще. Я нашел https://github.com/mbloch/mapshaper/, который имеет алгоритм автоматической очистки, но сначала пользователю нужно вручную позаботиться о больших пересечениях. Для этого я попытался использовать https://github.com/Turfjs/turf, чтобы сравнить пересечения всех пар многоугольников, а затем проверить, больше ли площадь пересечения, чем указанный процент (скажем, 50%) одного из многоугольников, но это занимает 10 -20 минут, и это должен быть интерактивный инструмент. Я оптимизировал его, сначала найдя пересечения ограничивающих прямоугольников полигонов, и только если границы пересекаются, проверьте пересечение полигонов, но это все равно занимает 10-20 секунд. Код выглядит примерно так: 

// fc is a GeoJSON feature collection

const overlapThreshold = 0.5

let largeOverlappingIds = []

fc.features.forEach(feature => {
  feature.bounds = turf.bbox(feature)
  feature.area = turf.area(feature)
})

fc.features.forEach(f1 => {
  if(largeOverlappingIds.includes(f1.properties.id)) {
    return
  }
  const [ f1x1, f1y1, f1x2, f1y2 ] = f1.bounds
  const f1minX = Math.min(f1x1, f1x2)
  const f1maxX = Math.max(f1x1, f1x2)
  const f1minY = Math.min(f1y1, f1y2)
  const f1maxY = Math.max(f1y1, f1y2)

  fc.features.forEach(f2 => {
    if(f1.properties.id === f2.properties.id || largeOverlappingIds.includes(f2.properties.id)) {
      return
    }

    const [ f2x1, f2y1, f2x2, f2y2 ] = f2.bounds
    const f2minX = Math.min(f2x1, f2x2)
    const f2maxX = Math.max(f2x1, f2x2)
    const f2minY = Math.min(f2y1, f2y2)
    const f2maxY = Math.max(f2y1, f2y2)

    if(f1maxX < f2minX || f1minX > f2maxX || f1maxY < f2minY || f1minY > f2maxY) {
      return
    }

    const i = turf.intersect(f1, f2)
    if(i && i.geometry.type === 'Polygon') {
      const intersectionArea = turf.area(i)
      if(intersectionArea > f1.area * overlapThreshold) {
        largeOverlappingIds.push(f1.properties.id)
      }
      if(intersectionArea > f2.area * overlapThreshold) {
        largeOverlappingIds.push(f2.properties.id)
      }
    }
  })
})

Я читал об алгоритмах для поиска пересекающихся точек, но мне все равно нужно было бы найти только случаи большой пересекающейся области. Можно ли придумать какой-нибудь эффективный способ?

...