我有很多点（数十万个），我想检查哪些点在多边形内。对于一个相对较小的多边形（即，可能只包含数十或数百个点），我可以只使用多边形的边界框作为初始检查，然后对框内的这些点进行常规的多点检查. 但是想象一个大的（即，可能包含我的数千个点）、不规则形状的多边形。许多点将通过边界框检查，此外，多点检查将更昂贵，因为更大的多边形由更多点组成。所以我希望能够过滤掉大部分点，而不必进行完整的多点检查。
所以，我有一个计划，主要是我想知道我所描述的是否是一个众所周知的算法，如果是，它叫什么以及我可以在哪里找到它的现有代码。我不相信我所描述的是四叉树或 r-tree，我不知道如何搜索它。我在下面称它为“矩形树”。
这个想法是，要处理这些较大的多边形：
做一个“矩形树”预处理，矩形树的深度随多边形的大小而变化（即，允许更大的多边形有更多的深度）。矩形树将多边形的边界框分成四等分。它会检查每个四分之一矩形是否完全在多边形内，完全在多边形外，或者两者都不。在两者都不是的情况下，它不会递归地划分子矩形，以这种方式继续，直到所有矩形都完全在内部或外部，或者已经达到最大深度。所以这个想法是（a）制作这棵树的预处理时间，即使它本身会做几个多边形点检查，也是非常值得的，因为这个时间与要检查的点的数量相比相形见绌，
那个算法叫什么？代码在哪里？它实际上看起来并不难写，但我想在开始编码之前我会问一下。