gordon@cs.tamu.edu (Dan Gordon) (05/05/90)
In article <374@van-bc.UUCP} jtc@van-bc.UUCP (J.T. Conklin) writes: }[Followup-To: comp.misc] } }In article <1857@gould.doc.ic.ac.uk> zmacy67@doc.ic.ac.uk (Roger Attrill) writes: }> I am currently writing a 3-D solids modeller. A simple part of this }>requires the depth sorting of a large number of triangular surfaces. While }>the quicksort algorithm is ok, I have heard of the Shell-Metzner sort, }>(actual spelling unknown). I have even spoken to two other people who }>have heard of it, but I can't find anyone who has GOT it. If any one knows }>the algorithm, or knows someone who knows someone ..... then I'd be very }>grateful. Also If anyone knows any other very fast sorting algorithms ( ie }>faster than quicksort ) then I'd like to hear from you. } }You really need to grab an elementary algorithms text before you start }evaluating the performance of sorting algorithms. I suggest taking a }look at Knuth's Sorting and Searching. } }That said, every algorithm has its strengths and weaknesses. The data }that you are working with will play a large part of which algoritm you }choose. } }For example, the ubiquous bubblesort. It is small, easy to implement, }Quicksort is is generally quite fast O(n log n), but its worst case }The Shell sort tends to fall between the fast algorithms like --- stuff deleted --- If you want to do depth sorting, your best bet is to use bucket sort. For every integral value of z between ZMIN and ZMAX, you maintain a sorted linked list of all the points whose integral value of z is equal to the bucket number (see any good book on data structures and/or design & analysis of algorithms). After all the points have been inserted into the buckets, you can traverse all the linked lists and copy the points into an array. Alternatively, by maintaining also a pointer to the end of each list, you can (at the end) efficiently link all the lists together into one sorted linked list. Let us all know which method works best in your situation. It has been demonstrated that for various problems in computational geometry, bucketing techniques work best in practice, even though their theoretical worst-case running times are bad.
gordon@cs.tamu.edu (Dan Gordon) (05/06/90)
In article <374@van-bc.UUCP> jtc@van-bc.UUCP (J.T. Conklin) writes: >[Followup-To: comp.misc] >In article <1857@gould.doc.ic.ac.uk> zmacy67@doc.ic.ac.uk (Roger Attrill) writes: ]> I am currently writing a 3-D solids modeller. A simple part of this ]>requires the depth sorting of a large number of triangular surfaces. While ]>the quicksort algorithm is ok, I have heard of the Shell-Metzner sort, ]>(actual spelling unknown). I have even spoken to two other people who ]>have heard of it, but I can't find anyone who has GOT it. If any one knows ]>the algorithm, or knows someone who knows someone ..... then I'd be very ]>grateful. Also If anyone knows any other very fast sorting algorithms ( ie ]>faster than quicksort ) then I'd like to hear from you. ] ]That said, every algorithm has its strengths and weaknesses. The data ]that you are working with will play a large part of which algoritm you ]choose. ] ]For example, the ubiquous bubblesort. It is small, easy to implement, ]Quicksort is is generally quite fast O(n log n), but its worst case ]or mergesort. ]The Shell sort tends to fall between the fast algorithms like -- stuff deleted -- If you want to do depth sorting, your best bet is bucket sorting. For every integral value of z between ZMIN and ZMAX, maintain a sorted linked list of all the points whose integral value of z matches the bucket number. At the end, you can copy all the points from the lists into an array and get a sorted array of the points. Alternatively, you can link the lists together to form one sorted linked list of all the points. If you want this second alternative, then it is more efficient to maintain a pointer to the end of each list. See any good book on data structures and/or design & analysis of algorithms. Let us all know what works best for you. There are papers in computational geometry that indicate that bucketing techniques work best in practice, even though their theoretical worst-case running times are bad. Dan Gordon
gordon@cs.tamu.edu (Dan Gordon) (05/06/90)
Sorry about posting the same thing 3 times - I was expecting it to appear in comp.graphics, and when it didn't, I reposted it twice. "C" (cancel) doesn't seem to work on our system.
coy@ssc-vax.UUCP (Stephen B Coy) (05/07/90)
In article <374@van-bc.UUCP} jtc@van-bc.UUCP (J.T. Conklin) writes: }[Followup-To: comp.misc] } }In article <1857@gould.doc.ic.ac.uk> zmacy67@doc.ic.ac.uk (Roger Attrill) writes: }> I am currently writing a 3-D solids modeller. A simple part of this }>requires the depth sorting of a large number of triangular surfaces. While }>the quicksort algorithm is ok, I have heard of the Shell-Metzner sort, }>(actual spelling unknown). I have even spoken to two other people who }>have heard of it, but I can't find anyone who has GOT it. If any one knows }>the algorithm, or knows someone who knows someone ..... then I'd be very }>grateful. Also If anyone knows any other very fast sorting algorithms ( ie }>faster than quicksort ) then I'd like to hear from you. > worst-case running times are bad. First off, sorry if I've screwed up the attributions. I've come across this discussion kind of late. On to the topic. One thing to keep in mind is how you are going to manipulate the images. If you are going to generate relatively random views of your object then a quick(er)sort or a shell sort is applicable. If you are trying to generate views of the object as you rotate it slowly an insertion sort will take advantage of the view to view coherence much better. As the viewpoint changes, relatively few polygons will change order from frame to frame. Also, the ones that are out of order will still be fairly close to their correct position. An insertion sort will be at its best under these conditions and should be able to outperform the others easily with complexity approaching O(n). Another advantage is that its quite easy to implement. Stephen Coy uw-beaver!ssc-vax!coy