如何分辨圆和矩形在二维欧几里得空间中是否相交?(即经典二维几何)
当前回答
我为处理形状创建了类 希望你喜欢
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;
}
}
其他回答
假设你有矩形的四条边，检查从这些边到圆心的距离，如果小于半径，那么这些形状是相交的。
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
首先检查矩形和与圆相切的正方形是否重叠(简单)。如果它们不重叠，就不会碰撞。 检查圆的中心是否在矩形内(简单)。如果它在里面，它们就会碰撞。 计算矩形边到圆中心的最小平方距离(略硬)。如果小于半径的平方，它们就会碰撞，否则不会。
它是有效的，因为:
首先，它用一个便宜的算法检查最常见的场景，当它确定它们没有碰撞时，它就结束了。 然后它用一个廉价的算法检查下一个最常见的场景(不要计算平方根，使用平方值)，当它确定它们碰撞时，它就结束了。 然后它执行更昂贵的算法来检查与矩形边框的碰撞。
如果你对一个更图形化的解决方案感兴趣，甚至在(平面上)旋转的矩形..
演示: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点)。
我为处理形状创建了类 希望你喜欢
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;
}
}
我在制作这款游戏时开发了这个算法:https://mshwf.github.io/mates/
如果圆与正方形接触，那么圆的中心线与正方形中心线之间的距离应该等于(直径+边)/2。 让我们有一个名为touching的变量来保存这个距离。问题是:我应该考虑哪条中心线:水平的还是垂直的? 考虑这个框架:
每条中心线给出了不同的距离，只有一条是没有碰撞的正确指示，但利用人类的直觉是理解自然算法如何工作的开始。
They are not touching, which means that the distance between the two centerlines should be greater than touching, which means that the natural algorithm picks the horizontal centerlines (the vertical centerlines says there's a collision!). By noticing multiple circles, you can tell: if the circle intersects with the vertical extension of the square, then we pick the vertical distance (between the horizontal centerlines), and if the circle intersects with the horizontal extension, we pick the horizontal distance:
另一个例子，圆4:它与正方形的水平延伸相交，那么我们考虑水平距离等于接触。
Ok, the tough part is demystified, now we know how the algorithm will work, but how we know with which extension the circle intersects? It's easy actually: we calculate the distance between the most right x and the most left x (of both the circle and the square), and the same for the y-axis, the one with greater value is the axis with the extension that intersects with the circle (if it's greater than diameter+side then the circle is outside the two square extensions, like circle #7). The code looks like:
right = Math.max(square.x+square.side, circle.x+circle.rad);
left = Math.min(square.x, circle.x-circle.rad);
bottom = Math.max(square.y+square.side, circle.y+circle.rad);
top = Math.min(square.y, circle.y-circle.rad);
if (right - left > down - top) {
//compare with horizontal distance
}
else {
//compare with vertical distance
}
/*These equations assume that the reference point of the square is at its top left corner, and the reference point of the circle is at its center*/
