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

[tormoz]

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

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

[ЛысыЙ_Чук-Иванчук]

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

[tormoz]

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

[HolyDel]

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

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

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

[Platon]

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

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 - новые координаты точки

[Knightmare]

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

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

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

[Frank]

http://blitz.pp.ru/forum/showthread....&threadid=1378

[dimanche13]

http://algolist.manual.ru/maths/geom/belong/poly2d.php

[Render]

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

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