円と長方形が 2D ユークリッド空間で交差しているかどうかを確認するにはどうすればよいですか? (つまり、従来の 2D ジオメトリ)
235583 次
26 に答える
310
これが私がそれを行う方法です：
bool intersects(CircleType circle, RectType rect)
{
circleDistance.x = abs(circle.x - rect.x);
circleDistance.y = abs(circle.y - rect.y);
if (circleDistance.x > (rect.width/2 + circle.r)) { return false; }
if (circleDistance.y > (rect.height/2 + circle.r)) { return false; }
if (circleDistance.x <= (rect.width/2)) { return true; }
if (circleDistance.y <= (rect.height/2)) { return true; }
cornerDistance_sq = (circleDistance.x - rect.width/2)^2 +
(circleDistance.y - rect.height/2)^2;
return (cornerDistance_sq <= (circle.r^2));
}
仕組みは次のとおりです。
最初の行のペアは、円の中心と長方形の中心の間の x と y の差の絶対値を計算します。これにより、4 つの象限が 1 つに折りたたまれ、計算を 4 回行う必要がなくなります。画像は、円の中心が位置しなければならない領域を示しています。1 つの象限のみが表示されていることに注意してください。四角形は灰色の領域で、赤い境界線は、四角形の端から半径 1 つだけ離れた重要な領域の輪郭を示しています。交点が発生するには、円の中心がこの赤い枠内にある必要があります。
2 番目の線のペアは、円が四角形から (どちらの方向にも) 十分に離れていて交差できないという簡単なケースを排除します。これは、画像の緑色の領域に対応します。
3 番目の線のペアは、交点が保証されるほど円が四角形に (いずれかの方向で) 十分に近い場合の簡単なケースを処理します。これは、画像のオレンジ色と灰色の部分に対応しています。ロジックを理解するには、この手順を手順 2 の後に実行する必要があることに注意してください。
残りの行は、円が長方形の角と交差する可能性があるという難しいケースを計算します。解決するには、円の中心と角からの距離を計算し、その距離が円の半径以下であることを確認します。この計算は、中心が赤い影付きの領域内にあるすべての円に対して false を返し、中心が白い影付きの領域内にあるすべての円に対して true を返します。
于 2008-12-31T01:14:50.663 に答える
218
円が長方形と交差するケースは 2 つだけです。
- 円の中心が長方形の内側にあるか、または
- 四角形の辺の 1 つは、円の中に点があります。
これは、長方形が軸平行である必要はないことに注意してください。
(これを確認する 1 つの方法: エッジのいずれも円内に点を持たない場合 (すべてのエッジが完全に円の「外側」にある場合)、円がポリゴンと交差できる唯一の方法は、ポリゴンが完全に内側にある場合です。ポリゴン。）
その洞察により、円には centerPと radiusRがあり、長方形には頂点A、B、CがDその順序である次のようなものが機能します (完全なコードではありません)。
def intersect(Circle(P, R), Rectangle(A, B, C, D)):
S = Circle(P, R)
return (pointInRectangle(P, Rectangle(A, B, C, D)) or
intersectCircle(S, (A, B)) or
intersectCircle(S, (B, C)) or
intersectCircle(S, (C, D)) or
intersectCircle(S, (D, A)))
ジオメトリを作成している場合は、ライブラリに上記の関数が既にある可能性があります。それ以外の場合はpointInRectangle()、いくつかの方法で実装できます。多角形メソッドの一般的なポイントのいずれかが機能しますが、長方形の場合、これが機能するかどうかを確認できます。
0 ≤ AP·AB ≤ AB·AB and 0 ≤ AP·AD ≤ AD·AD
またintersectCircle()、実装も簡単です。1 つの方法はP、線への垂線の足が端点の間に十分に近いかどうかを確認し、そうでない場合は端点を確認することです。
すばらしいことに、同じ考え方が長方形だけでなく、円と単純な多角形の交点にも機能します。凸面である必要さえありません!
于 2008-12-31T01:17:13.433 に答える
135
これは、実装が非常に簡単な（そして非常に高速な）別のソリューションです。球が四角形に完全に入っている場合を含め、すべての交点をキャッチします。
// clamp(value, min, max) - limits value to the range min..max
// Find the closest point to the circle within the rectangle
float closestX = clamp(circle.X, rectangle.Left, rectangle.Right);
float closestY = clamp(circle.Y, rectangle.Top, rectangle.Bottom);
// Calculate the distance between the circle's center and this closest point
float distanceX = circle.X - closestX;
float distanceY = circle.Y - closestY;
// If the distance is less than the circle's radius, an intersection occurs
float distanceSquared = (distanceX * distanceX) + (distanceY * distanceY);
return distanceSquared < (circle.Radius * circle.Radius);
適切な数学ライブラリを使用すると、3 行または 4 行に短縮できます。
于 2009-12-10T07:30:04.003 に答える
10
球と四角形が交差する IIF
円の中心と四角形の 1 つの頂点との間の距離が球の半径よりも小さい、
または
円の中心と四角形の 1 つの端との間の距離が球の半径よりも小さい ( [点-線距離])
または、円の中心が四角形の
点-点距離
の内側にある
:
P1 = [x1,y1] P2 = [x2,y2] 距離 = sqrt(abs(x1 - x2)+abs(y1-y2))
点線距離:
L1 = [x1,y1],L2 = [x2,y2] (線の 2 点、つまり頂点) P1 = [px,py] あるポイント 距離 d = abs( (x2-x1)(y1-py)-(x1-px)(y2-y1) ) / 距離(L1,L2)
四角形の内側の円の中心:
分離軸アプローチを取ります: 点から四角形を分離する線への射影が存在する場合、それらは交差しません
四角形の辺に平行な線に点を投影すると、それらが交差するかどうかを簡単に判断できます。それらが 4 つの投影すべてで交差しない場合、それら (点と長方形) は交差できません。
内積（ x= [x1,x2] 、 y = [y1,y2] 、 x*y = x1*y1 + x2*y2 ）だけが必要です
テストは次のようになります。
//長方形のエッジ: TL (左上)、TR (右上)、BL (左下)、BR (右下)
// テストするポイント: POI
区切られた = false
for egde in { {TL,TR}, {BL,BR}, {TL,BL},{TR-BR} }: // エッジ
D = エッジ[0] - エッジ[1]
innerProd = D * POI
Interval_min = min(D*エッジ[0],D*エッジ[1])
Interval_max = max(D*エッジ[0],D*エッジ[1])
そうでない場合 ( Interval_min ≤ innerProd ≤ Interval_max )
区切られた = true
break // ループの終了
終了する場合
終了
if (区切りが真)
「交差点なし」を返す
そうしないと
「交差点」を返す
終了する場合
これは、軸に沿った長方形を想定しておらず、凸集合間の交差をテストするために簡単に拡張できます。
于 2009-05-11T09:09:51.957 に答える
6
これが最速のソリューションです。
public static boolean intersect(Rectangle r, Circle c)
{
float cx = Math.abs(c.x - r.x - r.halfWidth);
float xDist = r.halfWidth + c.radius;
if (cx > xDist)
return false;
float cy = Math.abs(c.y - r.y - r.halfHeight);
float yDist = r.halfHeight + c.radius;
if (cy > yDist)
return false;
if (cx <= r.halfWidth || cy <= r.halfHeight)
return true;
float xCornerDist = cx - r.halfWidth;
float yCornerDist = cy - r.halfHeight;
float xCornerDistSq = xCornerDist * xCornerDist;
float yCornerDistSq = yCornerDist * yCornerDist;
float maxCornerDistSq = c.radius * c.radius;
return xCornerDistSq + yCornerDistSq <= maxCornerDistSq;
}
実行の順序に注意してください。幅/高さの半分が事前に計算されます。また、2乗は「手動」で行われ、クロックサイクルを節約します。
于 2012-09-11T23:36:00.350 に答える
4
実際には、これははるかに簡単です。必要なものは 2 つだけです。
まず、円の中心から長方形の各線までの4 つの直交距離を見つける必要があります。次に、そのうちの3つが円の半径よりも大きい場合、円は長方形と交差しません。
次に、円の中心と長方形の中心の間の距離を見つける必要があります。距離が長方形の対角線の長さの半分より大きい場合、円は長方形の内側にはなりません。
幸運を！
于 2013-04-09T15:33:07.733 に答える
3
これは、球と軸に沿っていないボックスとの間の衝突を解決するための私の C コードです。これは私自身のライブラリ ルーチンのいくつかに依存していますが、一部の人にとっては役立つかもしれません。ゲームで使用していますが、問題なく動作します。
float physicsProcessCollisionBetweenSelfAndActorRect(SPhysics *self, SPhysics *actor)
{
float diff = 99999;
SVector relative_position_of_circle = getDifference2DBetweenVectors(&self->worldPosition, &actor->worldPosition);
rotateVector2DBy(&relative_position_of_circle, -actor->axis.angleZ); // This aligns the coord system so the rect becomes an AABB
float x_clamped_within_rectangle = relative_position_of_circle.x;
float y_clamped_within_rectangle = relative_position_of_circle.y;
LIMIT(x_clamped_within_rectangle, actor->physicsRect.l, actor->physicsRect.r);
LIMIT(y_clamped_within_rectangle, actor->physicsRect.b, actor->physicsRect.t);
// Calculate the distance between the circle's center and this closest point
float distance_to_nearest_edge_x = relative_position_of_circle.x - x_clamped_within_rectangle;
float distance_to_nearest_edge_y = relative_position_of_circle.y - y_clamped_within_rectangle;
// If the distance is less than the circle's radius, an intersection occurs
float distance_sq_x = SQUARE(distance_to_nearest_edge_x);
float distance_sq_y = SQUARE(distance_to_nearest_edge_y);
float radius_sq = SQUARE(self->physicsRadius);
if(distance_sq_x + distance_sq_y < radius_sq)
{
float half_rect_w = (actor->physicsRect.r - actor->physicsRect.l) * 0.5f;
float half_rect_h = (actor->physicsRect.t - actor->physicsRect.b) * 0.5f;
CREATE_VECTOR(push_vector);
// If we're at one of the corners of this object, treat this as a circular/circular collision
if(fabs(relative_position_of_circle.x) > half_rect_w && fabs(relative_position_of_circle.y) > half_rect_h)
{
SVector edges;
if(relative_position_of_circle.x > 0) edges.x = half_rect_w; else edges.x = -half_rect_w;
if(relative_position_of_circle.y > 0) edges.y = half_rect_h; else edges.y = -half_rect_h;
push_vector = relative_position_of_circle;
moveVectorByInverseVector2D(&push_vector, &edges);
// We now have the vector from the corner of the rect to the point.
float delta_length = getVector2DMagnitude(&push_vector);
float diff = self->physicsRadius - delta_length; // Find out how far away we are from our ideal distance
// Normalise the vector
push_vector.x /= delta_length;
push_vector.y /= delta_length;
scaleVector2DBy(&push_vector, diff); // Now multiply it by the difference
push_vector.z = 0;
}
else // Nope - just bouncing against one of the edges
{
if(relative_position_of_circle.x > 0) // Ball is to the right
push_vector.x = (half_rect_w + self->physicsRadius) - relative_position_of_circle.x;
else
push_vector.x = -((half_rect_w + self->physicsRadius) + relative_position_of_circle.x);
if(relative_position_of_circle.y > 0) // Ball is above
push_vector.y = (half_rect_h + self->physicsRadius) - relative_position_of_circle.y;
else
push_vector.y = -((half_rect_h + self->physicsRadius) + relative_position_of_circle.y);
if(fabs(push_vector.x) < fabs(push_vector.y))
push_vector.y = 0;
else
push_vector.x = 0;
}
diff = 0; // Cheat, since we don't do anything with the value anyway
rotateVector2DBy(&push_vector, actor->axis.angleZ);
SVector *from = &self->worldPosition;
moveVectorBy2D(from, push_vector.x, push_vector.y);
}
return diff;
}
于 2010-06-18T14:43:06.710 に答える
2
この関数は、CircleとRectangleの間の衝突（交差）を検出します。彼は答えのe.Jamesメソッドのように機能しますが、これは長方形のすべての角度（右上隅だけでなく）の衝突を検出します。
ノート：
aRect.origin.xとaRect.origin.yは、長方形の左下の角度の座標です。
aCircle.xとaCircle.yはサークルセンターの座標です！
static inline BOOL RectIntersectsCircle(CGRect aRect, Circle aCircle) {
float testX = aCircle.x;
float testY = aCircle.y;
if (testX < aRect.origin.x)
testX = aRect.origin.x;
if (testX > (aRect.origin.x + aRect.size.width))
testX = (aRect.origin.x + aRect.size.width);
if (testY < aRect.origin.y)
testY = aRect.origin.y;
if (testY > (aRect.origin.y + aRect.size.height))
testY = (aRect.origin.y + aRect.size.height);
return ((aCircle.x - testX) * (aCircle.x - testX) + (aCircle.y - testY) * (aCircle.y - testY)) < aCircle.radius * aCircle.radius;
}
于 2012-04-23T23:33:18.043 に答える
2
視覚化するには、キーボードのテンキーを取ります。キー「5」が長方形を表す場合、1 ～ 9 のすべてのキーは、長方形を構成する線で分割された 9 つの空間の象限を表します (5 は内側です)。
1) 円の中心が第 5 象限 (つまり、長方形の内側) にある場合、2 つの形状は交差します。
これで、次の 2 つのケースが考えられます。 a) 円が、長方形の隣接する 2 つ以上のエッジと交差している。b) 円は長方形の 1 つのエッジと交差します。
最初のケースは単純です。円が四角形の隣接する 2 つのエッジと交差する場合、それらの 2 つのエッジを接続するコーナーが円に含まれている必要があります。(それ、またはその中心は、すでに説明した第 5 象限にあります。また、円が長方形の 2 つの対向するエッジのみと交差する場合も同様にカバーされることに注意してください。)
2) 長方形の角 A、B、C、D のいずれかが円の内側にある場合、2 つの図形は交差します。
2 番目のケースはよりトリッキーです。円の中心が象限 2、4、6、または 8 のいずれかにある場合にのみ発生する可能性があることに注意してください (実際、中心が象限 1、3、7、8 のいずれかにある場合、対応するコーナーがそれに最も近いポイントになります。)
ここで、円の中心が「エッジ」象限の 1 つにあり、対応するエッジとのみ交差する場合があります。次に、円の中心に最も近いエッジ上のポイントは、円の内側にある必要があります。
3) 各直線 AB、BC、CD、DA について、円の中心 P を通る垂線 p(AB,P)、p(BC,P)、p(CD,P)、p(DA,P) を作成します。元のエッジとの交点が円の内側にある場合、2 つの形状は交差します。
この最後のステップにはショートカットがあります。円の中心が象限 8 にあり、エッジ AB が上端である場合、交点は A と B の y 座標と、中心 P の x 座標になります。
4 つの線の交点を作成して、それらが対応するエッジ上にあるかどうかを確認したり、P がどの象限にあるかを調べて、対応する交点を確認したりできます。どちらも同じブール式に単純化する必要があります。上記のステップ 2 では、P が「コーナー」象限の 1 つにあることを除外していないことに注意してください。交差点を探しただけです。
編集: 結局のところ、#2 は上記の #3 のサブケースであるという単純な事実を見落としていました。結局のところ、コーナーもエッジ上のポイントです。優れた説明については、以下の @ShreevatsaR の回答を参照してください。それまでの間、迅速で冗長なチェックが必要でない限り、上記の #2 は忘れてください。
于 2008-12-31T00:20:58.040 に答える
1
これが100％機能する変更されたコードです：
public static bool IsIntersected(PointF circle, float radius, RectangleF rectangle)
{
var rectangleCenter = new PointF((rectangle.X + rectangle.Width / 2),
(rectangle.Y + rectangle.Height / 2));
var w = rectangle.Width / 2;
var h = rectangle.Height / 2;
var dx = Math.Abs(circle.X - rectangleCenter.X);
var dy = Math.Abs(circle.Y - rectangleCenter.Y);
if (dx > (radius + w) || dy > (radius + h)) return false;
var circleDistance = new PointF
{
X = Math.Abs(circle.X - rectangle.X - w),
Y = Math.Abs(circle.Y - rectangle.Y - h)
};
if (circleDistance.X <= (w))
{
return true;
}
if (circleDistance.Y <= (h))
{
return true;
}
var cornerDistanceSq = Math.Pow(circleDistance.X - w, 2) +
Math.Pow(circleDistance.Y - h, 2);
return (cornerDistanceSq <= (Math.Pow(radius, 2)));
}
バッサムアルギリ
于 2010-08-16T06:47:30.857 に答える
1
必要がなければ高価なピタゴラスを避ける方法があります。長方形と円の境界ボックスが交差しない場合。
そして、それは非ユークリッドでも機能します：
class Circle {
// create the bounding box of the circle only once
BBox bbox;
public boolean intersect(BBox b) {
// test top intersect
if (lat > b.maxLat) {
if (lon < b.minLon)
return normDist(b.maxLat, b.minLon) <= normedDist;
if (lon > b.maxLon)
return normDist(b.maxLat, b.maxLon) <= normedDist;
return b.maxLat - bbox.minLat > 0;
}
// test bottom intersect
if (lat < b.minLat) {
if (lon < b.minLon)
return normDist(b.minLat, b.minLon) <= normedDist;
if (lon > b.maxLon)
return normDist(b.minLat, b.maxLon) <= normedDist;
return bbox.maxLat - b.minLat > 0;
}
// test middle intersect
if (lon < b.minLon)
return bbox.maxLon - b.minLon > 0;
if (lon > b.maxLon)
return b.maxLon - bbox.minLon > 0;
return true;
}
}
- minLat、maxLatはminY、maxYに置き換えることができ、minLon、maxLonについても同じです。minX、maxXに置き換えます。
- normDistは、完全な距離の計算よりも少し速い方法です。たとえば、ユークリッド空間に平方根がない場合（または、ハバーシンの場合は他に多くのものがない場合）
dLat=(lat-circleY); dLon=(lon-circleX); normed=dLat*dLat+dLon*dLon：。もちろん、そのnormDistメソッドを使用する場合はnormedDist = dist*dist;、サークルのを作成する必要があります
GraphHopperプロジェクトの完全なBBoxおよびCircleコードを参照してください。
于 2012-05-26T09:53:53.497 に答える
1
- まず、四角形と円に接する四角形が重なっているかどうかを確認します (簡単)。重ならなければ衝突しません。
- 円の中心が長方形の内側にあるかどうかを確認します (簡単)。中にあればぶつかります。
- 四角形の辺から円の中心までの最小二乗距離を計算します (少し難しい)。半径の 2 乗より小さい場合は衝突し、そうでない場合は衝突しません。
次の理由により、効率的です。
- 最初に最も一般的なシナリオを安価なアルゴリズムでチェックし、衝突しないことが確認されたら終了します。
- 次に、安価なアルゴリズム (平方根を計算せず、平方値を使用) を使用して次に一般的なシナリオをチェックし、それらが衝突することが確実な場合に終了します。
- 次に、より高価なアルゴリズムを実行して、長方形の境界線との衝突をチェックします。
于 2015-08-21T21:16:55.803 に答える
1
これに対する高速な 1 行のテストを次に示します。
if (length(max(abs(center - rect_mid) - rect_halves, 0)) <= radius ) {
// They intersect.
}
rect_halvesこれは、が長方形の中央から角を指す正のベクトルである、軸に沿ったケースです。内部の式は、長方形内の最も近い点length()からのデルタ ベクトルです。centerこれはどの次元でも機能します。
于 2015-07-22T06:12:50.187 に答える
0
SQL を使用して地理座標で円/長方形の衝突を計算する必要がある場合、これはe.James が提案したアルゴリズム
の oracle 11 での私の実装です。
入力では、円の座標、km 単位の円の半径、および四角形の 2 つの頂点の座標が必要です。
CREATE OR REPLACE FUNCTION "DETECT_CIRC_RECT_COLLISION"
(
circleCenterLat IN NUMBER, -- circle Center Latitude
circleCenterLon IN NUMBER, -- circle Center Longitude
circleRadius IN NUMBER, -- circle Radius in KM
rectSWLat IN NUMBER, -- rectangle South West Latitude
rectSWLon IN NUMBER, -- rectangle South West Longitude
rectNELat IN NUMBER, -- rectangle North Est Latitude
rectNELon IN NUMBER -- rectangle North Est Longitude
)
RETURN NUMBER
AS
-- converts km to degrees (use 69 if miles)
kmToDegreeConst NUMBER := 111.045;
-- Remaining rectangle vertices
rectNWLat NUMBER;
rectNWLon NUMBER;
rectSELat NUMBER;
rectSELon NUMBER;
rectHeight NUMBER;
rectWIdth NUMBER;
circleDistanceLat NUMBER;
circleDistanceLon NUMBER;
cornerDistanceSQ NUMBER;
BEGIN
-- Initialization of remaining rectangle vertices
rectNWLat := rectNELat;
rectNWLon := rectSWLon;
rectSELat := rectSWLat;
rectSELon := rectNELon;
-- Rectangle sides length calculation
rectHeight := calc_distance(rectSWLat, rectSWLon, rectNWLat, rectNWLon);
rectWidth := calc_distance(rectSWLat, rectSWLon, rectSELat, rectSELon);
circleDistanceLat := abs( (circleCenterLat * kmToDegreeConst) - ((rectSWLat * kmToDegreeConst) + (rectHeight/2)) );
circleDistanceLon := abs( (circleCenterLon * kmToDegreeConst) - ((rectSWLon * kmToDegreeConst) + (rectWidth/2)) );
IF circleDistanceLon > ((rectWidth/2) + circleRadius) THEN
RETURN -1; -- -1 => NO Collision ; 0 => Collision Detected
END IF;
IF circleDistanceLat > ((rectHeight/2) + circleRadius) THEN
RETURN -1; -- -1 => NO Collision ; 0 => Collision Detected
END IF;
IF circleDistanceLon <= (rectWidth/2) THEN
RETURN 0; -- -1 => NO Collision ; 0 => Collision Detected
END IF;
IF circleDistanceLat <= (rectHeight/2) THEN
RETURN 0; -- -1 => NO Collision ; 0 => Collision Detected
END IF;
cornerDistanceSQ := POWER(circleDistanceLon - (rectWidth/2), 2) + POWER(circleDistanceLat - (rectHeight/2), 2);
IF cornerDistanceSQ <= POWER(circleRadius, 2) THEN
RETURN 0; -- -1 => NO Collision ; 0 => Collision Detected
ELSE
RETURN -1; -- -1 => NO Collision ; 0 => Collision Detected
END IF;
RETURN -1; -- -1 => NO Collision ; 0 => Collision Detected
END;
于 2015-03-13T16:33:55.763 に答える
0
1週間前にこれを理解したばかりで、今それをテストするようになりました。
double theta = Math.atan2(cir.getX()-sqr.getX()*1.0,
cir.getY()-sqr.getY()*1.0); //radians of the angle
double dBox; //distance from box to edge of box in direction of the circle
if((theta > Math.PI/4 && theta < 3*Math.PI / 4) ||
(theta < -Math.PI/4 && theta > -3*Math.PI / 4)) {
dBox = sqr.getS() / (2*Math.sin(theta));
} else {
dBox = sqr.getS() / (2*Math.cos(theta));
}
boolean touching = (Math.abs(dBox) >=
Math.sqrt(Math.pow(sqr.getX()-cir.getX(), 2) +
Math.pow(sqr.getY()-cir.getY(), 2)));
于 2014-08-22T17:45:45.240 に答える
-2
長方形の 4 つのエッジがあると仮定すると、エッジから円の中心までの距離をチェックし、半径よりも小さい場合、形状は交差しています。
if sqrt((rectangleRight.x - circleCenter.x)^2 +
(rectangleBottom.y - circleCenter.y)^2) < radius
// then they intersect
if sqrt((rectangleRight.x - circleCenter.x)^2 +
(rectangleTop.y - circleCenter.y)^2) < radius
// then they intersect
if sqrt((rectangleLeft.x - circleCenter.x)^2 +
(rectangleTop.y - circleCenter.y)^2) < radius
// then they intersect
if sqrt((rectangleLeft.x - circleCenter.x)^2 +
(rectangleBottom.y - circleCenter.y)^2) < radius
// then they intersect
于 2008-12-30T23:42:11.067 に答える