Алгоритм сортировки

← →
Styx_ (2005-12-13 23:21) [0]

Добрый день!

Необходимо отсортировать массив объектов с использованием функции сравнения элементов f(a,b), которая может возвращать значения "больше" (1), "меньше" (-1) и "объекты несравнимы" (0), причём в принципе возможна ситуация, когда
a < b < c < a
Что-то я не могу сообразить, как бы это всё отсортировать, а в случае возникновения указанной неразрешимости - не впасть в бесконечный цикл, а попытаться выдать результат с наименьшим числом несоответствий.

Нужно всё это, собственно, для сортировки графических примитивов в "алгоритме художника".

Спасибо!

← →
PAVIA © (2005-12-13 23:39) [1]

Просто сортируешь обыкновенным методом. Алгоритм художника как раз и не дает правельного результат на том случае. Если такой случай имеет место, то для нахождения наименьшего числа несоответствий нужен полный перебором всех вариантов. Что бывает не приемлимым из-за большого числа объектов.

← →
Styx_ (2005-12-14 00:50) [2]

А каким "обыкновенным"? Все известные мне алгоритмы подразумевают, что 0 - это равенство, и из
f(a,b) = -1 и f(b,c) = 0 следует, что f(a,c)=-1
Что в данном случае не так, и действительно нужно вычислить f() для всех пар... Или я чего-то не понимаю?

← →
Думкин © (2005-12-14 06:49) [3]

> Styx_ (13.12.05 23:21)

А как должен будет выглядеть результат, например в приведенном вами случае? На данный момент - постановка задачи некорректна.

← →
TUser © (2005-12-14 09:12) [4]

А что значит несравнимые объекты. Должно быть определено отношение порядка (а значит они всегда сравнимы), иначе ничего отсортировать нельзя.

← →
TUser © (2005-12-14 09:14) [5]

Я что-то подобное делал. Объекты могли быть нормально сортируемыми, а могли образовывать цикл. Все сделал обычным пузырьком.

← →
Styx_ (2005-12-14 12:15) [6]

> А что значит несравнимые объекты

Значение функции f(a,b) трактуется следующим образом:
-1: a в проекции перекрывает b
1: b в проекции перекрывает a
0: проекции объектов не пересекаются

Причем случай с циклом пока не принципиален, потому как в трёхмерной модели, которую мне нужно отрисовать, таких циклов не будет.

А пузырьком и я сделал... Но вылезают ошибки сортировки :(

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

← →
Digitman © (2005-12-14 12:20) [7]

> перекрывает

т.е. частичное перекрытие невозможно по условию .. так ?

← →
Styx_ (2005-12-14 12:30) [8]

> т.е. частичное перекрытие невозможно по условию .. так ?

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

← →
Styx_ (2005-12-14 12:43) [9]

А, я понял, что неправильно применил термин "перекрывает". Вот более точное описание:

0: проекции объектов не пересекаются
-1: проекции объектов пересекаются, a ближе к наблюдателю
1: проекции объектов пересекаются, b ближе к наблюдателю

← →
Digitman © (2005-12-14 12:52) [10]

> a ближе к наблюдателю

> b ближе к наблюдателю

дай определение "ближе-дальше" для случая именно пересекающихся проекций

← →
Leonid Troyanovsky © (2005-12-14 12:57) [11]

> Styx_ (13.12.05 23:21)

> функции сравнения элементов f(a,b), которая может возвращать
> значения "больше" (1), "меньше" (-1) и "объекты несравнимы"
> (0), причём в принципе возможна ситуация, когда
> a < b < c < a

> Styx_ (14.12.05 12:43) [9]
> 0: проекции объектов не пересекаются
> -1: проекции объектов пересекаются, a ближе к наблюдателю

Т.е., "a" ближе к наблюдателю, чем "a"?
Чего-то не так с физической моделью.

А, вообще-то, у TList есть метод Sort, который сортирует элементы
по произвольному критерию. Задай оную функцию и сортируй.

--
Regards, LVT.

← →
TUser © (2005-12-14 13:00) [12]

Задача решаема.

> Но вылезают ошибки сортировки :(

Приведи свою реализацию пузырька.

← →
Styx_ (2005-12-14 13:01) [13]

> дай определение "ближе-дальше" для случая именно пересекающихся
> проекций

Определение вполне бытовое :)
С точки зрения отрисовки по "алгоритму художника" - объекты, расположенные дальше, должны отрисовываться раньше; порядок отрисовки объектов с непересекающимися проекциями непринципиален.

← →
Styx_ (2005-12-14 13:10) [14]

Делается всё это не на Delphi, а на Action Script во Flash... Уж простите, что залез с этим сюда, но здесь люди явно более подкованные, чем на Flash-форумах :) Соответственно использовался метод sort() объекта Array, который точно так же позволяет задавать произвольную функцию сравнения. Насколько я понимаю (судя по трассировке вызовов моей функции), он работает именно пузырьком.

