Конференция VBStreets

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

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

Но всё равно это неустойчивый метод.

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

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

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

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

Да и картинку надо рассемлить.

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

Отрезок, соединающий центры, не пересекает никакой третий рект?
Отрезки, соединяющие соответствующие вершины прямоугольников, нигде не пересекают другие прямоугольники?

Хакер писал(а):Для всех ребёр высчитывается итоговый вес. Далее ищется эйлеров путь по графу при помощи алгоритма Дейкстры.

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

Нумеруем узлы по пути.

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

Угу, попутал - пятерка выше восьмерки, и с таким алгоритмом получится не твой, а снова мой ряд

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

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

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

Пытаюсь разобраться. Тема графов для меня пока новая

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

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

Рассемплить.

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

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

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

О неориентированном. Пути два будут совпадающих.

Хакер писал(а):Рассемплить.

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

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

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

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

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