Обнаружение столкновений круглого прямоугольника (пересечение)

geometry collision-detection

170495 просмотра

20 ответа

Как я могу определить, пересекаются ли круг и прямоугольник в двумерном евклидовом пространстве? (т.е. классическая 2D-геометрия)

Автор: aib Источник Размещён: 17.05.2019 03:34

Ответы (20)


148 плюса

Решение

Есть только два случая, когда круг пересекается с прямоугольником:

  • Либо центр круга находится внутри прямоугольника, либо
  • Один из краев прямоугольника имеет точку в круге.

Обратите внимание, что это не требует, чтобы прямоугольник был параллельным оси.

Некоторые различные способы пересечения круга и прямоугольника

(Один из способов увидеть это: если ни один из ребер не имеет точки в круге (если все ребра полностью «вне» круга), то единственный способ, по которому круг может пересекать многоугольник, - это если он полностью лежит внутри многоугольник.)

С этим пониманием, что - то вроде следующего будет работать, где круг имеет центр 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до линии достаточно близко и между конечными точками, и в противном случае проверить конечные точки.

Самое интересное, что эта же идея работает не только для прямоугольников, но и для пересечения круга с любым простым многоугольником - даже не должна быть выпуклой!

Автор: ShreevatsaR Размещён: 31.12.2008 01:17

259 плюса

Вот как я это сделаю:

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));
}

Вот как это работает:

illusration

  1. Первая пара строк вычисляет абсолютные значения разности x и y между центром круга и центром прямоугольника. Это сворачивает четыре квадранта вниз на один, так что вычисления не нужно делать четыре раза. На изображении отображается область, в которой теперь должен находиться центр круга. Обратите внимание, что показан только один квадрант. Прямоугольник - это серая область, а красная граница - критическая область, которая находится ровно на один радиус от краев прямоугольника. Центр круга должен находиться внутри этой красной границы для пересечения.

  2. Вторая пара линий исключает простые случаи, когда круг достаточно далеко от прямоугольника (в любом направлении), что пересечение невозможно. Это соответствует зеленой зоне изображения.

  3. Третья пара линий обрабатывает простые случаи, когда круг достаточно близко к прямоугольнику (в любом направлении), что пересечение гарантировано. Это соответствует оранжевой и серой части изображения. Обратите внимание, что этот шаг должен быть выполнен после шага 2, чтобы логика имела смысл.

  4. Остальные строки вычисляют сложный случай, когда круг может пересекать угол прямоугольника. Чтобы решить, вычислите расстояние от центра круга и угла, а затем убедитесь, что расстояние не больше радиуса круга. Этот расчет возвращает false для всех кругов, центр которых находится в красной заштрихованной области, и возвращает значение true для всех кругов, центр которых находится в области белого оттенка.

Автор: e.James Размещён: 31.12.2008 01:14

112 плюса

Вот еще одно решение, которое довольно просто реализовать (и довольно быстро). Он поймает все перекрестки, в том числе, когда сфера полностью войдет в прямоугольник.

// 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 строк.

Автор: Cygon Размещён: 10.12.2009 07:30

10 плюса

ваша сфера и прямоугольник пересекают IIF,
расстояние между центром круга и одной вершиной вашего прямоугольника меньше радиуса вашей сферы
ИЛИ
расстояние между центром круга и одним краем вашего прямоугольника меньше радиуса вашей сферы ( [расстояние по точке ])
ИЛИ
центр окружности находится внутри прямого

точечного расстояния:

P1 = [x1, y1]
P2 = [x2, y2]
Расстояние = sqrt (abs (x1 - x2) + abs (y1-y2))

точка-расстояние:

L1 = [x1, y1], L2 = [x2, y2] (две точки вашей линии, т. Е. Точки вершин)
P1 = [px, py] некоторая точка

Расстояние d = abs ((x2-x1) (y1-py) - (x1-px) (y2-y1)) / Расстояние (L1, L2)


центр круга внутри прямоугольника:
возьмите осевую ось aproach: если существует проекция на линию, которая отделяет прямоугольник от точки, они не пересекаются

