给定一个点列表，如何确定哪些点彼此在一定距离内
给出一个2d点的列表和一个最大距离d，比O(n^2更好的方法是什么)找出哪些点位于每个点的d以内。我不需要解决方案，只需要一些开始的想法。
共有2个答案
可能有n^2点对要“寻找”，所以并不清楚你在寻找什么。
这样做的一种“输出敏感”方法，其运行时间类似于O（n log（n）h），其中h是您“找到”的对的数量，如下所示：
- 按y坐标对点排序。
- 向下扫描一条线，当扫描线碰到它时，将一个点抛入平衡二叉树，一旦它在扫描线上方达到d，就将其移除。
- 当您用扫描线击中一个点时，迭代平衡二叉树中新点最左d和最右d的所有内容。“查找”新点距离d内的每个点。
在第三个项目符号中，如果你必须看k
使用kd树等空间索引结构，可以得到O（n log n）
啊，我想我误解了你的评论。如果你在查询中设置n个最近的邻居，在最坏的情况下，单个搜索成本为O（n log n），但是你可以在每个找到的最近的点上放一个标志来表示它们是否已经属于一个特定的集群。然后你不必为这些点再次执行最近的邻居查询。所以最终的复杂度仍然是O（n log n）。这里有一些关于这种范围搜索http://www.cs.utah.edu/~lifeifei/cs6931/kdtree.pdf的更多细节。
我在这里假设，期望的行为是从考虑中删除一个点，如果它已经属于一个集群。也许您可以澄清一下问题规范？
-
问题内容： 为了在地图上画一个圆，我有一个中心GLatLng（A）和一个半径（r）以米为单位。 这是一个图： 如何计算位置B的GLatLng？假设r平行于赤道。 使用GLatLng.distanceFrom（）方法获得给定A和B时的半径是微不足道的-但反之则不然。似乎我需要做一些更重的数学运算。 问题答案： 我们将需要一种方法，该方法会在给定方位角和距源点的距离时返回目标点。幸运的是，克里斯·韦尼
-
在此输入图像说明
-
我正在使用chart.js绘制多个折线图。当用户点击其中一个图表时，我需要知道是哪个图表。为了捕捉用户的单击，我在图表的中添加了以及一个以在用户单击图表时调用函数。现在我有了这个： null null 每次单击图表时，它都会给出一个（包含每个图表的信息），还会给出一个包含click事件信息的对象。但我似乎找不到信息来断定哪个图表被点击了。我怎么能这么做？
-
给定少量的点和圆（比方说在100以下），我如何分辨哪个点在哪个圆里？圆圈可以相交，所以一个点可以位于多个圆圈中。
-
我们得到了一个有序线程的二叉树。这意味着，如果一个节点没有左子节点（右子节点），左线程（右线程）将从该节点链接到其索引前一个节点（索引后一个节点）。 你能帮我找到一个节点的父节点的伪代码或算法吗？例如（见下图），给定的节点是Q，父节点必须是I。（我们应该利用给定的想法，即二进制是有序线程） TMI：我实际上需要这个伪代码/算法来创建另一个算法，它将获得二叉树的后序继承者。
-
我正在考虑以下问题（非常粗略的描述）： 假设我们有一个图，其中边被分配了一些非负成本，一个起始节点和一些成本常数。找出： 一组节点，可从到达，其中从起始节点到中任何节点的最短路径成本不大于 对于集合中的每个，上面是最短路径的成本 基本上是有成本限制的Dijkstra。 我的主要问题是：图论中关于这个问题的正确术语是什么？ 我一直在看“可访问性”或“可达性”，但这些似乎是错误的关键词。 最终，我正在