I see your point. So what you with a almost planar 2D polygon P living anywhere in 3D is: 1. choose any three non-colinear points of P and construct a plane E 2. find a map T() that maps the base vectors of E to the base {x, y} 3. calculate P'=T(P) and drop the z-dimension (projection) 4. cycle around P' and count for each triple of consequent points whether the third point is left with respect to the first two. If this count is lower than len(P)/2 use the orientation CW otherwise CCW. -- View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16844.html Sent from the OpenSCAD mailing list archive at Nabble.com.

On 2016-03-31 13:11, Parkinbot wrote: > I see your point. So what you with a almost planar 2D polygon P living > anywhere in 3D is: > > 1. choose any three non-colinear points of P and construct a plane E This will not always work. It will give you a plane, but you don't know which of the 2 possible normals that plane will have, since you cannot assume the polygon is convex. Look up "Newell's method". It will give you the polygon normal corresponding to CCW directly for a planar polygon, including concave polygons. As mentioned, a slightly non-planar might work too, but I have not checked. Carsten Arnholm

Your point is adressed in step 4 not in step 1. -- View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16850.html Sent from the OpenSCAD mailing list archive at Nabble.com.

Parkinbot wrote > this works, just the polygon generator does not always produce a non > selfintersecting polygon. Surprisingly short solution, Parkinbot. However, in my tests, it does not deal with more than a few dozen vertices. You recurring cycling is the villain. And to avoid it you should consider that not only the first three vertices in the sequence is a candidate to be an ear. The following code changes yours addressing those issues. I provide also a detection of non-simple polygons to avoid crashing. It is a lot slow yet, taking 16sec for 200 vertices excluding the display. > seed = floor(rands(0,10000,1)[0]); > //seed = 4628; > echo(seed); > > N = 400; > p = randpolyg(N); // too easy to be not perfect > q = triag(p); > if( len(q[len(q)-1]) > 3) echo("Non-simple polygon"); > > for (i=[0:len(q)]) color([i,i,i]/N) polygon(q[i]); > > translate([0, 0,-1]) polygon(p); > > // generate a randomized polygon > function randpolyg(N=10) = let (rnd = rands(3,10,2*N,seed)) > [for (i=[0:360/N:359.9]) [rnd[2*N*i/360]*sin(i), > rnd[2*N*i/360+1]*cos(i)]]; > > function triag(S) = > len(S) <= 3 ? > [S]: > let( ear = valid_ears(S)[0], l = len(S) ) > ear== undef? [] : // case S is a non-simple polygon > concat([[S[(ear+l-1)%l], S[ear], S[(ear+1)%l]]], > triag(exclude_vertex(ear,S), k) ); > > function exclude_vertex(k,S) = > concat( k<=0? []: [for(i=[0 :k-1]) S[i] ] , > k>=len(S)-1? []: [for(i=[k+1:len(S)-1]) S[i] ] ); > > function valid_ears(S) = > [ for( i=[0:len(S)-1]) if( is_valid(i,S) ) i ]; > > function is_valid(k,S) = // false, if not ear or any other point of S > inside ear > let( l = len(S) ) > is_left(S[(k+l-1)%l], S[k], S[(k+1)%l],0)? // is S[k] an ear? > let ( res = [ for(i=[0:l-1]) // test all other points > if( (i!=k) && (i!=(k+l-1)%l) && (i!=(k+1)%l) && > is_left(S[(k+l-1)%l], S[k], S[i],1) && > is_left(S[k], S[(k+1)%l], S[i],1) && > is_left(S[(k+1)%l], S[(k+l-1)%l], S[i],1)) 1] > ) > res==[]: > false; > > function is_left(a, b, c, ind) = // true if c is left of a--->b > ind==0? > (b[0] - a[0])*(c[1] - a[1]) - (b[1] - a[1])*(c[0] - a[0]) < 0 : > (b[0] - a[0])*(c[1] - a[1]) - (b[1] - a[1])*(c[0] - a[0]) <= 0; -- View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16852.html Sent from the OpenSCAD mailing list archive at Nabble.com.

