VPF::[C++] Пересечение фигур на плоскости

Pale_Master

Дата 22.2.2007, 17:00 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 13
Регистрация: 22.2.2007

Репутация: нет
Всего: нет

Заданы две фигуры на плоскости.
Круг (именно круг, а не окружность) координатами центра и радиусом + прямоугольник - координатами левого верхнего угла и шириной+высотой (под прямоугольником имеется ввиду множество точек, а не 4 прямых).
Нужно определить факт существования общих точек у этих фигур.
Буду рад увидить математический алгоритм решения этой задачи.
Заранее благодарен.

Sartorius

Дата 22.2.2007, 17:26 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1568
Регистрация: 18.7.2006
Где: Ivory tower

Репутация: 8
Всего: 37

Ну начнем с того, что для плоскости не важно круг это или окружность и про прямоугольтик тоже самое. А решается она например так
- выбираем сторону четырехугольника. находим точки пересечения линии, которой она пренадлежит и окружности.
- если такие есть - проверяем попадают они на сторону или нет( смотрим диапазон по каждой координате).
- и так для каждой стороны.

KelTron

Дата 22.2.2007, 17:36 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 745
Регистрация: 8.10.2006
Где: Красноярск

Репутация: нет
Всего: 38

Чисто математически:
Решаем систему уравнений:
1: (x-a)^2 + (y-b)^2 <= r^2
2: s1<= x <=s3
3: s2<= y <=s4

Здесь1 - уравнение круга(или неравенство) причем a - расстояние от центра по х, b - расстояние от центра по у, r - радиус круга.
2 и 3 - множество точек которые являются прямоугольником(+ то что внутри него) со сторонами s1, s2, s3,s4
Из этой системы можно найти все точки пересечения круга и заполненного прямоугольника

Но как сказал Sartorius

Цитата(Sartorius @ 22.2.2007, 17:26

)

не важно круг это или окружность и про прямоугольтик тоже самое

елси тебе надо определить только факт существования точек пересечения

Это сообщение отредактировал(а) KelTron - 22.2.2007, 17:38

--------------------

Тысячами незримых нитей обвивает тебя Закон. Разрубишь одну - преступник. Десять - смертник. Все - Бог.
Эвенгар Салладорский, основатель Школы Тьмы.

Pale_Master

Дата 22.2.2007, 17:43 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 13
Регистрация: 22.2.2007

Репутация: нет
Всего: нет

Цитата

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

Ну как это неважно? Ведь если фигуры будут вписаны друг в друга, то если говорить про линии, а не множества точек, то это не будет считаться пересечением.

2.

Цитата

1: (x-a)^2 + (y-b)^2 <= r^2
2: s1<= x <=s3
3: s2<= y <=s4

Это понятно. А вот решить, да ещё и так, чтобы выполнялось быстро.. вот с этим проблема..

KelTron

Дата 22.2.2007, 17:53 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 745
Регистрация: 8.10.2006
Где: Красноярск

Репутация: нет
Всего: 38

Цитата(Pale_Master @ 22.2.2007, 17:43

)

Ну как это неважно? Ведь если фигуры будут вписаны друг в друга, то если говорить про линии, а не множества точек, то это не будет считаться пересечением.

Ты прав

--------------------

KelTron

Дата 22.2.2007, 18:32 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 745
Регистрация: 8.10.2006
Где: Красноярск

Репутация: нет
Всего: 38

Вот что взбрело мне в голову:

Если провести через окружность вертикальный диаметр и горизонтальный, то получим 4 точки пересечения - левая, правая, верхняя, нижняя.
для левой xLeft = a - r, для правой xRight = a + r, для нижней yBottom = b - r, для верхней yTop = b + r.

Пусть rectLeft, rectRight - координаты х для левой и праваой сторон прямоугольника, а reftTop, rectBottom - координаты у для верхней и нижней сторон прямоугольника.

