Эффективный способ определения пересечения многоугольника с ограничивающей рамкой

Question

У меня есть набор полигонов, и мне нужно проверить, пересекаются ли они с заданным ограничивающим прямоугольником (прямоугольником). То, что я делаю, я беру каждую вершину многоугольника и проверяю, находится ли она в ограничительной рамке или нет.

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, но снова мне не удалось найти этот код функции.

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

Answer 1

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