How do I determine whether or not two lines intersect, and if they do, at what x,y point?
521557 次
27 に答える
658
この問題には、ベクトルの外積を使用する優れたアプローチがあります。2 次元ベクトルの外積v × wをv x w y − <strong>v y w xと定義します。
2 つの線分がpからp + rまで、およびqからq + sまで伸びているとします。次に、1 行目の任意の点はp + t r (スカラー パラメーター tの場合) として表現でき、2 行目の任意の点はq + u s (スカラー パラメーター uの場合) として表現できます。
次のようなtとuを見つけることができれば、2 つの線は交差します。
p + t r = q + u s
両側をsで交差させて、
( p + t r ) × s = ( q + u s ) × s
s × s = 0なので、これは
t ( r × s ) = ( q − p ) × s
したがって、 tを解くと、次のようになります。
t = ( q − p ) × s / ( r × s )
同様に、 uについても解くことができます。
( p + t r ) × r = ( q + u s ) × r
u ( s × r ) = ( p − q ) × r
u = ( p − q ) × r / ( s × r )
計算ステップの数を減らすには、これを次のように書き直すと便利です ( s × r = − <strong>r × sであることを思い出してください)。
u = ( q − p ) × r / ( r × s )
現在、次の 4 つのケースがあります。
r × s = 0 かつ ( q − <strong>p) × r = 0 の場合 、2 つの直線は同一線上にあります。
この場合、2 番目のセグメントの終点 ( qおよびq + s ) を最初の線分の方程式 ( p + t r )で表します。
t 0 = ( q − p ) · r / ( r · r )
t 1 = ( q + s − p ) · r / ( r · r ) = t 0 + s · r / ( r · r )
t 0とt 1の間の間隔が間隔 [0, 1] と交差する場合、線分は同一線上にあり、重なり合っています。それ以外の場合、それらは同一直線上にあり、ばらばらです。
sとrが反対方向を指している場合、 s · r < 0 なので、チェックする間隔は[ t 0 , t 1 ]ではなく[ t 1 , t 0 ] であることに注意してください。
r × s = 0 かつ ( q − <strong>p) × r ≠ 0 の場合 、2 つの直線は平行で交差していません。
r × s ≠ 0 かつ 0 ≤ <em>t ≤ 1 かつ 0 ≤ <em>u ≤ 1 の場合、2 つの線分は点p + t r = q + u sで交わります。
そうでない場合、2 つの線分は平行ではなく、交差しません。
クレジット: この方法は、 Graphics Gemsの 304 ページに掲載された Ronald Goldman による記事「Intersection of two lines in three-space」の 3D 線交差アルゴリズムの 2 次元特殊化です。3 次元では、通常、線が歪んでいる (平行でも交差でもない) 場合、メソッドは 2 つの線の最も近い点を示します。
于 2009-02-19T13:24:36.073 に答える
230
FWIW、次の関数（C）は、線の交点を検出し、交点を決定します。これは、Andre LeMothe の「 Tricks of the Windows Game Programming Gurus 」のアルゴリズムに基づいています。他の回答の一部のアルゴリズム (Gareth など) と似ていません。次に、LeMothe は Cramer の規則 (私に聞かないでください) を使用して、方程式自体を解きます。
私の弱い小惑星のクローンで動作することを証明でき、エレメンタル、ダン、ウォズによる他の回答で説明されているエッジケースを正しく処理しているようです。また、それはすべて乗算と除算であり、平方根がないため、KingNestor によって投稿されたコードよりもおそらく高速です!
私の場合は問題ではありませんでしたが、ゼロで除算する可能性があると思います。とにかくクラッシュを回避するために変更するのは簡単です。
// Returns 1 if the lines intersect, otherwise 0. In addition, if the lines
// intersect the intersection point may be stored in the floats i_x and i_y.
char get_line_intersection(float p0_x, float p0_y, float p1_x, float p1_y,
float p2_x, float p2_y, float p3_x, float p3_y, float *i_x, float *i_y)
{
float s1_x, s1_y, s2_x, s2_y;
s1_x = p1_x - p0_x; s1_y = p1_y - p0_y;
s2_x = p3_x - p2_x; s2_y = p3_y - p2_y;
float s, t;
s = (-s1_y * (p0_x - p2_x) + s1_x * (p0_y - p2_y)) / (-s2_x * s1_y + s1_x * s2_y);
t = ( s2_x * (p0_y - p2_y) - s2_y * (p0_x - p2_x)) / (-s2_x * s1_y + s1_x * s2_y);
if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
{
// Collision detected
if (i_x != NULL)
*i_x = p0_x + (t * s1_x);
if (i_y != NULL)
*i_y = p0_y + (t * s1_y);
return 1;
}
return 0; // No collision
}
ところで、LeMothe の本では、明らかにアルゴリズムを正しく理解していると言わざるを得ませんが、彼が示す具体的な例では、間違った数値を差し込んで計算を間違っています。例えば：
(4 * (4 - 1) + 12 * (7 - 1)) / (17 * 4 + 12 * 10)
= 844/0.88
= 0.44
それは私を何時間も混乱させました。:(
于 2009-12-28T07:16:45.873 に答える
63
問題は次の質問に帰着します: A から B への 2 本の直線と C から D への直線は交差しますか? 次に、4 回尋ねることができます (線と長方形の 4 つの辺のそれぞれの間)。
これを行うためのベクトル計算は次のとおりです。AからBへの線が問題の線であり、CからDへの線が長方形の線の1つであると想定しています。私の表記法はAx、「A の x 座標」でCyあり、「C の y 座標」です。そして " *" は内積を意味するので、例えばA*B = Ax*Bx + Ay*By.
E = B-A = ( Bx-Ax, By-Ay )
F = D-C = ( Dx-Cx, Dy-Cy )
P = ( -Ey, Ex )
h = ( (A-C) * P ) / ( F * P )
このh数字が鍵です。hが と の間0にある場合1、線は交差し、それ以外の場合は交差しません。がゼロの場合F*P、もちろん計算を行うことはできませんが、この場合、線は平行であるため、明らかな場合にのみ交差します。
正確な交点はC + F*hです。
もっと楽しく：
hが正確 0であるか1、線が終点で接触している場合。これを「交差点」と見なすことも、そうでないこともできます。
具体的にhは、他の線に正確に接触するために線の長さをどれだけ掛ける必要があるかです。
したがって、 Ifh<0は、長方形の線が指定された線の「後ろ」にあり (「方向」は「A から B へ」)、h>1長方形の線が指定された線の「前」にあることを意味します。
導出：
A と C は、線の始点を指すベクトルです。E と F は、直線を形成する A と C の端からのベクトルです。
平面内の任意の 2 つの非平行線については、スカラーのペアが 1 つだけ存在し、次の式が成り立つ必要がありgますh。
A + E*g = C + F*h
なんで？平行でない 2 本の線は交差する必要があるため、両方の線をそれぞれある程度拡大縮小し、互いに接触させることができます。
(最初、これは 2 つの未知数を持つ 1 つの方程式のように見えます! しかし、これが 2D ベクトル方程式であると考えると、そうではありません。つまり、これは実際には と の方程式のペアですx。y)
これらの変数の 1 つを排除する必要があります。簡単な方法は、E項をゼロにすることです。これを行うには、E でドットをゼロにするベクトルを使用して、方程式の両辺の内積をとります。P上で呼び出したそのベクトルで、E の明らかな変換を行いました。
あなたは今持っています：
A*P = C*P + F*P*h
(A-C)*P = (F*P)*h
( (A-C)*P ) / (F*P) = h
于 2009-02-18T23:09:18.547 に答える
46
私は、上記のJasonによって非常にエレガントに記述されたアルゴリズムを実装しようとしました。残念ながら、デバッグで数学を使って作業していると、うまくいかないケースがたくさん見つかりました。
たとえば、点A（10,10）B（20,20）C（10,1）D（1,10）がh = .5を与えると考えてください。それでも、これらのセグメントがそれぞれの近くにないことは、調査によって明らかです。他の。
これをグラフ化すると、0 <h <1の基準は、インターセプトポイントが存在する場合にCD上にあることを示すだけであり、そのポイントがAB上にあるかどうかはわかりません。クロスポイントがあることを確認するには、変数gに対して対称計算を実行する必要があり、切片の要件は次のとおりです。0 <g <1 AND 0 <h <1
于 2009-07-29T16:05:54.133 に答える
45
これがGavinの答えの改善です。marcp の解決策も同様ですが、除算を延期することはありません。
これは実際には、Gareth Rees の回答の実用的なアプリケーションでもあることがわかります。これは、2D でクロス積に相当するものが perp-dot-product であるためです。これは、このコードが 3 つを使用するものです。3D に切り替えて外積を使用し、最後に s と t の両方を補間すると、3D の線の間に最も近い 2 つの点が得られます。とにかく、2D ソリューション:
int get_line_intersection(float p0_x, float p0_y, float p1_x, float p1_y,
float p2_x, float p2_y, float p3_x, float p3_y, float *i_x, float *i_y)
{
float s02_x, s02_y, s10_x, s10_y, s32_x, s32_y, s_numer, t_numer, denom, t;
s10_x = p1_x - p0_x;
s10_y = p1_y - p0_y;
s32_x = p3_x - p2_x;
s32_y = p3_y - p2_y;
denom = s10_x * s32_y - s32_x * s10_y;
if (denom == 0)
return 0; // Collinear
bool denomPositive = denom > 0;
s02_x = p0_x - p2_x;
s02_y = p0_y - p2_y;
s_numer = s10_x * s02_y - s10_y * s02_x;
if ((s_numer < 0) == denomPositive)
return 0; // No collision
t_numer = s32_x * s02_y - s32_y * s02_x;
if ((t_numer < 0) == denomPositive)
return 0; // No collision
if (((s_numer > denom) == denomPositive) || ((t_numer > denom) == denomPositive))
return 0; // No collision
// Collision detected
t = t_numer / denom;
if (i_x != NULL)
*i_x = p0_x + (t * s10_x);
if (i_y != NULL)
*i_y = p0_y + (t * s10_y);
return 1;
}
基本的に、除算を最後の瞬間まで延期し、ほとんどのテストを特定の計算が完了する前に移動することで、アーリーアウトを追加します。最後に、線が平行な場合に発生するゼロ除算のケースも回避します。
ゼロとの比較ではなく、イプシロン テストの使用を検討することもできます。平行に非常に近い線は、わずかにずれている結果を生成する可能性があります。これはバグではなく、浮動小数点演算の制限です。
于 2013-02-10T06:56:51.403 に答える
40
質問 C: 2 つの線分が交差しているかどうかをどのように検出しますか?
同じトピックを検索しましたが、答えに満足できませんでした。そこで、2 つの線分が多くの画像と交差しているかどうかを確認する方法を非常に詳細に説明する記事を書きました。完全な (そしてテスト済みの) Java コードがあります。
最も重要な部分を切り取った記事は次のとおりです。
線分 a が線分 b と交差するかどうかをチェックするアルゴリズムは、次のようになります。
境界ボックスとは 2 つの線分の 2 つの境界ボックスを次に示します。
両方の境界ボックスに交点がある場合は、1 つの点が (0|0) になるように線分 a を移動します。これで、a で定義された原点を通る線ができました。次に、線分 b を同じ方法で移動し、線分 b の新しい点が線 a の異なる側にあるかどうかを確認します。その場合は、逆に確認してください。これも当てはまる場合、線分は交差します。そうでない場合、それらは交差しません。
問題 A: 2 つの線分が交差する場所はどこですか?
2 つの線分 a と b が交差することがわかります。それがわからない場合は、「質問 C」でお渡ししたツールで確認してください。
これで、いくつかのケースを調べて、7 年生の数学で解を得ることができます (コードとインタラクティブな例を参照してください)。
質問 B: 2 つの線が交差しているかどうかをどのように検出しますか?
A = (x1, y1)あなたのポイント、ポイントB = (x2, y2)、、、C = (x_3, y_3)としましょうD = (x_4, y_4)。最初の行は AB (A != B) で定義され、2 行目は CD (C != D) で定義されます。
function doLinesIntersect(AB, CD) {
if (x1 == x2) {
return !(x3 == x4 && x1 != x3);
} else if (x3 == x4) {
return true;
} else {
// Both lines are not parallel to the y-axis
m1 = (y1-y2)/(x1-x2);
m2 = (y3-y4)/(x3-x4);
return m1 != m2;
}
}
質問 D: 2 つの直線はどこで交差しますか?
それらがまったく交差するかどうか、質問 B で確認してください。
線 a と線 b は、各線の 2 つの点によって定義されます。基本的に、質問 A で使用したのと同じロジックを適用できます。
于 2013-02-21T11:31:22.977 に答える
21
ここで一度受け入れられた答えは正しくありません (それ以来受け入れられていないので、万歳!)。すべての非交差を正しく排除するわけではありません。自明に動作するように見えるかもしれませんが、特に 0 と 1 が h に対して有効であると見なされる場合、失敗する可能性があります。
次のケースを検討してください。
(4,1)-(5,1) および (0,0)-(0,2) の行
これらは、明らかに重なり合わない垂直線です。
A=(4,1)
B=(5,1)
C=(0,0)
D=(0,2)
E=(5,1)-(4,1)=(-1,0)
F= (0,2)-(0,0)=(0,-2)
P=(0,1)
h=((4,1)-(0,0)) dot (0,1) / ((0 ,-2) ドット (0,1)) = 0
上記の回答によると、これら 2 つの線分は終点 (値 0 と 1) で交わります。そのエンドポイントは次のようになります。
(0,0)+(0,-2)*0=(0,0)
したがって、明らかに 2 つの線分は (0,0) で交わります。これは線 CD にありますが、線 AB にはありません。それで、何がうまくいかないのですか？答えは、0 と 1 の値は有効ではなく、エンドポイントの交差を正しく予測するために時々発生するだけです。一方の線の延長線 (もう一方の線分ではない) が線分と交わる場合、アルゴリズムは線分の交点を予測しますが、これは正しくありません。AB 対 CD でテストを開始し、次に CD 対 AB でテストすることで、この問題は解消されると思います。両方が 0 と 1 の間に包括的に収まる場合にのみ、交差していると言えます。
エンドポイントを予測する必要がある場合は、ベクトルの外積法を使用することをお勧めします。
-ダン
于 2009-04-04T00:26:13.593 に答える
11
2 つの線分の正しい交点を見つけることは、多くのエッジ ケースを伴う重要な作業です。Javaで十分に文書化され、機能し、テストされたソリューションを次に示します。
本質的に、2 つの線分の交点を見つけるときに発生する可能性のある 3 つのことがあります。
セグメントが交差していません
独特の交点がある
交差点は別のセグメントです
注：コードでは、x1 = x2およびy1 = y2の線分（x1、y1）、（x2、y2）が有効な線分であると想定しています。数学的に言えば、線分は個別の点で構成されますが、完全を期すために、この実装では線分が点であることを許可しています。
コードは私のgithub リポジトリから取得されます
/**
* This snippet finds the intersection of two line segments.
* The intersection may either be empty, a single point or the
* intersection is a subsegment there's an overlap.
*/
import static java.lang.Math.abs;
import static java.lang.Math.max;
import static java.lang.Math.min;
import java.util.ArrayList;
import java.util.List;
public class LineSegmentLineSegmentIntersection {
// Small epsilon used for double value comparison.
private static final double EPS = 1e-5;
// 2D Point class.
public static class Pt {
double x, y;
public Pt(double x, double y) {
this.x = x;
this.y = y;
}
public boolean equals(Pt pt) {
return abs(x - pt.x) < EPS && abs(y - pt.y) < EPS;
}
}
// Finds the orientation of point 'c' relative to the line segment (a, b)
// Returns 0 if all three points are collinear.
// Returns -1 if 'c' is clockwise to segment (a, b), i.e right of line formed by the segment.
// Returns +1 if 'c' is counter clockwise to segment (a, b), i.e left of line
// formed by the segment.
public static int orientation(Pt a, Pt b, Pt c) {
double value = (b.y - a.y) * (c.x - b.x) -
(b.x - a.x) * (c.y - b.y);
if (abs(value) < EPS) return 0;
return (value > 0) ? -1 : +1;
}
// Tests whether point 'c' is on the line segment (a, b).
// Ensure first that point c is collinear to segment (a, b) and
// then check whether c is within the rectangle formed by (a, b)
public static boolean pointOnLine(Pt a, Pt b, Pt c) {
return orientation(a, b, c) == 0 &&
min(a.x, b.x) <= c.x && c.x <= max(a.x, b.x) &&
min(a.y, b.y) <= c.y && c.y <= max(a.y, b.y);
}
// Determines whether two segments intersect.
public static boolean segmentsIntersect(Pt p1, Pt p2, Pt p3, Pt p4) {
// Get the orientation of points p3 and p4 in relation
// to the line segment (p1, p2)
int o1 = orientation(p1, p2, p3);
int o2 = orientation(p1, p2, p4);
int o3 = orientation(p3, p4, p1);
int o4 = orientation(p3, p4, p2);
// If the points p1, p2 are on opposite sides of the infinite
// line formed by (p3, p4) and conversly p3, p4 are on opposite
// sides of the infinite line formed by (p1, p2) then there is
// an intersection.
if (o1 != o2 && o3 != o4) return true;
// Collinear special cases (perhaps these if checks can be simplified?)
if (o1 == 0 && pointOnLine(p1, p2, p3)) return true;
if (o2 == 0 && pointOnLine(p1, p2, p4)) return true;
if (o3 == 0 && pointOnLine(p3, p4, p1)) return true;
if (o4 == 0 && pointOnLine(p3, p4, p2)) return true;
return false;
}
public static List<Pt> getCommonEndpoints(Pt p1, Pt p2, Pt p3, Pt p4) {
List<Pt> points = new ArrayList<>();
if (p1.equals(p3)) {
points.add(p1);
if (p2.equals(p4)) points.add(p2);
} else if (p1.equals(p4)) {
points.add(p1);
if (p2.equals(p3)) points.add(p2);
} else if (p2.equals(p3)) {
points.add(p2);
if (p1.equals(p4)) points.add(p1);
} else if (p2.equals(p4)) {
points.add(p2);
if (p1.equals(p3)) points.add(p1);
}
return points;
}
// Finds the intersection point(s) of two line segments. Unlike regular line
// segments, segments which are points (x1 = x2 and y1 = y2) are allowed.
public static Pt[] lineSegmentLineSegmentIntersection(Pt p1, Pt p2, Pt p3, Pt p4) {
// No intersection.
if (!segmentsIntersect(p1, p2, p3, p4)) return new Pt[]{};
// Both segments are a single point.
if (p1.equals(p2) && p2.equals(p3) && p3.equals(p4))
return new Pt[]{p1};
List<Pt> endpoints = getCommonEndpoints(p1, p2, p3, p4);
int n = endpoints.size();
// One of the line segments is an intersecting single point.
// NOTE: checking only n == 1 is insufficient to return early
// because the solution might be a sub segment.
boolean singleton = p1.equals(p2) || p3.equals(p4);
if (n == 1 && singleton) return new Pt[]{endpoints.get(0)};
// Segments are equal.
if (n == 2) return new Pt[]{endpoints.get(0), endpoints.get(1)};
boolean collinearSegments = (orientation(p1, p2, p3) == 0) &&
(orientation(p1, p2, p4) == 0);
// The intersection will be a sub-segment of the two
// segments since they overlap each other.
if (collinearSegments) {
// Segment #2 is enclosed in segment #1
if (pointOnLine(p1, p2, p3) && pointOnLine(p1, p2, p4))
return new Pt[]{p3, p4};
// Segment #1 is enclosed in segment #2
if (pointOnLine(p3, p4, p1) && pointOnLine(p3, p4, p2))
return new Pt[]{p1, p2};
// The subsegment is part of segment #1 and part of segment #2.
// Find the middle points which correspond to this segment.
Pt midPoint1 = pointOnLine(p1, p2, p3) ? p3 : p4;
Pt midPoint2 = pointOnLine(p3, p4, p1) ? p1 : p2;
// There is actually only one middle point!
if (midPoint1.equals(midPoint2)) return new Pt[]{midPoint1};
return new Pt[]{midPoint1, midPoint2};
}
/* Beyond this point there is a unique intersection point. */
// Segment #1 is a vertical line.
if (abs(p1.x - p2.x) < EPS) {
double m = (p4.y - p3.y) / (p4.x - p3.x);
double b = p3.y - m * p3.x;
return new Pt[]{new Pt(p1.x, m * p1.x + b)};
}
// Segment #2 is a vertical line.
if (abs(p3.x - p4.x) < EPS) {
double m = (p2.y - p1.y) / (p2.x - p1.x);
double b = p1.y - m * p1.x;
return new Pt[]{new Pt(p3.x, m * p3.x + b)};
}
double m1 = (p2.y - p1.y) / (p2.x - p1.x);
double m2 = (p4.y - p3.y) / (p4.x - p3.x);
double b1 = p1.y - m1 * p1.x;
double b2 = p3.y - m2 * p3.x;
double x = (b2 - b1) / (m1 - m2);
double y = (m1 * b2 - m2 * b1) / (m1 - m2);
return new Pt[]{new Pt(x, y)};
}
}
簡単な使用例を次に示します。
public static void main(String[] args) {
// Segment #1 is (p1, p2), segment #2 is (p3, p4)
Pt p1, p2, p3, p4;
p1 = new Pt(-2, 4); p2 = new Pt(3, 3);
p3 = new Pt(0, 0); p4 = new Pt(2, 4);
Pt[] points = lineSegmentLineSegmentIntersection(p1, p2, p3, p4);
Pt point = points[0];
// Prints: (1.636, 3.273)
System.out.printf("(%.3f, %.3f)\n", point.x, point.y);
p1 = new Pt(-10, 0); p2 = new Pt(+10, 0);
p3 = new Pt(-5, 0); p4 = new Pt(+5, 0);
points = lineSegmentLineSegmentIntersection(p1, p2, p3, p4);
Pt point1 = points[0], point2 = points[1];
// Prints: (-5.000, 0.000) (5.000, 0.000)
System.out.printf("(%.3f, %.3f) (%.3f, %.3f)\n", point1.x, point1.y, point2.x, point2.y);
}
于 2016-06-30T01:41:01.267 に答える
8
良い説明と明確な解決策が数値レシピシリーズにあることを述べたかっただけです。私は第3版を持っています、そして答えは1117ページのセクション21.4にあります。命名法が異なる別の解決策は、Marina Gavrilova Reliable Line SectionIntersectionTestingの論文に記載されています。彼女の解決策は、私の考えでは、もう少し簡単です。
私の実装は以下のとおりです。
bool NuGeometry::IsBetween(const double& x0, const double& x, const double& x1){
return (x >= x0) && (x <= x1);
}
bool NuGeometry::FindIntersection(const double& x0, const double& y0,
const double& x1, const double& y1,
const double& a0, const double& b0,
const double& a1, const double& b1,
double& xy, double& ab) {
// four endpoints are x0, y0 & x1,y1 & a0,b0 & a1,b1
// returned values xy and ab are the fractional distance along xy and ab
// and are only defined when the result is true
bool partial = false;
double denom = (b0 - b1) * (x0 - x1) - (y0 - y1) * (a0 - a1);
if (denom == 0) {
xy = -1;
ab = -1;
} else {
xy = (a0 * (y1 - b1) + a1 * (b0 - y1) + x1 * (b1 - b0)) / denom;
partial = NuGeometry::IsBetween(0, xy, 1);
if (partial) {
// no point calculating this unless xy is between 0 & 1
ab = (y1 * (x0 - a1) + b1 * (x1 - x0) + y0 * (a1 - x1)) / denom;
}
}
if ( partial && NuGeometry::IsBetween(0, ab, 1)) {
ab = 1-ab;
xy = 1-xy;
return true;
} else return false;
}
于 2013-01-03T17:11:50.693 に答える
8
上記の解決策はたくさんありますが、以下の解決策は非常にシンプルで理解しやすいと思います。
2 つのセグメント ベクトル AB とベクトル CD が交差するのは、次の場合のみです。
- 端点 a と b は、セグメント CD の反対側にあります。
- 端点 c と d は線分 AB の反対側にあります。
より具体的には、a と b は、2 つのトリプル a、c、d および b、c、d のいずれかが反時計回りの順序である場合にのみ、セグメント CD の反対側にあります。
Intersect(a, b, c, d)
if CCW(a, c, d) == CCW(b, c, d)
return false;
else if CCW(a, b, c) == CCW(a, b, d)
return false;
else
return true;
ここで CCW は反時計回りを表し、ポイントの向きに基づいて true/false を返します。
ソース: http://compgeom.cs.uiuc.edu/~jeffe/teaching/373/notes/x06-sweepline.pdf ページ 2
于 2014-04-25T21:38:36.060 に答える
8
C と Objective-C
Gareth Reesの回答に基づく
const AGKLine AGKLineZero = (AGKLine){(CGPoint){0.0, 0.0}, (CGPoint){0.0, 0.0}};
AGKLine AGKLineMake(CGPoint start, CGPoint end)
{
return (AGKLine){start, end};
}
double AGKLineLength(AGKLine l)
{
return CGPointLengthBetween_AGK(l.start, l.end);
}
BOOL AGKLineIntersection(AGKLine l1, AGKLine l2, CGPoint *out_pointOfIntersection)
{
// http://stackoverflow.com/a/565282/202451
CGPoint p = l1.start;
CGPoint q = l2.start;
CGPoint r = CGPointSubtract_AGK(l1.end, l1.start);
CGPoint s = CGPointSubtract_AGK(l2.end, l2.start);
double s_r_crossProduct = CGPointCrossProductZComponent_AGK(r, s);
double t = CGPointCrossProductZComponent_AGK(CGPointSubtract_AGK(q, p), s) / s_r_crossProduct;
double u = CGPointCrossProductZComponent_AGK(CGPointSubtract_AGK(q, p), r) / s_r_crossProduct;
if(t < 0 || t > 1.0 || u < 0 || u > 1.0)
{
if(out_pointOfIntersection != NULL)
{
*out_pointOfIntersection = CGPointZero;
}
return NO;
}
else
{
if(out_pointOfIntersection != NULL)
{
CGPoint i = CGPointAdd_AGK(p, CGPointMultiply_AGK(r, t));
*out_pointOfIntersection = i;
}
return YES;
}
}
CGFloat CGPointCrossProductZComponent_AGK(CGPoint v1, CGPoint v2)
{
return v1.x * v2.y - v1.y * v2.x;
}
CGPoint CGPointSubtract_AGK(CGPoint p1, CGPoint p2)
{
return (CGPoint){p1.x - p2.x, p1.y - p2.y};
}
CGPoint CGPointAdd_AGK(CGPoint p1, CGPoint p2)
{
return (CGPoint){p1.x + p2.x, p1.y + p2.y};
}
CGFloat CGPointCrossProductZComponent_AGK(CGPoint v1, CGPoint v2)
{
return v1.x * v2.y - v1.y * v2.x;
}
CGPoint CGPointMultiply_AGK(CGPoint p1, CGFloat factor)
{
return (CGPoint){p1.x * factor, p1.y * factor};
}
関数と構造体の多くは非公開ですが、何が起こっているのかを簡単に知ることができるはずです。これは、このレポで公開されています https://github.com/hfossli/AGGeometryKit/
于 2013-02-20T18:37:41.200 に答える
6
これらの回答のいくつかを試しましたが、うまくいきませんでした (申し訳ありません)。さらにネット検索した後、これを見つけました。
彼のコードを少し変更すると、交点を返すこの関数ができました。交点が見つからない場合は、-1、-1 を返します。
Public Function intercetion(ByVal ax As Integer, ByVal ay As Integer, ByVal bx As Integer, ByVal by As Integer, ByVal cx As Integer, ByVal cy As Integer, ByVal dx As Integer, ByVal dy As Integer) As Point
'// Determines the intersection point of the line segment defined by points A and B
'// with the line segment defined by points C and D.
'//
'// Returns YES if the intersection point was found, and stores that point in X,Y.
'// Returns NO if there is no determinable intersection point, in which case X,Y will
'// be unmodified.
Dim distAB, theCos, theSin, newX, ABpos As Double
'// Fail if either line segment is zero-length.
If ax = bx And ay = by Or cx = dx And cy = dy Then Return New Point(-1, -1)
'// Fail if the segments share an end-point.
If ax = cx And ay = cy Or bx = cx And by = cy Or ax = dx And ay = dy Or bx = dx And by = dy Then Return New Point(-1, -1)
'// (1) Translate the system so that point A is on the origin.
bx -= ax
by -= ay
cx -= ax
cy -= ay
dx -= ax
dy -= ay
'// Discover the length of segment A-B.
distAB = Math.Sqrt(bx * bx + by * by)
'// (2) Rotate the system so that point B is on the positive X axis.
theCos = bx / distAB
theSin = by / distAB
newX = cx * theCos + cy * theSin
cy = cy * theCos - cx * theSin
cx = newX
newX = dx * theCos + dy * theSin
dy = dy * theCos - dx * theSin
dx = newX
'// Fail if segment C-D doesn't cross line A-B.
If cy < 0 And dy < 0 Or cy >= 0 And dy >= 0 Then Return New Point(-1, -1)
'// (3) Discover the position of the intersection point along line A-B.
ABpos = dx + (cx - dx) * dy / (dy - cy)
'// Fail if segment C-D crosses line A-B outside of segment A-B.
If ABpos < 0 Or ABpos > distAB Then Return New Point(-1, -1)
'// (4) Apply the discovered position to line A-B in the original coordinate system.
'*X=Ax+ABpos*theCos
'*Y=Ay+ABpos*theSin
'// Success.
Return New Point(ax + ABpos * theCos, ay + ABpos * theSin)
End Function
于 2010-07-31T10:32:49.377 に答える
6
Cortijon がコメントで javascript バージョンを提案し、 iMalc がわずかに少ない計算でバージョンを提供したGavin の回答に関心があるようです。さまざまなコード提案の欠点を指摘する人もいれば、いくつかのコード提案の効率についてコメントする人もいます。
Gavinの回答を介してiMalcが提供するアルゴリズムは、私が現在javascriptプロジェクトで使用しているものであり、誰かに役立つ場合は、ここでクリーンアップされたバージョンを提供したかっただけです.
// Some variables for reuse, others may do this differently
var p0x, p1x, p2x, p3x, ix,
p0y, p1y, p2y, p3y, iy,
collisionDetected;
// do stuff, call other functions, set endpoints...
// note: for my purpose I use |t| < |d| as opposed to
// |t| <= |d| which is equivalent to 0 <= t < 1 rather than
// 0 <= t <= 1 as in Gavin's answer - results may vary
var lineSegmentIntersection = function(){
var d, dx1, dx2, dx3, dy1, dy2, dy3, s, t;
dx1 = p1x - p0x; dy1 = p1y - p0y;
dx2 = p3x - p2x; dy2 = p3y - p2y;
dx3 = p0x - p2x; dy3 = p0y - p2y;
collisionDetected = 0;
d = dx1 * dy2 - dx2 * dy1;
if(d !== 0){
s = dx1 * dy3 - dx3 * dy1;
if((s <= 0 && d < 0 && s >= d) || (s >= 0 && d > 0 && s <= d)){
t = dx2 * dy3 - dx3 * dy2;
if((t <= 0 && d < 0 && t > d) || (t >= 0 && d > 0 && t < d)){
t = t / d;
collisionDetected = 1;
ix = p0x + t * dx1;
iy = p0y + t * dy1;
}
}
}
};
于 2016-02-17T12:52:21.060 に答える
6
これは私にとってはうまくいっています。ここから撮影。
// calculates intersection and checks for parallel lines.
// also checks that the intersection point is actually on
// the line segment p1-p2
Point findIntersection(Point p1,Point p2,
Point p3,Point p4) {
float xD1,yD1,xD2,yD2,xD3,yD3;
float dot,deg,len1,len2;
float segmentLen1,segmentLen2;
float ua,ub,div;
// calculate differences
xD1=p2.x-p1.x;
xD2=p4.x-p3.x;
yD1=p2.y-p1.y;
yD2=p4.y-p3.y;
xD3=p1.x-p3.x;
yD3=p1.y-p3.y;
// calculate the lengths of the two lines
len1=sqrt(xD1*xD1+yD1*yD1);
len2=sqrt(xD2*xD2+yD2*yD2);
// calculate angle between the two lines.
dot=(xD1*xD2+yD1*yD2); // dot product
deg=dot/(len1*len2);
// if abs(angle)==1 then the lines are parallell,
// so no intersection is possible
if(abs(deg)==1) return null;
// find intersection Pt between two lines
Point pt=new Point(0,0);
div=yD2*xD1-xD2*yD1;
ua=(xD2*yD3-yD2*xD3)/div;
ub=(xD1*yD3-yD1*xD3)/div;
pt.x=p1.x+ua*xD1;
pt.y=p1.y+ua*yD1;
// calculate the combined length of the two segments
// between Pt-p1 and Pt-p2
xD1=pt.x-p1.x;
xD2=pt.x-p2.x;
yD1=pt.y-p1.y;
yD2=pt.y-p2.y;
segmentLen1=sqrt(xD1*xD1+yD1*yD1)+sqrt(xD2*xD2+yD2*yD2);
// calculate the combined length of the two segments
// between Pt-p3 and Pt-p4
xD1=pt.x-p3.x;
xD2=pt.x-p4.x;
yD1=pt.y-p3.y;
yD2=pt.y-p4.y;
segmentLen2=sqrt(xD1*xD1+yD1*yD1)+sqrt(xD2*xD2+yD2*yD2);
// if the lengths of both sets of segments are the same as
// the lenghts of the two lines the point is actually
// on the line segment.
// if the point isn’t on the line, return null
if(abs(len1-segmentLen1)>0.01 || abs(len2-segmentLen2)>0.01)
return null;
// return the valid intersection
return pt;
}
class Point{
float x,y;
Point(float x, float y){
this.x = x;
this.y = y;
}
void set(float x, float y){
this.x = x;
this.y = y;
}
}
于 2009-02-19T10:03:58.067 に答える
5
この問題にはもっと簡単な解決策があると思います。今日、別のアイデアを思いつきましたが、うまく機能しているようです (少なくとも今のところ 2D では)。必要なのは、2 つの線分の交点を計算し、計算された交点が両方の線分の境界ボックス内にあるかどうかを確認することだけです。そうである場合、線分は交差します。それでおしまい。
編集：
これは、交差点を計算する方法です（このコードスニペットを見つけた場所はもうわかりません）
Point3D
から来た
System.Windows.Media.Media3D
public static Point3D? Intersection(Point3D start1, Point3D end1, Point3D start2, Point3D end2) {
double a1 = end1.Y - start1.Y;
double b1 = start1.X - end1.X;
double c1 = a1 * start1.X + b1 * start1.Y;
double a2 = end2.Y - start2.Y;
double b2 = start2.X - end2.X;
double c2 = a2 * start2.X + b2 * start2.Y;
double det = a1 * b2 - a2 * b1;
if (det == 0) { // lines are parallel
return null;
}
double x = (b2 * c1 - b1 * c2) / det;
double y = (a1 * c2 - a2 * c1) / det;
return new Point3D(x, y, 0.0);
}
これは私の（答えのために簡略化された）BoundingBoxクラスです：
public class BoundingBox {
private Point3D min = new Point3D();
private Point3D max = new Point3D();
public BoundingBox(Point3D point) {
min = point;
max = point;
}
public Point3D Min {
get { return min; }
set { min = value; }
}
public Point3D Max {
get { return max; }
set { max = value; }
}
public bool Contains(BoundingBox box) {
bool contains =
min.X <= box.min.X && max.X >= box.max.X &&
min.Y <= box.min.Y && max.Y >= box.max.Y &&
min.Z <= box.min.Z && max.Z >= box.max.Z;
return contains;
}
public bool Contains(Point3D point) {
return Contains(new BoundingBox(point));
}
}
于 2014-09-24T20:19:40.297 に答える
2
C# での線分の基本的な実装と、対応する交差検出コードを次に示します。と呼ばれる 2D ベクトル/ポイント構造体Vector2fが必要ですが、これを X/Y プロパティを持つ他のタイプに置き換えることができます。それがあなたのニーズにより適している場合は、floatに置き換えることもできます。double
このコードは、私の .NET 物理ライブラリBoingで使用されています。
public struct LineSegment2f
{
public Vector2f From { get; }
public Vector2f To { get; }
public LineSegment2f(Vector2f @from, Vector2f to)
{
From = @from;
To = to;
}
public Vector2f Delta => new Vector2f(To.X - From.X, To.Y - From.Y);
/// <summary>
/// Attempt to intersect two line segments.
/// </summary>
/// <remarks>
/// Even if the line segments do not intersect, <paramref name="t"/> and <paramref name="u"/> will be set.
/// If the lines are parallel, <paramref name="t"/> and <paramref name="u"/> are set to <see cref="float.NaN"/>.
/// </remarks>
/// <param name="other">The line to attempt intersection of this line with.</param>
/// <param name="intersectionPoint">The point of intersection if within the line segments, or empty..</param>
/// <param name="t">The distance along this line at which intersection would occur, or NaN if lines are collinear/parallel.</param>
/// <param name="u">The distance along the other line at which intersection would occur, or NaN if lines are collinear/parallel.</param>
/// <returns><c>true</c> if the line segments intersect, otherwise <c>false</c>.</returns>
public bool TryIntersect(LineSegment2f other, out Vector2f intersectionPoint, out float t, out float u)
{
var p = From;
var q = other.From;
var r = Delta;
var s = other.Delta;
// t = (q − p) × s / (r × s)
// u = (q − p) × r / (r × s)
var denom = Fake2DCross(r, s);
if (denom == 0)
{
// lines are collinear or parallel
t = float.NaN;
u = float.NaN;
intersectionPoint = default(Vector2f);
return false;
}
var tNumer = Fake2DCross(q - p, s);
var uNumer = Fake2DCross(q - p, r);
t = tNumer / denom;
u = uNumer / denom;
if (t < 0 || t > 1 || u < 0 || u > 1)
{
// line segments do not intersect within their ranges
intersectionPoint = default(Vector2f);
return false;
}
intersectionPoint = p + r * t;
return true;
}
private static float Fake2DCross(Vector2f a, Vector2f b)
{
return a.X * b.Y - a.Y * b.X;
}
}
于 2016-05-24T07:18:22.693 に答える
2
これは、ガレス・リーの答えに基づいています。また、線分の重なりがあればそれも返します。C++ でコーディングされた V は単純なベクトル クラスです。2D の 2 つのベクトルの外積は単一のスカラーを返します。それは私の学校の自動テストシステムによってテストされ、合格しました。
//Required input point must be colinear with the line
bool on_segment(const V& p, const LineSegment& l)
{
//If a point is on the line, the sum of the vectors formed by the point to the line endpoints must be equal
V va = p - l.pa;
V vb = p - l.pb;
R ma = va.magnitude();
R mb = vb.magnitude();
R ml = (l.pb - l.pa).magnitude();
R s = ma + mb;
bool r = s <= ml + epsilon;
return r;
}
//Compute using vector math
// Returns 0 points if the lines do not intersect or overlap
// Returns 1 point if the lines intersect
// Returns 2 points if the lines overlap, contain the points where overlapping start starts and stop
std::vector<V> intersect(const LineSegment& la, const LineSegment& lb)
{
std::vector<V> r;
//http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect
V oa, ob, da, db; //Origin and direction vectors
R sa, sb; //Scalar values
oa = la.pa;
da = la.pb - la.pa;
ob = lb.pa;
db = lb.pb - lb.pa;
if (da.cross(db) == 0 && (ob - oa).cross(da) == 0) //If colinear
{
if (on_segment(lb.pa, la) && on_segment(lb.pb, la))
{
r.push_back(lb.pa);
r.push_back(lb.pb);
dprintf("colinear, overlapping\n");
return r;
}
if (on_segment(la.pa, lb) && on_segment(la.pb, lb))
{
r.push_back(la.pa);
r.push_back(la.pb);
dprintf("colinear, overlapping\n");
return r;
}
if (on_segment(la.pa, lb))
r.push_back(la.pa);
if (on_segment(la.pb, lb))
r.push_back(la.pb);
if (on_segment(lb.pa, la))
r.push_back(lb.pa);
if (on_segment(lb.pb, la))
r.push_back(lb.pb);
if (r.size() == 0)
dprintf("colinear, non-overlapping\n");
else
dprintf("colinear, overlapping\n");
return r;
}
if (da.cross(db) == 0 && (ob - oa).cross(da) != 0)
{
dprintf("parallel non-intersecting\n");
return r;
}
//Math trick db cross db == 0, which is a single scalar in 2D.
//Crossing both sides with vector db gives:
sa = (ob - oa).cross(db) / da.cross(db);
//Crossing both sides with vector da gives
sb = (oa - ob).cross(da) / db.cross(da);
if (0 <= sa && sa <= 1 && 0 <= sb && sb <= 1)
{
dprintf("intersecting\n");
r.push_back(oa + da * sa);
return r;
}
dprintf("non-intersecting, non-parallel, non-colinear, non-overlapping\n");
return r;
}
于 2014-05-08T19:55:59.217 に答える
1
@Gareth Rees の回答に基づく、Python のバージョン:
import numpy as np
def np_perp( a ) :
b = np.empty_like(a)
b[0] = a[1]
b[1] = -a[0]
return b
def np_cross_product(a, b):
return np.dot(a, np_perp(b))
def np_seg_intersect(a, b, considerCollinearOverlapAsIntersect = False):
# https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect/565282#565282
# http://www.codeproject.com/Tips/862988/Find-the-intersection-point-of-two-line-segments
r = a[1] - a[0]
s = b[1] - b[0]
v = b[0] - a[0]
num = np_cross_product(v, r)
denom = np_cross_product(r, s)
# If r x s = 0 and (q - p) x r = 0, then the two lines are collinear.
if np.isclose(denom, 0) and np.isclose(num, 0):
# 1. If either 0 <= (q - p) * r <= r * r or 0 <= (p - q) * s <= * s
# then the two lines are overlapping,
if(considerCollinearOverlapAsIntersect):
vDotR = np.dot(v, r)
aDotS = np.dot(-v, s)
if (0 <= vDotR and vDotR <= np.dot(r,r)) or (0 <= aDotS and aDotS <= np.dot(s,s)):
return True
# 2. If neither 0 <= (q - p) * r = r * r nor 0 <= (p - q) * s <= s * s
# then the two lines are collinear but disjoint.
# No need to implement this expression, as it follows from the expression above.
return None
if np.isclose(denom, 0) and not np.isclose(num, 0):
# Parallel and non intersecting
return None
u = num / denom
t = np_cross_product(v, s) / denom
if u >= 0 and u <= 1 and t >= 0 and t <= 1:
res = b[0] + (s*u)
return res
# Otherwise, the two line segments are not parallel but do not intersect.
return None
于 2016-04-05T02:52:47.243 に答える
1
指定された 2 つの線分が交差しているかどうかをチェックする C++ プログラム
#include <iostream>
using namespace std;
struct Point
{
int x;
int y;
};
// Given three colinear points p, q, r, the function checks if
// point q lies on line segment 'pr'
bool onSegment(Point p, Point q, Point r)
{
if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
return true;
return false;
}
// To find orientation of ordered triplet (p, q, r).
// The function returns following values
// 0 --> p, q and r are colinear
// 1 --> Clockwise
// 2 --> Counterclockwise
int orientation(Point p, Point q, Point r)
{
// See 10th slides from following link for derivation of the formula
// http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf
int val = (q.y - p.y) * (r.x - q.x) -
(q.x - p.x) * (r.y - q.y);
if (val == 0) return 0; // colinear
return (val > 0)? 1: 2; // clock or counterclock wise
}
// The main function that returns true if line segment 'p1q1'
// and 'p2q2' intersect.
bool doIntersect(Point p1, Point q1, Point p2, Point q2)
{
// Find the four orientations needed for general and
// special cases
int o1 = orientation(p1, q1, p2);
int o2 = orientation(p1, q1, q2);
int o3 = orientation(p2, q2, p1);
int o4 = orientation(p2, q2, q1);
// General case
if (o1 != o2 && o3 != o4)
return true;
// Special Cases
// p1, q1 and p2 are colinear and p2 lies on segment p1q1
if (o1 == 0 && onSegment(p1, p2, q1)) return true;
// p1, q1 and p2 are colinear and q2 lies on segment p1q1
if (o2 == 0 && onSegment(p1, q2, q1)) return true;
// p2, q2 and p1 are colinear and p1 lies on segment p2q2
if (o3 == 0 && onSegment(p2, p1, q2)) return true;
// p2, q2 and q1 are colinear and q1 lies on segment p2q2
if (o4 == 0 && onSegment(p2, q1, q2)) return true;
return false; // Doesn't fall in any of the above cases
}
// Driver program to test above functions
int main()
{
struct Point p1 = {1, 1}, q1 = {10, 1};
struct Point p2 = {1, 2}, q2 = {10, 2};
doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";
p1 = {10, 0}, q1 = {0, 10};
p2 = {0, 0}, q2 = {10, 10};
doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";
p1 = {-5, -5}, q1 = {0, 0};
p2 = {1, 1}, q2 = {10, 10};
doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n";
return 0;
}
于 2015-02-08T05:32:34.097 に答える
0
t3chb0t の回答に基づく:
int intersezione_linee(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, int& p_x, int& p_y)
{
//L1: estremi (x1,y1)(x2,y2) L2: estremi (x3,y3)(x3,y3)
int d;
d = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4);
if(!d)
return 0;
p_x = ((x1*y2-y1*x2)*(x3-x4) - (x1-x2)*(x3*y4-y3*x4))/d;
p_y = ((x1*y2-y1*x2)*(y3-y4) - (y1-y2)*(x3*y4-y3*x4))/d;
return 1;
}
int in_bounding_box(int x1, int y1, int x2, int y2, int p_x, int p_y)
{
return p_x>=x1 && p_x<=x2 && p_y>=y1 && p_y<=y2;
}
int intersezione_segmenti(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, int& p_x, int& p_y)
{
if (!intersezione_linee(x1,y1,x2,y2,x3,y3,x4,y4,p_x,p_y))
return 0;
return in_bounding_box(x1,y1,x2,y2,p_x,p_y) && in_bounding_box(x3,y3,x4,y4,p_x,p_y);
}
于 2014-09-26T15:22:04.650 に答える
0
長方形の各辺が線分であり、ユーザーが描いた部分が線分である場合、ユーザーが描いた線分と 4 つの辺の線分との交差をチェックするだけで済みます。各セグメントの開始点と終了点を考えると、これはかなり単純な演習になるはずです。
于 2009-02-18T22:53:00.050 に答える
0
これらのアルゴリズムは、本「多視点幾何学」から読みました
次のテキストを使用して
' 転置記号として
*内積として
x を外積として、演算子として使用する場合
1.ライン定義
点 x_vec = (x, y)' は線 ax + by + c = 0 上にあります
L = (a, b, c)' とし、点を (x, y, 1)' として同次座標とする
直線方程式は次のように記述できます。
(x, y, 1)(a, b, c)' = 0 または x' * L = 0
2.線の交点
L1=(a1, b1, c1)'、L2=(a2, b2, c2)' の 2 つの行があります。
x は点、ベクトル、x = L1 x L2 (L1 外積 L2) であると仮定します。
注意してください、x は常に 2D 点です。(L1xL2) が 3 つの要素のベクトルであり、x が 2D 座標であることに混乱している場合は、同次座標を読んでください。
三重積によると、
L1 * ( L1 x L2 ) = 0、および L2 * (L1 x L2) = 0 (L1,L2 同一平面のため)
(L1xL2) をベクトル x に置き換えると、L1*x=0、L2*x=0 が得られます。これは、x が L1 と L2 の両方にあることを意味し、x は交点です。
注意してください。ここで x は同次座標です。x の最後の要素がゼロの場合、L1 と L2 が平行であることを意味します。
于 2015-09-08T18:15:44.603 に答える