вы проецируете точку на линии, параллельные сторонам вашего прямоугольника, и затем можете легко определить, пересекаются ли они. если они пересекаются не на всех 4 проекциях, они (точка и прямоугольник) не могут пересекаться.

вам просто нужен внутренний продукт (x = [x1, x2], y = [y1, y2], x * y = x1 * y1 + x2 * y2)

ваш тест будет выглядеть так:

// прямоугольники прямоугольника: TL (вверху слева), TR (верхний правый), BL (внизу слева), BR (внизу справа)
// точка для проверки: POI

seperated = false
для egde в {{TL, TR}, {BL, BR}, {TL, BL}, {TR-BR}}: // ребра
    D = край [0] - край [1]
    innerProd = D * POI
    Interval_min = min (D * edge [0], D * edge [1])
    Interval_max = max (D * edge [0], D * edge [1])
    если нет (Interval_min ≤ innerProd ≤ Interval_max) 
           seperated = true
           break // end for loop 
    конец, если
конец для
если (разделено верно)    
      вернуть "нет пересечения"
еще 
      возвращение "пересечения"
конец, если

это не предполагает прямоугольник, выровненный по оси и легко расширяемый для проверки пересечений между выпуклыми множествами.

Автор: user104676 Размещён: 11.05.2009 09:09

6 плюса

Это самое быстрое решение:

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;
}

Обратите внимание на порядок выполнения, а половина ширины / высоты предварительно вычисляется. Также возведение в квадрат выполняется «вручную», чтобы сохранить некоторые тактовые циклы.

Автор: intrepidis Размещён: 11.09.2012 11:36

3 плюса

Вот мой код 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;
}
Автор: Madrayken Размещён: 18.06.2010 02:43

3 плюса

Собственно, это намного проще. Вам нужно всего две вещи.

Во-первых, вам нужно найти четыре ортогональных расстояния от центра круга до каждой линии прямоугольника. Тогда ваш круг не будет пересекать прямоугольник, если любые три из них больше радиуса круга.

Во-вторых, вам нужно найти расстояние между центром окружности и центром прямоугольника, тогда вы не будете внутри прямоугольника, если расстояние больше половины длины диагонали прямоугольника.

Удачи!

Автор: ole Размещён: 09.04.2013 03:33

2 плюса

Чтобы визуализировать, введите numpad клавиатуры. Если ключ «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) через центр круга. каждая перпендикулярная линия, если пересечение с исходным ребром лежит внутри круга, то две формы пересекаются.

Для последнего шага есть ярлык. Если центр круга находится в квадранте 8, а край AB - верхний край, точка пересечения будет иметь y-координату A и B, а x-координату центра P.

Вы можете построить четыре пересечения линий и проверить, лежат ли они на соответствующих ребрах, или выяснить, какой квадрант P находится и проверить соответствующее пересечение. Оба должны упростить одно и то же булево уравнение. Будьте осторожны, что шаг 2 выше не исключал, что P находится в одном из «угловых» квадрантов; он просто искал перекресток.

Edit: Как оказалось, я упустил тот простой факт, что # 2 является подкадром № 3 выше. В конце концов, углы тоже являются точками по краям. См. Ответ @ ShreevatsaR ниже для отличного объяснения. И тем временем, забудьте № 2 выше, если вы не хотите быстрой, но избыточной проверки.

Автор: aib Размещён: 31.12.2008 12:20

2 плюса

Эта функция обнаруживает столкновения (пересечения) между Кругом и Прямоугольником. В своем ответе он работает как метод Э. Джеймс, но обнаруживает столкновения для всех углов прямоугольника (не только в правом углу).

НОТА:

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;
}
Автор: Faraona Размещён: 23.04.2012 11:33

2 плюса

Самое простое решение, которое я придумал, довольно просто.

Он работает, находя точку в прямоугольнике, ближайшем к кругу, затем сравнивая расстояние.

Вы можете сделать все это с помощью нескольких операций и даже избежать функции 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;
}

И это все! Вышеприведенное решение предполагает начало в верхнем левом углу мира с опущенной осью х.

