c++ - 确定多边形与边界框相交的有效方法

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)  

这种接近的方式花费了太多时间。我想要另一种比这更快的算法。我试图在谷歌上搜索答案，但找不到任何东西。我尝试在 github 上查找 mysql st_intersects() 函数的代码，但我再次找不到该函数代码。

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

Answer 1

您可以创建多边形的边界框，并将测试与体积进行比较。如果多边形的边界框在您的测试体积内，则您没有交集。如果两个包围体相交，你自然会有一个交集。如果多边形的边界框在测试体积之外，则必须测试每条边，看看它们是否相交。您可以在创建边界框时进行此测试。