원-직사각형 충돌 감지(교차점)
https://stackoverflow.com/questions/401847
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
2D 유클리드 공간에서 원과 직사각형이 교차하는지 어떻게 알 수 있나요?(즉.클래식 2D 기하학)
해결책
원이 사각형과 교차하는 경우는 두 가지뿐입니다.
- 원의 중심이 직사각형 안에 있거나
- 사각형의 가장자리 중 하나는 원 안에 점이 있습니다.
이것은 사각형이 축-팔찌가 필요하지 않습니다.
(이것을 볼 수있는 한 가지 방법 : 가장자리가 원 안에 포인트가 없다면 (모든 가장자리가 완전히 "외부"원형 인 경우) 원이 여전히 다각형을 교차 할 수있는 유일한 방법은 완전히 내부에 완전히 놓여있는 것입니다. 다각형.)
그 통찰력으로 다음과 같은 것이 작동합니다. 서클에 중심이 있습니다. P 그리고 반경 R, 및 사각형에는 정점이 있습니다 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() 구현하기 쉽습니다. 한 가지 방법은 수직의 발이 P 선으로는 충분히 가깝고 엔드 포인트 사이에 있고 엔드 포인트를 확인하십시오.
멋진 것은 그게 같은 아이디어는 직사각형뿐만 아니라 원과의 교차로를 위해 작동합니다. 간단한 다각형 - 볼록 할 필요조차 없습니다!
다른 팁
다음은 다음과 같습니다.
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 개의 사분면이 하나로 붕괴되어 계산을 4 번 수행 할 필요가 없습니다. 이미지는 원의 중심이 거짓말을 해야하는 영역을 보여줍니다. 단일 사분면 만 표시됩니다. 직사각형은 회색 영역이며, 빨간색 경계는 사각형의 가장자리에서 정확히 1 개의 반경 인 임계 영역을 간략하게 설명합니다. 원의 중심은 교차로가 발생하기 위해이 붉은 테두리 안에 있어야합니다.
두 번째 라인 쌍은 원이 직사각형 (어느 방향 으로든)에서 멀리 떨어져있는 쉬운 케이스를 제거합니다. 이것은 이미지의 녹색 영역에 해당합니다.
세 번째 라인 쌍은 원이 교차로가 보장되는 직사각형 (어느 방향 으로든)에 충분히 가까운 쉬운 케이스를 처리합니다. 이것은 이미지의 주황색 및 회색 섹션에 해당합니다. 이 단계는 논리가 이해 되려면 2 단계 후에 수행해야합니다.
나머지 선은 원이 사각형의 모서리를 교차시킬 수있는 어려운 경우를 계산합니다. 해결하려면 원과 모서리의 중심에서 거리를 계산 한 다음 거리가 원의 반지름이 아닌지 확인하십시오. 이 계산은 중심이 빨간색 음영 영역 내에있는 모든 서클에 대해 False를 반환하고 중앙이 흰색 음영 영역 내에있는 모든 서클에 대해 true를 반환합니다.
구현이 매우 간단하고 매우 빠른 또 다른 솔루션이 있습니다.구가 직사각형에 완전히 들어간 경우를 포함하여 모든 교차점을 포착합니다.
// 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줄로 단축할 수 있습니다.
당신의 구와 직장은 IIF를 교차시킵니다
원 중심과 직장의 1 정점 사이의 거리는 구의 반경보다 작습니다.
또는
원 중심과 직장의 한쪽 가장자리 사이의 거리는 구의 반경보다 작습니다 ([포인트 라인 거리 ])
또는
원 센터는 직장 안에 있습니다
점수 거리 :
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)
rect 내부의 원 센터 :
분리 된 축 aproach : 지점에서 사각형을 분리하는 선에 투영이 있으면 교차하지 않습니다.
당신은 직장의 측면과 평행 한 줄에 포인트를 투사하고 교차하는지 쉽게 결정할 수 있습니다. 그들이 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
이것은 축-정렬 된 사각형을 가정하지 않으며 볼록 세트 간의 교차점을 테스트하기에 쉽게 확장 할 수 있습니다.
이것은 가장 빠른 해결책입니다.
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;
}
실행 순서와 너비/높이의 절반이 사전 계산됩니다. 또한 시계 사이클을 절약하기 위해 제곱이 "수동으로"수행됩니다.
다음은 구와 비가축 정렬 상자 간의 충돌을 해결하기위한 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;
}
실제로 이것은 훨씬 더 간단합니다. 두 가지만 필요합니다.
먼저 4 개를 찾아야합니다 직교 원 중심에서 사각형의 각 선까지의 거리. 그러면 원이 원 반경보다 큰 경우 원이 사각형을 교차하지 않습니다.
둘째, 원 중심과 사각형 센터 사이의 거리를 찾아야한다면 거리가 사각형 대각선 길이의 절반보다 큰 경우 원이 사각형 안에 있지 않습니다.
행운을 빕니다!
내가 생각해 낸 가장 간단한 솔루션은 매우 간단합니다.
원과 가장 가까운 사각형의 지점을 찾은 다음 거리를 비교하여 작동합니다.
몇 가지 작업 으로이 모든 작업을 수행하고 SQRT 기능을 피할 수도 있습니다.
public boolean intersects(float cx, float cy, float radius, float left, float top, float right, float bottom)
{
float closestX = (cx < left ? left : (cx > right ? right : cx));
float closestY = (cy < top ? top : (cy > bottom ? bottom : cy));
float dx = closestX - cx;
float dy = closestY - cy;
return ( dx * dx + dy * dy ) <= radius * radius;
}
그리고 그게 다야! 위의 솔루션은 X 축이 아래로 향한 세계 왼쪽 상단의 기원을 가정합니다.
움직이는 원과 사각형 사이의 충돌을 처리 할 수있는 솔루션을 원한다면 훨씬 더 복잡하고 덮여 있습니다. 내 다른 대답에서.
시각화하려면 키보드의 Numpad를 가져 가십시오. 키 '5'가 사각형을 나타내는 경우, 모든 키 1-9는 9 개의 사분면을 사각형을 구성하는 선으로 나눈 (5는 내부입니다.)
1) 원의 중심이 사분면 5 (즉, 사각형 내부)에 있다면 두 모양이 교차합니다.
그와 함께, 두 가지 가능한 경우가 있습니다. a) 원은 사각형의 둘 이상의 가장자리와 교차합니다. b) 원은 사각형의 한쪽 가장자리와 교차합니다.
첫 번째 사례는 간단합니다. 원이 직사각형의 두 개의 가장자리와 교차하는 경우, 두 개의 가장자리를 연결하는 코너가 포함되어야합니다. (또는 그 중심은 우리가 이미 덮은 사분면 5에 있습니다. 또한 원이 2 개만 교차하는 경우에 주목하십시오. 반대 사각형의 가장자리도 덮여 있습니다.)
2) 사각형의 모서리 A, B, C, D가 원 안에 놓인 경우 두 모양이 교차합니다.
두 번째 사례는 까다 롭습니다. 원의 중심이 사분면 2, 4, 6 또는 8 중 하나에있을 때만 발생할 수 있음을 기록해야합니다. (실제로 중심이 사분면 1, 3, 7, 8, 해당 코너가 가장 가까운 지점이 될 것입니다.)
이제 우리는 원의 중심이 '가장자리'사분면 중 하나에 있고 해당 가장자리와 교차하는 경우가 있습니다. 그런 다음 원의 중심에 가장 가까운 가장자리의 지점은 원 안에 누워야합니다.
3) 각 라인 AB, BC, CD, DA, 생성 수직선 P (AB, P), P (BC, P), P (CD, P), P (DA, P)는 원의 중심 P에 대한 P. 각각의 수직선, 원래 가장자리와의 교차점이 원 안에 있으면 두 모양이 교차합니다.
이 마지막 단계를위한 바로 가기가 있습니다. 원의 중심이 사분면 8에 있고 모서리 AB가 상단 가장자리 인 경우 교차점의 지점은 y 좌표 A와 B의 X- 코어디 네이트가 중심 P의 X- 좌표를 갖습니다.
네 개의 라인 교차로를 구성하고 해당 가장자리에 놓여 있는지 확인하거나 어떤 사분면 P가 있는지 확인하고 해당 교차로를 확인할 수 있습니다. 둘 다 동일한 부울 방정식으로 단순화해야합니다. 위의 2 단계는 P를 '코너'사분면 중 하나에 배제하지 않았다. 그것은 단지 교차로를 찾았습니다.
편집 : 결과적으로, 나는 #2가 위의 #3의 서브 케이스라는 간단한 사실을 간과했습니다. 결국, 모서리도 가장자리의 점입니다. 훌륭한 설명은 아래 @shreevatsar의 답변을 참조하십시오. 그 동안 빠르고 중복 점검을 원하지 않는 한 위의 #2를 잊어 버리십시오.
이 기능은 원과 사각형 사이의 충돌 (교차)을 감지합니다. 그는 대답에서 E.James 방법처럼 일하지만 이것은 사각형의 모든 각도에 대한 충돌을 감지합니다 (오른쪽 구석뿐만 아니라).
노트:
arect.origin.x 그리고 arect.origin.y 사각형의 왼쪽 각도의 좌표입니다!
acircle.x 그리고 acircle.y Circle Center의 좌표입니다!
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;
}
나는 당신이 즐기기를 바랍니다.
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;
}
}
Here is the modfied code 100% working:
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
Here's a fast one-line test for this:
if (length(max(abs(center - rect_mid) - rect_halves, 0)) <= radius ) {
// They intersect.
}
This is the axis-aligned case where rect_halves is a positive vector pointing from the rectangle middle to a corner. The expression inside length() is a delta vector from center to a closest point in the rectangle. This works in any dimension.
- First check if the rectangle and the square tangent to the circle overlaps (easy). If they do not overlaps, they do not collide.
- Check if the circle's center is inside the rectangle (easy). If it's inside, they collide.
- Calculate the minimum squared distance from the rectangle sides to the circle's center (little hard). If it's lower that the squared radius, then they collide, else they don't.
It's efficient, because:
- First it checks the most common scenario with a cheap algorithm and when it's sure they do not collide, it ends.
- Then it checks the next most common scenario with a cheap algorithm (do not calculate square root, use the squared values) and when it's sure they collide it ends.
- Then it executes the more expensive algorithm to check collision with the rectangle borders.
I've a method which avoids the expensive pythagoras if not necessary - ie. when bounding boxes of the rectangle and the circle do not intersect.
And it'll work for non-euclidean too:
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 can be replaced with minY,maxY and the same for minLon, maxLon: replace it with minX, maxX
- normDist ist just a bit faster method then the full distance calculation. E.g. without the square-root in euclidean space (or without a lot of other stuff for haversine):
dLat=(lat-circleY); dLon=(lon-circleX); normed=dLat*dLat+dLon*dLon. Of course if you use that normDist method you'll need to do create anormedDist = dist*dist;for the circle
See the full BBox and Circle code of my GraphHopper project.
For those have to calculate Circle/Rectangle collision in Geographic Coordinates with SQL,
this is my implementation in oracle 11 of e.James suggested algorithm.
In input it requires circle coordinates, circle radius in km and two vertices coordinates of the rectangle:
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;
Works, just figured this out a week ago, and just now got to testing it.
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)));
def colision(rect, circle):
dx = rect.x - circle.x
dy = rect.y - circle.y
distance = (dy**2 + dx**2)**0.5
angle_to = (rect.angle + math.atan2(dx, dy)/3.1415*180.0) % 360
if((angle_to>135 and angle_to<225) or (angle_to>0 and angle_to<45) or (angle_to>315 and angle_to<360)):
if distance <= circle.rad/2.+((rect.height/2.0)*(1.+0.5*abs(math.sin(angle_to*math.pi/180.)))):
return True
else:
if distance <= circle.rad/2.+((rect.width/2.0)*(1.+0.5*abs(math.cos(angle_to*math.pi/180.)))):
return True
return False
Assuming you have the four edges of the rectangle check the distance from the edges to the center of the circle, if its less then the radius, then the shapes are intersecting.
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
If the rectangle intersects to the circle, one or more corner points of the rectangle should be inside in the circle. Suppose a rectangle's four points are A,B,C,D. at least one of them should intersect the circle. so if the distance from one point to the center of the circle is less than the radius of the circle it should intersect the circle. To get the distance you can use the Pythagorean theorem,
H^2 = A^2 + B^2
This technique has some limits. But it will work better for the game developers. especially collision detection
It is a good update to Arvo's Algorithm
