Still don't see the application of quicksort, but I guess a subdivision
scheme would be faster than the 'dumb' approach I presented.

A subdivsion approach for is_simple() would be:

1. calc the bounding box and split that recursively with respect to its
   larger size. (If that fails one can subdivide with respect to the smaller
   size - for optimization.)
2. For each divison you keep track of the points within.
3. Recursion ends, if the enlarged box containing also the neighbors of the
   points within the set can't be subdivided any more. This means:
   a) a box contains a single point (i.e. one point and its two neighbors
   are to be regarded),
   b) the subdivision scheme does not reduce the number of points any more.
4. now check each box containing more than 1 points for intersections using
   is_simple() from the 'dumb' approach.

I think this could apply well to your problem and guess it would expect it
to be something like O(n log n)

--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16999.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

I think the time performance was worst than O(n^2) due to the quicksort
implementation, not the method itself.

Now the shortcut of the new version: I collect the polygon edges (pairs of
vertices) in a list sorted from left to right (x coordinate) and parse the
list from left. When comparing two edges for intersection, I first check if
the second edge is to the right of the rightest extreme of the first edge.
If so, I can avoid the geometrical test of the second edge and all the
following edges in the list because they are sorted. Some special care
should be taken when the two edges are subsequent in the polygon border: if
it pass the previous test we may disregard it; if not we must check if they
aren't collinear and overlapping. Another small detail: if two subsequent
vertices are coincident (this may happens in practice!) the method may give
a false negative. This case should be deal with before sorting.

That is my last version of the method:

simple_polygon_test.scad
http://forum.openscad.org/file/n17000/simple_polygon_test.scad

I hope it is more diggestible :)

--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p17000.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

How do you imagine the subdivision would deal with a big edge crossing the
cloud of the others (intersecting or not) ? This seems to be a bad case for
my method.

Will you be able to write a subdivision method without the support of a tree
data structure?

If tree data structure is not a burden for you, consider the Shamos method,
it is O(n log n).

http://euro.ecom.cmu.edu/people/faculty/mshamos/1976GeometricIntersection.pdf
http://euro.ecom.cmu.edu/people/faculty/mshamos/1976GeometricIntersection.pdf

--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p17001.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

There is always a worst case. I guess, sorting only in x dimension will give
you trouble with structures extending in y direction, while some oszillation
in x direction occurs.

Having a diagonal edge will indeed reduce the speed of the my subdivision
approach to O(n²). Thanks for pointing this out.
I guess, one can analyze this worst case when the two suggested subdivisons
have failed and the set is still too large for the 'dumb' test, using either
a) the longest edge as subdivision axis then ending up with two (worst case)
equally sized boxes containing reduced sets
or b) scale the bounding box by sqrt(2) and rotate the point set around its
middle point by 45°.

But this is optimization stuff and follows the 20/80 rule: It makes a code
faster on the last 20% of the cases, with 80% of the time expended for dev.

I'll have a look into the paper ... thanks for the link. I found for me, its
good have some own thoughts, before going into the literature, to better
understand the nature of a problem.

Recursion has many disadvantages, but one advantage: You don't have to pay
for tree structures (remember the indexing). In practice it is always faster
to use an idexing scheme, but in OpenSCAD you depend on lists anyway. So
structured values just being passed through are copied by reference, which
is as fast as using indices - indeed it is indexing.

--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p17002.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

A more readable code of the merge sort:

merge_sort2.scad http://forum.openscad.org/file/n17003/merge_sort2.scad

--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p17003.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

I had a look into the paper. The core trick that accelerates the algorithm
from O(n²) to O(n log n) is the use of a balanced tree. Therefore, O(n²) is
all what you can gain for this problems from programming with OpenSCAD now.
BTW all that stuff (like is_simple, is_convex, triangulation, intersection
and union) is for sure build-in with OpenSCAD. Why not do feature requests
for native wrapper functions?

--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p17016.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

This thread is to too long and to specialized now for this. Better open a new
one and give a titel like "feature request ... "

--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p17018.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

I have news! My simple polygon test and polygon triangulation is already
integrated in my modelling scheme. And some interesting features emerge from
that.
The following image shows the preview of a solid whose boundary consists in
two polyhedral surfaces and four vertical triangulated almost planar faces.
The top polyhedral surface is a discretization of a Bezier surface and the
other is a repositioning of its control point polygon. A difference
operation made the hole.
http://forum.openscad.org/file/n17150/modelling_demo_previewed.png
The edges were highlighted so the implicit triangulation of the meshes and
the imposed triangulation to the vertical faces become apparent. All
polyhedron faces were triangulated to avoid a CGAL error due to non-planar
faces.

The next image shows the corresponding render of the same solid.
http://forum.openscad.org/file/n17150/modelling_demo_CGAL.png
The edge highlighting shows that CGAL has removed a lot of edges, supposedly
the ones adjacent to two co-planar facets. For instance, all the edges
created by my triangulation procedure for the 4 vertical faces were removed.
So, CGAL reduces the unnecessary complexity of the model in order to
simplify the work on boolean operations.

In short: if you doesn't triangulate some face, CGAL may reject it as
non-planar and if you triangulate all faces, CGAL may undo your hard work.

--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p17150.html
Sent from the OpenSCAD mailing list archive at Nabble.com.