通过坐标搜索笛卡尔平面上的几何形状

Question

我在笛卡尔平面上有算法问题..我需要高效地搜索与给定点相交的几何形状。有几种形状（矩形，圆形，三角形和多边形），但这些并不重要，因为确定实际点包含在这里不是问题，我将自己实现这些。问题在于确定哪些形状需要验证包含在给定的点。在平面上迭代我的所有形状并在它们中的每一个上运行点包含方法都是低效的，因为形状的实例数量会非常大。我的第一个想法是为平面划分平面（平面是有限的，但对于任何类型的3D阵列都太大），并且在向数据库添加形状时，我将确定它将与哪些分段相交并将它们保存在对象中形状。然后，当给出包含验证的点时，我只需要确定点所在的段，然后只验证包含与该段相交的对象的包含。

这就是要走的路吗？我不知道我描述的方法是最优的还是我没有错过什么。任何帮助将提前感激..

感谢

P.S：我会在C写这篇++。这并不真正相关，因为它更像是一个算法问题，但我想把它说出来，如果有人很好奇......

Answer 1

网格化方法可以在这里使用。

将平面看作光栅图像，使用扫描转换算法绘制所有形状，确保所有像素部分覆盖。对于每个图像像素，保留一个填充它的形状列表。

查询是直截了当然后：找到该查询点落在时间O(1)像素和检查每个形状在列表中，在时间O(K)，其中K是列表的长度，约等于交叉形状的数量。

如果图像是由N²像素，你必须有一个平均面积A像素M对象，您将需要存储N²+M.A列表元素（形状识别+到下一个链接）。您将选择像素大小以实现准确性和存储成本之间的良好折中。无论如何，您必须将自己限制为N²<Q.M，其中Q是查询的总数，否则仅初始化映像的成本可能会超过总查询时间。

如果场景非常稀疏（空洞多于形状），则可以使用压缩的图像表示，使用quadtree。