Simple polygon triangulation
Output should be persistent until user decision (file), or buffer full
(console).
jpmendes
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16958.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
runsun wrote
Ronaldo wrote
function sum_list0(p, from=0, to) =
let(til = (to==undef) ? len(p)-1 : to )
from==til ?
p[til] :
sum_list0( p, from+1, til );
This one doesn't work AT ALL, 'cos it didn't actually sum up things:
Ops, a transcription mistake. The correct one:
function sum_list0(p, from=0, to) =
let(til = (to==undef) ? len(p)-1 : to )
from==til ?
p[til] :
p[from] + sum_list0( p, from+1, til );
runsun wrote
Ronaldo wrote
function sum_list1(p, from=0, to, sum=0) =
let(til = (to==undef) ? len(p)-1 : to )
from>til?
sum :
sum_list1( p, from+1, til, sum + p[from] );
No success. No tail recursion was done.
This one looks like a tail recursion to me, and seems to be working:
To see it is not, compare:
echo(sum_list1([ for(i=[1:1000]) for(j=[1:1000]) 1 ]));
with:
echo(sum_list3([ for(i=[1:1000]) for(j=[1:1000]) 1 ]));
or:
echo(sum_list2([ for(i=[1:1000]) for(j=[1:1000]) 1 ]));
runsun wrote
This one works in my computer:
a=[3,4,5,6];
echo( sum_list2(a)); ==> 18
echo( sum_list2(a, to=2)); ==> 12
In mine too, sorry. And here the tail recursion works as well.
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16959.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
Ronaldo wrote
The bad news first: my previous sum_list worked with any uniform list of
numbers, vectors or even matrices. The tail recursion version no! You have
to know the list element type to initialize the sum. :(
Yes, but it is possible to add vectors and matrix with sum_list2 if we
initialize correctly the sum in the call :
echo(sum_list2([ for(i=[1:100]) for(j=[1:100]) [ 1, 2] ], sum=[0,0]));
echo(sum_list2([ for(i=[1:100]) for(j=[1:100]) [ [ 1, 2], [0,1] ] ],sum=[
[0,0], [0,0] ]));
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16960.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
Ronaldo wrote
To see it is not, compare:
echo(sum_list1([ for(i=[1:1000]) for(j=[1:1000]) 1 ]));
with:
echo(sum_list3([ for(i=[1:1000]) for(j=[1:1000]) 1 ]));
or:
echo(sum_list2([ for(i=[1:1000]) for(j=[1:1000]) 1 ]));
Before making comparison, let me make sure I am not wrong about something:
how do you decide if it's a tail recursion ?
I look at the code and see it fits the definition of tail recursion. From my
understanding, the result doesn't matter. Maybe my approach is wrong ?
$ Runsun Pan, PhD $ libs: doctest , faces ( git ), offline doc ( git ), runscad.py( 1 , 2 , git ), synwrite( 1 , 2 ); $ tips: hash( 1 , 2 ), matrix( 1 , 2 ),sweep( 1 , 2 ), var( 1 , 2 ), lerp , animation ( gif , prodVid ), precision( 1 , 2 ), xl-control , type , rounded polygon , chfont
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16961.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
The OpenSCAD implementation only supports a limited subset of tail
recursion. The body of the function f() must match the pattern c ? a : b,
where a or b is a call to f(). Adding a let() to the beginning of that
breaks the pattern.
We can extend this a bit, but full support for tail recursion elimination
will require a significant redesign of the evaluator.
On 4 April 2016 at 12:43, runsun runsun@gmail.com wrote:
Ronaldo wrote
To see it is not, compare:
echo(sum_list1([ for(i=[1:1000]) for(j=[1:1000]) 1 ]));
with:
echo(sum_list3([ for(i=[1:1000]) for(j=[1:1000]) 1 ]));
or:
echo(sum_list2([ for(i=[1:1000]) for(j=[1:1000]) 1 ]));
Before making comparison, let me make sure I am not wrong about something:
how do you decide if it's a tail recursion ?
I look at the code and see it fits the definition of tail recursion. From
my
understanding, the result doesn't matter. Maybe my approach is wrong ?
$ Runsun Pan, PhD $ libs: doctest , faces ( git ), offline doc ( git ),
runscad.py( 1 , 2 , git ), synwrite( 1 , 2 ); $ tips: hash( 1 , 2 ),
matrix( 1 , 2 ),sweep( 1 , 2 ), var( 1 , 2 ), lerp , animation ( gif ,
prodVid ), precision( 1 , 2 ), xl-control , type , rounded polygon , chfont
--
View this message in context:
http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16961.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
doug.moen wrote
The OpenSCAD implementation only supports a limited subset of tail
recursion. The body of the function f() must match the pattern c ? a : b,
where a or b is a call to f(). Adding a let() to the beginning of that
breaks the pattern.
Arrrhhh thx for that. I didn't recall seeing this explanation anywhere. Lots
and LOTS of my code are recursions that I thought are recursions but with
let(). Maybe it'd be a good idea to document this.
$ Runsun Pan, PhD $ libs: doctest , faces ( git ), offline doc ( git ), runscad.py( 1 , 2 , git ), synwrite( 1 , 2 ); $ tips: hash( 1 , 2 ), matrix( 1 , 2 ),sweep( 1 , 2 ), var( 1 , 2 ), lerp , animation ( gif , prodVid ), precision( 1 , 2 ), xl-control , type , rounded polygon , chfont
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16963.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
As mentioned by Parkinbot somewhere in this thread, one annoying aspect of
the OpenSCAD language is the non-existence of a loop escape - something like
the break in C. For instance, if you have to do some test in a list like:
function test(l) = [ for(i=[0:len(l)-1]) if (some_test_fail(l,i)) 0 ]==[];
there is no way to exit the loop test as soon as a fail is detected. I found
a way to escape using tail recursion. For the above case, it would be:
function test(l,i=0) =
(i==len(l)) || some_test_fail(l,i)) ?
i==len(l) :
test(l,i+1);
If two nested loops are needed, we define one recursion for each:
function passed_for_all(n, i=0) =
(i==n) || ! passed_for_i(n, i, (i+1)) ?
i==n :
passed_for_all(n, (i+1));
function passed_for_i(n, i, j) =
(j==n) || some_test_fail(i, (i+1)) ?
j==n :
passed_for_i(n, i, (j+1));
That last example is just a skeleton to show the principle, where n defines
the number of "iterations" of i and j.
The very surprising aspect is that the recursive solution, even if all inner
tests returns false, is faster than the iterative one. In my machine,
passed_iter(2500) expends 33sec while the recursive version
passed_for_all(2500) expends 27sec . This is a bonus to the escape from a
loop.
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16974.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
Thanks for addressing this aspect again. Let me annote that the semantics of
function test(l,i=0) =
(i==len(l)) || some_test_fail(l,i)) ?
i==len(l) :
test(l,i+1);
is not unique from the perspective of a functional language. In general,
there is no reliable evaluation sequence of an OR expression. To avoid
calling some_test() for len(l)==i accidently, which might crash or slow down
your code, you'd prefer to write:
function test(l,i=0) =
(i>=len(l)) ?
false:
some_test_fail(l,i)) ?
false:
test(l,i+1);
I suppose you tweeked your is_ear() test with this pattern.
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16980.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
On Wed, 6 Apr 2016 02:48:25 -0700 (MST)
Parkinbot rudolf@parkinbot.com wrote:
Thanks for addressing this aspect again. Let me annote that the
semantics of
function test(l,i=0) =
(i==len(l)) || some_test_fail(l,i)) ?
i==len(l) :
test(l,i+1);
is not unique from the perspective of a functional language. In
general, there is no reliable evaluation sequence of an OR
expression. To avoid calling some_test() for len(l)==i accidently,
which might crash or slow down your code, you'd prefer to write:
That's a surprising thing to say. Every C-derived language I've worked
in has had the same evaluation sequence for OR, based on short-cut
semantics. By this definition, left-hand term is evaluated and only if
it is false is the right hand side evaluated.
I would agree that mathematically it doesn't matter. In every
programming language I've checked, this has been the order.
G. Wade
function test(l,i=0) =
(i>=len(l)) ?
false:
some_test_fail(l,i)) ?
false:
test(l,i+1);
I suppose you tweeked your is_ear() test with this pattern.
--
View this message in context:
http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16980.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
--
I'm pretty sure it's been declared dead at least once, which is usually
a requirement for a technology to be production grade stable.
-- Matt S. Trout
Parkinbot wrote
Let me annote that the semantics of
function test(l,i=0) =
(i==len(l)) || some_test_fail(l,i)) ?
i==len(l) :
test(l,i+1);
is not unique from the perspective of a functional language.
I considered that. However, as OpenSCAD language has no mutable state, I
think there is no harm calling some_test_fail() with improper arguments. The
undef value that may be returned is dealed as false by the boolean operator.
So no need to overcharge the code with one more conditional expression.
Parkinbot wrote
I suppose you tweeked your is_ear() test with this pattern.
You might be referring to any_ear() :
function any_ear(lsp) =
let( l = len(lsp) )
[ for(j=[0:l-1]) if( is_ear(j, lsp) ) j ] [0];
Yes, it can benefit from tail recursion/escape with the code:
function any_ear(lsp, j=0) =
(j==len(lsp)) ?
undef :
is_ear(j,lsp) ?
j :
any_ear(lsp,j+1);
// or simply:
function any_ear(lsp, j=0) =
(j==len(lsp)) || is_ear(j,lsp) ?
j :
any_ear(lsp,j+1);
But what bothers me yet are functions like the exclude_vertex():
function exclude_vertex(k,lsp) =
concat( k<=0? []: [for(i=[0 :k-1]) lsp[i] ] ,
k>=len(lsp)-1? []: [for(i=[k+1:len(lsp)-1]) lsp[i] ] );
which would be simpler, and possibly faster, with more list processing
function in the language:
function exclude_vertex(k,lsp) =
concat(sub_list(0, k-1, lsp ), sub_list(k+1, len(lsp)-1, lsp) );
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16982.html
Sent from the OpenSCAD mailing list archive at Nabble.com.