В прошлом топике возникло много вопросов, поэтому я задаю новый, более конкретный. Есть двумерное пространство, оно состоит из прямоугольников. Эти прямоугольники нужно нарисовать в правильном порядке. То есть перед каждым объектом должны рисоваться объекты которые слева и сверху от него, и после него те, которые справа и снизу. Если бы задача была с квадратами, то сортировка была бы по критерию X1+Y1+W1/2>X2+Y2+W2/2 (x,y — координаты, w — ширина). Но как отсортировать произвольные прямоугольные объекты?

Здравствуйте, Launcher, Вы писали:

L>...Эти прямоугольники нужно нарисовать в правильном порядке...

Для того, чтобы тебе можно было что-то ответить, тебе нужно объяснить что означает ПРАВИЛЬНЫЙ порядок. Как именно ты хочешь рисовать прямоугольники? Или ты хочешь, чтобы мы попытались угадать правильный порядок?

Launcher wrote:
>
> В прошлом топике возникло много вопросов, поэтому я задаю новый, более
> конкретный. Есть двумерное пространство, оно состоит из прямоугольников.
> Эти прямоугольники нужно нарисовать в правильном порядке. То есть перед
> каждым объектом должны рисоваться объекты которые слева и сверху от
> него, и после него те, которые справа и снизу. Если бы задача была с
> квадратами, то сортировка была бы по критерию X1+Y1+W1/2>X2+Y2+W2/2 (x,y
> — координаты, w — ширина). Но как отсортировать произвольные
> прямоугольные объекты?
Ну в частности ты можешь применить сортировку по левому верхнему углу,
по центру, по нижнему правому углу, как критерии сортировки, на выбор, в
данной ситуации все эти критерии равнозначны. А правило ты записал выше
меньше <=> если слева "или"("и") сверху (как тебя по логике будет).

Здравствуйте, Launcher, Вы писали:

u<v <=> левый_верхний_угол(u)<левый_верхний_угол(v) — частичный порядок. Далее топологическая сортировка.

Я ж вроде понятно написал:
То есть перед каждым объектом должны рисоваться объекты которые слева и сверху от него, и после него те, которые справа и снизу

нет, ты неправ. Представь прямоугольник. Из него выходит зона x>Xобъекта, y>Yобъекта (условие для следующих объектов), еще зона — x<Xо+Wo, y<Yo+Ho (условие для предыдущих объектов. Но есть еще две зоны... Они означают "А фиг знает". Нарисую два интересных случая (числа — порядок объектов после сортировки, 0 — пустота):

0 2 3
0 2 0
1 2 0

и второй:

0 0 1
2 2 2
3 0 0

Launcher wrote:
>
> нет, ты неправ. Представь прямоугольник. Из него выходит зона
> x>Xобъекта, y>Yобъекта (условие для следующих объектов), еще зона —
Я тебе дал одно из решений в случае вышеназванной формулировки.
Формулируй тогда точнее.

Vzhyk wrote:
>
>> нет, ты неправ. Представь прямоугольник. Из него выходит зона
>> x>Xобъекта, y>Yобъекта (условие для следующих объектов), еще зона —
> Я тебе дал одно из решений в случае вышеназванной формулировки.
> Формулируй тогда точнее.
А квадрат — это всего-лишь частный случай прямоугольника.

Здравствуйте, Launcher, Вы писали:

L>Я ж вроде понятно написал:
L>То есть перед каждым объектом должны рисоваться объекты которые слева и сверху от него, и после него те, которые справа и снизу

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

Хорошо. Попробуй своим методом отсортировать два примера:
А(0, 2, 1, 1), B(2, 0, 1, 1), C(1, 0, 1, 2);
А(0, 2, 1, 1), B(2, 0, 1, 1), C(0, 1, 2, 1);
Два практически одинаковых примера, но вот порядок разный...

Знаешь как обычно паркет выкладывают елочкой? ВОт так и мне надо выкладывать из угла... только весь паркет разный...

Здравствуйте, Launcher, Вы писали:

L>Знаешь как обычно паркет выкладывают елочкой? ВОт так и мне надо выкладывать из угла... только весь паркет разный...

Замечательно — мы получили новое условие задачи! Если я правильно понял, то прямоугольники НЕ ПЕРЕСЕКАЮТСЯ! Тогда я не вижу проблем, почему бы не отсортировать прямоугольники по левому верхнему краю. Хотя в другом посте ты писал, что тебе это не подходит, но я так и не понял — почему?

Launcher wrote:
>
> Хорошо. Попробуй своим методом отсортировать два примера:
> А(0, 2, 1, 1), B(2, 0, 1, 1), C(1, 0, 1, 2);
> А(0, 2, 1, 1), B(2, 0, 1, 1), C(0, 1, 2, 1);
> Два практически одинаковых примера, но вот порядок разный...
Так вот сформулирую свою задачу четко. Надоело уже угадывать, что же ты
хочешь.
Вариантов, как делать сортировку тебе тут уже написали с добрую дюжину.

Ок, два примера (Х, У, ширина, высота):
A(0, 2, 1, 1), B(2, 0, 1, 1), C(1, 0, 1, 2);
A(2, 0, 1, 1), B(0, 2, 1, 1), C(0, 1, 2, 1);
Во-первых, A и B будут по твоему методу будут однозначны. Во-вторых, пока не появится C, мы не узнаем их порядка.

Я же писал: x>Xобъекта, y>Yобъекта (условие для следующих объектов), x<Xо+Wo, y<Yo+Ho (условие для предыдущих объектов).