如何分辨圆和矩形在二维欧几里得空间中是否相交?(即经典二维几何)
当前回答
对于那些需要用SQL在地理坐标中计算圆/矩形碰撞的人， 这是我在oracle 11中实现的e.James建议算法。
在输入中，它需要圆坐标，圆半径km和矩形的两个顶点坐标:
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;
其他回答
下面是修改后的代码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
对于那些需要用SQL在地理坐标中计算圆/矩形碰撞的人， 这是我在oracle 11中实现的e.James建议算法。
在输入中，它需要圆坐标，圆半径km和矩形的两个顶点坐标:
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;
首先检查矩形和与圆相切的正方形是否重叠(简单)。如果它们不重叠，就不会碰撞。 检查圆的中心是否在矩形内(简单)。如果它在里面，它们就会碰撞。 计算矩形边到圆中心的最小平方距离(略硬)。如果小于半径的平方，它们就会碰撞，否则不会。
它是有效的，因为:
首先，它用一个便宜的算法检查最常见的场景，当它确定它们没有碰撞时，它就结束了。 然后它用一个廉价的算法检查下一个最常见的场景(不要计算平方根，使用平方值)，当它确定它们碰撞时，它就结束了。 然后它执行更昂贵的算法来检查与矩形边框的碰撞。
有效，一周前才发现，现在才开始测试。
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)));
我有一个方法可以避免昂贵的毕达哥拉斯，如果没有必要的话。当矩形和圆的包围框不相交时。
对非欧几里得也适用
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方法比全距离计算快一点。例如，在欧几里得空间中没有平方根(或者没有很多其他的haversine): dat =(lat-circleY);dLon = (lon-circleX);赋范= dLat * dLat + dLon * dLon。当然，如果你使用normDist方法你需要创建一个normedDist = dist*dist;对于圆来说
查看我的GraphHopper项目的完整的BBox和Circle代码。
