四个点之间的最短距离怎么算？平面内四个点的最短连线网络怎么构建？

　　四个点之间的最短距离，指的是连接所有点的总长度最小的连通结构，并非简单的两两距离相加，平面内四个凸分布的点的最短连线总长度，通常比直接连四边形三条边要短10%到15%左右，核心是通过增加中转点减少总路径。

　　1、四个点之间的最短距离计算

　　基础前提确认

　　先明确四个点的位置分布，是凸四边形分布、有三点共线，还是存在点落在另外三点构成的三角形内部，不同分布的计算逻辑有差异。

　　先算出所有两两顶点之间的直线距离，也就是6条边的长度，先排除明显过长的边，缩小后续计算范围。

　　如果是求四个点中任意两点的最短距离，直接对比6条边的长度取最小值即可，这是最基础的单点到单点的最短距离场景。

　　2、四个点的最短连线网络构建

　　如果是要把四个点全部连通的最短总距离，也就是最小生成树的场景，用克鲁斯卡尔算法，把6条边按长度从小到大排序，依次选边，只要不形成闭环，选够3条边就能得到连通四个点的最短总长度，这是没有额外中转点的情况。

　　如果允许增加额外的中转点，也就是斯坦纳树的场景，对于凸四边形的四个点，最短连线是在四边形内部加两个斯坦纳点，让每个点连接的三条线夹角都是120度，总长度会比最小生成树更短。

　　如果四个点里有一个点落在另外三个点构成的三角形内部，最短连线的斯坦纳点通常就在这个内部点附近，直接把内部点和三个顶点连通，总长度就是最短的。

　　3、常见场景的快速判断

　　如果是日常做题或者工程里的简单布线，先算最小生成树的总长度，要是对长度要求更高，再考虑斯坦纳树的优化方案。

　　如果四个点是共线的，直接按顺序把相邻点连起来，总长度就是最外侧两个点的距离，这是最短的连通方式。

　　如果是求四个点围成的图形的最短边界，那就是凸包的周长，把最外侧的点按顺序连起来就行，内部的点不用算进边界里。

（ZuiDuan）