通过坐标在笛卡尔平面上搜索几何形状
Searching for geometric shape on cartesian plane by coordinates
我在笛卡尔平面上有一个算法问题。我需要有效地搜索与给定点相交的几何形状。有几种形状（矩形、圆形、三角形和多边形），但这些并不重要，因为确定实际的点包含在这里不是问题，我将自己实现。问题在于确定需要验证哪些形状以包含给定点。遍历我在平面上的所有形状和 运行 每个形状的点包含方法效率低下，因为形状实例的数量会非常大。我的第一个想法是将平面划分为段（平面是有限的，但对于任何类型的 3D 数组来说都太大了）并且在将形状添加到数据库时，我将确定它将与哪些段相交并将它们保存在对象中形状。那么当给出包含验证的点时，我只需要确定该点所在的线段，然后只对与该线段相交的对象进行包含验证。
这是要走的路吗？我不知道我描述的方法是否最佳，或者我是否没有遗漏任何东西。任何帮助将不胜感激..
提前致谢
P.S.: 我将用 C++ 编写。这并不是真正相关的，因为它更像是一个算法问题，但如果有人好奇的话，我想把它说出来……
这里可以使用网格化方法。
将平面视为光栅图像，在其中使用扫描转换算法绘制所有形状，确保所有像素甚至部分覆盖都被填充。对于每个图像像素，保留一个填充它的形状列表。
然后查询就很简单了：在时间 O(1) 中找到查询点所在的像素，并在时间 O(K) 中检查列表中的每个形状，其中 K 是列表长度，大约等于相交形状的数量。
如果您的图像由 N² 像素组成，并且您有 M 个平均面积为 A 像素的对象，您将需要存储 N²+M.A 列表元素（一个形状标识符 + 一个 link 到下一个）。您将选择像素大小以在准确性和存储成本之间取得良好的折衷。在任何情况下，您都必须将自己限制在 N²<Q.M，其中 Q 是查询总数，否则仅初始化图像的成本可能会超过总查询时间。
如果您的场景非常稀疏（空隙多于形状），您可以使用图像的压缩表示，使用 quadtree。
我在笛卡尔平面上有一个算法问题。我需要有效地搜索与给定点相交的几何形状。有几种形状（矩形、圆形、三角形和多边形），但这些并不重要，因为确定实际的点包含在这里不是问题，我将自己实现。问题在于确定需要验证哪些形状以包含给定点。遍历我在平面上的所有形状和 运行 每个形状的点包含方法效率低下，因为形状实例的数量会非常大。我的第一个想法是将平面划分为段（平面是有限的，但对于任何类型的 3D 数组来说都太大了）并且在将形状添加到数据库时，我将确定它将与哪些段相交并将它们保存在对象中形状。那么当给出包含验证的点时，我只需要确定该点所在的线段，然后只对与该线段相交的对象进行包含验证。
这是要走的路吗？我不知道我描述的方法是否最佳，或者我是否没有遗漏任何东西。任何帮助将不胜感激..
提前致谢
P.S.: 我将用 C++ 编写。这并不是真正相关的，因为它更像是一个算法问题，但如果有人好奇的话，我想把它说出来……
这里可以使用网格化方法。
将平面视为光栅图像，在其中使用扫描转换算法绘制所有形状，确保所有像素甚至部分覆盖都被填充。对于每个图像像素，保留一个填充它的形状列表。
然后查询就很简单了：在时间 O(1) 中找到查询点所在的像素，并在时间 O(K) 中检查列表中的每个形状，其中 K 是列表长度，大约等于相交形状的数量。
如果您的图像由 N² 像素组成，并且您有 M 个平均面积为 A 像素的对象，您将需要存储 N²+M.A 列表元素（一个形状标识符 + 一个 link 到下一个）。您将选择像素大小以在准确性和存储成本之间取得良好的折衷。在任何情况下，您都必须将自己限制在 N²<Q.M，其中 Q 是查询总数，否则仅初始化图像的成本可能会超过总查询时间。
如果您的场景非常稀疏（空隙多于形状），您可以使用图像的压缩表示，使用 quadtree。