As I wrote: it is the random polygon generator that freaks out and delivers malformed polygons, not the triangulation. As the code cycles around the part of the polygon not being triangulated yet, it is indeed enough to just regard the first three points. -- View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16853.html Sent from the OpenSCAD mailing list archive at Nabble.com.

Parkinbot wrote > I see your point. So what you do with an almost planar 2D polygon P living > anywhere in 3D is: > > 1. choose any three non-colinear points of P and construct a plane E > 2. find a map T() that maps the base vectors of E to the base {x, y} > 3. calculate P'=T(P) and drop the z-dimension (projection) > 4. cycle around P' and count for each triple of consequent points whether > the third point is left with respect to the first two. If this count is > lower than len(P)/2 use the orientation CW otherwise CCW. I am trying another approach to step 4. Find the indices of the extreme vertices of P': those with minimum x, minimum y, maximum x, maximum y, in that order. If they are cycling ordered (that is they follows the order of the CCW orientation) you got it. As an example, if the indices are [ 4, 0, 0, 3] it is CCW, if they are [3,0,0,4] it is CW. -- View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16854.html Sent from the OpenSCAD mailing list archive at Nabble.com.

Parkinbot wrote > 1. choose any three non-colinear points of P and construct a plane E I would rather prefer a plane fitting. Plane E is a good choice for that three points but may be very bad for the remaining. -- View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16855.html Sent from the OpenSCAD mailing list archive at Nabble.com.

I agree. There are lots of ad hoc ways of almost solving this problem - eventually everyone figures out that you need to do a proper fit of a plane to all the points. If you compute eigenvectors for the covariance matrix, you can even use the eigenvalues to determine whether or not the points lie “almost” in a plane. And then, you might as well use the eigenvector associated with the largest eigenvalue as your x-axis. -- Kenneth Sloan KennethRSloan@gmail.com Vision is the art of seeing what is invisible to others. > On Mar 31, 2016, at 13:03 , Ronaldo <rcmpersiano@gmail.com> wrote: > > Parkinbot wrote >> 1. choose any three non-colinear points of P and construct a plane E > > I would rather prefer a plane fitting. Plane E is a good choice for that > three points but may be very bad for the remaining. > > > > > -- > View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16855.html > Sent from the OpenSCAD mailing list archive at Nabble.com. > > _______________________________________________ > OpenSCAD mailing list > Discuss@lists.openscad.org > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

Shrewd! 2016-03-31 15:09 GMT-03:00 Kenneth Sloan <kennethrsloan@gmail.com>: > I agree. There are lots of ad hoc ways of almost solving this problem - > eventually everyone figures out that you need to do a proper fit of a plane > to all the points. If you compute eigenvectors for the covariance matrix, > you can even use the eigenvalues to determine whether or not the points lie > “almost” in a plane. And then, you might as well use the eigenvector > associated with the largest eigenvalue as your x-axis. > > -- > Kenneth Sloan > KennethRSloan@gmail.com > Vision is the art of seeing what is invisible to others. > > > > > > On Mar 31, 2016, at 13:03 , Ronaldo <rcmpersiano@gmail.com> wrote: > > > > Parkinbot wrote > >> 1. choose any three non-colinear points of P and construct a plane E > > > > I would rather prefer a plane fitting. Plane E is a good choice for that > > three points but may be very bad for the remaining. > > > > > > > > > > -- > > View this message in context: > http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16855.html > > Sent from the OpenSCAD mailing list archive at Nabble.com. > > > > _______________________________________________ > > OpenSCAD mailing list > > Discuss@lists.openscad.org > > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org > > > _______________________________________________ > OpenSCAD mailing list > Discuss@lists.openscad.org > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >

Parkinbot wrote > As I wrote: it is the random polygon generator that freaks out and > delivers malformed polygons, not the triangulation. > > As the code cycles around the part of the polygon not being triangulated > yet, it is indeed enough to just regard the first three points. I agree. But my objection is exactly the cycling that increases the inefficiency and, I suppose, quickly grows the recursion stack. -- View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16859.html Sent from the OpenSCAD mailing list archive at Nabble.com.