Собственно, в чем суть:
есть исходный массив
a,b,c,d
f(a,b)=-1
f(b,c)=0
f(c,d)=-1
С точки зрения "пузырька" он отсортирован, но фактически может быть, что
f(a,c)=1

> Чего-то не так с физической моделью

Не понимаю.
-1 -> a ближе, чем b,
1 -> b ближе, чем a

← →
Leonid Troyanovsky © (2005-12-14 13:13) [15]

> Styx_ (14.12.05 13:01) [13]

> расположенные дальше, должны отрисовываться раньше; порядок
> отрисовки объектов с непересекающимися проекциями непринципиален.

Вот именно такой интерпретации и следует придерживаться, т.е.
f(a, b) = -1 ~ b ближе a
f(a, b) = 0 ~ a, b равноудалены
f(a, b) = 1 ~ a ближе b.

И никакого "зацикливания" не будет.

Ну, а TList сортирует путем QuickSort, т.е. лучше пузырька.

--
Regards, LVT.

← →
Romkin © (2005-12-14 13:14) [16]

Вообще-то это больше похоже на топологическую сортировку графа :))
Пусть имеется ориентированный граф (стрелка от "меньшего" к "большему" идет, например) без циклов
Надо указать такой линейный порядок вершин, что любое ребро ведет от меньшей вершины к большей в смысле этого порядка.
То есть расположить вершины горизонтально, чтобы все ребра шли слева направо.
Тебе это требуется? Тогда это делается через поиск в глубину...

← →
Digitman © (2005-12-14 13:18) [17]

> TUser © (14.12.05 13:00) [12]
> Приведи свою реализацию пузырька

"пузырёк" он и в Африке "пузырёк".
точно так же как любой иной алгоритм сортировки.

> Leonid Troyanovsky © (14.12.05 12:57) [11]

с учетом

> массив объектов

тогда уж TObjectList ...

> Styx_ (14.12.05 13:01) [13]

понятно что лошадь)

но при пересечении проекций определение "ближе-дальше" попросту теряет смысл ...

← →
Leonid Troyanovsky © (2005-12-14 13:19) [18]

> Styx_ (14.12.05 13:10) [14]

> > Чего-то не так с физической моделью
>
> Не понимаю.
> -1 -> a ближе, чем b,
> 1 -> b ближе, чем a

a<b<c<a => a ближе a.
Т.е., такое, при правильной интерпретации, невозможно.

--
Regards, LVT.

← →
Styx_ (2005-12-14 13:20) [19]

> f(a, b) = 0 ~ a, b равноудалены

Это не так. Объект имеет протяжённость в пространстве, поэтому нельзя говорить об удалённости объекта в целом, а лишь о том, какой из двух перекрывающихся на проекции объектов загораживает другой.

> Вообще-то это больше похоже на топологическую сортировку
> графа
> Тебе это требуется?

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

← →
Styx_ (2005-12-14 13:23) [20]

> a<b<c<a => a ближе a.
> Т.е., такое, при правильной интерпретации, невозможно

Возможно - первый рисунок на http://www.helloworld.ru/texts/comp/games/3d/faq/articles/32.htm

Другой вопрос, что в данной частной интерпретации я точно знаю, что таких циклов нет.

← →
Digitman © (2005-12-14 13:27) [21]

проблема надумана и сводится к определению "кто первый".

задумайся над тем, как в соревнованиях, например, по спринту определяется победитель спринтерского забега ..

← →
Romkin © (2005-12-14 13:32) [22]

Styx_ (14.12.05 13:20) [19] Ну в твоем случае просто: объекты - это вершины, если два объекта перекрываются, то вершины соединены стрелкой (направленным ребром), от более дальнего объекта к более близкому (вроде у тебя так)
Далее, ищешь алгоритмы по ключевым словам topological sort (топологическая сортировка) и depth-first search (поиск в глубину, DFS), смотришь, какое представление графа идет на вход, представляешь свое имущество так же и все ;)
Только учти, циклов быть не должно. Намекаю: a < b < c < a - это цикл ;)
Убрать циклы, скорее всего, можно найдя минимальное покрывающее дерево (с одинаковым весом ребер). Думаю, это задачу не изменит

