LINUX.ORG.RU

Нечёткая сортировка

 ,


1

1

Есть многоугольники на плоскости. Нужно отрисовать это как сцену в изометрии - вытянуть многоугольники в высоту получив призмы. При этом нужно рисовать их в правильной последовательности, чтобы ближние закрывали дальние. OpenGL и z-buffer использовать нельзя. Разбивать призмы нельзя, т.е. выводить каждую только целиком. Порядок призм по условию задачи определяется довольно хитрым образом: о двух призмах мы можем сказать: либо А ближе Б, либо Б ближе А, либо порядок не важен. Причём эта операция не коммутативна: А может считать себя ближе Б, но Б может считать что пересекается с А. Понятно, что в этих условиях некоторые случаи невозможно нарисовать корректно (например, пересекающиеся призмы, или призму в выемке другой, невыпуклой), а некоторые можно нарисовать разными способами (из-за хитрого сравнения) - это нормально.

Собственно вопрос - чем это сортировать. Понятно что стандартный std::sort даст скорее всего непредсказуемые результаты, да и работает он с бинарным предикатом, а нужен тернарный. Кроме этого, сортировка нужна стабильная и эффективно сортирующая (почти) отсортированную последовательность, ибо есть идея при изменении сцены/позиции наблюдателя использовать сортировку с предыдущего кадра которая почти всегда будет подходить в неизменном виде.

Можно было бы использовать самые банальные алгоритмы начиная с пузырька, учитывая что для отсортированной последовательности он даст O(n), но меня беспокоит нестабильность на штуках типа А < Б, Б < В, В < А которые по условию тоже возможны.

★★★★★

сортировка слиянием. Она стабильная и простая (на списках).

emulek
()

Нифига не понятно. Нормально формализуй условие для сортировки. Что такое «А ближе Б» и «порядок не важен»?

anonymous
()
Ответ на: комментарий от anonymous

Нормально формализуй условие для сортировки.

у него в том и фича, что условие нечёткое. Т.е. можно вычислить A<B и B<C, но из истинности этого НЕ следует A<C.

И ТС хочет «абы как» сделать.

emulek
()

ТС хуйню какую-то понаписал. Если рисовать можно только призму целиком, то рисуй от наиболее удаленной от наблюдателя до самой близкой. Но так никто не делает. Ну и ясен пень, всю муру, которую ты написал, выбрось из головы

anonymous
()

Нечёткая сортировка

Пацаны не поймут.

Можно было бы использовать самые банальные алгоритмы начиная с пузырька, учитывая что для отсортированной последовательности он даст O(n), но меня беспокоит нестабильность на штуках типа А < Б, Б < В, В < А которые по условию тоже возможны.

Напиши чоткую функцию, которая железно скажет A < B или нет (если «порядок не важен» придумай дополнительный критерий, вплоть до адреса указателя в памяти), возьми qsort и спокойно иди пить пивасик и жрат семки.

anonymous
()
Ответ на: комментарий от anonymous

Не могу представить такое расположение объектов в пространстве, чтобы А>С.

большая призма А может одним концом быть ближе к нам, чем маленькая Б, а другим концом дальше.

По уму конечно необходимо большую призму разрезать на две части, что-бы не было неоднозначности. Но ТСа устраивает, что будет такой глюк.

emulek
()
Ответ на: комментарий от anonymous

Расстояние до призмы возьми как расстояние до самой близкой её точки, естественно

маленькая призма может заслонять большую, даже если самая близкая точка большой ближе к нам, чем самая близкая точка маленькой.

emulek
()

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

AIv ★★★★★
()
Ответ на: комментарий от anonymous

Расстояние до призмы возьми как расстояние до самой близкой её точки, естественно

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

Естественно, нет. Вот такой случай будет обработан неправильно:

  BBBBBBBBBBBBBB
   BBBBBBBBBBBB
    BBBBBBBBBB
   A BBBBBBBB
      BBBBBB
       BBBB
        BB

        ^^
   (наблюдатель)
slovazap ★★★★★
() автор топика
Последнее исправление: slovazap (всего исправлений: 1)
Ответ на: комментарий от anonymous

Напиши чоткую функцию, которая железно скажет A < B или нет (если «порядок не важен» придумай дополнительный критерий, вплоть до адреса указателя в памяти), возьми qsort и спокойно иди пить пивасик и жрат семки.

Да, до этого я между делом додумался. Предикат можно сделать бинарным, но остаётся проблема A<B B<C C<A

slovazap ★★★★★
() автор топика
Ответ на: комментарий от CunMun

Я конечно утверждать не могу. Но предполагаю что вас подталкивают в сторону Topological_sorting.

Выглядит релевантно, копну в эту сторону. Однако пока всё алгоритмы что я нашёл предполагают ацикличность графа.

slovazap ★★★★★
() автор топика
Ответ на: комментарий от slovazap

Да, кстати - получается что вариант «порядок не важен» как раз уменьшает количество циклов. Но устранить их совсем скорее всего нельзя.

slovazap ★★★★★
() автор топика
Ответ на: комментарий от slovazap

Эта проблема существует в 3D. У тебя по сути двумерный случай, поскольку все треугольники вытягиваются в призмы вертикально параллельно друг другу.

kvap
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.