Есть два прямоугольника с координатами. Надо найти входит ли второй в координаты первого.
Первый прямоугольник M имеет координаты сторон MT MR MB ML
Второй прямоугольник C имеет координаты сторон CT CR CB CL
T,R,B,L - top, right, bottom, left
Что у меня выходит:

((ML<CL<MR) И ((MT<CT<MB) ИЛИ (MT<CB<MB))) ИЛИ ((ML<CR<MR) И ((MT<CT<MB) ИЛИ (MT<CB<MB)))

Вроде как два раза проходила логику в Школе и в Институте, но не могу вспомнить правила упрощения. Здесь есть повторяющийся блок. Как его правильно вынести?

А почему равенство не используешь?
Ты не допускаешь, что у них может быть общая грань? Или одна из вершин внутреннего прямоугольника может лежать на грани внешнего?


Замени отдельные условия на буквы, которые явно визуально повторяются, т.е. формально MT<CB<MB = А, которое принимает два значения True или False и я думаю сразу сможешь увидеть что и как упростить.
Просто работать с операциями меньше/больше не удобно, их проще обозначать через буквы и там уже глядишь и решение приходит более простое ;)

 

Проверять-ли равенство зависит от условий задачи, а именно от того, что определяется словом "входит". Если общая грань считается вхождением, то вместо < или > надо использовать <= или =>. Вот и все. В остальном же сложность проверки зависит исключительно от того параллельны ли прямоугольники. 

Если параллельны, то все предельно просто. Сначала, если надо, поворачиваем систему координат параллельно прямоугольникам. Потом проверяем.
ML<CL
И 
MT<CT
И
CB<MB
И
CR<MR

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

(MT-CT)*(MB-CB)<=0

Akina, выглядит, конечно, красивее, но если уж доводить до абсолюта, то булево выражение должно работать быстрее:

(ML<CL) && (CB<MB)
(ML<CL) && (CR<MR) 
жутко извиняюсь за ошибку в символах  

Это сообщение отредактировал(а) _Y_ - 24.9.2012, 12:24

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

Попробовать решить обратную задачу. Она проще.

(CM < ML) or (CR > MR) or (CT > MT) or (CB < MB) - если это условие верно, то второй прямоугольник не входит в первый.

DarkProg, Допускаю, упустила из виду.
Раставила буквы, вышло:
(A И (C ИЛИ D)) ИЛИ (B И (C ИЛИ D))
Упростила, но не совсем уверена в правоте, так правильно:
(A ИЛИ B) И (C ИЛИ D)
?

Добавлено через 1 минуту и 49 секунд
_Y_, В каком плане параллельны?
Параллельны ли стороны вроде ML / CL? Да параллельны. Ну то есть по оси никак не повёрнуты.

Добавлено через 7 минут и 6 секунд

Не совсем понимаю данную формулу. Она не полна или мне кажется? Так или иначе, я просто подставила туда цифры, и результат не верен. Возможно моя вина, я не совсем верно выразилась, но имеет ввиду, не то, что фигура Б должна быть полностью внутри фигуры А, хватить любое соприкосновение.

Добавлено через 8 минут и 52 секунды

Согласна, но наврятли её так просто запихнуть потом в запрос SQL   

Это полное покрытие по одной координате.

Я так и предполагала.

Оно верно. Сделала по старинке, как в школе, расчертила сетку с строками от 0000 до 1111 для обоих вариантов, результат 100% совпадение. Потом глянула, а что же это будет в начальных вариаблах, и тут вырисовывается легкое читаемое "Если сторона левая либо сторона правая входят в прямоугольник, а так же либо сторона верхняя либо сторона нижняя тоже туда входят" поняв простоту, хлопнула себя по лбу. Простота ведь была рядом, прям на ладони

ИМХО если любые две стороны принадлежащие двум прямоугольникам параллельны друг другу, то прямоугольники параллельны. У Вас, в придачу, прямоугольники еще и параллельны системе координат - даже поворачивать ничего не нужно.

Давайте я Вам картинку нарисую, чтобы понятнее было. Зеленые линии - система координат с нулем в верхнем левом углу.


