Обнаружение столкновения круга и Прямоугольника (пересечение)
https://stackoverflow.com/questions/401847
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Как я могу определить, пересекаются ли круг и прямоугольник в двумерном евклидовом пространстве?(т.е.классическая 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 чтобы линия находилась достаточно близко и между конечными точками, и проверьте конечные точки в противном случае.
Самое классное, что то же самое idea работает не только для прямоугольников, но и для пересечения круга с любым простой многоугольник — даже не обязательно должно быть выпуклым!
Другие советы
Вот как бы я это сделал:
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 между центром окружности и центром прямоугольника.Это сводит четыре квадранта в один, так что вычисления не нужно выполнять четыре раза.На рисунке показана область, в которой теперь должен находиться центр круга.Обратите внимание, что показан только один квадрант.Прямоугольник - это серая область, а красная граница очерчивает критическую область, которая находится ровно в одном радиусе от краев прямоугольника.Чтобы произошло пересечение, центр круга должен находиться в пределах этой красной границы.
Вторая пара линий исключает простые случаи, когда окружность находится достаточно далеко от прямоугольника (в любом направлении), так что пересечение невозможно.Это соответствует зеленой области на изображении.
Третья пара линий обрабатывает простые случаи, когда окружность находится достаточно близко к прямоугольнику (в любом направлении), чтобы гарантировать пересечение.Это соответствует оранжевому и серому участкам на изображении.Обратите внимание, что этот шаг должен быть выполнен после шага 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 строк.
ваша сфера и прямая пересекаются , если
расстояние между центром окружности и одной вершиной вашей прямой меньше радиуса вашей сферы
или
расстояние между центром окружности и одним краем вашей прямой линии меньше радиуса вашей сферы ([расстояние от точки до линии ])
или
центр круга находится внутри прямой кишки
расстояние от точки до точки:
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
это не предполагает прямоугольника, выровненного по оси, и легко расширяется для проверки пересечений между выпуклыми множествами.
Это самое быстрое решение:
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;
}
На самом деле, это гораздо проще.Вам нужны только две вещи.
Во-первых, вам нужно найти четыре ортогональный расстояния от центра круга до каждой линии прямоугольника.Тогда ваш круг не будет пересекать прямоугольник, если любые три из них больше радиуса круга.
Во-вторых, вам нужно найти расстояние между центром окружности и центром прямоугольника, тогда ваш круг не будет находиться внутри прямоугольника, если расстояние больше половины длины диагонали прямоугольника.
Удачи вам!
Самое простое решение, которое я придумал, довольно прямолинейно.
Это работает путем нахождения точки в прямоугольнике, ближайшей к окружности, а затем сравнения расстояния.
Вы можете сделать все это с помощью нескольких операций и даже избежать функции 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, направленной вниз.
Если вам нужно решение для обработки столкновений между движущимся кругом и прямоугольником, это гораздо сложнее и покрыто в другом моем ответе.
Чтобы визуализировать, возьмите цифровую панель вашей клавиатуры.Если клавиша "5" представляет ваш прямоугольник, то все клавиши 1-9 представляют 9 квадрантов пространства, разделенных линиями, составляющими ваш прямоугольник (где 5 - внутренняя сторона).
1) Если центр окружности находится в квадранте 5 (т.е.внутри прямоугольника), затем две фигуры пересекаются.
Учитывая это, есть два возможных случая:а) Окружность пересекается с двумя или более соседними краями прямоугольника.б) Окружность пересекается с одним краем прямоугольника.
Первый случай прост.Если окружность пересекается с двумя соседними краями прямоугольника, она должна содержать угол, соединяющий эти два края.(Это или его центр находится в квадранте 5, который мы уже рассмотрели.Также обратите внимание, что случай, когда окружность пересекается только с двумя противостоящий края прямоугольника также закрываются.)
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.Для каждой перпендикулярной линии, если пересечение с исходным ребром лежит внутри окружности, то две фигуры пересекаются.
Для этого последнего шага есть короткий путь.Если центр окружности находится в квадранте 8, а ребро AB является верхним краем, точка пересечения будет иметь y-координату A и B и x-координату центра P.
Вы можете построить четыре пересечения линий и проверить, лежат ли они на соответствующих ребрах, или выяснить, в каком квадранте находится P, и проверить соответствующее пересечение.Оба должны быть упрощены до одного и того же булева уравнения.Будьте осторожны с тем, что шаг 2 выше не исключал, что P находится в одном из "угловых" квадрантов;он просто искал перекресток.
Редактировать:Как оказалось, я упустил из виду простой факт, что #2 является подосновой #3 выше.В конце концов, углы тоже являются точками на ребрах.Смотрите ответ @ShreevatsaR ниже для получения отличного объяснения.А пока забудьте о пункте 2 выше, если только вы не хотите быстрой, но избыточной проверки.
Эта функция обнаруживает столкновения (пересечения) между Кругом и прямоугольником.Он работает как метод э. Джеймса в своем ответе, но этот метод обнаруживает столкновения для всех углов прямоугольника (не только для прямого верхнего угла).
ПРИМЕЧАНИЕ:
aRect.origin.x и aRect.origin.y являются координатами нижнего левого угла прямоугольника!
Окружность.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;
}
Я создал класс для работы с фигурами надеюсь, вам понравится
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;
}
}
Вот модифицированный код, работающий на 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)));
}
Бассам Алугили
Вот быстрый однострочный тест для этого:
if (length(max(abs(center - rect_mid) - rect_halves, 0)) <= radius ) {
// They intersect.
}
Это случай, выровненный по оси, когда rect_halves является положительным вектором, указывающим от середины прямоугольника к углу.Выражение внутри length() является дельта - вектором из center к ближайшей точке прямоугольника.Это работает в любом измерении.
- Сначала проверьте, перекрываются ли прямоугольник и квадрат, касательные к окружности (легко).Если они не перекрываются, они не сталкиваются.
- Проверьте, находится ли центр круга внутри прямоугольника (легко).Если это внутри, они сталкиваются.
- Вычислите минимальное квадратное расстояние от сторон прямоугольника до центра круга (немного жестковато).Если он меньше квадрата радиуса, то они сталкиваются, в противном случае - нет.
Это эффективно, потому что:
- Сначала он проверяет наиболее распространенный сценарий с помощью дешевого алгоритма и, когда убеждается, что они не сталкиваются, завершает работу.
- Затем он проверяет следующий наиболее распространенный сценарий с помощью дешевого алгоритма (не вычисляйте квадратный корень, используйте возведенные в квадрат значения), и когда он уверен, что они совпадают, все заканчивается.
- Затем он выполняет более дорогостоящий алгоритм для проверки коллизии с границами прямоугольника.
У меня есть метод, который позволяет избежать дорогостоящего пифагора, если в этом нет необходимости - ie.когда ограничивающие прямоугольники прямоугольника и круга не пересекаются.
И это сработает и для неевклидовых систем:
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):
dLat=(lat-circleY); dLon=(lon-circleX); normed=dLat*dLat+dLon*dLon.Конечно, если вы используете этот метод normDist, вам нужно будет создатьnormedDist = dist*dist;для круга
Смотрите полный BBox ( почтовый ящик) и Круг код моего Графоман проект.
Для них необходимо вычислить столкновение круга и прямоугольника в географических координатах с помощью SQL,
это моя реализация в oracle 11 из э.Джеймс предложил алгоритм.
При вводе требуются координаты окружности, радиус окружности в км и координаты двух вершин прямоугольника:
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)));
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
Предполагая, что у вас есть четыре края прямоугольника, проверьте расстояние от краев до центра круга, если оно меньше радиуса, значит, фигуры пересекаются.
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
Если прямоугольник пересекается с кругом, то одна или несколько угловых точек прямоугольника должны находиться внутри круга.Предположим, что четыре точки прямоугольника - это A, B, C, D.по крайней мере, один из них должен пересекать окружность.таким образом, если расстояние от одной точки до центра окружности меньше радиуса окружности, оно должно пересекать окружность.Чтобы определить расстояние, вы можете воспользоваться теоремой Пифагора,
H^2 = A^2 + B^2
Этот метод имеет некоторые ограничения.Но это будет лучше работать для разработчиков игр.особенно обнаружение столкновений
Это хорошее обновление алгоритма Arvo
