# Quicksort

28 messages
12
Open this post in threaded view
|

## Quicksort

 I am stuck. I got an implementation of quicksort as an example of list comprehension in the manual: function quicksort(arr) =   !(len(arr)>0) ? [] :       let(  pivot   = arr[floor(len(arr)/2)],             lesser  = [ for (y = arr) if (y  < pivot) y ],             equal   = [ for (y = arr) if (y == pivot) y ],             greater = [ for (y = arr) if (y  > pivot) y ]       )       concat( quicksort(lesser), equal, quicksort(greater) ); It works well for very large random arrays and, in the worst case, for arrays with length at least 3000 without stack overflow. Usually the partitions of quicksort are in two subarrays. So I tweaked the code to get: function quicksort1(arr) =   !(len(arr)>0) ? [] :       let( pivot   = arr[floor(len(arr)/2)],            lesser  = [ for (y = arr) if (y  <= pivot) y ],            greater = [ for (y = arr) if (y  >  pivot) y ]       )       concat( quicksort1(lesser), quicksort1(greater) ); where the partition "equal" is included in the partition "lesser". The trouble is that this last version is not working: I get a stack overflow for any non void array. And I don't see why.
Open this post in threaded view
|

## Re: Quicksort

 In the first implementation there is always at least one element that gets taken away from the sorting (the pivot), so that you will always finish. In quicksort1 when the array has just 1 element it gets always selected as pivot, always included in lesser and you get infinite recursion. > I am stuck. I got an implementation of quicksort as an example of > list > comprehension in the manual: > > > function quicksort(arr) =   > >   !(len(arr)>0) ? [] :   > >       let(  pivot   = arr[floor(len(arr)/2)], > >             lesser  = [ for (y = arr) if (y  < pivot) y ], > >             equal   = [ for (y = arr) if (y == pivot) y ], > >             greater = [ for (y = arr) if (y  > pivot) y ] > >       ) > >       concat( quicksort(lesser), equal, quicksort(greater) );   > > It works well for very large random arrays and, in the worst case, for > arrays with length at least 3000 without stack overflow. > Usually the partitions of quicksort are in two subarrays. So I > tweaked the code to get: > > > function quicksort1(arr) =   > >   !(len(arr)>0) ? [] :   > >       let( pivot   = arr[floor(len(arr)/2)], > >            lesser  = [ for (y = arr) if (y  <= pivot) y ], > >            greater = [ for (y = arr) if (y  >  pivot) y ] > >       ) > >       concat( quicksort1(lesser), quicksort1(greater) );   > > where the partition "equal" is included in the partition "lesser". > The trouble is that this last version is not working: I get a stack > overflow for any non void array. And I don't see why. > > > > -- > View this message in context: > http://forum.openscad.org/Quicksort-tp17044.html Sent from the > OpenSCAD mailing list archive at Nabble.com. > > _______________________________________________ > OpenSCAD mailing list > [hidden email] > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Quicksort

 Bingo! Why I didn't see that? Well, I think I hadn't fully grasped quicksort algorithm. :( Meanwhile, I got a version of quicksort which seems to have the pattern of tail recursion: function qs(arr, arr_out=[]) =     !(len(arr)>0) ?         arr_out :         qs( arr     = high_part(arr),             arr_out = concat(qs( low_part(arr), arr_out ), middle_part(arr)) ); function high_part  (arr) = [ for (y = arr) if (y >  pivot(arr)) y ]; function middle_part(arr) = [ for (y = arr) if (y == pivot(arr)) y ]; function low_part   (arr) = [ for (y = arr) if (y <  pivot(arr)) y ]; function pivot      (arr) = arr[floor(len(arr)/2)]; I were able to sort a worst case array of length 5000 in 48sec with qs(). The previous quicksort() function fail with stack overflow for lengths lesser than 4000. However, it is much slower: for a random array with 40000 values, qs() required 60 sec while quicksort() spent just 4sec.
Open this post in threaded view
|

## Re: Quicksort

Open this post in threaded view
|

## Re: Quicksort

Open this post in threaded view
|

## Re: Quicksort

Open this post in threaded view
|

## Re: Quicksort

Open this post in threaded view
|

## Re: Quicksort

Open this post in threaded view
|

## Re: Quicksort

Open this post in threaded view
|

## Re: Quicksort

Open this post in threaded view
|

## Re: Quicksort

 In reply to this post by nophead As far as I know, polyhedron faces isn't triangulated in rendering just in preview. That is the main reason I searched for a polygon triangulation. Apparently, when CGAL rejects a face as non-planar, OpenSCAD tries to triangulate it: the alternative procedure. But sometimes this doesn't work either. I don't need to sort 40000 array values. I was only doing a time analysis to compare different methods. Remember that the quicksort exemplified in the manual, to be robust, should be restricted to handle vectors with 3000 elements. That is the limit for the worst (very unlikely) case, but you never know.
Open this post in threaded view
|

## Re: Quicksort

 As I said before in another thread, OpenSCAD should provide a good set of list processing operators. And sorting is a very basic one. After all, lists are the only available data structure in the language. Besides, CGAL has lots of computational geometry methods and very very few of them are accessible by the language. My dream is to have a general OpenSCAD interface to CGAL library for people who wants to dig in the CGAL world. To dough: I like F-rep too. It is a very general paradigm but it requires some mathematical-oriented mind. I see no way to include F-rep without a robust optimized kernel to support it. If CGAL is able to give that support, it would a good path to pursuit.
Open this post in threaded view
|

## Re: Quicksort

Open this post in threaded view
|

## Re: Quicksort

 In reply to this post by Ronaldo As I wrote in the other thread, quicksort alone will not speed up your code from O(n²) to O(n log n). What you need, is a sorter operating over a balanced tree. Thus: better "ask" for this. BUT: this approach needs function pointers, as you will have to provide a predicate for general sorting. So better wait for OpenSCAD2, use a richer programming language, or try your luck and ask for an API ;-)
