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

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

Qt

Выбрось эту гадость.

4 раза посчитать точку пересечения двух прямых и проверить, что полученная точка внутри отрезка (т.е. x1<x<x2 && y1<y<y2)

Формула есть тут: http://e-maxx.ru/algo/lines_intersection

Плюс частные случаи, когда делишь на нуль. Если есть.

Пиши... составляй... находи... проверяй

Не хочу. Хочу готовое... Задача-то типичная. Уверен, что у кого-то из ЛОРовцев тупо есть нужный мне кусок кода.

гадость

Видал я такую гадость, по сравнению с которой Qt — квинтэссенция рационализма.

плоскость то ему зачем? пусть оперирует уравнениями прямых.

На тебе, двоечник!

Плоскость у тебя z=const. Строй систему, решай.

Затем, что проще найти координаты точки в СК прямоугольника и проверить принадлежность, нежели мучиться с кучей прямых (а если у тебя прямоугольник расположен в пространстве произвольно, то с плоскостью элементарно получится, а с прямыми сложно)

Как задан отрезок? Если координатами двух точек, то решение банально.

найди вот такую мурзилку или учебник по геометрии.

В любом банальном решении есть частные случаи и прочая билиберда, тестирующая моё внимание.
Да, задачка для старшеклассника, но вы не представляете НАСКОЛЬКО МНЕ ЛЕНЬ её решать:)
Тем более, что этот код написан сотни тысяч раз. Не хочу писать его в 100501 раз.

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

Да, считается.

Как-то так должно работать:

отрезок - px1, py1 - px2, py2 прямоугольник: x1, y1 - x2, y2

min( px1, px2 ) <= max( x1, x2 ) && max( px1, px2 ) >= min( x1, x2 ) && min( py1, py2 ) <= max( y1, y2 ) && max( py1, py2 ) >= min( y1, y2 )

И не надо ничего умножать-делить.

Да, считается.

Тогда для пересечения достаточно, чтобы внутри бокса находился любой из концов отрезка:

function p_inside_b(bx1,by1, bx2,by2, px,py) {
  return (bx1<=px) && (px<=bx2) && (by1<=py) && (py<=by2)
}

function crossed(bx1,by1, bx2,by2, px1,py1, px2,py2) {
  return p_inside_b(bx1,by1, bx2,by2, px1,py1) || p_inside_b(bx1,by1, bx2,by2, px2,py2)
}

На «ассемблерах для быстроты» переписывайте сами ;)

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

Нет, не достаточно.
Представь себе ситуацию, когда оба конца вне прямоугольника и отрезок отсекает «уголок».

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

Тогда для пересечения достаточно, чтобы внутри бокса находился любой из концов отрезка:

А если

    ***********************
    *                     *
    *                     *
    *                     *
A-----------------------------B
    *                     *
    *                     *
    *                     *
    ***********************

Действительно, забыл. Ну, тогда уравнения в зубы и барабан на шею :)

Представь себе ситуацию, когда оба конца вне прямоугольника и отрезок отсекает «уголок».

Хм... что-то я затупил.(

прямоугольник = 4 отрезка, или 4 отрезка + внутренняя область?

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

  static boolean intersect(Rect a, Rect b) {
    final float bxMin = b.getXMin();
    final float bxMax = b.getXMax();
    final float axMin = a.getXMin();
    final float axMax = a.getXMax();
    
    final float ayMin = a.getYMin();
    final float ayMax = a.getYMax();
    final float byMin = b.getYMin();
    final float byMax = b.getYMax();
    
    return (
            bxMin >= axMin && bxMin <= axMax ||
            bxMax >= axMin && bxMax <= axMax ||
            bxMin <= axMin && bxMax >= axMax
           ) && (
            byMin >= ayMin && byMin <= ayMax ||
            byMax >= ayMin && byMax <= ayMax ||
            byMin <= ayMin && byMax >= ayMax
           );
  }

результат ковыряния R*-tree Split

Ну ситуация когда оба конца отрезка внутри прямоугольника тривиальна. Так что не важно на самом деле-то.

Алгоритм Коэна — Сазерленда. Или наоборот. Они решили эту задачу почти полвека назад.

для определения факта пересечения.

Ласло М. Вычислительная геометрия и компьютерная графика на C++: © (progbook.ru)
5.6. алгоритм Цируса-Бека.
5.7. алгоритм Сазерленда-Хожмана.

Если все сделано на сцене с QGraphicsItem'ами, и простота реализации на первом месте, то самый очевидный вариант — использовать contains, где point это точки отрезка.

но вы не представляете НАСКОЛЬКО МНЕ ЛЕНЬ

Это ты не представляешь, насколько нам ЛЕ…

если тебе нужен самый простой в реализации способ, то важно.

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

быстрее реализовать это парой функций, чем пытаться сократить

https://www.rsdn.ru/forum/alg/641103.1 — уравнениями.

для float:

struct rect { float x1,y1,x2,y2; }
struct line  { float kx,ky,b;}//kx*x+ky*y+b=0
float p1 = kx*x1+ky*y1+b;
float p2 = kx*x1+ky*y2+b;
float p3 = kx*x2+ky*y1+b;
float p4 = kx*x2+ky*y2+b;
int32 i1  = 0x80000000 & reinterpret_cast<int32>(p1);
... то же для остальных p2 p3 p4;
int32 sum = 0xF & ((i1>>31)+(i2>>30)+(i3>>29)+(i4>>28));
if (sum != 0 && sum != 0xF) пересекаются;

можно сделать и на SSE2. для последней операции есть команда maskmov - она сразу и 0x80000000& и сдвиги сделает.

Алгоритм Коэна — Сазерленда

Взять уравнение прямой вида Ax+By+C=0. подставить все четыре точки в уравнение. Если результат для всех четырех будет одного знака, то пересечения нет.

Ах да, проверку данного условия легко сделать так:

пусть

a[i]=A*x[i]+B*y[i]+C

для каждго из углов прямоугольника.

if(a[0]*a[1]*a[2]*a[3]==0 || abs(a[0]/abs(a[0])+a[1]/abs(a[1])+a[2]/abs(a[2])+a[3]/abs(a[3]))!=4)
return пересекаются.

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

Проверка на пересечение двух отрезков — два левых поворота плюс, возможно, частные случаи. Энивей, уж пересечение двух отрезков-то легко нагуглить можно, наверняка на каком-нибудь e-maxx.ru/algo есть реализация.

Плюсую, задачка простая. Спроси у меня кто еще в школе, и то, кажется, решил бы.

но вы не представляете НАСКОЛЬКО МНЕ ЛЕНЬ

Это ты не представляешь, насколько нам ЛЕ…

В голос!