私が開発しているゲームでは、交点を計算できるアルゴリズムが必要です。私は問題を解決しましたが、私が行った方法は本当に厄介で、ここの誰かがよりエレガントな解決策を持っていることを願っています.
点のペアは、それらの間に引かれた線の終点を表します。2 組の点が与えられたとき、描かれた線は交差しますか?交差する場合、どの点で交差しますか?
たとえば、(Ax, Ay)-(Bx, By) および (Cx, Cy)-(Dx, Dy) という行を呼び出します。
誰でも解決策を考えることができますか？任意の言語でのソリューションで十分です。
編集:より明確にする必要がある点です。交点が線分の長さを超えている場合、アルゴリズムは false を返す必要があります。
すでにここにある答えのほとんどは、次のような一般的な考え方に従っているようです。
しかし、交差点が頻繁に発生しない場合は、おそらくこれらの手順を逆にするのがより良い方法です。
注：手順2を実行するには、（Cy-a（Cx）-b）と（Dy-a（Dx）-b）の符号が同じかどうかを確認します。手順3も同様です。ステップ5は、2つの方程式からの単なる標準的な数学です。
さらに、各線分を（n-1）の他の線分と比較する必要がある場合は、すべての線に対してステップ1を事前に計算することで、時間を節約できます。
重要なことを行う予定がある場合は、機会があれば、衝突検出のバイブルである「リアルタイム衝突検出」を実際に確認する必要があります。私はプロのゲーム プログラマーではありませんが、その概念を理解し、問題なく適用することができました。
基本的に、ライン交差テストのセットを行うには、何があってもコストがかかります。あなたがしていることは、複雑なポリゴンに対してバウンディング ボックス (軸の位置合わせまたは向き) などを使用することです。これにより、各「オブジェクト」間の衝突の最悪の場合の O(N^2) チェックをすばやく実行できます。次に、空間ツリー (Binary Partitioning または QuadTrees) を使用して、互いに近いオブジェクトの交差のみをチェックすることで、さらに高速化できます。
これにより、非常に多くの衝突テストを削除できます。最善の最適化は、何もしないことです。バウンディング ボックス間の衝突が発生した場合にのみ、コストのかかる線の交差を行って、オブジェクトが本当に交差するかどうかを判断します。これにより、妥当な速度を維持しながら、オブジェクトの数を増やすことができます。
float x12 = x1 - x2;
float x34 = x3 - x4;
float y12 = y1 - y2;
float y34 = y3 - y4;
float c = x12 * y34 - y12 * x34;
if (fabs(c) < 0.01)
{
// No intersection
return false;
}
else
{
// Intersection
float a = x1 * y2 - y1 * x2;
float b = x3 * y4 - y3 * x4;
float x = (a * x34 - b * x12) / c;
float y = (a * y34 - b * y12) / c;
return true;
}
から取られた式：
線線交叉-ウィキペディア
時間を大幅に節約できる簡単な最適化は、交差点の計算に入る前に、線の軸に沿った境界ボックスをチェックすることです。
バウンディングボックスが完全にばらばらである場合は、交差がないことを確認できます。
もちろん、これはあなたが持っているデータに依存します。すべてのチェックで交差点が発生する可能性が非常に高い場合は、常に正しいチェックに時間を浪費していることに気付くかもしれません。
public struct PointD
{
public double X { get; set; }
public double Y { get; set; }
}
/// <summary>
/// Find the intersection point between two lines.
/// </summary>
/// <param name="IntersectPoint">The intersection point. A <see cref="Esteem.Geometry.PointD">PointD</see> structure.</param>
/// <param name="L1StartPoint">The starting point of first line. A PointD structure.</param>
/// <param name="L1EndPoint">The end point of first line. A PointD structure.</param>
/// <param name="L2StartPoint">The starting point of second line. A PointD structure.</param>
/// <param name="L2EndPoint">The end point of second line. A PointD structure.</param>
/// <param name="L1IntersectPos">The intersection position at first line.</param>
/// <param name="L2IntersectPos">The intersection position at second line.</param>
/// <returns>Returns a boolean. True if there is intersection, false otherwise.</returns>
/// <remarks>The formula is taken from comp.graphics.algorithms Frequently Asked Questions.</remarks>
public static bool LineIntersect(out PointD IntersectPoint, PointD L1StartPoint, PointD L1EndPoint, PointD L2StartPoint, PointD L2EndPoint, out double L1IntersectPos, out double L2IntersectPos)
{
IntersectPoint = new PointD();
double ay_cy, ax_cx, px, py;
double dx_cx = L2EndPoint.X - L2StartPoint.X,
dy_cy = L2EndPoint.Y - L2StartPoint.Y,
bx_ax = L1EndPoint.X - L1StartPoint.X,
by_ay = L1EndPoint.Y - L1StartPoint.Y;
double de = (bx_ax) * (dy_cy) - (by_ay) * (dx_cx);
//double tor = 1.0E-10; //tolerance
L1IntersectPos = 0; L2IntersectPos = 0;
if (Math.Abs(de)<0.01)
return false;
//if (de > -tor && de < tor) return false; //line is in parallel
ax_cx = L1StartPoint.X - L2StartPoint.X;
ay_cy = L1StartPoint.Y - L2StartPoint.Y;
double r = ((ay_cy) * (dx_cx) - (ax_cx) * (dy_cy)) / de;
double s = ((ay_cy) * (bx_ax) - (ax_cx) * (by_ay)) / de;
px = L1StartPoint.X + r * (bx_ax);
py = L1StartPoint.Y + r * (by_ay);
IntersectPoint.X = px; //return the intersection point
IntersectPoint.Y = py; //return the intersection position
L1IntersectPos = r; L2IntersectPos = s;
return true; //indicate there is intersection
}
交点が線の元の長さを超えていないかどうかを確認するには、次のことを確認し0<r<1てください。0<s<1
以下は、 MathWorldで説明されている私の線と線の交点です。一般的な衝突検出/交差については、Separating Axis Theoremを参照してください。SAT に関するこのチュートリアルは非常に有益であることがわかりました。
/// <summary>
/// Returns the intersection point of the given lines.
/// Returns Empty if the lines do not intersect.
/// Source: http://mathworld.wolfram.com/Line-LineIntersection.html
/// </summary>
public static PointF LineIntersection(PointF v1, PointF v2, PointF v3, PointF v4)
{
float tolerance = 0.000001f;
float a = Det2(v1.X - v2.X, v1.Y - v2.Y, v3.X - v4.X, v3.Y - v4.Y);
if (Math.Abs(a) < float.Epsilon) return PointF.Empty; // Lines are parallel
float d1 = Det2(v1.X, v1.Y, v2.X, v2.Y);
float d2 = Det2(v3.X, v3.Y, v4.X, v4.Y);
float x = Det2(d1, v1.X - v2.X, d2, v3.X - v4.X) / a;
float y = Det2(d1, v1.Y - v2.Y, d2, v3.Y - v4.Y) / a;
if (x < Math.Min(v1.X, v2.X) - tolerance || x > Math.Max(v1.X, v2.X) + tolerance) return PointF.Empty;
if (y < Math.Min(v1.Y, v2.Y) - tolerance || y > Math.Max(v1.Y, v2.Y) + tolerance) return PointF.Empty;
if (x < Math.Min(v3.X, v4.X) - tolerance || x > Math.Max(v3.X, v4.X) + tolerance) return PointF.Empty;
if (y < Math.Min(v3.Y, v4.Y) - tolerance || y > Math.Max(v3.Y, v4.Y) + tolerance) return PointF.Empty;
return new PointF(x, y);
}
/// <summary>
/// Returns the determinant of the 2x2 matrix defined as
/// <list>
/// <item>| x1 x2 |</item>
/// <item>| y1 y2 |</item>
/// </list>
/// </summary>
public static float Det2(float x1, float x2, float y1, float y2)
{
return (x1 * y2 - y1 * x2);
}
（どうすればよいかまだわからない場合を除いて、これをコメントとして残しておきます。）
境界ボックス テストの代替/補足として、線の中点間の距離が線の合計長の半分より大きいかどうかをテストすることもできます。もしそうなら、線が交差することはありません。
各線を囲む最小限の円を想像してから、円の交差をテストします。これにより、事前計算 (少なくとも静的な線、およびそれらの長さを保持する線) と、多くの潜在的な交差を除外する効率的な方法が可能になります。
そこで数学とスカラー積が役に立ちます。
- 線分 [AB] と [CD] を交差させたいとします - 線分
の交点を M とします
M がセグメント [ÅB] 内にあるのは、 Vector(AB)の場合のみです。ベクトル(AM) >= 0
および
ベクトル(AB) . ベクトル(MB) >= 0
ドット「。」はスカラー積を表します: u . v = ux * vx + uy * vy
したがって、あなたのアルゴリズムは次の
とおり
です
。ベクトル(AM) >= 0
ベクトル(AB) . ベクトル(MB) >= 0
ベクトル(CD) . ベクトル(CM) >= 0
ベクトル(CD) . ベクトル(MD) >= 0
お役に立てれば
private function Loop(e:Event):void
{
var x12:Number = Ball1.x - Ball2.x;
var x34:Number = Ball3.x - Ball4.x;
var y12:Number = Ball1.y - Ball2.y;
var y34:Number = Ball3.y - Ball4.y;
// Det
var c:Number = x12 * y34 - y12 * x34;
if (Math.abs(c) < 0.01)
{
Circle.visible = false;
}
else
{
var a:Number = Ball1.x * Ball2.y - Ball1.y * Ball2.x;
var b:Number = Ball3.x * Ball4.y - Ball3.y * Ball4.x;
var px:Number = (a * x34 - b * x12) / c;
var py:Number = (a * y34 - b * y12) / c;
var Btwn12x:Boolean = (px >= Math.min(Ball1.x, Ball2.x)) && (px <= Math.max(Ball1.x, Ball2.x));
var Btwn12y:Boolean = (py >= Math.min(Ball1.y, Ball2.y)) && (py <= Math.max(Ball1.y, Ball2.y));
var Btwn34x:Boolean = (px >= Math.min(Ball3.x, Ball4.x)) && (px <= Math.max(Ball3.x, Ball4.x));
var Btwn34y:Boolean = (py >= Math.min(Ball3.y, Ball4.y)) && (py <= Math.max(Ball3.y, Ball4.y));
var Btwn12:Boolean = Btwn12x && Btwn12y;
var Btwn34:Boolean = Btwn34x && Btwn34y;
if(Btwn12 && Btwn34)
{
Circle.visible = true;
Circle.x = px;
Circle.y = py;
}
else
{
Circle.visible = false;
}
}
}