Если вам нужно решение для обработки столкновений между движущимся кругом и прямоугольником, это намного сложнее и покрыто другим моим ответом.

Автор: ClickerMonkey Размещён: 13.09.2013 05:15

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;
  } 
}
Автор: pwipo Размещён: 22.06.2012 03:40

1 плюс

Ниже приведен код modfied 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 Размещён: 16.08.2010 06:47

1 плюс

Вот быстрый однострочный тест для этого:

if (length(max(abs(center - rect_mid) - rect_halves, 0)) <= radius ) {
  // They intersect.
}

Это выровненный по оси случай, где rect_halves- положительный вектор, указывающий от середины прямоугольника к углу. Выражение внутри length()- это дельта-вектор от centerближайшей точки в прямоугольнике. Это работает в любом измерении.

Автор: Tyler Размещён: 22.07.2015 06:12

1 плюс

  • Сначала проверьте, перекрывается ли прямоугольник и квадрат касательной к кругу (легко). Если они не перекрываются, они не сталкиваются.
  • Проверьте, находится ли центр круга внутри прямоугольника (легко). Если он внутри, они сталкиваются.
  • Вычислите минимальное квадратное расстояние от сторон прямоугольника до центра круга (немного трудно). Если он меньше радиуса квадрата, то они сталкиваются, иначе они этого не делают.

Это эффективно, потому что:

  • Сначала он проверяет наиболее распространенный сценарий с дешевым алгоритмом, и когда он уверен, что они не сталкиваются, он заканчивается.
  • Затем он проверяет следующий наиболее распространенный сценарий с дешевым алгоритмом (не вычисляйте квадратный корень, используйте квадратные значения), и когда он уверен, что они сталкиваются с концом.
  • Затем он выполняет более дорогой алгоритм проверки столкновения с границами прямоугольника.
Автор: David C. Размещён: 21.08.2015 09:16

0 плюса

У меня есть метод, который позволяет избежать дорогостоящих пифагор, если не нужно, т.е. когда ограничивающие прямоугольники и круг не пересекаются.

И он будет работать и для неевклидовых:

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 ist немного быстрее, чем полный расчет расстояния. Например , без квадратного корня в евклидовом пространстве (или без него много других вещей для гаверсинуса) dLat=(lat-circleY); dLon=(lon-circleX); normed=dLat*dLat+dLon*dLon. Конечно, если вы используете этот метод normDist, вам нужно будет создать a normedDist = dist*dist;для круга

См. Полный код BBox и Circle моего проекта GraphHopper .

Автор: Karussell Размещён: 26.05.2012 09:53

0 плюса

Для тех, кто должен вычислить столкновение Круг / Прямоугольник в Географических Координатах с SQL,
это моя реализация в oracle 11 предложенного алгоритма e.James .

Для ввода требуются координаты окружности, радиус окружности в км и две вершины координат прямоугольника:

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;    
Автор: fl4l Размещён: 13.03.2015 04:33

0 плюса

Работы, только что выяснили это неделю назад, и только сейчас прошли тестирование.

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)));
Автор: user3026859 Размещён: 22.08.2014 05:45

0 плюса

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
Автор: Cassiano Размещён: 22.11.2018 03:12

-1 плюса

Предполагая, что у вас четыре края прямоугольника, проверьте расстояние от краев до центра круга, если его меньше радиуса, то формы пересекаются.

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
Автор: ForYourOwnGood Размещён: 30.12.2008 11:42

-2 плюса

Если прямоугольник пересекается с кругом, одна или несколько угловых точек прямоугольника должны быть внутри круга. Предположим, что четыре точки прямоугольника - A, B, C, D. по крайней мере один из них должен пересекать круг. поэтому, если расстояние от одной точки до центра круга меньше радиуса круга, оно должно пересекать круг. Чтобы получить расстояние, вы можете использовать теорему Пифагора,

H^2 = A^2 + B^2

Этот метод имеет некоторые ограничения. Но он будет работать лучше для разработчиков игр. особенно обнаружение столкновения

Это хорошее обновление алгоритма Арво

Автор: Md. Ashraful Islam Размещён: 26.11.2017 06:48
Вопросы из категории :
32x32