objective-c - 使用一组坐标的外边界构建 MKPolygon - 如何分割落在一条线两侧的坐标？

Question

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

据我所知，Xcode 中没有提供实现此目的的功能(MKPolygon 方法将使用所有点来构建多边形，包括内部点)。

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

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

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

后续问题是是否存在 HitTest 来确定点是否落在 MKPolygon 内。

谢谢!

Answer 1

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

在格式化完整代码时遇到问题，所以我只能输入我的步骤(可能更好，因为我有一些清理工作要做!)

我从一组 MKPointAnnotations 开始

1) 我得到了最左边的最低点。为此，我循环遍历所有点并比较纬度/经度以获得最低点。该点肯定会在凸包中，因此将其添加到 NSMutableArray 中，该数组将存储我们的凸包点(cvp)

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

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

• 一旦 cvp 数组中至少有 3 个点，请使用数组中的所有 cvp 构建另一个多边形，并使用 HitTest 删除其中的所有内容。

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

4) 使用相同的计算和多边形测试来删除点并添加发现的 cvp 最后，您将得到构成凸包的点列表。