3

一連の座標の外側の境界を使用して MKPolygon を構築しようとしています。

私が知る限り、これを実現するための提供された機能はありませんXcode(MKPolygon メソッドは、内部ポイントを含むすべてのポイントを使用してポリゴンを構築します)。

いくつかの調査の後、凸包がこの問題を解決することがわかりました。さまざまなアルゴリズムを調べた結果、実装するのに最も適しているのは QuickHull です。

これは、外側の緯度座標を取得し、2 つの間に線を引きます。そこから、その線に基づいてポイントを 2 つのサブセットに分割し、外側の緯度間の距離を処理して三角形の構築を開始し、外側の境界が残るまで内側のポイントを削除します。

最小/最大緯度を見るだけで外側のポイントを見つけることができ、2 つの間に線を引くことができます ( MKPolyline) - しかし、ポイントがこの MKPolyline の一方の側にあるか、もう一方の側にあるかをどのように判断すればよいでしょうか?

フォローアップの質問は、ポイントが MKPolygon 内にあるかどうかを判断するためのヒット テストがあるかどうかです。

ありがとう!

4

1 に答える 1

0

ギフト包装アルゴリズムのバリエーションを使用することになりました。確かに簡単な作業ではありません。

完全なコードのフォーマットに問題があるため、手順を追加する必要があります (クリーンアップを行う必要があるため、おそらくより良いでしょう!)

MKPointAnnotations の配列から始めました

1) 一番左にある最低点を取得しました。これを行うために、すべてのポイントをループし、緯度/経度を比較して最低ポイントを取得しました。このポイントは間違いなく凸包内にあるため、凸包ポイント (cvp) を格納する NSMutableArray に追加します。

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 を追加します。最後に、凸包を構成するポイントのリストが残ります。

于 2012-10-27T01:00:19.643 に答える