Вхождение одного прямоугольника в другой описывается четырьмя условиями. Несоблюдение любого из них указывает на то, что внутренний прямоугольник не входит во внешний. Поэтому условия обединяются операторами AND. Сколь помню SQL, такое объединение будет работать довольно быстро, поскольку несоблюдение первого же условия отменит необходимость проверки последующих.

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

В моем посте выше именно все это и было описано, но для проверки только по одной оси т.к. проверка по осям производится одинаково. Но я, к сожалению, перепутал символы, за что и жутко извиняюсь. Надо 
(ML<CL) && (CR<MR) 

Это сообщение отредактировал(а) _Y_ - 24.9.2012, 12:23

А в чём проблема?

Долго коробило, не могла понять, теперь поняла. Так ведь вы этой формулой находите всё что угодно. Как бы объяснить. Ну как минимум сравнение двух координат надо ведь, иначе как-то странно. Опять сама запуталась. Не могу объяснить, но в голове не укладывается, всё почему-то говорит за то, что результат будет неверный. 

Человеческими словами это как будет?

Как я понял из вашего первого сообщения



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



 и EFGH



Условие, по которому левая грань треугольника EFGH выходит за границу ABCD


Аналогично для верхней, правой, нижней, соответственно:



Если, хотя бы, одна грань прямоугольника EFGH выходит за границу прямоугольника ABCD,то EFGH не входит в ABCD. Следовательно, все остальные прямоугольники, не попавшие под это условие выполняют требуемое условие.

В итоге получаем код приведенный мною выше


где C.L аналогично CL, в рассуждениях выше, C.B - CB и так далее. Код получает все прямоугольники, кроме тех, в которых EFGH хотя бы одной гранью выходит за ABCD.

Объясните мне, пожалуйста, чем этот код лучше вот такого?



По мне, так здесь на одну операцию отрицания меньше.

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

просто он использует вышеупомянутую (им же) форму, а потому в данном контексте так понятнее

_Y_, В общем случае ничем. Один из законов логического преобразования. Главное, чтобы, что в том, что в другом случае, соблюдались условия:

Про координаты, я поняла, а вот про алгоритм не совсем, у вас там три раза И а у меня ( ИЛИ ) И ( ИЛИ )
Не могу понять, толи одна из формул не верна, толи вы ищите ПОЛНОЕ вхождение одной фигуры в другую, что не есть верно.

WTF?

Три раза И - вхождение, три раза ИЛИ - невхождение.

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

Да, именно так, я не верно выразилась, вроде бы несколько раз поправлялась, но видимо всё равно не верно   

Так это в принципе другая задача....

Наличие пересечения по одной координате легко определяется значением (вернее, знаком) выражения (ML-CR)*(MR-CL), то же и по другой координате. Чтобы прямоугольники пересекались, должны пересекаться проекции по обеим осям одновременно.

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

animegirl, эту новую задачу тоже можно записать в Булевых выражениях. Но, в этом случае, Булевы условия будут гораздо длиннее того, что предложил Akina. Расписывать?

Можно еще сдалать что-нибудь неожиданно-глупо-оригинальное. Скорее всего, работающее гораздо медленнее, но, зато, прикольнее   Придумывать?

_Y_, Да, очень хочу посмотреть какие ещё есть варианты.

Не поняла, что это и как это   

Что непонятно? где какая координата? или в каком порядке вычитать и умножать?

Если обе разности отрицательны или обе разности положительны, то результат положителен. Если одна отрицательна, другая положительна, то отрицателен. 

Давайте рассмотрим всемварианты по одной из осей. Во всех вариантах, естественно, ML < MR и CL < CR.

• ML-CR > 0 значит внутренний прямоугольник слева от внешнего; MR-CL > 0 будет соблюдаться всегда раз уж он слева.
• MR-CL < 0 значит внутренний прямоугольник справа от внешнего; ML-CR < 0 будет соблюдаться всегда раз уж он справа.
• ML-CR < 0 левая сторона внешнего слева от правой стороны внутреннего; если  MR-CL > 0 значит внутренний внутри внешнего.
• MR-CL < 0 и ML-CR > 0 сочетание в нашем мире невозможное.

Это выражение по одной из осей. Вам нужно рассматривать две (прямоугольник - двухмерная фигура), но принцип тот же. 

Про булев вариант позже распишу. Спать хоца