forum.boolean.name - Сортировка координат

forum.boolean.name (http://forum.boolean.name/index.php)

- Алгоритмика (http://forum.boolean.name/forumdisplay.php?f=21)

- - Сортировка координат (http://forum.boolean.name/showthread.php?t=8505)

Mr_F_

18.06.2009 23:10

Сортировка координат

туплю...как можно просортировать объекты типа, имеющие x, y и z?

типа есть:

60 73 29
-50 20 48
-100 82 4
-100 29 4
-100 29 6

а надо:

-100 29 4
-100 29 6
-100 82 4
-50 20 48
60 73 29

jimon

18.06.2009 23:31

Ответ: Сортировка координат

что-то я не понимаю каким образом ты хочешь сортировать
если по растоянию то сортируй по ключу D = x*x+y*y+z*z

impersonalis

18.06.2009 23:53

Ответ: Сортировка координат

Код:

60   73   29   

-50  20   48   

-100 82   4    

-100 29   4    

-100 29   6    



-100 29   4    

-100 29   6    

-100 82   4    

-50  20   48   

60   73   29

Вариант номер один:

Код:

Data 60, 73, 29

Data -50, 20, 48

Data -100, 82, 4

Data -100, 29, 4

Data -100, 29, 6



Global XS%=3

Global YS%=5

Dim p(XS,YS)



Function debug_matrix()

        Local s$

        For y=1 To YS

                s=""

                For x=1 To XS

                        s=s+LSet(p(x,y),5)

                Next

                DebugLog s

        Next

End Function



Function PrevColCor%(z%,i%)

        If z=1 Return True

        If p(z-1,i)=p(z-1,i+1)

                Return True

        EndIf

        Return False

End Function



For y=1 To YS

        For x=1 To XS

                Read p(x,y)

        Next

Next



debug_matrix()

DebugLog ""

;====================

For z=1 To XS

        For j=2 To YS

                For i=1 To YS-j+1

                        If p(z,i)>p(z,i+1) And PrevColCor(z,i)

                                For r=z To XS

                                        Local t%=p(r,i)

                                        p(r,i)=p(r,i+1)

                                        p(r,1+i)=t

                                Next

                        EndIf

                Next

        Next

Next

;====================

debug_matrix()

DebugLog ""

WaitKey()

End

impersonalis

19.06.2009 00:01

Ответ: Сортировка координат

Второй способ с ключом (как сказал Джимон), но ключ составляется по-другому:
D=(x-min)*(R^2)+(x-min)*(R^1)+(x-min)*(R^0)
аналогично, например RGB-системе, где
min - миниальное возможное значение координаты (для rgb =0)
R - разброс значений (для rgb =256)

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

Вообще говоря, ТЗ весьма размыто.

impersonalis

19.06.2009 00:05

Ответ: Сортировка координат

функцию

Код:

Function PrevColCor%(z%,i%)

        If z=1 Return True

        If p(z-1,i)=p(z-1,i+1)

                Return True

        EndIf

        Return False

End Function

в первом методе можно выродить до проверки тождества
p(z-1,i)=p(z-1,i+1)
если матрица слева имеет буферный столбец забитый одинаковыми значениями (в том же б3д можно было сдлать именно так).
Также, используемую в семпле сортировку методом пузырька можно заменить на другую, исходя из априорных данных об упорядоченности.

Mr_F_

21.06.2009 00:28

Ответ: Сортировка координат

-------------

Часовой пояс GMT +4, время: 13:16.