Как сравнить два ректа?

Различные алгоритмы, связанные с выводом графики.
Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16107
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Как сравнить два ректа?

Сообщение Хакер » 23.02.2011 (Ср) 14:19

iGrok писал(а):Его проекция на ось Y не пересекается с таковой от 3-го. Берётся же не первый, а "самый верхний".

Признаю ошибку: я прочитал «левый верхний» вместо «самый верхний».

Но всё равно это неустойчивый метод.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

iGrok
Артефакт VBStreets
Артефакт VBStreets
 
Сообщения: 4254
Зарегистрирован: 10.05.2007 (Чт) 16:11
Откуда: Сетевое сознание

Re: Как сравнить два ректа?

Сообщение iGrok » 23.02.2011 (Ср) 14:34

Хакер писал(а):Но всё равно это неустойчивый метод.

Да тут, имхо, любой метод будет неустойчивым. Под любой можно найти комбинацию, которая выдаст совершенно неожиданный результат.
label:
cli
jmp label

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16107
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Как сравнить два ректа?

Сообщение Хакер » 23.02.2011 (Ср) 14:43

Я, в общем, предлагаю такой более-менее универсальный метод: ректы принять узлами графа. Смежность узлов графа определяется бинарной функцией смежности: значение функции истинно, если на пути между двумя ректами, соответсвующими проверяемым узлам, не лежит третий рект.

Граф объявляется взвешанным. Вводится несколько критериев (вроде площади «русла» между сторонами ректов, минимальности угла наклона линии между центрами) каждому критерию ставится в соответствие свой весовой коэффициент. Для всех ребёр высчитывается итоговый вес. Далее ищется эйлеров путь по графу при помощи алгоритма Дейкстры.

Да и картинку надо рассемлить.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Debugger
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1657
Зарегистрирован: 17.06.2006 (Сб) 15:11

Re: Как сравнить два ректа?

Сообщение Debugger » 23.02.2011 (Ср) 17:43

Хакер писал(а):Смежность узлов графа определяется бинарной функцией смежности: значение функции истинно, если на пути между двумя ректами, соответсвующими проверяемым узлам, не лежит третий рект.

Отрезок, соединающий центры, не пересекает никакой третий рект?
Отрезки, соединяющие соответствующие вершины прямоугольников, нигде не пересекают другие прямоугольники?
Хакер писал(а):Для всех ребёр высчитывается итоговый вес. Далее ищется эйлеров путь по графу при помощи алгоритма Дейкстры.

Хорошо, мы сделали граф, взвесили его ребра. Нашли эйлеров путь (он?). Дальше что?
Программист - это локальный бог (С) Я

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16107
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Как сравнить два ректа?

Сообщение Хакер » 23.02.2011 (Ср) 17:46

Нумеруем узлы по пути.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

arthur2
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1598
Зарегистрирован: 23.01.2008 (Ср) 14:35

Re: Как сравнить два ректа?

Сообщение arthur2 » 23.02.2011 (Ср) 21:26

iGrok писал(а):Потому что теперь и я не вижу, каким же образом ты при таком алгоритме получил мой ряд. :)
Угу, попутал - пятерка выше восьмерки, и с таким алгоритмом получится не твой, а снова мой ряд :oops:

Сейчас пока так:
Ввожу понятие соседних ректов. Это два таких ректа, проекции которых на ось Х не накладываются, и между которыми нет других ректов. Соседние ректы не обязаны накладываться проекцией на ось У, но зазор не должен быть больше какого-то оговоренного процента. Скажем, у восьмерки соседи справа - 5 и 9, у девятки - 10 и 14.

1. Идем слева направо. Находим все ректы, которые станут началами рядов.
2. Идем от начала каждого ряда вправо, каждый раз выбирая самого верхнего соседа из ещё не посчитаных.
3. После прохода всех рядов останутся какие-то неприкаянные ректы и даже ряды ректов. Смотрим, кому они приходились соседом справа и вставляем неприкаяный ряд в список на нужную позицию.

Хакер писал(а):Я, в общем, предлагаю такой более-менее универсальный метод: ректы принять узлами графа.
Пытаюсь разобраться. Тема графов для меня пока новая :oops:

Что значит "рассемлить"
Артур
 
   

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16107
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Как сравнить два ректа?

Сообщение Хакер » 23.02.2011 (Ср) 23:19

arthur2 писал(а):Что значит "рассемлить"

Рассемплить.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Debugger
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1657
Зарегистрирован: 17.06.2006 (Сб) 15:11

Re: Как сравнить два ректа?

Сообщение Debugger » 23.02.2011 (Ср) 23:32

Хакер писал(а):Нумеруем узлы по пути.

Подозреваю, мы говорим об ориентированном графе. Иначе будут два варианта пути (вперед и назад).
Значит, должны происходить ситуации, когда из прямоугольника A к прямоугольнику B перейти можно, а наоборот - нельзя. Или же можно, но весы этих ребер будут разными. Что-то мне тяжело представить такую ситуацию. Покажешь?
Программист - это локальный бог (С) Я

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16107
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Как сравнить два ректа?

Сообщение Хакер » 23.02.2011 (Ср) 23:34

Debugger писал(а):Подозреваю, мы говорим об ориентированном графе. Иначе будут два варианта пути (вперед и назад).

О неориентированном. Пути два будут совпадающих.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

arthur2
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1598
Зарегистрирован: 23.01.2008 (Ср) 14:35

Re: Как сравнить два ректа?

Сообщение arthur2 » 24.02.2011 (Чт) 5:54

Хакер писал(а):Рассемплить.
Что значит "рассемплить"? Если - прочитать ректы с картинки - то ректы прочитаны. Имеем массив структур RECT.
Артур
 
   

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16107
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Как сравнить два ректа?

Сообщение Хакер » 24.02.2011 (Чт) 12:10

arthur2 писал(а):Что значит "рассемплить"?

ein_artur_samling.png
ein_artur_samling.png (40.56 Кб) Просмотров: 3914


Только делать это нужно, разумеется, не в действительности, а математически, чтобы вычисление метрики исказить.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

arthur2
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1598
Зарегистрирован: 23.01.2008 (Ср) 14:35

Re: Как сравнить два ректа?

Сообщение arthur2 » 25.02.2011 (Пт) 7:40

Зачем? Не понял идеи :oops: Типа, делаем бесконечное поле, чтобы правый край снова переходил в левый?
Артур
 
   

Debugger
Продвинутый гуру
Продвинутый гуру
Аватара пользователя
 
Сообщения: 1657
Зарегистрирован: 17.06.2006 (Сб) 15:11

Re: Как сравнить два ректа?

Сообщение Debugger » 26.02.2011 (Сб) 23:38

Мой способ (и вправду) работает нормально только на очень ограниченном числе случаев.
Предлагаю реализовать способ Хакера, из спортивного интереса.
Какие прямоугольники считаются связанными? Для которых прямая, соединяющая центры, не пересекает другие прямоугольники?
Предположим, мы нашли Эйлеров путь: A-B-C-D. Что делать дальше? Где гарантии, что на самом деле мы не нашли путь "наоборот", и прямоугольнику/узлу A на самом деле нужно присваивать номер 4, а B - 3 (и так далее)?
P.S. Можно придумать хитрую функцию, которая из двух прямоугольников выбирает тот, который должен стоять первым. Но это уже костыль, вылезающий за концепцию графа, разве нет?
Программист - это локальный бог (С) Я

Пред.

Вернуться в Графика

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

    TopList  
cron