Open this post in threaded view
|

## Re: Quicksort

Open this post in threaded view
|

## Re: Quicksort

 doug.moen wrote Ronaldo, it sounds like you are writing your own polygon triangulation software in order to work around a possible bug in polyhedron(). There is some argument to polyhedron(), involving a non-planar face, that works in preview, but doesn't work in rendering. Can you describe the bug in more detail, maybe provide a failing test case? I don't have a failing test case anymore. I integrated the polygon triangulation in my system and have no more the issues I had before. I am working on a system that allows solid (sets with manifold boundaries) modelling using polyhedron primitive with faces defined by Bezier patches and planar (or almost) faces. It evolved very well but I faced now and then with annoying messages by CGAL of non-planar faces. The analysis of the face definition usually shown that the face was planar (for instance, all vertices had the same x coordinate). Sometimes the alternate construction solved the trouble. Sometimes not. So, I decided to write my own polygon triangulation algorithm which unhappily is not good enough and took too much of my time. The discussions on simple polygon test, plane fitting and sorting, all came from that target. That is the story. I have no way to say that I was facing a bug. I don't know what is being considered for OpenSCAD2. But, it would be nice to have access to this sort of geometrical methods that are in the core of CGAL. And a richer set of list processing functions.
Open this post in threaded view
|

## Re: Quicksort

 Administrator In reply to this post by Ronaldo > On Apr 12, 2016, at 11:01 AM, Ronaldo <[hidden email]> wrote: > > Besides, CGAL has lots of computational geometry methods and very very few > of them are accessible by the language. My dream is to have a general > OpenSCAD interface to CGAL library for people who wants to dig in the CGAL > world. > Ronaldo, Keep in mind that OpenSCAD isn’t primarily a wrapper around CGAL. We use it as a last resort to perform certain types of computational geometry operations. Due to severe performance challenges with CGAL, we’re actively looking for ways to reduce our dependency on CGAL. To dig into the CGAL world, I would recommend using their officially supported SWIG bindings as a starting point.  -Marius _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Quicksort

 Administrator In reply to this post by Ronaldo > On Apr 12, 2016, at 10:44 AM, Ronaldo <[hidden email]> wrote: > > Apparently, when CGAL rejects a face as non-planar, OpenSCAD tries to > triangulate it: the alternative procedure. But sometimes this doesn't work > either. > “sometimes this doesn’t work” sounds like a bug. CGAL frequently rejects polygons as non-planar, if those polygons were specified using floating point vertices. We have workarounds for that, but our workaround are only as good as our test cases. Any additional corner cases breaking this would be valuable input allowing us to be more robust. As a side-note for anyone wondering: The polygon triangulator built into CGAL isn’t very robust and crashes on some of our test cases. We thus had to switch to a more robust implementation, currently libtess2, as mentioned earlier in this thread.  -Marius _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Open this post in threaded view
|

## Re: Quicksort

 "CGAL frequently rejects polygons as non-planar, if those polygons were specified using floating point vertices. We have workarounds for that, but our workaround are only as good as our test cases."I suggest that polyhedron() should automatically triangulate any face with more than 3 vertices, since in this case floating point vertices are always used.On 13 April 2016 at 11:16, Marius Kintel wrote:> On Apr 12, 2016, at 10:44 AM, Ronaldo <[hidden email]> wrote: > > Apparently, when CGAL rejects a face as non-planar, OpenSCAD tries to > triangulate it: the alternative procedure. But sometimes this doesn't work > either. > “sometimes this doesn’t work” sounds like a bug. CGAL frequently rejects polygons as non-planar, if those polygons were specified using floating point vertices. We have workarounds for that, but our workaround are only as good as our test cases. Any additional corner cases breaking this would be valuable input allowing us to be more robust. As a side-note for anyone wondering: The polygon triangulator built into CGAL isn’t very robust and crashes on some of our test cases. We thus had to switch to a more robust implementation, currently libtess2, as mentioned earlier in this thread.  -Marius _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org