cocoa - なげなわツールを実装するためのアルゴリズム？

Question

私はMacOSXアプリケーションを開発しています。このアプリケーションは、UIの一部として、選択可能なメインビューに多くの視覚要素を表示します。これらの要素は、ビュー内の実際にはどこにでも配置できます。UIは、要素を選択するさまざまな方法をサポートします。長方形のマーキー選択、楕円形のマーキー選択、および「自由な」なげなわ選択です。

私はすでに長方形と楕円形のマーキー選択を行っています。アルゴリズムは非常に単純です。要素の領域が長方形/楕円の領域と交差する場合、要素は「選択された」と見なされます。

なげなわツールの選択は、Photoshopなどの最新の画像操作アプリケーションと同じように機能します。ユーザーはパスをクリックしてドラッグすると閉じます。描画されたパスに含まれる要素が選択されます。

このアルゴリズムは、選択の形式に制限がないため、長方形/楕円形の選択よりもはるかに複雑になる可能性があります。誰かがこのようなものを書いた経験があるかどうか、またはどのようなプログラミング手法が必要か、そしてこのアルゴリズムが機能する最も効率的な方法について私を正しい方向に向けることができるかどうか疑問に思います。

前もって感謝します。

Answer 1

私が考えることができる唯一の方法は、なげなわの輪郭を多角形として扱うことです。次に、標準のポリゴン内ポイントテストを使用して、選択する要素を確認できます。

ポリゴンがそれ自体と交差するときに何をするかを決定する必要があります（例：図8）。

ポリゴンを作成するときは、ポイントが多すぎないように、前のポイントに近すぎるポイント（アプリケーションによっては3ピクセル程度）をスキップできる場合があります。

Answer 2

ポリゴンの問題のポイントを見ています：http： //en.wikipedia.org/wiki/Point_in_polygonポリゴンが凸面である（可能性が低い）ことを保証できる場合、アルゴリズムはより単純になります。

Answer 3

フリーハンドのなげなわツールの場合、この非常に単純な解決策をとることができます。選択境界のすべてのポイントを辞書に保存します。xキーとして、（y1、y2）を値として使用します。ここで、y1 <= y2。次に、すべてをループしてx'、dictにエントリがあるかどうかを確認します。その場合、すべてのポイント、wherex' = xおよびy >= y1 and y <= y2、が選択範囲に含まれます。

最善の解決策ではないかもしれませんが、うまくいくはずです。