Эффективный способ определения пересечения полигонов с ограничительной рамкой
У меня есть набор полигонов, и мне нужно проверить, пересекаются ли они с заданным ограничивающим прямоугольником (прямоугольником). Я беру каждую вершину многоугольника и проверяю, находится ли она внутри ограничительной рамки или нет.
If yes
return true
else
Now I am taking every vertex(i.e 4 vertices) of my bounding box and checking whether it is inside polygon or not,
using the algorithm from http://assemblysys.com/php-point-in-polygon-algorithm/
if yes
return true
else
return false(box and polygon are not intersecting)
Этот способ сближения занимает слишком много времени. Я хочу другой алгоритм, который быстрее, чем этот. Я пытался найти ответ в Google, но ничего не смог найти. Я пытался найти код функции mysql st_intersects () на github, но снова мне не удалось найти этот код функции.
Я знаю, что есть много алгоритмов, но, поскольку я новичок в этой области, я не смог найти алгоритмы, поэтому я использовал вышеуказанный подход.
Решение
Вы можете создать ограничивающий прямоугольник многоугольника и сравнить его с объемом.
Если ограничительная рамка многоугольника находится внутри тестового объема, у вас нет пересечения.
Если два ограничивающих тома пересекаются, у вас, естественно, будет пересечение.
Если ограничивающая рамка многоугольника находится за пределами тестового объема, вам придется проверить каждое ребро, чтобы увидеть, не пересекаются ли они. Возможно, вы могли бы сделать этот тест при создании ограничивающего прямоугольника.
Другие решения