3

我正在尝试使用一组坐标的外边界构建一个 MKPolygon。

据我所知，没有提供的功能可以实现这一点Xcode（MKPolygon 方法将使用所有点来构建多边形，包括内部点）。

经过一些研究，我发现凸包解决了这个问题。在研究了各种算法之后，我最能想到实现的一种算法是 QuickHull。

这需要外部纬度坐标并在两者之间画一条线。从那里，您根据该线将您的点拆分为两个子集，并处理外部纬度之间的距离以开始构建三角形并消除其中的点，直到您留下外部边界。

我可以通过查看最小/最大纬度来找到外部点，并且可以在两者之间画一条线 ( MKPolyline) - 但是我如何确定一个点是落在这条 MKPolyline 的一侧还是另一侧？

一个后续问题是是否有命中测试来确定点是否属于 MKPolygon。

谢谢！

4

1 回答 1

0

我最终使用了礼品包装算法的一种变体。当然不是一项微不足道的任务。

在格式化完整代码时遇到问题，所以我只需要把我的步骤（可能更好，因为我有一些清理工作要做！）

我从一组 MKPointAnnotations 开始

1）我得到了最左边的最低点。为此，我遍历所有点并比较 lat/lng 以获得最低点。这个点肯定会在凸包中，所以将它添加到一个 NSMutableArray 中，它将存储我们的凸包点（cvp）

2）获取最低点左侧的所有点并循环遍历它们，计算cvp与左侧剩余点的角度。无论哪个角度最大，都将是您需要添加到数组中的点。
atan(cos(lat1)sin(lat2)-sin(lat1)*cos(lat2)*cos(lon2-lon1), sin(lon2-lon1)*cos(lat2))

  • 对于找到的每个点，创建一个三角形（通过使用新点的纬度和前一点的长）并创建一个多边形。我使用此代码对我的多边形进行了命中测试： BOOL mapCoordinateIsInPolygon = CGPathContainsPoint(polygonView.path, NULL, polygonViewPoint, NO); 如果在命中测试中发现任何内容，请将其从比较数组中删除（原始数组左侧的所有内容减去船体点）

  • 一旦您的 cvp 数组中至少有 3 个点，使用数组中的所有 cvp 构建另一个多边形，并使用命中测试删除其中的任何内容。

3) 一旦你处理完所有的左侧点，创建一个新的比较数组，其中包含尚未消除或添加到船体的剩余点

4）使用相同的计算和多边形测试来删除点并添加 cvp's found 最后，您会得到一个构成凸包的点列表。

于 2012-10-27T01:00:19.643 回答