線分が2Dで軸に沿った長方形と交差するかどうかをテストする方法は? セグメントは、その 2 つの端点 p1、p2 で定義されます。四角形は、左上と右下の点で定義されます。
metamal
質問する
39678 次
12 に答える
61
元のポスターは、線分とポリゴンの交点を検出したいと考えていました。交差点がある場合は、その場所を特定する必要はありませんでした。それがあなたがそれを意味した方法であるならば、あなたはLiang-BarskyまたはCohen-Sutherlandより少ない仕事をすることができます：
セグメントの端点をp1=（x1 y1）およびp2 =（x2 y2）とします。
長方形の角を（xBL yBL）と（xTR yTR）とします。
その後、あなたがしなければならないのは
A.長方形の4つの角すべてが線の同じ側にあるかどうかを確認します。p1とp2を通る直線の陰方程式は次のとおりです。
F（xy）=（y2-y1）* x +（x1-x2）* y +（x2 * y1-x1 * y2）
F（xy）= 0の場合、（xy）は回線上にあります。
F（xy）> 0の場合、（xy）は線の「上」にあります。
F（xy）<0の場合、（xy）は線の「下」にあります。
4つの角すべてをF（xy）に置き換えます。それらがすべて負またはすべて正の場合、共通部分はありません。一部が正で一部が負の場合は、手順Bに進みます。
B.端点をx軸に投影し、セグメントの影がポリゴンの影と交差するかどうかを確認します。y軸で繰り返します。
（x1>xTRおよびx2>xTR）の場合、交差はありません（線は長方形の右側にあります）。
（x1<xBLおよびx2<xBL）の場合、交差はありません（線は長方形の左側にあります）。
（y1>yTRおよびy2>yTR）の場合、交点はありません（線は長方形の上にあります）。
（y1<yBLおよびy2<yBL）の場合、交点はありません（線は長方形の下にあります）。
そうでなければ、交差点があります。コーエン-サザランドまたはあなたの質問に対する他の回答で言及されたコードを実行してください。
もちろん、最初にBを実行し、次にAを実行できます。
アレホ
于 2008-11-15T21:07:35.647 に答える
27
非常にシンプルで実用的なソリューションを作成しました：
bool SegmentIntersectRectangle(double a_rectangleMinX,
double a_rectangleMinY,
double a_rectangleMaxX,
double a_rectangleMaxY,
double a_p1x,
double a_p1y,
double a_p2x,
double a_p2y)
{
// Find min and max X for the segment
double minX = a_p1x;
double maxX = a_p2x;
if(a_p1x > a_p2x)
{
minX = a_p2x;
maxX = a_p1x;
}
// Find the intersection of the segment's and rectangle's x-projections
if(maxX > a_rectangleMaxX)
{
maxX = a_rectangleMaxX;
}
if(minX < a_rectangleMinX)
{
minX = a_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 = a_p1y;
double maxY = a_p2y;
double dx = a_p2x - a_p1x;
if(Math::Abs(dx) > 0.0000001)
{
double a = (a_p2y - a_p1y) / dx;
double b = a_p1y - a * 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 > a_rectangleMaxY)
{
maxY = a_rectangleMaxY;
}
if(minY < a_rectangleMinY)
{
minY = a_rectangleMinY;
}
if(minY > maxY) // If Y-projections do not intersect return false
{
return false;
}
return true;
}
于 2008-09-19T07:07:52.417 に答える
9
長方形が整列しているため、Liang-Barsky が良い解決策になる可能性があります。ここで速度が重要な場合、Cohen-Sutherland よりも高速です。
于 2008-09-19T03:51:35.290 に答える
7
また、セグメントから四角形を作成し、他の四角形がそれと衝突するかどうかをテストすることもできます。これは一連の比較にすぎないためです。pygame ソースから:
def _rect_collide(a, b):
return a.x + a.w > b.x and b.x + b.w > a.x and \
a.y + a.h > b.y and b.y + b.h > a.y
于 2012-12-12T16:57:45.013 に答える
5
Cohen-Sutherland アルゴリズムを使用します。
クリッピングに使用されますが、このタスク用に微調整できます。2D 空間を、長方形を「中央の正方形」として三目並べボードに分割します。
次に、ラインの 2 つのポイントがそれぞれ 9 つの領域のどれにあるかを確認します。
- 両方のポイントが左、右、上、または下の場合、自明に拒否します。
- いずれかのポイントが内側にある場合は、自明に受け入れます。
- 残りのまれなケースでは、それらがどの領域にあるかに基づいて、交差する可能性のある長方形の辺と交差するように計算を行うことができます.
于 2008-09-19T03:42:10.523 に答える
3
または、すでにJavaメソッドにあるコードを使用/コピーするだけです
java.awt.geom.Rectangle2D.intersectsLine(double x1, double y1, double x2, double y2)
便宜上、静的に変換した後のメソッドを次に示します。
/**
* Code copied from {@link java.awt.geom.Rectangle2D#intersectsLine(double, double, double, double)}
*/
public class RectangleLineIntersectTest {
private static final int OUT_LEFT = 1;
private static final int OUT_TOP = 2;
private static final int OUT_RIGHT = 4;
private static final int OUT_BOTTOM = 8;
private static int outcode(double pX, double pY, double rectX, double rectY, double rectWidth, double rectHeight) {
int out = 0;
if (rectWidth <= 0) {
out |= OUT_LEFT | OUT_RIGHT;
} else if (pX < rectX) {
out |= OUT_LEFT;
} else if (pX > rectX + rectWidth) {
out |= OUT_RIGHT;
}
if (rectHeight <= 0) {
out |= OUT_TOP | OUT_BOTTOM;
} else if (pY < rectY) {
out |= OUT_TOP;
} else if (pY > rectY + rectHeight) {
out |= OUT_BOTTOM;
}
return out;
}
public static boolean intersectsLine(double lineX1, double lineY1, double lineX2, double lineY2, double rectX, double rectY, double rectWidth, double rectHeight) {
int out1, out2;
if ((out2 = outcode(lineX2, lineY2, rectX, rectY, rectWidth, rectHeight)) == 0) {
return true;
}
while ((out1 = outcode(lineX1, lineY1, rectX, rectY, rectWidth, rectHeight)) != 0) {
if ((out1 & out2) != 0) {
return false;
}
if ((out1 & (OUT_LEFT | OUT_RIGHT)) != 0) {
double x = rectX;
if ((out1 & OUT_RIGHT) != 0) {
x += rectWidth;
}
lineY1 = lineY1 + (x - lineX1) * (lineY2 - lineY1) / (lineX2 - lineX1);
lineX1 = x;
} else {
double y = rectY;
if ((out1 & OUT_BOTTOM) != 0) {
y += rectHeight;
}
lineX1 = lineX1 + (y - lineY1) * (lineX2 - lineX1) / (lineY2 - lineY1);
lineY1 = y;
}
}
return true;
}
}
于 2011-03-22T04:50:23.920 に答える
1
Google で簡単に検索すると、交差点をテストするための C++ コードを含むページがポップアップ表示されました。
基本的に、線とすべての境界線または長方形の間の交差をテストします。
于 2008-09-19T03:45:09.410 に答える
0
私は同様の問題を見ていましたが、ここに私が思いついたものがあります。私は最初に端を比較していて、何かに気づきました。最初のボックスの反対側の軸内にあるエッジの中点が、同じ軸の最初のボックスの外側のポイントのエッジの長さの半分以内にある場合、その辺のどこかに交点があります。しかし、それは 1 次元で考えており、理解するには 2 番目のボックスの各側面を調べる必要がありました。
2 番目のボックスの「中点」を見つけ、中点の座標を比較して、最初のボックスの外寸の (2 番目のボックスの) 辺の長さの 1/2 以内にあるかどうかを確認すると、突然思いつきました。 、そしてどこかに交差点があります。
i.e. box 1 is bounded by x1,y1 to x2,y2
box 2 is bounded by a1,b1 to a2,b2
the width and height of box 2 is:
w2 = a2 - a1 (half of that is w2/2)
h2 = b2 - b1 (half of that is h2/2)
the midpoints of box 2 are:
am = a1 + w2/2
bm = b1 + h2/2
So now you just check if
(x1 - w2/2) < am < (x2 + w2/2) and (y1 - h2/2) < bm < (y2 + h2/2)
then the two overlap somewhere.
If you want to check also for edges intersecting to count as 'overlap' then
change the < to <=
もちろん、逆の方法で簡単に比較することもできます (ボックス 1 の中点がボックス 2 の外側の寸法の 1/2 の長さ以内であることを確認します)。
さらに単純化すると、中点を半分の長さだけシフトすると、そのボックスの原点と同じになります。つまり、境界範囲内にあるポイントだけをチェックできるようになり、プレーンを左上にシフトすることで、下隅が最初のボックスの下隅になります。はるかに少ない数学:
(x1 - w2) < a1 < x2
&&
(y1 - h2) < b1 < y2
[overlap exists]
または非置換:
( (x1-(a2-a1)) < a1 < x2 ) && ( (y1-(b2-b1)) < b1 < y2 ) [overlap exists]
( (x1-(a2-a1)) <= a1 <= x2 ) && ( (y1-(b2-b1)) <= b1 <= y2 ) [overlap or intersect exists]
于 2012-07-26T18:10:40.550 に答える
0
私は少しナプキンソリューションをしました..
次に、m と c を見つけて、方程式y = mx + cを見つけます。
y = (Point2.Y - Point1.Y) / (Point2.X - Point1.X)
P1座標を代入してcを見つけます
長方形の頂点の場合、X 値を直線方程式に入れ、Y 値を取得して、Y 値が以下に示す長方形の境界内にあるかどうかを確認します。
(そのような長方形の定数値 X1、X2、Y1、Y2 を見つけることができます)
X1 <= x <= X2 &
Y1 <= y <= Y2
Y 値が上記の条件を満たし、(Point1.Y, Point2.Y) の間にある場合、交差があります。これがカットに失敗した場合は、すべての頂点を試してください。
于 2008-09-19T04:11:53.213 に答える
0
PHP でのコーディング例 (ポリゴンの外側の座標を取得するために getLeft()、getRight()、getTop()、getBottom() などのメソッドを持ち、getWidth() と getHeight を持つオブジェクト モデルを使用しています) () - 与えられたパラメータに応じて、未知数を計算してキャッシュします - つまり、x1、y1 および ... w、h または x2、y2 でポリゴンを作成し、他のものを計算できます)
「n」を使用して、オーバーラップをチェックする「新しい」アイテムを指定します ($nItem はポリゴン オブジェクトのインスタンスです) - 再度テストするアイテム [これはビン/ソート ナップザック プログラム] で構成される配列です。 (同じ) ポリゴン オブジェクトの複数のインスタンス。
public function checkForOverlaps(BinPack_Polygon $nItem) {
// grab some local variables for the stuff re-used over and over in loop
$nX = $nItem->getLeft();
$nY = $nItem->getTop();
$nW = $nItem->getWidth();
$nH = $nItem->getHeight();
// loop through the stored polygons checking for overlaps
foreach($this->packed as $_i => $pI) {
if(((($pI->getLeft() - $nW) < $nX) && ($nX < $pI->getRight())) &&
((($pI->getTop() - $nH) < $nY) && ($nY < $pI->getBottom()))) {
return false;
}
}
return true;
}
于 2012-07-26T19:12:33.790 に答える
0
私のソリューションのサンプルコード（php）：
// returns 'true' on overlap checking against an array of similar objects in $this->packed
public function checkForOverlaps(BinPack_Polygon $nItem) {
$nX = $nItem->getLeft();
$nY = $nItem->getTop();
$nW = $nItem->getWidth();
$nH = $nItem->getHeight();
// loop through the stored polygons checking for overlaps
foreach($this->packed as $_i => $pI) {
if(((($pI->getLeft() - $nW) < $nX) && ($nX < $pI->getRight())) && ((($pI->getTop() - $nH) < $nY) && ($nY < $pI->getBottom()))) {
return true;
}
}
return false;
}
于 2012-07-27T15:49:59.190 に答える