google-maps - 给定一组点时如何找到最多的端点？

Question

我需要从一组点中找到最端点并通过它们绘制一个多边形。任务如下所示：

1）红点是地图上的一组LatLng点。

2）我需要确定它们中最远的并通过它们绘制一个多边形（绿线）。

如果您知道坐标，则绘制多边形并不难。但我不知道如何识别最远的点。

更新 1：

现在我发现这个任务有一个名字。它被称为“顶点覆盖”。

更新 2：

该任务称为“凸包”。这是任务http://computacion.cs.cinvestav.mx/~anzures/geom/hull.php的可视化实现

Answer 1

您可以使用 delaunay 三角剖分计算一组点的凸包。然后您可以查找与超三角形相连的所有顶点。你可以在@phpclasses.org 下载我的php 类凸包。我还写了一个php类凹壳。我建议使用凹形外壳，因为乡村形状并不总是凸出的。这是一个例子：http ://www.phpdevpad.de/geofence 。