如何分辨圆和矩形在二维欧几里得空间中是否相交?(即经典二维几何)
当前回答
下面是修改后的代码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)));
}
Bassam Alugili
其他回答
球面和矩形相交于IIF 圆心和矩形的一个顶点之间的距离小于球体的半径 或 圆心与矩形的一条边之间的距离小于球面的半径([点线距离]) 或 圆的中心在矩形的内部 一点上距离:
P1 = [x1,y1] P2 = [x2,y2] Distance = sqrt(abs(x1 - x2)+abs(y1-y2))
点线路距离:
L1 = [x1,y1],L2 = [x2,y2] (two points of your line, ie the vertex points) P1 = [px,py] some point Distance d = abs( (x2-x1)(y1-py)-(x1-px)(y2-y1) ) / Distance(L1,L2)
矩形内圆中心: 采用分离轴的方法:如果存在一个投影到一条直线上,将矩形与点分开,它们就不相交
您将点投影在平行于矩形边的直线上,然后可以很容易地确定它们是否相交。如果它们不在所有4个投影上相交,它们(点和矩形)就不能相交。
你只需要内积(x= [x1,x2],y = [y1,y2],x *y = x1*y1 + x2*y2)
你的测试应该是这样的:
//rectangle edges: TL (top left), TR (top right), BL (bottom left), BR (bottom right) //point to test: POI seperated = false for egde in { {TL,TR}, {BL,BR}, {TL,BL},{TR-BR} }: // the edges D = edge[0] - edge[1] innerProd = D * POI Interval_min = min(D*edge[0],D*edge[1]) Interval_max = max(D*edge[0],D*edge[1]) if not ( Interval_min ≤ innerProd ≤ Interval_max ) seperated = true break // end for loop end if end for if (seperated is true) return "no intersection" else return "intersection" end if
它没有假设一个轴对齐的矩形,并且很容易扩展用于测试凸集之间的交集。
这里有另一个解决方案,实现起来非常简单(也非常快)。它将捕获所有的交点,包括当球体完全进入矩形时。
// 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行。
我为处理形状创建了类 希望你喜欢
public class Geomethry {
public static boolean intersectionCircleAndRectangle(int circleX, int circleY, int circleR, int rectangleX, int rectangleY, int rectangleWidth, int rectangleHeight){
boolean result = false;
float rectHalfWidth = rectangleWidth/2.0f;
float rectHalfHeight = rectangleHeight/2.0f;
float rectCenterX = rectangleX + rectHalfWidth;
float rectCenterY = rectangleY + rectHalfHeight;
float deltax = Math.abs(rectCenterX - circleX);
float deltay = Math.abs(rectCenterY - circleY);
float lengthHypotenuseSqure = deltax*deltax + deltay*deltay;
do{
// check that distance between the centerse is more than the distance between the circumcircle of rectangle and circle
if(lengthHypotenuseSqure > ((rectHalfWidth+circleR)*(rectHalfWidth+circleR) + (rectHalfHeight+circleR)*(rectHalfHeight+circleR))){
//System.out.println("distance between the centerse is more than the distance between the circumcircle of rectangle and circle");
break;
}
// check that distance between the centerse is less than the distance between the inscribed circle
float rectMinHalfSide = Math.min(rectHalfWidth, rectHalfHeight);
if(lengthHypotenuseSqure < ((rectMinHalfSide+circleR)*(rectMinHalfSide+circleR))){
//System.out.println("distance between the centerse is less than the distance between the inscribed circle");
result=true;
break;
}
// check that the squares relate to angles
if((deltax > (rectHalfWidth+circleR)*0.9) && (deltay > (rectHalfHeight+circleR)*0.9)){
//System.out.println("squares relate to angles");
result=true;
}
}while(false);
return result;
}
public static boolean intersectionRectangleAndRectangle(int rectangleX, int rectangleY, int rectangleWidth, int rectangleHeight, int rectangleX2, int rectangleY2, int rectangleWidth2, int rectangleHeight2){
boolean result = false;
float rectHalfWidth = rectangleWidth/2.0f;
float rectHalfHeight = rectangleHeight/2.0f;
float rectHalfWidth2 = rectangleWidth2/2.0f;
float rectHalfHeight2 = rectangleHeight2/2.0f;
float deltax = Math.abs((rectangleX + rectHalfWidth) - (rectangleX2 + rectHalfWidth2));
float deltay = Math.abs((rectangleY + rectHalfHeight) - (rectangleY2 + rectHalfHeight2));
float lengthHypotenuseSqure = deltax*deltax + deltay*deltay;
do{
// check that distance between the centerse is more than the distance between the circumcircle
if(lengthHypotenuseSqure > ((rectHalfWidth+rectHalfWidth2)*(rectHalfWidth+rectHalfWidth2) + (rectHalfHeight+rectHalfHeight2)*(rectHalfHeight+rectHalfHeight2))){
//System.out.println("distance between the centerse is more than the distance between the circumcircle");
break;
}
// check that distance between the centerse is less than the distance between the inscribed circle
float rectMinHalfSide = Math.min(rectHalfWidth, rectHalfHeight);
float rectMinHalfSide2 = Math.min(rectHalfWidth2, rectHalfHeight2);
if(lengthHypotenuseSqure < ((rectMinHalfSide+rectMinHalfSide2)*(rectMinHalfSide+rectMinHalfSide2))){
//System.out.println("distance between the centerse is less than the distance between the inscribed circle");
result=true;
break;
}
// check that the squares relate to angles
if((deltax > (rectHalfWidth+rectHalfWidth2)*0.9) && (deltay > (rectHalfHeight+rectHalfHeight2)*0.9)){
//System.out.println("squares relate to angles");
result=true;
}
}while(false);
return result;
}
}
这个函数检测Circle和Rectangle之间的碰撞(交集)。他的回答类似于e.James的方法,但这个方法检测矩形的所有角(不仅仅是右角)的碰撞。
注意:
aRect.origin.x和aRect.origin.y是矩形左下角的坐标!
aCircle。x和圆。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;
}
如果你对一个更图形化的解决方案感兴趣,甚至在(平面上)旋转的矩形..
演示:https://jsfiddle.net/exodus4d/94mxLvqh/2691/
这个想法是:
将场景转换为原点[0,0] 如果矩形不在平面上,则旋转中心应在 (0,0) 将场景旋转回平面 计算交点
const hasIntersection = ({x: cx, y: cy, r: cr}, {x, y, width, height}) => { const distX = Math.abs(cx - x - width / 2); const distY = Math.abs(cy - y - height / 2); if (distX > (width / 2 + cr)) { return false; } if (distY > (height / 2 + cr)) { return false; } if (distX <= (width / 2)) { return true; } if (distY <= (height / 2)) { return true; } const Δx = distX - width / 2; const Δy = distY - height / 2; return Δx * Δx + Δy * Δy <= cr * cr; }; const rect = new DOMRect(50, 20, 100, 50); const circ1 = new DOMPoint(160, 80); circ1.r = 20; const circ2 = new DOMPoint(80, 95); circ2.r = 20; const canvas = document.getElementById('canvas'); const ctx = canvas.getContext('2d'); ctx.strokeRect(rect.x, rect.y, rect.width, rect.height); ctx.beginPath(); ctx.strokeStyle = hasIntersection(circ1, rect) ? 'red' : 'green'; ctx.arc(circ1.x, circ1.y, circ1.r, 0, 2 * Math.PI); ctx.stroke(); ctx.beginPath(); ctx.strokeStyle = hasIntersection(circ2, rect) ? 'red' : 'green'; ctx.arc(circ2.x, circ2.y, circ2.r, 0, 2 * Math.PI); ctx.stroke(); <canvas id="canvas"></canvas>
提示:而不是旋转矩形(4点)。你可以向相反的方向旋转圆(1点)。