我需要一个基本函数来找到点和线段之间的最短距离.随意用您想要的任何语言编写解决方案; 我可以把它翻译成我正在使用的(Javascript).
编辑:我的线段由两个端点定义.所以我的线段AB由两点A (x1,y1)和B (x2,y2).我试图找到这个线段和一个点之间的距离C (x3,y3).我的几何技能很生疏,所以我看到的例子令人困惑,我很遗憾地承认.
建立
对于函数实现,我知道一个简单的方法是使用标准距离到线段公式来测试到多边形的所有段的距离.这个选项规模相当慢,我相信应该有更好的选择.
我的直觉是,对于这种类型的功能应该有一些非常快速已知的算法,这些算法可以在游戏引擎中实现,但我不知道在哪里看.
我找到了一个用于在四叉树中存储线段的参考,这将提供非常快速的搜索,我认为它可以用于我的目的,以快速缩小哪个段看作最近的段然后只需要计算到一个线段的距离. https://people.cs.vt.edu/~shaffer/Papers/SametCVPR85.pdf
我无法找到任何代码示例来说明这将如何工作.我不介意从头开始实现算法,但是如果存在一个可用的,经过测试的代码库,那么就不会明白这一点.
我一直在寻找几个四叉树实现,我认为它的工作方式是每个多边形创建一个四叉树,并将每个多边形的线段与一个边界框插入到该多边形的四叉树中.
我将要制作的函数的"查询"部分将包括创建一个点作为一个非常小的边界框,然后将其用于搜索四叉树结构,然后只能找到多边形的最接近的部分.
http://www.codeproject.com/Articles/30535/A-Simple-QuadTree-Implementation-in-C
和
我真正的问题是,这对于快速搜索时间功能来说似乎是一种合理的方法吗？
有什么东西可以更快地运作吗？
编辑:我一直在环顾四周,发现使用四叉树的一些问题.四叉树的工作方式有利于碰撞检测,但不能设置为允许有效的最近邻搜索. https://gamedev.stackexchange.com/questions/14373/in-2d-how-do-i-efficiently-find-the-nearest-object-to-a-point
R-Trees看起来是更好的选择. https://en.wikipedia.org/wiki/R-tree
和
基于这些帖子,R树看起来像赢家.也很方便看到C++ Boost已经实现了它们.这看起来足够接近我计划做的事情,我将继续实施并验证结果.