只使用极坐标，有没有找到附近点的算法？

Question

假设我有一个极坐标点向量。

假设其中一个点是探针，我想找到与之相距一定距离的所有其他点。

是否有一种算法可以在不转换为笛卡尔形式的情况下完成这个任务？

- drb

---

欧几里得算法对你适用吗？ - Lostsoul

你可以计算与完全包含你的点和搜索半径相对应的弧段的半径和弧度，然后检查所有在这些边界内的其他点。当然，最终你必须以某种方式计算这些点与你的距离。 - Hot Licks

Answer 1

您正在寻找极坐标距离。您可以在这个链接中找到公式：link。

点（r1，a1）和点（r2，a2）之间的距离为：

D = sqrt(r1*r1 + r2*r2 - 2*r1*r2*cos(a1-a2))

- sch

Answer 2

请注意，如果您计划将算法扩展到许多点，则最好使用空间索引来探测附近的点。我不知道使用极坐标的空间索引的存在，并且我确定它们会有点复杂。因此，如果您有：

- 大量点 - 探测次数比移动点多

那么请问自己是否应该使用笛卡尔坐标和空间索引。

根据您的典型用例自己算一下：

1. 使用笛卡尔和极坐标： - 仅在点移动时转换极坐标为笛卡尔坐标，涉及两个三角函数； - 查找距离另一个点小于某个距离的点可以在O(1)时间内完成（取决于平均距离、空间索引的大小、点数等），不涉及其他任何操作（仅包括加/乘，不涉及平方根，您可以比较距离平方）。 2. 仅使用极坐标： - 扫描所有点而不使用空间索引是O(n)； - 这每次比较都涉及一个三角函数（因此每次探测需要n个三角函数调用）。

请注意，三角函数的计算时间非常昂贵。

- Laurent Grégoire

---

你好，许多点是多少点？我知道进行计算的设备很重要，所以假设它是像iPhone 4这样的移动设备。谢谢。 - Maziyar

这取决于您的CPU、语言等等。您必须进行原型设计才能真正知道。通常问题不在于平均有多少，而是是否存在关于集合大小的限制。 - Laurent Grégoire

我认为最好尽可能少地调用数据，首先通过使用城市/邮编或甚至数据类型（如餐厅或咖啡店等）进行过滤。或者甚至在附近限制数据，如果在5公里内有一百万个点，请尝试按等级或其他方式对它们进行排序，因为没有人会在手机上查看那么多的数据。感谢您提到的不断增长的集合是关键。 - Maziyar

这只是空间索引的典型用例：以 O(1) 的时间复杂度返回给定半径内基准点周围点的列表。根据邮政编码进行过滤是错误的，因为您可能会坐在邮政编码限制上，并且附近有另一个邮政编码的点。没有索引的过滤仍然是 O(n)，而正确的空间索引是 O(1)，最坏情况下是 O(log(n))。 - Laurent Grégoire

那么假设我已经有了用户当前位置和该物品之间的距离（直接点对点，而非通过路线或交通方式），将它们放入循环中并通过简单的<>操作和IF语句检查它们是否在该距离范围内，这种方法可以吗？在这种情况下，这是一个可行的附近处理方法吗？ - Maziyar