Тогда проверяем условие:
если ((xLeft < rectLeft) и (xRight < rectLeft)) или ((xLeft > rectRight) и (xRight > rectRight))
или((yTop > rectTop) и (yBotton > rectTop)) или ((yTop < rectBottom) и (yBottom < rectBottom))
то значит фигуры не имеют общих точек, иначе - фигуры имеют общие точки.

--------------------

Sartorius

Дата 22.2.2007, 18:42 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1568
Регистрация: 18.7.2006
Где: Ivory tower

Репутация: 8
Всего: 37

KelTron, а почему ты думаешь, что стороны прямоугольника параллельны осям координат ? да и для такого случая такая система неравенств не годиться. ( нарисовать тут пример не могу)

Pale_Master,

Цитата

Да этот случай пропустил((

Мне кажется, что врядли найдется что то лучше обычной системы неравенств

Y <=(>=) kx + b( для каждой из сторон прямоугольника задаем)
(X-X0)^2 + (Y-Y0)^2 <= R^2 - окружность

если у нее есть решение - то есть общие точки

KelTron

Дата 22.2.2007, 18:49 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 745
Регистрация: 8.10.2006
Где: Красноярск

Репутация: нет
Всего: 38

Цитата(Sartorius @ 22.2.2007, 18:42

)

KelTron, а почему ты думаешь, что стороны прямоугольника параллельны осям координат

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

Цитата(Sartorius @ 22.2.2007, 18:42

)

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

я придумал этот алгоритм 5 минут назад, хотелось бы всё - таки увидеть пример, а то сам что то не могу представить (голова уже слабо варит - спать надо)

--------------------

Sartorius

Дата 22.2.2007, 19:30 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1568
Регистрация: 18.7.2006
Где: Ivory tower

Репутация: 8
Всего: 37

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

Это сообщение отредактировал(а) Sartorius - 22.2.2007, 19:32

Присоединённый файл ( Кол-во скачиваний: 10 )

______.JPG 11,03 Kb

Pale_Master

Дата 23.2.2007, 00:15 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 13
Регистрация: 22.2.2007

Репутация: нет
Всего: нет

И всё же, как вот это:

Цитата

1: (x-a)^2 + (y-b)^2 <= r^2
2: s1<= x <=s3
3: s2<= y <=s4

превратить в код ?

Rockie

Дата 23.2.2007, 02:59 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1143
Регистрация: 23.4.2006

Репутация: 13
Всего: 31

Если расстояние от одной из вершин прямоугольника до центра окружности меньше радиуса - есть общие точки.
Если центр окружности лежит внутри прямоугольника: есть общие точки.

Есть функция определения принадлежности точки к полигону, с кодом, в том числе на Си
Point in polygon

--------------------

Чтобы иметь большой гардероб - надо иметь большой гардероб.

Sartorius

Дата 23.2.2007, 09:48 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1568
Регистрация: 18.7.2006
Где: Ivory tower

Репутация: 8
Всего: 37

Цитата

Если расстояние от одной из вершин прямоугольника до центра окружности меньше радиуса

неверно. Представь , что окружность касается одной из сторон... Расстояние до всех вершин больше радиуса, а общие точки есть.

Rockie

Дата 23.2.2007, 11:27 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1143
Регистрация: 23.4.2006

Репутация: 13
Всего: 31

Цитата(Sartorius @ 23.2.2007, 09:48

)

неверно.

вообще-то верно, но не единственно верно. =)
Да, я сам до этого уже додумал. Тогда нахождением пересечения.

Пересечение отрезка и круга(окружности)

--------------------

Чтобы иметь большой гардероб - надо иметь большой гардероб.

Pale_Master

Дата 23.2.2007, 12:40 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 13
Регистрация: 22.2.2007

Репутация: нет
Всего: нет

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

Но все жё жутко интересно, как вот это:

Цитата

1: (x-a)^2 + (y-b)^2 <= r^2
2: s1<= x <=s3
3: s2<= y <=s4

превратить в код.. smile

Код


#ifndef MGCINTR2DCIRBOX_H
#define MGCINTR2DCIRBOX_H

#include "MgcBox2.h"

namespace Mgc
{

// Find first time/point of contact of moving circle and oriented rectangle.
//
// Inputs are:
//   rkC:       circle center
//   fR:        circle radius
//   rkV:       circle velocity
//   rkBox:     oriented rectangle
//   rfTFirst:  first time of contact
//   rkIntr:    first point of contact
//
// Return -1 if initially intersecting, 0 if no intersection, +1 if intersects
// at some positive time.  First time/point of contact are only valid if the
// return value is +1.

MAGICFM int FindIntersection (const Vector2& rkC, Real fR, const Vector2& rkV,
    const Box2& rkBox, Real& rfTFirst, Vector2& rkIntr);

}

#endif

Код


#include "MgcIntr2DCirBox.h"
using namespace Mgc;

//----------------------------------------------------------------------------
// All functions return -1 if initially intersecting, 0 if no intersection,
// +1 if intersects at some positive time.
//----------------------------------------------------------------------------
static int TestVertexRegion (Real fCx, Real fCy, Real fR, Real fVx, Real fVy,
    Real fEx, Real fEy, Real& rfTFirst, Real& rfIx, Real& rfIy)
{
    Real fDx = fCx + fEx;
    Real fDy = fCy + fEy;
    Real fRSqr = fR*fR;
    Real fDiff = fDx*fDx + fDy*fDy - fRSqr;
    if ( fDiff <= 0.0f )
    {
        // circle is already intersecting the box
        rfTFirst = 0.0f;
        return -1;
    }

    Real fDot = fVx*fDx + fVy*fDy;
    if ( fDot >= 0.0f )
    {
        // circle not moving towards box
        return 0;
    }

    Real fKross = fVx*fDy - fVy*fDx;
    Real fVSqr, fInv;

    if ( fKross >= 0.0f )
    {
        // potential contact on left edge
        if ( fKross <= fR*fVy )
        {
            // lower left corner is first point of contact
            rfIx = -fEx;
            rfIy = -fEy;
            fVSqr = fVx*fVx + fVy*fVy;
            fInv = Math::InvSqrt(Math::FAbs(fDot*fDot-fVSqr*fDiff));
            rfTFirst = fDiff*fInv/(1.0f-fDot*fInv);
            return 1;
        }

        if ( fVx <= 0.0f )
        {
            // passed corner, moving away from box
            return 0;
        }

        fVSqr = fVx*fVx + fVy*fVy;
        fDy = fCy - fEy;
        fKross = fVx*fDy - fVy*fDx;
        if ( fKross >= 0.0f && fKross*fKross > fRSqr*fVSqr )
        {
            // circle misses box
            return 0;
        }

        // Circle will intersect box.  Determine first time and place of
        // contact with x = xmin.
        rfIx = -fEx;

        if ( fKross <= fR*fVy )
        {
            // first contact on left edge of box
            rfTFirst = -(fDx+fR)/fVx;
            rfIy = fCy + rfTFirst*fVy;
        }
        else
        {
            // first contact at upper left corner of box
            fDot = fVx*fDx + fVy*fDy;
            fDiff = fDx*fDx + fDy*fDy - fRSqr;
            fInv = Math::InvSqrt(Math::FAbs(fDot*fDot-fVSqr*fDiff));
            rfTFirst = fDiff*fInv/(1.0f-fDot*fInv);
            rfIy = fEy;
        }
    }
    else
    {
        // potential contact on bottom edge
        if ( -fKross <= fR*fVx )
        {
            // lower left corner is first point of contact
            rfIx = -fEx;
            rfIy = -fEy;
            fVSqr = fVx*fVx + fVy*fVy;
            fInv = Math::InvSqrt(Math::FAbs(fDot*fDot-fVSqr*fDiff));
            rfTFirst = fDiff*fInv/(1.0f-fDot*fInv);
            return 1;
        }

        if ( fVy <= 0.0f )
        {
            // passed corner, moving away from box
            return 0;
        }

        fVSqr = fVx*fVx + fVy*fVy;
        fDx = fCx - fEx;
        fKross = fVx*fDy - fVy*fDx;
        if ( -fKross >= 0.0f && fKross*fKross > fRSqr*fVSqr )
        {
            // circle misses box
            return 0;
        }

        // Circle will intersect box.  Determine first time and place of
        // contact with y = ymin.
        rfIy = -fEy;

        if ( -fKross <= fR*fVx )
        {
            // first contact on bottom edge of box
            rfTFirst = -(fDy+fR)/fVy;
            rfIx = fCx + rfTFirst*fVx;
        }
        else
        {
            // first contact at lower right corner of box
            fDot = fVx*fDx + fVy*fDy;
            fDiff = fDx*fDx + fDy*fDy - fRSqr;
            fInv = Math::InvSqrt(Math::FAbs(fDot*fDot-fVSqr*fDiff));
            rfTFirst = fDiff*fInv/(1.0f-fDot*fInv);
            rfIx = fEx;
        }
    }

    return 1;
}
//----------------------------------------------------------------------------
static int TestEdgeRegion (Real fCx, Real fCy, Real fR, Real fVx, Real fVy,
    Real fEx, Real fEy, Real& rfTFirst, Real& rfIx, Real& rfIy)
{
    Real fDx = fCx + fEx;
    Real fXSignedDist = fDx + fR;
    if ( fXSignedDist >= 0.0f )
    {
        // circle is already intersecting the box
        rfTFirst = 0.0f;
        return -1;
    }

    if ( fVx <= 0.0f )
    {
        // circle not moving towards box
        return 0;
    }

    Real fRSqr = fR*fR;
    Real fVSqr = fVx*fVx + fVy*fVy;
    Real fDy, fDot, fKross, fDiff, fInv;

    if ( fVy >= 0.0f )
    {
        fDy = fCy - fEy;
        fKross = fVx*fDy - fVy*fDx;
        if ( fKross >= 0.0f && fKross*fKross > fRSqr*fVSqr )
        {
            // circle misses box
            return 0;
        }

        // Circle will intersect box.  Determine first time and place of
        // contact with x = xmin.
        rfIx = -fEx;

        if ( fKross <= fR*fVy )
        {
            // first contact on left edge of box
            rfTFirst = -fXSignedDist/fVx;
            rfIy = fCy + rfTFirst*fVy;
        }
        else
        {
            // first contact at corner of box
            fDot = fVx*fDx + fVy*fDy;
            fDiff = fDx*fDx + fDy*fDy - fRSqr;
            fInv = Math::InvSqrt(Math::FAbs(fDot*fDot-fVSqr*fDiff));
            rfTFirst = fDiff*fInv/(1.0f-fDot*fInv);
            rfIy = fEy;
        }
    }
    else
    {
        fDy = fCy + fEy;
        fKross = fVx*fDy - fVy*fDx;
        if ( fKross <= 0.0f && fKross*fKross > fRSqr*fVSqr )
        {
            // circle misses box
            return 0;
        }

        // Circle will intersect box.  Determine first time and place of
        // contact with x = xmin.
        rfIx = -fEx;

        if ( fKross >= fR*fVy )
        {
            // first contact on left edge of box
            rfTFirst = -fXSignedDist/fVx;
            rfIy = fCy + rfTFirst*fVy;
        }
        else
        {
            // first contact at corner of box
            fDot = fVx*fDx + fVy*fDy;
            fDiff = fDx*fDx + fDy*fDy - fRSqr;
            fInv = Math::InvSqrt(Math::FAbs(fDot*fDot-fVSqr*fDiff));
            rfTFirst = fDiff*fInv/(1.0f-fDot*fInv);
            rfIy = -fEy;
        }
    }

    return 1;
}
//----------------------------------------------------------------------------
int Mgc::FindIntersection (const Vector2& rkC, Real fR, const Vector2& rkV,
    const Box2& rkBox, Real& rfTFirst, Vector2& rkIntr)
{
    // Convert circle center to box coordinates.
    Vector2 kDiff = rkC - rkBox.Center();
    Real fCx = kDiff.Dot(rkBox.Axis(0));
    Real fCy = kDiff.Dot(rkBox.Axis(1));
    Real fVx = rkV.Dot(rkBox.Axis(0));
    Real fVy = rkV.Dot(rkBox.Axis(1));
    Real fEx = rkBox.Extent(0);
    Real fEy = rkBox.Extent(1);
    Real fIx, fIy;

    int iType = 0;

    if ( fCx < -fEx )
    {
        if ( fCy < -fEy )
        {
            // region Rmm
            iType = TestVertexRegion(fCx,fCy,fR,fVx,fVy,fEx,fEy,
                rfTFirst,fIx,fIy);
        }
        else if ( fCy <= fEy )
        {
            // region Rmz
            iType = TestEdgeRegion(fCx,fCy,fR,fVx,fVy,fEx,fEy,
                rfTFirst,fIx,fIy);
        }
        else
        {
            // region Rmp
            iType = TestVertexRegion(fCx,-fCy,fR,fVx,-fVy,fEx,fEy,
                rfTFirst,fIx,fIy);
            fIy = -fIy;
        }
    }
    else if ( fCx <= fEx )
    {
        if ( fCy < -fEy )
        {
            // region Rzm
            iType = TestEdgeRegion(fCy,fCx,fR,fVy,fVx,fEy,fEx,
                rfTFirst,fIy,fIx);
        }
        else if ( fCy <= fEy )
        {
            // region Rzz: circle is already intersecting the box
            rfTFirst = 0.0f;
            return -1;
        }
        else
        {
            // region Rzp
            iType = TestEdgeRegion(-fCy,fCx,fR,-fVy,fVx,fEy,fEx,
                rfTFirst,fIy,fIx);
            fIy = -fIy;
        }
    }
    else
    {
        if ( fCy < -fEy )
        {
            // region Rpm
            iType = TestVertexRegion(-fCx,fCy,fR,-fVx,fVy,fEx,fEy,
                rfTFirst,fIx,fIy);
            fIx = -fIx;
        }
        else if ( fCy <= fEy )
        {
            // region Rpz
            iType = TestEdgeRegion(-fCx,fCy,fR,-fVx,fVy,fEx,fEy,
                rfTFirst,fIx,fIy);
            fIx = -fIx;
        }
        else
        {
            // region Rpp
            iType = TestVertexRegion(-fCx,-fCy,fR,-fVx,-fVy,fEx,fEy,
                rfTFirst,fIx,fIy);
            fIx = -fIx;
            fIy = -fIy;
        }
    }

    if ( iType == 1 )
        rkIntr = rkBox.Center() + fIx*rkBox.Axis(0) + fIy*rkBox.Axis(1);

    return iType;
}
//----------------------------------------------------------------------------

MBo

Дата 23.2.2007, 13:30 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 234
Регистрация: 10.6.2002

Репутация: 7
Всего: 18

Код


function IsCircRectIntersect(CX, CY, CR: Integer; RR: TRect): Boolean;
var
  wh, hh, dx, dy, t, dr: Double;
begin
  dr := 0;
  wh := 0.5 * (RR.Right - RR.Left);
  hh := 0.5 * (RR.Bottom - RR.Top);
  dx := CX - 0.5 * (RR.Left + RR.Right);
  dy := CY - 0.5 * (RR.Top + RR.Bottom);
  t := dx + wh;
  if t < 0 then
    dr := t * t
  else begin
    t := dx - wh;
    if t > 0 then
      dr := t * t
  end;
  t := dy + hh;
  if t < 0 then
    dr := dr + t * t
  else begin
    t := dy - hh;
    if t > 0 then
      dr := dr + t * t
  end;
  Result := CR * CR > dr;
end;

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »