3

私の Cocoa 趣味プロジェクト (OSX 上) では、いくつかの点が特定されたビューがあります。このようなもの：

NSPoint pt1 = NSMakePoint(20,100);
NSPoint pt2 = NSMakePoint(100,30);

この 2 点の間に蛇行する (決して交差しない) 線を作成したいと思います。もちろん、ポイントは異なる場合があります。私はよく知ってNSBezierPathいますが、グラフィックスの達人ではありません。

これには2つのバリエーションがあります。の与えられNSBezierPath *p ...た設定[p moveToPoint:pt1]

  1. [p lineToPoint:ptx]ギザギザの曲がりくねった線を作成する場合に使用します。
  2. [p curveToPoint:ptx controlPoint1:cpt1 controlPoint2:cpt2]なめらかな蛇行ラインでご使用ください。

適切な制御点も計算する必要があるため、2 番目のケースはより困難に思えます。

最後に、線の蛇行量を調整できるようにしたいと思います。変数 like を 1 に設定すると、 と の間にint numOfIntermediatePoints滑らかな曲線ができます。10に設定すると、線の動きが大きくなります。最後の中間点が最終点から遠く離れないようにしたい (線の最後に大きな変化を残す)。pt1pt2numberOfIntermediatePoints

パーリンノイズを使ってみたのですが、線を終点に誘導するのが難しそうです。NSPoint項目の配列 (ケース 2 では、場合によっては制御点の配列)を計算し、それらをループして線を作成するのが理にかなっているように思えます。

これに対する最善のアプローチは何ですか？

アップデート

Tommy のアドバイスに従い、Raymond Hill の Javascript-Voronoiライブラリを Obj-C に移植することになりました。ここで見つけることができます: https://github.com/cheaton/objcvoronoi

別のアップデート

もう 1 つ更新 - ダイクストラのアルゴリズムを試してみたところ、私が達成しようとしていたことに対してやり過ぎであることがわかりました。最終的に、ランダム ラインのガイド ノードを指定できる単純化されたバリエーションを実装しました。この画像では、線の始点が左中央、線の終点が右中央にあり、(xMax * 0.33, 0) と (xMax * 0.66, yMax) にガイド ポイントがあります。

経路探索の例

最終更新

ぎざぎざを少し少なくするために、オプションの緩和アルゴリズムを追加しました。パフォーマンスは今のところ素晴らしいものではありませんが、私が考えている用途には問題ありません。

セル サイトに適用される緩和アルゴリズム

4

1 に答える 1

3

頭に浮かぶアプローチがたくさんあります。

インターネットから直接取得できるコードに関しては、ランダムな迷路ジェネレーターと迷路ソルバーを取得してから、必要に応じて入口点と出口点を含む迷路を生成し、解を得ることができます。

私が進めているように、再帰的なアプローチを試みることができます — 最初から最後まで直線で始めてから、直線ごとに次のようにします。

  • 中心点で線を分割し、それをどこかに移動することで、線を 2 つに分割することを想像してください。それで...
    • 線法線を計算する
    • 線が既存の線と重なる前に、線の法線に沿って仮想の中心カットポイントをどれだけ移動できるかを計算します（これを行う最も簡単な方法は、分析ではなく二分探索だと思います）
    • 両極端が近すぎる場合は戻ります
    • それ以外の場合は、両極端の間のランダムな位置を選択し、行を分割して再帰します

他の興味深いアイデアとして、始点と終点の間にランダムな点を大量に投げ、ボロノイ図を計算してから (i) 始点からその境界上の任意の場所まで歩きます。（ｉｉ）終点の境界への最短経路に従ってセル境界に沿って（例えば、ダイクストラのアルゴリズムを使用して）。そして (iii) 終点まで。次に、(ii) によって追加されたすべての頂点間リンクを調べて、現在選択されているすべてのリンクが潜在的なセットから除外された最短ルートを見つけ、それを数回繰り返して、パスをより興味深いものにすることができます。

ほぼ同じ考え方からすると、ポイント間にランダムな障害物をたくさん投げて、A* スタイルのパスファインダーを実行すると、おそらく何か興味深い結果が得られるでしょう。

于 2012-03-09T21:43:24.147 に答える