这种方法与@GarethRees的想法类似：首先，廉价地发现哪些多边形对不需要检查包含关系。一旦需要检查的多边形对数可接受，就进行精确（昂贵）的几何检查。
很容易为每个多边形p计算其边界矩形，即左、右、上和下，因此让我们首先这样做。例如，对于左侧：p.L = min { x : (x,y)是p的顶点 }时间与点数成线性关系。
为了避免将每个多边形与其他每个多边形进行比较，可以将区域分成2x2的网格。假设区域的宽度和高度分别由Dx和Dy给出，则可以创建九个集合top,bottom,left,right,topright,topleft,bottomright,bottomleft,rest并执行以下操作：
for p in polygons:
in_top = p.B > Dy/2
in_bottom = p.T < Dy/2
in_left = p.R < Dx/2
in_right = p.L > Dx/2
if in_top:
if in_left:
add p to topleft
elsif in_right:
add p to topright
else:
add p to top
elsif in_bottom:
if in_left:
add p to bottomleft
elsif in_right:
add p to bottomright
else:
add p to bottom
if in_right and not (in_top or in_bottom):
add p to right
elsif in_left and not (in_top or in_bottom):
add p to left
if not (in_top or in_bottom or in_left or in_right):
add p to rest
这又是线性时间。每个多边形都被分成了它最“紧密”包含的扇区。这样做有什么好处呢？比如说，你知道对于任何在left中的多边形p，它们与集合right之间不可能存在包含关系，因此你不需要进行比较。同样，在bottomleft和right、bottomleft和topleft之间也是如此。下面是在你的示例上的效果：
Dx/2
+----------------------|---------------------+
| | |
| +----------------+ | +--------+ |
| | | | / | |
| | +--------+ | | / | |
|___|___|________|___|_|____ /__+===d(2)=+___|_ Dy/2
| | | | | | / | |
| | +---b(3)-+ | | / | +---+ |
| | | | +-----+ | | |
| +-----------c(2)-+ | e(2)+ |
| | |
+----------------------|----------------a(1)-+
所以，rest = {a}, top = {}, bottom = {}, left = {b,c}, right = {d}
topleft = {}, topright = {}, bottomleft = {}, bottomright = {e}
因此，现在您需要使用昂贵的精确检查来比较最多b与c，d与e以及a与其他所有元素。实际上，如果您以聪明的方式对检查进行排序，则不需要将a与其他所有元素进行比较，因为包含是传递性的，因此如果您注意到c包含b，并且a包含c，那么就不需要检查a是否包含b。
另一个要点是，您可以递归地应用上述推理。例如，假设集合topright超出了您的预期大小；那么您可以通过进一步划分该子区域来应用相同的技术（只需要正确进行簿记）。
