0

ここでは、線は一連の 2D 節点として定義されます。今、私は2つのそのような行を持っていますAとB.

A=[(0, 0), (1, 1), (2.1, 3), (4,7)]
B=[(2, 0), (2, 6)]

それらを紙に描くと、 または のいずれかのノード メンバーではない点で 2 つの線が交差することが簡単にわかります。AB

しかし、両方ともA実際B にこの点を超えています。つまり、点は確かに と の両方にAありB、節点と衝突しないだけです。

私は今、交点を見つけたいと思っています。

(もう一度注意してください: 交差点は と にAありBますが、ノードではない可能性があります)

私が今思いついたのは、多項式を使用して各ポイントシリーズに適合させることです。このようにして、方程式との交点を解くことができます。しかし、それは自分にはかなり愚かな方法のようです。

そうするための賢い方法はありますか？

私は Python について話していますが、一般的な回答も大歓迎です。

4

3 に答える 3

0

2 つの点X(x1, x2), Y(y1, y2)があると、次のような直線方程式を決定できます。

(x-x1)/(x2-x1) = (y-y1)/(y2-y1)

これを A 行と B 行で行います。

あなたはラインのために得るでしょう

A: y = m1*x+n1
B: y = m2*x+n2

ここで、上記の両方の方程式を尊重する y と x の値を見つける必要があります。

于 2013-11-08T16:13:46.337 に答える
0

ラインに含まれるセグメントが非常に少ない場合、考えられるすべてのセグメント ペアをテストすることは実用的ですが、うまくスケーリングできません。

この問題に対する最も一般的な解決策は、Bentley-Ottmanアルゴリズムです。疑似コードやそれを実装するライブラリをインターネットで検索するのは簡単です。これは単純なスイープ ライン アルゴリズムであり、その実行時間はO( (n + k) log n)、nが線分の数 (両方の線分の合計) で、kが交点の数です。交点があるかどうかだけを知りたい場合は、見つかった最初の交点で停止できます。その時点で、アルゴリズムは に縮小されO(n log n)ます。

これは、あなたがそれを知っていて、内部交差が含まれていないAことを前提としています。BBentley-Ottman の単純な実装 (2 セットの線分が無差別に処理される) は、自己交差を含むすべての交差を報告します。

于 2013-11-08T16:30:16.577 に答える
0 
for i in range(0, len(A), 2):
    line1 = A[i:i+2]
    for j in range(0, len(B), 2):
        line1 = A[j:j+2]
        point_of_intersect = intersection(line1, line2)
        if point_of_intersect:
            print point_of_intersect

関数は、このウィキペディアのエントリintersectionに従って定義されています。

于 2013-11-08T16:09:03.670 に答える