Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

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

Страницы: 1 2 >
Styx_ © (2005-12-13 23:21:00)
Добрый день!

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

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

Спасибо!

Styx_ (2005-12-14 19:59:00) [1]

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

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

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

Digitman (2005-12-14 14:19:00) [2]

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

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

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

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

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

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

Digitman (2005-12-14 13:59:00) [4]

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

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

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

Digitman (2005-12-14 13:52:00) [5]

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

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

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

^
|
|

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

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

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

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

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

Styx_ (2005-12-14 13:44:00) [7]
2 Romkinспасибо, направление действий понял :)

Digitman (2005-12-14 13:44:00) [8]

> Styx_ (14.12.05 13:42) [27]

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

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

Styx_ (2005-12-14 13:42:00) [9]

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

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

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

Digitman (2005-12-14 13:38:00) [11]

> Styx_ (14.12.05 13:35) [23]

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

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

Styx_ (2005-12-14 13:38:00) [12]

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

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

Styx_ (2005-12-14 13:35:00) [13]

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

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

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

Digitman (2005-12-14 13:27:00) [15]
проблема надумана и сводится к определению "кто первый".

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

Styx_ (2005-12-14 13:23:00) [16]

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

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

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

Styx_ (2005-12-14 13:20:00) [17]

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

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

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

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

Leonid Troyanovsky (2005-12-14 13:19:00) [18]

> Styx_ (14.12.05 13:10) [14]

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

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

--
Regards, LVT.

Digitman (2005-12-14 13:18:00) [19]

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

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

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

с учетом

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

тогда уж TObjectList ...

> Styx_ (14.12.05 13:01) [13]

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

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

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

Страницы: 1 2 >

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »