问题标签 [distance]

我有1 个红色多边形和50 个随机放置的蓝色多边形- 它们位于地理2D 空间中。找到红色多边形与其最近的蓝色多边形之间最短距离的最快/最快算法是什么？

请记住，将构成多边形顶点的点作为值来测试距离并不是一个简单的情况，因为它们不一定是最近的点。

所以最后 - 答案应该将最接近的蓝色多边形归还给奇异的红色多边形。

这比听起来更难！

我想实现一种方法来显示按与给定地址的接近程度排序的存储地址列表。

列表中的地址将存储在数据库表中。单独的部分有单独的字段（我们有邮政编码、城市名称等字段），因此它不仅仅是一个巨大的varchar. 这些是用户输入的，并且由于系统的性质可能并不总是完整的（有些可能缺少邮政编码，而另一些可能只有城市和州）。

虽然这是针对 Intranet 应用程序，但我在使用外部资源（包括访问 Internet Web 服务等）时没有问题。实际上，我更喜欢自己动手，除非自己做是微不足道的。如果谷歌或雅虎！已经提供免费服务，我非常愿意检查一下。关键字是它必须​​是免费的，因为我不能随意为这个项目引入任何额外的成本，因为它已经是一个额外的“特权”可以这么说。

我想这很像许多实体店做他们的“查找位置”功能。将它显示在一个适当排序的简单表格中并显示距离（例如英里）非常棒。显示地图混搭更酷，但我绝对可以忍受只是恢复距离，我处理所有后续显示和排序。

简单距离算法的问题在于数据的性质。由于地址的全部或部分可能未定义，因此我没有任何方便的东西，例如纬度/经度坐标。此外，即使我要求邮政编码，90% 的地址也可能具有相同的五个邮政编码。

虽然它不需要非常快，但正如我们所知，由于延迟而需要超过 7 秒才能显示在页面上的任何内容可能对于普通用户来说等待时间太长。如果这样的假设服务支持一次发送一批地址而不是一次查询一个，那就太好了。尽管如此，我不应该认为地址列表总数会超过 50 个，如果有的话。

我想交叉引用构建一个与此处类似的距离图表（例如道路距离交叉引用图表），理想情况下，将数据存储在 SQL Server 2008（最好是 Express 版本）中。它需要这些属性/能力

• 每列都有一个具有相同名称的对应行（即没有像我的示例那样拼写错误）。
• 更改一个 Row-Column 交叉点的值将更新镜像交叉点（Column-Row），或者可以忽略镜像数据。
• 距离值需要最终用户可编辑。
• 最终用户需要能够添加、删除或重命名列/行对。
• 最终用户需要能够对列进行排序并让行自动移动。
• 可能有数百对。
• 查找查询需要找到给定起点和目的地的距离（行和列）

距离图在 Excel 中实现起来相当简单。考虑到这一点，我是不是更好...

• 使用 Excel 作为用户编辑 UI，然后用新数据更新 SQL '东西'？
• 使用 Excel 作为数据源，即使这意味着查询数据的性能问题？
• 使用答案中详述的尚未发现的天才笔触？

这是对这个问题的跟进。

我似乎被困在这一点上。基本上，我需要能够来回转换以参考标准度数系统中的坐标，或者通过测量沿国际日期变更线从南极向北的距离，然后从日期的那个点开始向东的距离线。为了做到这一点（以及一些更一般的距离测量的东西），我有一种方法来确定两个纬度/经度点之间的距离，另一种方法需要一个纬度/经度点、一个航向和一个距离，然后返回该课程结束时的纬度/经度点。

这是我定义的两个静态方法：

这是我用来测试它的函数：

“结束于”值应该是 appx。72.0 / 31.5。但相反，我得到大约 1.25 / 0.021。

我想我一定是错过了一些愚蠢的东西，忘记在某处转换单位，或者其他什么......任何帮助将不胜感激！

更新 1：

我已经（正确地）写了距离函数来返回米，但是在评论中错误地写了公里......当我今天回到它时，这当然让我感到困惑。无论如何，现在已经修复了，我已经修复了 endOfCourse 方法中的因式分解错误，而且我还意识到我也忘记了在该方法中将弧度转换回度数。无论如何：虽然看起来我现在得到了正确的纬度数（71.99 ...），但经度数却很差（我得到的是 3.54 而不是 11.5）。

更新 2： 我在测试中有一个错字，如下所述。它现在已在代码中修复。然而，经度数仍然是错误的：我现在得到的是 -11.34 而不是 11.5。我认为这些行一定有问题：

我从This page中获取了邮政编码及其经度/纬度等的数据库 。它有以下字段：

邮编、纬度、经度、城市、州、县、邮编类

数据在一个文本文件中，但我将它插入到 MySQL 表中。我现在的问题是，我如何利用上面的字段来计算用户可以在网站上输入的两个邮政编码之间的距离？PHP中的工作代码将不胜感激

我正在寻找一种用于我正在制作的赛车游戏的算法。地图/关卡/轨道是随机生成的，所以我需要找到两个位置，起点和目标，以充分利用地图。

• 该算法是在二维空间内工作
• 从每一点出发，只能从四个方向穿越到下一个点；上下左右
• 点只能被阻塞或非阻塞，只能遍历非阻塞点

关于距离的计算，应该不是没有更好的词的“鸟道”。如果 A 和 B 之间有墙（或其他阻挡区域），则 A 和 B 之间的路径应该更长。

我不确定从哪里开始，非常欢迎评论，并且建议的解决方案在伪代码中是首选。

编辑：对。在查看了gs 的代码后，我又试了一次。这次我用 C++ 编写而不是 python。但是，即使在阅读了Dijkstras 算法、洪水填充和Hosam Alys 解决方案之后，我仍然没有发现任何关键的区别。我的代码仍然有效，但没有你看起来运行的那么快。完整的源代码在paste上。唯一有趣的行（我猜）是第 78-118 行的 Dijkstra 变体本身。

但速度不是这里的主要问题。如果有人愿意指出算法中的差异，我将非常感谢您的帮助。

• 在 Hosam Alys 算法中，他从边界而不是每个节点扫描的唯一区别是什么？
• 在 Dijkstras 中，您跟踪并覆盖步行距离，但不是在洪水填充中，但仅此而已？

我在使用该Location.distanceTo方法计算距离时遇到问题。

有人能告诉我为什么我的距离计算显示为 12,637,795 米吗？

我有一个点类，如：

和点列表：

我正在向我的 pointList 推送点数（尽管如果尚未推送任何点数，该列表可能还没有包含点数）。

我有两个问题：

如何从列表中删除与某个任意 (x, y) 的最近点？

假设我有 x,y (5,12)，我想在列表中找到最接近该点的点并将其从 STD::List 中删除。

我知道我必须使用距离公式，并且必须使用迭代器遍历列表，但是我在概念化如何在遍历列表时跟踪哪个点最接近时遇到了一些麻烦.

如何返回给定（x，y）的x半径内的点数组或列表？

类似于最后一个问题，除了我需要一个指向给定（x，y）半径内的“点”对象的指针列表。另外，我应该返回一个数组还是一个列表？

如果有人可以帮助我，我仍然在 C++ 中苦苦挣扎，我很感激。

嘿伙计们，我正在为我的一个参与道路建设的朋友研究一些东西。他需要某种设备来测量点之间的距离或面积。我过去做过一些 GPS 编程，但对于移动设备，我对准确性并没有太大印象。那是几年前的事了，我认为技术已经改进，但是我不确定我应该使用什么设备作为接收器。由于移动设备可能是不可能的，因为我需要能够在其上运行我的自定义应用程序，通过 USB 端口连接的东西可能会起作用吗？我发现 u-blox PCI 很难与笔记本电脑和 PC 配合使用。这里有没有人有过这方面的经验？也许还有其他我需要研究的设备？

我很感激我能得到的任何帮助。谢谢你。

我有一个圆圈，里面有两个点组成一条线段。如何计算从一个端点到直线相交的圆边缘的距离？