如何计算点到polyline的距离

      polyline的本质为由大于等于一条线段所组成的线段首位衔接的不闭合的折线。(注:首尾衔接的闭合为polygon,直线为折线的特殊情况)。所以求解点point到polyline的距离的问题就转化为求解点到每个线段的距离。由于实际中我们多数使用第三方库来调用也很轻松方便,但是在这里我们也思考一下这简单的小算法也是基础的图形学知识,很多时候复杂的算法实际由多个简单的算法嵌套完成。

实际计算过程如下:

①线段l;

②偏离距离H;

③匹配的结果坐标点P0

④point位置p及p到l的距离h;

⑤线段两个端点A1、A2;

⑥线段所在直线l1;

⑦过线段两端点做线段的法线p1、p2;

⑧P1、p2与线段所成内夹角分别为a,b;

⑨P到A1和A2的距离分别为d1,d2;

图1 点到线段示意图

      当计算时我们会发现要考虑多种情况,一般我们会求点到线段所在直线的垂线的距离。实际上只有point与线段端点组成的三角形不为锐角三角形时所求垂线长度才是正确距离。为此我画了一个表列出所有情况(表中p的结果为匹配到线段上的最近点):

图2 点到线段距离的情况

     遍历计算得出所有点到直线的距离之后就求解最小值。这是一件很简单的事了。(你们会问,这么简单的算法有什么用?我在GPS导航(很渣的)实现中消除GPS因为误差不在路线上的简单处理,还有可以做鼠标拾取polyline/polygon上的点需要。)

下面为简单的实例代码:

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容