решение системы неравенств

← →
vidiv © (2006-08-08 07:59) [0]

Есть система неравенств:
(AAx + ABy + AC)(AAx + ABy + AD) <= 0 (BAx + BBy + BC)(BAx + BBy + BD) <= 0 (CAx + CBy + CC)(CAx + CBy + CD) <= 0 (DAx + DBy + DC)(DAx + DBy + DD) <= 0
Где AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD -известные коэффиценты.
Нужно выяснить существуют ли какая либо пара чисел (x, y)удовлетворяющая данной системе. (саму пару находить не нужно, главное определить существует ли).

Какие есть предложения

← →
MBo © (2006-08-08 08:17) [1]

Геометрически -
AA*x + AB*y + AC = 0 есть уравнение прямой
AA*x + AB*y + AC <0 или >=0 описывает полуплоскость
произведение (AAx + ABy + AC)(AAx + ABy + AD) <= 0 имеет такое множество решений - если прямые пересекаются - две внутренности противолежащих углов, а если параллельны - может быть полоса, полуплоскость, или плоскость с вырезанной полосой.
Если пересечение областей решений всех неравенств непусто - решения есть

← →
vidiv © (2006-08-08 08:34) [2]

(AAx + ABy + AC)(AAx + ABy + AD) <= 0
в данном случае (коффиценты при x и y равны) прямые параллельны. и данное неравенство описывает полосу на плоскости (потому что <= 0).

Причем я не уточнил, у коффициентов есть такое свойсво (некоторые из них равны, я их переобозначил:):
(Ax + By + C1)(Ax + By + C2) <= 0 (Bx - Ay + C3)(Bx - Ay + C4) <= 0
остальные два неравенства аналогины:
(Mx + Ny + C5)(Mx + Ny + C6) <= 0 (Nx - My + C7)(Nx - My + C8) <= 0

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

П.С. Задачу нужно решить достаточно оптимально, чтобы можно было решить порядка 32 млн. таких систем за время около 1 сек.

← →
vidiv © (2006-08-08 08:54) [3]

Точнее не найти пересечение, а определить, пусто оно или нет )

← →
MBo © (2006-08-08 09:15) [4]

>(коффиценты при x и y равны)
ага, я не обратил внимания.

(Ax + By + C1) и (Bx - Ay + C3) - перпендикулярны, так что про прямоугольные области - верно.

>Как тогда геометрически найти пересечение прямоугольных областей?
Если пересечения будут редкими, тогда сначала проверить пересечение axis-aligned ограничивающих пр-ков
Затем использовать известные в CG (computer geometry) алгоритмы отсечения прямоугольным окном
(возможно, для простоты проведя аффинное преобразование, переводящее один из прямоугольников в axis-aligned (пр-к, стороны которого параллельны осям координат), и один угол в начале координат)

← →
StriderMan © (2006-08-08 09:18) [5]

загони все в МАТЛАБ . он разрюхает

← →
Думкин © (2006-08-08 09:54) [6]

> vidiv © (08.08.06 08:34) [2]
> (AAx + ABy + AC)(AAx + ABy + AD) <= 0
> в данном случае (коффиценты при x и y равны) прямые параллельны.
> и данное неравенство описывает полосу на плоскости (потому
> что <= 0).

То есть имеются в виду внутренние, ограниченные области или также и внешние?
Потому что иначе - любая точка не лежащая в 4-х полосах - удовлетворяет неравенствам. А такие - есть, иначе бы эти 4 полосы покрывали всю плоскость.

← →
Думкин © (2006-08-08 09:55) [7]

Упс - поспешил. Все-таки только внутренние. :(

← →
Думкин © (2006-08-08 10:03) [8]

Прямоугольники выпуклые фигуры. Значит если у них есть общие точки, то вершина одного из них лежит внутри или на границе другого и соответственно можно:
1. Провести афиинное перводящее один из в квадрат с диагональю (0,0)-(1,1) и с параллельными осям сторонами. И проверить координаты вершин напарника.
2. Поработать со взвешенными(? - так кажется) координатами, все точки со значениями координат в пределах(0-1) принадлежат соответствующему прямоугольнику. Посмотреть координаты вершин напарника.

← →
StriderMan © (2006-08-08 10:08) [9]

> Думкин © (08.08.06 10:03) [8]

эх зря я на Линейке пиво пил...

← →
Думкин © (2006-08-08 10:14) [10]

2 - фактически то же что и 1.

← →
Думкин © (2006-08-08 10:19) [11]

Или просто проверить вершины одного на верность неравенств второго. Самое затратное - нахождение вершин.

> 1. Провести афиинное перводящее один из в квадрат с диагональю
> (0,0)-(1,1) и с параллельными осям сторонами. И проверить
> координаты вершин напарника.

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

> Значит если у них есть общие точки, то вершина одного из
> них лежит внутри или на границе другого

Если исключения. например если написать знак "+" шрифтом Times размером например 144, то этот символ будет "похож" на два прямоугольника, которые имеют общие точки, и при этом не содержат друг в друге никаких вершин.

> [8] Думкин © (08.08.06 10:03)
> Значит если у них есть общие точки, то вершина одного из
> них лежит внутри или на границе другого

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

Если коэффициенты на экзамене даны в виде чисел, то очень может быть, что все требуют свести к четырем неравенствам типа (Ax + By)^2 + C <= 0. Или как-нибудь по-другому упростить.

> vidiv © (08.08.06 17:44) [12]

Да, такой вариант у меня высыпался из головы. Бывает. Но тогда через аффинку и к звездам, но уже сложнее. Можно МВо покурить.

> evvcom © (08.08.06 17:58) [13]

Вы опоздали. Мне уже доложили. :)

> vidiv © (08.08.06 17:44) [12]

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

Стороны выражаются параметрически с параметрами от 0 до 1. Надо будет решить несколько систем линейных уравнений порядка 2, и если хотя бы в одном решении пара попадет в диапазон от 0 до 1, то стороны пересекаются. Так как вершины не внутри взаимно, то у одного прямоугольника достаточно рассмотреть 2 стороны, у другого максимум 3.

Вроде ничего крайнего не упустил?

решение системы неравенств Найти похожие ветки