← →
Styx_ (2005-12-14 13:35) [23]

> проблема надумана и сводится к определению "кто первый".

Проблема-то, может, и надумана, а программа не работает :(

← →
Styx_ (2005-12-14 13:38) [24]

> объекты - это вершины

Э... видимо, не совсем так, но, кажется, начинаю понимать :) Спасибо!
А циклов нет - в смысле нет в той сцене, которую нужно отрисовать.

> Styx_ (14.12.05 13:35) [23]

> Проблема-то, может, и надумана, а программа не работает

и не5 будет работать. пока не дашь самому себе четкое определение, какой объект считается "поперед" другого объекта, каковы критерии оценки сего факта

Digitman © (14.12.05 13:27) [21] И ничего не надумано. Иногда встречается такое. Другое дело, что решений, как правило, много, и находят одно из них.
Styx_ (14.12.05 13:35) [23] Граф построй. Время работы такой сортировки вообще пропорционально O(V+E), V - кол-во вершин, E - кол-во ребер.

← →
Styx_ (2005-12-14 13:42) [27]

> какой объект считается "поперед"

Критерий прост - берётся любая точка из области пересечения проекций и сравниваются её z-координаты у двух объектов

> Styx_ (14.12.05 13:42) [27]

> берётся любая точка из области пересечения проекций и сравниваются
> её z-координаты у двух объектов

ну вот и реализуй это в своей ф-ции f(a,b) .. и проблема сама собой рассосется) ..

← →
Styx_ (2005-12-14 13:44) [29]

2 Romkin спасибо, направление действий понял :)

← →
Styx_ (2005-12-14 13:46) [30]

Digitman © (14.12.05 13:44) [28]
Так и сделано. Проблема в том, что нельзя ничего сказать о порядке объектов, для которых проекции не пересекаются - а большинство алгоритмов сортировки требует, чтобы можно было сравнить любую пару объектов.

> Romkin © (14.12.05 13:40) [26]

рисую в псевдографике "сцену" (вид сверху) :

\
\
\
\ /
\ /
\ /
/ \
/ \
/

^
|
|

символами "слеша" обозначена проекция некоего объекта A на некую плоскость

символами "бэкслеша" обозначена проекция некоего объекта В на ту же плоскость

символом ^ обозначено направление вектора взгляда наблюдателя

вопрос на засыпку: какой из объектов (A или B) ближе к наблюдателю ? и почему

> нельзя ничего сказать о порядке объектов, для которых проекции
> не пересекаются

imho, строго наоборот : если проекции пересекаются, то примитивный критерий оценки удаленности объектов по сравнению координат их вершин терпит полное фиаско.

мне же не понятно другое : в чем прелесть изобретения велосипеда, если на сей день есть огромная куча "мягких" и "жестких" реализаций удаления невидимых поверхностей ? как "он-борд"-средствами 3d-акселераторов, так и средствами программной эмуляции ф-ций оных в составе разного рода 3D-библиотек ?

Digitman © (14.12.05 13:59) [32]
мне же не понятно другое : в чем прелесть изобретения велосипеда, если на сей день есть огромная куча "мягких" и "жестких" реализаций удаления невидимых поверхностей ? как "он-борд"-средствами 3d-акселераторов, так и средствами программной эмуляции ф-ций оных в составе разного рода 3D-библиотек ?

А вот это уже совершенно другой вопрос должен был быть :)))
Если бы спросили что-то вроде "Как мне отрисовывать, чтобы объекты не пересекались" то и ответы были бы другими...

> Romkin © (14.12.05 14:04) [33]

> Если бы спросили что-то вроде

этот непрозвучавший вопрос понятен и без звука.

спрашивается, начерта сортировать объекты по некоему критерию "удаленности" от наблюдателя сцены, если о последующем рендеринге этой сцены речи не идет ?

← →
Styx_ (2005-12-14 19:59) [35]

> в чем прелесть изобретения велосипеда

Прелесть в отсутствии поддержки DirectX/OpenGL (и т.п.) указанной платформой (Macromedia/Adobe Flash) и таком же отсутствии каких-либо разумных 3D библиотек под неё (что неудивительно ввиду успользования интерпретируемого скриптового языка). А простенькую трёхмерную сцену отрисовать ну очень надо :)

В общем, всем спасибо!!! :)

Алгоритм сортировки Найти похожие ветки