用边界框确定多边形相交的有效方法

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上搜索答案，但无法找到任何内容。我尝试在github上查找mysql st_intersects（）函数的代码，但是我又无法找到该函数代码。

我知道有很多算法，但是，因为我是这个领域的新手，我无法找到算法，所以我使用了上面的方法。

Answer 1

您可以创建多边形的边界框，并比较测试结果和体积。 如果多边形的边界框位于测试体积内，则没有相交。 如果两个边界体积相交，则自然会有一个交点。 如果多边形的边界框位于测试体积之外，则必须测试每条边，看它们是否相交。你可能可以在创建边界框时做这个测试。