問題タブ [line-segment]

n 個の線分が与えられたときにすべての交点を見つけるアルゴリズムを探しています。以下は、 http://jeffe.cs.illinois.edu/teaching/373/notes/x06-sweepline.pdfからの疑似コードです。

入力 S[1 .. n] は線分の配列です。label[i] は、i 番目の左端のエンドポイントのラベルです。

以下に設定されたラインにアルゴリズムを適用します。1 つの交点のみがチェックされます。他の 2 つの交点の存在を知るにはどうすればよいですか?

1. 行[1]が入ります
2. line[2] が入り、line[1] と line[2] の交点がチェックされます。
3. line[3] が入り、line[2] と line[3] の交点がチェックされます。
4. line[4] が入り、line[4] と line[1] の交点がチェックされます。交差点 A が見つかりました。
5. line[4] が終了し、何もチェックされません。
6. line[1] が終了し、何もチェックされません。
7. line[2] が終了し、何もチェックされません。
8. line[3] が終了し、何もチェックされません。

これは少し難しい質問です。線の交点ほど単純ではありません (私はそうは思いません)。

まず、バス ルートを定義するために一連のマップ座標が与えられ、MKPolyline を使用してマップ (MapKit、iOS) に描画しています。複数の異なるバス路線を同時に表示できます。問題は、バス路線が同じ道路を共有し、非常によく似た経路をたどるポイントがいくつかあることですが、GPS 座標は正確ではありません。

私の質問は、ルートから作成された線分のサブシーケンスが同じパスをたどって、互いに重なり合わないようにするのをどのように最もよく検出できるかということです。それらはユーザーが区別する必要があるさまざまな色を持っていますが、それらはすべて非常に似ているため、色付きの線分が互いに重ねて描かれています。

また、言及された線分が検出された場合、それらが作成する線 (直線または曲線) の平均実行を取得する方法もあるでしょうか? そうすれば、座標を再作成して、それらがすべて隣り合って実行され、重複がないようにすることができます。

この種の問題はおそらく難しいと確信しているので、既に存在する特定のアルゴリズムを使用して正しい方向にプッシュする必要があるだけかもしれません。

指定された点が線分内にあるかどうかを確認する方法は?

私は最初にこれを使用しました：

LineSegment はオブジェクトではないため、実際には機能しませんでした..

これまでの私のコードは次のとおりです。

編集：私が知っているように、ここには私のものと同じかもしれないいくつかの質問があります...私が必要としていた答えはそこにありませんでした。

コードを変更しようとしていますが、タイトルに記載されているエラーが発生しました。誰か助けてください。

エラー: BruteCollinearPoints 型のセグメント () メソッドは、引数 (ポイント、ポイント) には適用できません。

n ノードのセットが 2 つあります。ここで、あるセットの各ノードを別のセットの別のノードに接続したいと考えています。結果のグラフには交差がないはずです。

私はいくつかのスイープ ライン アルゴリズムを知っています (交差が発生する場所を確認するための Bentley-Ottmann-Algorithmですが、これらの交差を解決するためのアルゴリズムは、ブルート フォース アプローチを除いて見つかりませんでした。

1 つのセットの各ノードは、他のセット内の任意のノードに接続できます。

この問題を解決する (効率的な) アルゴリズムへのポインターはありますか? 実装は必要ありません。

EDIT1：

の問題に対する 1 つの解決策を次に示しますn=7。

黒い点はノードのセットで、赤い点はセットです。黒の各ノードは、それらを結ぶ線が交差しないように、1 つの赤のノードに接続する必要があります。

EDIT2：

さらに明確にするために：すべてのノードの位置は固定されており、結果のグラフにはn個のエッジがあります。また、解決策が存在するという証拠もありませんが、解決策がない例を作成できませんでした。このような平面グラフの作成が常に可能であるという証拠がどこかにあると確信しています。また、考えられるすべてのソリューションではなく、 1 つのソリューションのみが必要です。

LineSegmentという関数を持つクラスがありますbool LineSegment::intersect(LineSegment &otherLineSegment, Point &intersectionPoint, bool continuous=false)。クラスから継承してクラスを作成するのcontinuousが面倒だったので(またはその逆) 、パラメーターを追加しました。この引数が行うことは、基本的に、2 つの線分の交差を線分としてだけでなく、線であるかのように (つまり、両方向に無限に広がる) チェックできるようにすることです。を返す場合、2 つのオブジェクト間の交点を保持します。LineSegmentLineintersectionPointintersect(...)true

• 最初のケースは、2 つの線分が実際に交差するかどうかを知る必要がある状況をカバーしています。
• 2 番目のケースは、2 つの線分が交差していなくても、これら 2 つの線分を 2 つの線の一部と見なした場合に、交差がどこかで発生するかどうかを知る必要がある状況をカバーしています。

このチェックを行う目的で、ここ (線の交差) とここ (線分の交差) で提供されているアルゴリズムを使用します。

私が抱えている問題は、2 つの一致する線分がある場合です。これは、2 つの線分の間に無限の数の交点があることを意味します。たとえば、線分l1(Point(0, 1), Point(1, 1))とを見てみましょうl2(Point(-1, 1), Point(2, 1))。両方を視覚化すると、

継続的なチェック (つまり、線が交差しているかどうか) が返されますtrue(交点Point(2, 1)は一部でもなくl2、線/線分のいずれかの方程式を使用して計算できる交点のプロパティと直接矛盾します) ) この場合、線分の交点は を返しますfalse。

この状況をどのように処理しますか? もちろん、両方をチェックすることもできますが、そのような不一致が発生した場合は、「一致する行があります」と言うことができます。ただし、次の理由から、これはそれ以上役に立ちません。

• ダブルチェックはコストがかかり、必要な線分のペアごとに実行する必要があります
• オーバーラップとは、交点が無限にあることを意味します (もちろん、マシンの浮動小数点数を扱う場合はそうではありません。これは、(ストレージと精度のために) その間隔内の数のセットが限られている (ただし、それでも十分大きい) ためです)。これは明らかに処理できないため、例外を作成する必要があります

一方で、これをそのままにして、コードに未定義または不適切な動作を作成することもできません。考えられる解決策は、2 つのベクトル (それぞれの線/線分の各部分) の間の角度を確認し、角度が 0 またはそれに非常に近い場合 (丸め誤差を処理す​​るため)、線が一致することです。これは、この情報をどうするかを決定するのにまだ役に立ちませんか?