forum.boolean.name - Проверка нахождения точки в прямоугольнике

forum.boolean.name (http://forum.boolean.name/index.php)

- Алгоритмика (http://forum.boolean.name/forumdisplay.php?f=21)

- - Проверка нахождения точки в прямоугольнике (http://forum.boolean.name/showthread.php?t=4784)

Проверка нахождения точки в прямоугольнике

Дано: Прямоугольник, заданный 4 точками. (дополнительный параметр - угол на кот повернут прямоугольник относительно оси координат Y)
Точка заданная координатами

Нужно написать функцию, возращающую Труе\Фалсе на нахождение точки внутри прямоугольника.
Я решил эту задачу довольно извращенным способом, хотелось бы увидеть правильную математику :@

Re: Проверка нахождения точки в прямоугольнике

2 Tormoz- а ты давай нам вариан как ты сделал, мы тебе его отимизируем;)

Re: Проверка нахождения точки в прямоугольнике

У меня не математика :)
я поставил пивот на место точки, припарентил его к прямоугольнику, повернул прямоугольник на ноль, просчитал попадание простыми вычитаниями, потом повернул прямоугольник как было.
Все средствами Блитц3д
Но это через анус.
Нужно формулами решить, ибо некрасиво.
(говорила мне мама - учись сынок. а я пиво, пиво... )

Re: Проверка нахождения точки в прямоугольнике

Цитата:

Дано: Прямоугольник, заданный 4 точками. (дополнительный параметр - угол на кот повернут прямоугольник относительно оси координат Y)

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

Цитата:

(говорила мне мама - учись сынок. а я пиво, пиво... )

Re: Проверка нахождения точки в прямоугольнике

Ну например через расстояния от точки до каждого отрезка. Если расстояние от точки до отрезка отрицательно, значит она находится с одной стороны, если положительно - с другой.

Код:

dx = x2 - x1

dy = y2 - y1

d1# = ((y1 - Py) * Dx + (Px - x1) * Dy) / (Dy * Dy + Dx * Dx)

dx = x3 - x2

dy = y3 - y2

d2# = ((y2 - Py) * Dx + (Px - x2) * Dy ) / (Dy * Dy + Dx * Dx)

dx = x4 - x3

dy = y4 - y3

d3# = ((y3 - Py) * Dx + (Px - x3) * Dy ) / (Dy * Dy + Dx * Dx)

dx = x1 - x4

dy = y1 - y4

d4# = ((y4 - Py) * Dx + (Px - x4) * Dy ) / (Dy * Dy + Dx * Dx)

Где x1, y1, x2, y2, x3, y3, x4, y4 - координаты точек, образующих четырехугольник, Px, Py - координаты проверяемой точки
если d1, d2, d3, d4 отрицательны - точка внутри четырехугольника

Еще можно трансформировать проверяемую точку, т.е. повернуть ее на угол поворота прямоугольника и потом проверить пересечение как обычно - без учета поворота.
Поворот точки на угол альфа, через центр cx, cy, можно осуществить так

Код:

dx = ox - cx

dy = oy - cy

nx = cx + (dx * cos(alpha) - dy * sin(alpha))

ny = cy + (dx * sin(alpha) + dy * cos(alpha))

Где ox, oy - старые координаты точки, nx, ny - новые координаты точки
:)

Re: Проверка нахождения точки в прямоугольнике

алгоритм для н-угольника (вершины все сперва ручками трансформируем... ну или в функции как вариант =)

Код:

// point - искомая точка

// verts - массив вершин n-угольника

// vertCount - кол-во вершин

bool InsidePolygon(Vector3 point, Vector3 verts[], int vertCount)

{

    const float MATCH = 0.99f; //для учета погрешностей вычислений

    float angle = 0.0f; // суммарный угол

    Vector3 vA; // временные вектора

    Vector3 vB;

    // цикл по всем вершинам

    for(int i = 0; i < vertCount; i++) 

    {

        // высчитываем вектора от искомой точки до текущей вершины

        vA = verts[i] - point;

        // и от искомой точки до следующей вершины

        vB = verts[(i + 1) % vertCount] - point;

        // увеличиваем angle на угол между этими векторами

        angle += AngleBetweenVectors(vA, vB);

    }

    // если в сумме угол = 2Pi (+-погрешность) значит точка находится внутри

    if(angle >= (MATCH * (2.0f * PI)))

    {

        return true;

    }

    return false;

}

думаю перевести в бейсик не трудно будет =) могу и на картинках показать суть алгоритма =)

Re: Проверка нахождения точки в прямоугольнике

Вот кстати ещё один способ. Но работает при одном условии, точки должны идти вподряд.

If (
((mouse_x-pr\px[0])*(pr\py[1]-pr\py[0])-(mouse_y-pr\py[0])*(pr\px[1]-pr\px[0]))>0)
And
(((mouse_x-pr\px[2])*(pr\py[1]-pr\py[2])-(mouse_y-pr\py[2])*(pr\px[1]-pr\px[2]))<0)
And
(((mouse_x-pr\px[3])*(pr\py[2]-pr\py[3])-(mouse_y-pr\py[3])*(pr\px[2]-pr\px[3]))<0)
And
(((mouse_x-pr\px[3])*(pr\py[0]-pr\py[3])-(mouse_y-pr\py[3])*(pr\px[0]-pr\px[3]))>0)
Then
Return 1
EndIf