public static bool LineIntersectsRect(Point p1, Point p2, Rectangle r)
{
return LineIntersectsLine(p1, p2, new Point(r.X, r.Y), new Point(r.X + r.Width, r.Y)) ||
LineIntersectsLine(p1, p2, new Point(r.X + r.Width, r.Y), new Point(r.X + r.Width, r.Y + r.Height)) ||
LineIntersectsLine(p1, p2, new Point(r.X + r.Width, r.Y + r.Height), new Point(r.X, r.Y + r.Height)) ||
LineIntersectsLine(p1, p2, new Point(r.X, r.Y + r.Height), new Point(r.X, r.Y)) ||
(r.Contains(p1) && r.Contains(p2));
}
private static bool LineIntersectsLine(Point l1p1, Point l1p2, Point l2p1, Point l2p2)
{
float q = (l1p1.Y - l2p1.Y) * (l2p2.X - l2p1.X) - (l1p1.X - l2p1.X) * (l2p2.Y - l2p1.Y);
float d = (l1p2.X - l1p1.X) * (l2p2.Y - l2p1.Y) - (l1p2.Y - l1p1.Y) * (l2p2.X - l2p1.X);
if( d == 0 )
{
return false;
}
float r = q / d;
q = (l1p1.Y - l2p1.Y) * (l1p2.X - l1p1.X) - (l1p1.X - l2p1.X) * (l1p2.Y - l1p1.Y);
float s = q / d;
if( r < 0 || r > 1 || s < 0 || s > 1 )
{
return false;
}
return true;
}
残念ながら、間違った答えが投票されました。実際の交点を計算するのは非常にコストがかかります。必要なのは比較だけです。検索するキーワードは「ライン クリッピング」( http://en.wikipedia.org/wiki/Line_clipping ) です。ウィキペディアは、おそらく最も一般的なシナリオである、迅速な拒否が必要な場合にCohen-Sutherland アルゴリズム ( http://en.wikipedia.org/wiki/Cohen%E2%80%93Sutherland ) を推奨しています。ウィキペディアのページに C++ 実装があります。実際に線を切り取ることに関心がない場合は、そのほとんどをスキップできます。@Johannの答えはそのアルゴリズムに非常に似ていますが、詳しくは見ていません。
ブルート フォース アルゴリズム...
最初に、四角形が線の終点の左または右にあるかどうかを確認します。
次に、上記が交差を除外するのに十分でない場合は、四角形が線の終点の上または下にあるかどうかを確認します。
次に、上記が交差を除外するのに十分でない場合は、線の方程式 をチェックしてy = m * x + b、四角形が線の上にあるかどうかを確認する必要があります。
次に、上記が交差を除外するのに十分でない場合は、四角形が線の下にあるかどうかを確認する必要があります。
次に、ここに着いたら：
注: もっと洗練された代数的ソリューションがあると確信していますが、これらの手順をペンと紙で幾何学的に実行するのは簡単です。
それに伴ういくつかの未テストおよび未コンパイルのコード：
public struct Line
{
public int XMin { get { ... } }
public int XMax { get { ... } }
public int YMin { get { ... } }
public int YMax { get { ... } }
public Line(Point a, Point b) { ... }
public float CalculateYForX(int x) { ... }
}
public bool Intersects(Point a, Point b, Rectangle r)
{
var line = new Line(a, b);
if (r.Left > line.XMax || r.Right < line.XMin)
{
return false;
}
if (r.Top < line.YMin || r.Bottom > line.YMax)
{
return false;
}
var yAtRectLeft = line.CalculateYForX(r.Left);
var yAtRectRight = line.CalculateYForX(r.Right);
if (r.Bottom > yAtRectLeft && r.Bottom > yAtRectRight)
{
return false;
}
if (r.Top < yAtRectLeft && r.Top < yAtRectRight)
{
return false;
}
return true;
}
このコードはより優れたパフォーマンスを発揮します:
public static bool SegmentIntersectRectangle(
double rectangleMinX,
double rectangleMinY,
double rectangleMaxX,
double rectangleMaxY,
double p1X,
double p1Y,
double p2X,
double p2Y)
{
// Find min and max X for the segment
double minX = p1X;
double maxX = p2X;
if (p1X > p2X)
{
minX = p2X;
maxX = p1X;
}
// Find the intersection of the segment's and rectangle's x-projections
if (maxX > rectangleMaxX)
{
maxX = rectangleMaxX;
}
if (minX < rectangleMinX)
{
minX = rectangleMinX;
}
if (minX > maxX) // If their projections do not intersect return false
{
return false;
}
// Find corresponding min and max Y for min and max X we found before
double minY = p1Y;
double maxY = p2Y;
double dx = p2X - p1X;
if (Math.Abs(dx) > 0.0000001)
{
double a = (p2Y - p1Y)/dx;
double b = p1Y - a*p1X;
minY = a*minX + b;
maxY = a*maxX + b;
}
if (minY > maxY)
{
double tmp = maxY;
maxY = minY;
minY = tmp;
}
// Find the intersection of the segment's and rectangle's y-projections
if (maxY > rectangleMaxY)
{
maxY = rectangleMaxY;
}
if (minY < rectangleMinY)
{
minY = rectangleMinY;
}
if (minY > maxY) // If Y-projections do not intersect return false
{
return false;
}
return true;
}
また、JS デモでどのように機能するかを確認することもできます: http://jsfiddle.net/77eej/2/
2 つの Points と Rect がある場合、この関数を次のように呼び出すことができます。
public static bool LineIntersectsRect(Point p1, Point p2, Rect r)
{
return SegmentIntersectRectangle(r.X, r.Y, r.X + r.Width, r.Y + r.Height, p1.X, p1.Y, p2.X, p2.Y);
}
うまく機能するHABJANのソリューションを採用し、それをObjective-Cに変換しました。Objective-C コードは次のとおりです。
bool LineIntersectsLine(CGPoint l1p1, CGPoint l1p2, CGPoint l2p1, CGPoint l2p2)
{
CGFloat q = (l1p1.y - l2p1.y) * (l2p2.x - l2p1.x) - (l1p1.x - l2p1.x) * (l2p2.y - l2p1.y);
CGFloat d = (l1p2.x - l1p1.x) * (l2p2.y - l2p1.y) - (l1p2.y - l1p1.y) * (l2p2.x - l2p1.x);
if( d == 0 )
{
return false;
}
float r = q / d;
q = (l1p1.y - l2p1.y) * (l1p2.x - l1p1.x) - (l1p1.x - l2p1.x) * (l1p2.y - l1p1.y);
float s = q / d;
if( r < 0 || r > 1 || s < 0 || s > 1 )
{
return false;
}
return true;
}
bool LineIntersectsRect(CGPoint p1, CGPoint p2, CGRect r)
{
return LineIntersectsLine(p1, p2, CGPointMake(r.origin.x, r.origin.y), CGPointMake(r.origin.x + r.size.width, r.origin.y)) ||
LineIntersectsLine(p1, p2, CGPointMake(r.origin.x + r.size.width, r.origin.y), CGPointMake(r.origin.x + r.size.width, r.origin.y + r.size.height)) ||
LineIntersectsLine(p1, p2, CGPointMake(r.origin.x + r.size.width, r.origin.y + r.size.height), CGPointMake(r.origin.x, r.origin.y + r.size.height)) ||
LineIntersectsLine(p1, p2, CGPointMake(r.origin.x, r.origin.y + r.size.height), CGPointMake(r.origin.x, r.origin.y)) ||
(CGRectContainsPoint(r, p1) && CGRectContainsPoint(r, p2));
}
どうもありがとうHABJAN。最初に、勾配に沿った各ポイントをチェックする独自のルーチンを作成し、パフォーマンスを最大化するためにできる限りのことを行いましたが、これはすぐにはるかに高速になりました。
これを実現するために呼び出すことができる単純な事前定義された .NET メソッドはありません。ただし、Win32 API を使用すると、これを行うための非常に簡単な方法があります (実装という意味では簡単ですが、パフォーマンスは長所ではありません)。
BOOL LineDDA(int nXStart,int nYStart,int nXEnd,int nYEnd,LINEDDAPROC lpLineFunc,LPARAM lpData)
この関数は、描画される線のすべてのピクセルに対してコールバック関数を呼び出します。この関数では、ピクセルが長方形内にあるかどうかを確認できます。見つかった場合は、交差します。
私が言うように、これは最速のソリューションではありませんが、実装は非常に簡単です。C# で使用するには、もちろん gdi32.dll から ddlimport する必要があります。
[DllImport("gdi32.dll")] public static extern int LineDDA(int n1,int n2,int n3,int n4,int lpLineDDAProc,int lParam);
最も単純な計算ジオメトリ手法は、ポリゴンのセグメントをウォークスルーし、それらのいずれかと交差するかどうかを確認することです。これは、ポリゴンとも交差する必要があるためです。
この方法 (およびほとんどの CG) の唯一の注意点は、エッジ ケースに注意する必要があることです。直線が四角形と一点で交差する場合、それを交点として数えますか? 実装には注意してください。
編集: 線分セグメント計算の典型的なツールはLeftOf(Ray, Point)テストで、点が光線の左側にあるかどうかを返します。線 (光線として使用) と点およびlを含む線分が与えられた場合、1 つの点が左にあり、1 つの点がそうでない場合、線は線分と交差します。ab
(LeftOf(l,a) && !LeftOf(l,b)) || (LeftOf(l,b) && !LeftOf(l,a))
繰り返しますが、点が線上にある場合はエッジケースに注意する必要がありますが、実際に交差点をどのように定義するかによって異なります。