我有很多点（数十万），我想检查哪些点在多边形内。对于一个相对较小的多边形（即可能只包含几十或数百个点），我可以使用多边形的边界框作为初始检查，然后对框内的这些点进行常规的点对点检查。但是想象一个大的（即，可能包含数千个我的点），形状不规则的多边形。许多点将通过边界框检查，而且多边形中的点检查将更加昂贵，因为较大的多边形由更多的点组成。所以我希望能够过滤大多数点，而不必在多边形中进行全点检查。
所以，我有一个计划，主要是想知道我所描述的是不是一个众所周知的算法，如果是的话，它被称为什么，我可以在哪里找到它的现有代码。我不相信我描述的是四叉树或r树，我不知道如何搜索它。我在下面称它为"矩形树"。
这个想法是，处理这些较大的多边形：
做一个"矩形树"预处理，矩形树的深度随多边形的大小而变化（即，允许更大的多边形有更大的深度）。矩形树将多边形的边界框分成四个四分之一。它会检查每个四分之一矩形是否完全在多边形内部、完全在多边形外部，或者两者都不在。在两者都不存在的情况下，它将递归地划分子矩形，以这种方式继续，直到所有矩形都完全在内部或外部，或者达到最大深度。因此，我们的想法是：（a）制作这棵树的预处理时间，即使它本身会进行几次多边形中点检查，也是非常值得的，因为与要检查的点的数量相比，这段时间相形见绌；（b）绝大多数点都可以使用简单的边界框检查来处理（通常在树下时会进行一些这样的检查），然后一个相对较小的数字将不得不在多边形中进行全点检查（当你到达一个仍然"两者都不是"的叶节点时）。
这个算法叫什么？密码在哪里？事实上，这似乎并不难写，但我想在开始编码之前我会问一下。
我最终使用了一种相关但不同的方法。我意识到，从本质上讲，我正在构建的这个树结构只不过是以低分辨率绘制的多边形。例如，如果我的树下降到8的深度，实际上这就像在分辨率为256x256的位图上绘制多边形，然后对该多边形进行像素命中测试。所以我扩展了这个想法，并使用了一个快速图形库（CImg库）。我在4000x4000大小的黑白位图上绘制多边形。然后我只需要对照位图检查点作为像素。神奇的是，与我构建树所花的时间相比，绘制那个巨大的位图真的很快。所以我得到了比我的树更高的分辨率。
一个问题是能够检测多边形边缘附近的点，由于舍入/分辨率问题，这些点可能会被错误地包括或排除，即使是4000x4000大小的点。如果你需要精确地知道这些点是在里面还是在外面，你可以用另一种颜色在多边形周围画一个笔划，如果你的像素测试达到了那个颜色，你可以在多边形中进行全点检查。就我的目的而言，4000x4000的分辨率已经足够好了（我可以容忍某些边缘点的错误包含/排除）。
因此，这个解决方案的基本技巧是，与其他"数字化"多边形的方法相比，多边形绘制算法非常快速。