私は2Dで作業しています。
私のユーザーは、カスタムオブジェクトクラスに保存するいくつかの線と線分を描くことができますが、基本的にはstartX-YとendX-Yです。
今、私は実際にはボールが内側にあるポリゴンだけを見つけたいと思っていますが、いくつかのアルゴリズムなどについて読んで調査した後、すべてのポリゴンを見つけて、その後正しいポリゴンを検索する必要があると思います。
サンプルコード、c#、Java Objective-C を持っている人はいますか!? 疑似コードの説明で何度か試しましたが、わかりません。
ここには、さまざまな興味深い質問があります。
1. 画面上に一連の線があり、ユーザーが任意の点から指を置き、任意の終点にドラッグすると、線をまたがず、始点と終点が交差しない新しい線を形成する必要があります。終点は実際には既存の線または境界線上にあります。
2. 次の問題は、ボールが存在する凸包を形成する「関連する」線分のアクティブなセットをどのように維持するかです。
3. 最後に、アクティブな線分のセットがある場合、この形状の面積をどのように見つけるか。
パート 1 はすでに回答済みのようです。パート 2 とパート 3 に焦点を当てます。
パート 2 では、次の質問にも関心があります。
4. 凸包と点がある場合、その点が包内にあるかどうかをどのように判断しますか。
使用しているデータ構造に注意すれば、完全な実装を効率的に行うことができます。これは簡単な演習として残します。ここで何か間違ったことをしたか、何かわからないことがあれば教えてください。準備ができたら、あなたのゲームをプレイするのを楽しみにしています!
実際、3 は 2 から簡単です。なぜなら、ボールを含むアクティブな線分のセット (これはタプルのペア ((x_1start,y_1start), (x_1end, y1_end)) のリスト) がわかっている場合、次の 2 つの方法があるからです。面積を計算します。1 つ目は、このタプルのリスト内のすべての始点と終点によって形成される凸包の面積を計算する単純なアルゴリズムを実行することです。面積のより洗練されたアルゴリズムを調べてください。ただし、見つからない場合は、n 辺のハルには n-2 個の重なり合わない三角形があり、三角形の面積は簡単に計算できることに注意してください ( http://www.mathopenref.com /polygontriangles.html )。ノート：
area = abs((x1-x2)*(y1-y3)-(y1-y2)*(x1-x3)) for triangle (x1,y1)(x2,y2)(x3,y3)
ここで、すべての (x,y) ポイントを正の x 軸を中心とした角度で並べ替えると、最初のポイントを固定し、残りのペアを連続して見て、それらの三角形の面積を見つけます。このソート手順が必要な理由を簡単な演習として残します (ヒント: 絵を描いてください)。
ここで難しいのは 2 です。ボールを囲むアクティブな線分セットがある場合、新しい線分を追加し、アクティブ セット内の線分のサイズと数を調整するにはどうすればよいでしょうか。ゲームの開始時には、画面の境界線であるアクティブ セットに正確に 4 つの線があることに注意してください (誘導が好きな場合は、これが基本ケースになります)。
ここで、ボールを含む任意のアクティブ セットがあり、ユーザーが新しい線を追加するとします。これは、正確に 2 つの既存の線分に当たり、どの線分とも交差しないと仮定します (パート 1 アルゴリズムによる)。ここで、アクティブ セットを変更する必要があります。アルゴリズム 1 により、この点がどの線分に当たるかがわかります。したがって、アクティブ セットを変更できる唯一の方法は、この点に到達した両方の線分がアクティブ セット内にある場合です (この事実を確認するには、絵を描いてください)。
ここで、新しい線分がアクティブ セット内の 2 つの線に当たると仮定します (これは、アクティブ セットを 2 つの凸包に実質的に分割することを意味します)。アクティブ セットを回転した順序で維持する場合 (つまり、正の x 軸を中心とした角度で常に並べ替えられるようにする場合)、この並べ替えられた順序を維持する方法で新しいポイントを追加するだけで済みます。たとえば、アクティブ セットのポイント (ライン セグメントを 1 つのラインに折りたたむ) が次のとおりであるとします。
[(x1, y1), (x2, y2), (x3, y3), ..., (xn, yn), (x1, y1)]
新しい線分 ((x', y'), (x'', y'')) を追加すると、新しいセットは次のようになります。
[(x1, y1), (x2, y2), (x', y'), (x3, y3), ..., (xn, yn), (x'', y''), (x1, y1)]
次に、2 つの凸包が形成されます。
1. [(x1, y1), (x2, y2), (x', y'), (x'', y''), (x1, y1)]
2. [(x', y'), (x3, y3), ..., (xn, yn), (x'', y'')]
したがって、残っている唯一の問題は、どれが新しいアクティブ セットであるかということです。単純にアルゴリズム 4 を使用します。
まず、線分と点のクラスが必要です (簡単にするために、equals や hashcode などの実装は避けています)。
class Point {
public int x;
public int y;
}
class LineSegment {
public Point lineStart;
public Point lineEnd;
}
これで、アクティブ セットのデータ構造を表すことができます。
class ActiveSet {
public List<Line> thesortedlist;
}
ここで、最初にアクティブ セットを 4 行で初期化し、画面の中心を (0,0) として示します。
LineSegment TopBorder = new LineSegment(new Point(10, 10), new Point(-10, 10));
LineSegment LftBorder = new LineSegment(new Point(-10, 10), new Point(-10, -10));
LineSegment BtmBorder = new LineSegment(new Point(-10, -10), new Point(10, -10));
LineSegment RightBorder = new LineSegment(new Point(10, -10), new Point(10, 10));
ActiveSet activeset = new ActiveSet();
activeSet.theActiveLines.add(TopBorder);
activeSet.theActiveLines.add(LftBorder);
activeSet.theActiveLines.add(BtmBorder);
activeSet.theActiveLines.add(RightBorder);
ここで、ユーザーが点 (0, 10) から (10, 0) に線を追加するとします。これは対角線 (newSegment と呼びます) であり、新しいアクティブ セットは次のようになります。
------
- -
- -
- -
- -
- -
- B -
- -
-----------
右上隅のカットに注意してください。B はボールを表します。アルゴリズム 1 により、行 TopBorder と RightBorder がヒットしたことがわかります。現在、これらは両方ともアクティブセット内にあります (ハッシュマップを使用すると、メンバーシップをより迅速にテストできます)。次に、次のように 2 つのアクティブセットを作成する必要があります。
ActiveSet activesetLeft = new ActiveSet();
ActiveSet activesetRight = new ActiveSet();
これらのセットを構築するには、次の手順に従います。
List<LineSegment> leftsegments = activeset.GetSegmentsBetween(TopBorder,
RightBorder);
List<RightSegment> rightsegments = activeset.GetSegmentsBetween(RightBorder,
TopBorder);
この関数 GetSegmentsBetween(LineSegment firstline, LineSegment secondline) は、リスト内の最初の行を見つけてから、2 番目の行が見つかるまですべての要素を返す必要があります (リストを 2 回通過する必要がある場合があります)。これらの firstline または secondline を戻り値に含めるべきではありません。ここで、activesetLeft と activesetright があるとします。次のことを行う必要があります。
activesetLeft.append(new Line(secondLine.lineStart, newSegment.lineStart));
activesetLeft.append(newSegment);
activesetLeft.append(new Line(newSegment.lineEnd, firstLine.lineEnd));
activesetRight.append(new Line(firstLine.lineStart, newSegment.lineEnd));
activesetRight.append(new Line(newSegment.lineEnd, newSegment.lineStart));
activesetRight.append(new Line(newSegment.lineStart, secondLine.lineEnd));
コードで理解するのは本当に難しいですが、上記のすべての順序は重要です。なぜなら、反時計回りの順序で並べ替えを維持したいからです。
これをどのように高速化できるかは、演習として残します (実際には、2 つのアクティブ セットを作成する必要はありません。最初に、ボールが新しいセグメントの上にあるか下にあるかを判断し、それに応じて左または右のアクティブ セットを作成するだけです)。