Simple polygon triangulation
You are right. I planned to include a randomized cutting scheme, but as the
algorithm was not traceble for me anymore, I thought it was a bad idea to
put another randomness on top of it.
So my new idea is to check the subdivision line AB against all other lines
PQ built by two subsequent points (with P,Q<>A,B of course). If they
intersect, the polygon APBQ will be convex in a CW or CCW sense. This is
easy to test with is_left()
Being short of time in the next days, I might implement it in Matlab next
weekend. With a debugger one can effectively trace recursions.
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16920.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
Ronaldo wrote
I think I have a full functional implementation of a O(n^3) ear-cutting
method to triangulate 2D simple polygon. I addopted the data structure
Parkinbot suggested to output the triangles as lists of the indices in the
array of vertices. The code is relatively simple:
yeah, nice! Much more interative.
Two annotations:
-
As you collect the set of all ears in one cycle, isn't it that you test
the ears already within the set again and again? Avoiding this might bring
you closer to O(n²) :-) -
I would suspect that approximating the best plane is not much safer than
using a suboptimal plane, as long as you don't have a criteria assuring that
the projection to this best (or any other) plane will be homomorph. Indeed
you easily can construct polygons, that don't project homomorph to the best
plane, but to a suboptimal plane. Also Eigenvector calculation takes time.
Projecting the polygon to xy, yz, zx planes and ranking the point triples
defining the largest areas within those projections in 3D, might be a good
and fast heuristics, until you give this criteria.
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16923.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
nophead wrote
If you want to write in a procedural language why not use the Python
binding, or the C++ binding, or Angel script, etc.
If you want us all to write in a functional language, why not offer at least
an echo() function primitive which outputs a value to console while
returning it unchanged.
function myfunction(a) = let(x=echo(f(a,i))) // inspect this value
g(x); // calculation some other value from it
function f(a,i) = i;// ... some function
function g(x) = x;// ... some other function
function echo(x) = x; // side effect to console
Also a break-function breaking a for-loop would not be incompatible.
Unbreakable for-loops are in fact foreach-loops and could be offered
additionally.
function myfunction(a) = [for(i=[n-1]) if (mypredicate(a,i))
break(fn(a,i))] ;
function myfunction1(A) = [foreach (a in A) fn(a)];
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16924.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
On 04/03/2016 03:00 PM, Parkinbot wrote:
If you want us all to write in a functional language, why not offer
at least an echo() function primitive which outputs a value to console
while returning it unchanged.
This is already sitting in the pull request queue. Mainly
the backward compatibility needs to be clarified:
Also a break-function breaking a for-loop would not be incompatible.
Unbreakable for-loops are in fact foreach-loops and could be offered
additionally.
That should be possible with the C++ style for loops which are
in the dev version as experimental feature, see
https://en.wikibooks.org/wiki/OpenSCAD_User_Manual/WIP
ciao,
Torsten.
Torsten has a recently active pull request which extends echo() to work
inside functions. The same pull also adds assert().
https://github.com/openscad/openscad/pull/1587
On Sunday, 3 April 2016, Parkinbot rudolf@parkinbot.com wrote:
why not offer at least
an echo() function primitive which outputs a value to console while
returning it unchanged.
function myfunction(a) = let(x=echo(f(a,i))) // inspect this value
g(x); // calculation some other value from it
function f(a,i) = i;// ... some function
function g(x) = x;// ... some other function
function echo(x) = x; // side effect to console
that is good news. Not exactly, what I meant, but I see a progress.
"each" is flattening a list. "foreach" would be a loop type.
the "echo" function seems to do much more, I had ever expected. But I doubt,
it is a good idea to allow it introducing new variables living in outer
scope. An output expression should not be allowed to have side effects on or
be vulnerable by surrounding code, as in most cases it might be used
temporarly for debugging only.
a = 3;
b = 6;
d = 9, // will be superseeded by echo
t6 = echo(c = 2, d = c + 9) abc*d;
echo(t6 = t6);
...
d = 10; // this anywhere in subsequent code, will superseed the output of
echo
t7 = echo(d=t6+a) d; // this one will win and have a side effect on the
first echo output.
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16927.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
On 04/03/2016 04:43 PM, Parkinbot wrote:
the "echo" function seems to do much more, I had ever expected. But I doubt,
it is a good idea to allow it introducing new variables living in outer
scope. An output expression should not be allowed to have side effects on or
be vulnerable by surrounding code, as in most cases it might be used
temporarly for debugging only.
If you use the variables defined in the echo() call, just replace it
with let() and you'll get the same behavior without the output.
ciao,
Torsten.
On 04/03/2016 04:47 PM, Torsten Paul wrote:
On 04/03/2016 04:43 PM, Parkinbot wrote:
the "echo" function seems to do much more, I had ever expected. But I doubt,
it is a good idea to allow it introducing new variables living in outer
scope. An output expression should not be allowed to have side effects on or
be vulnerable by surrounding code, as in most cases it might be used
temporarly for debugging only.
If you use the variables defined in the echo() call, just replace it
with let() and you'll get the same behavior without the output.
Well, that said, there's still the backward compatibility issue to
solve which is mainly that the new stuff should use sequential
assignment where the existing statement level echo() uses parallel
assignment.
So we might end up creating a new function with a different name
that could have the same behavior for both statement and function
level.
In that case we could have something like...
print(name = "x", value = x);
...which might open wishes for the next can of worms: formatting!!1!
ciao,
Torsten.
I agree with Parkinbot. echo(stuff) expr should not introduce local
variable bindings into expr.
The idea behind this particular syntax is that you can take an existing
function definition,
f(x) =
expr;
and you can temporarily introduce an echo for debugging, without
rearranging the code:
f(x) =
echo(stuff)
expr;
Once you are done debugging, you can delete the echo, or you can comment it
out for later use:
f(x) =
// echo(stuff)
expr;
echo() is a debugging mechanism. Commenting out an echo() should not change
the meaning of the code.
Doug.
On 3 April 2016 at 10:43, Parkinbot rudolf@parkinbot.com wrote:
that is good news. Not exactly, what I meant, but I see a progress.
"each" is flattening a list. "foreach" would be a loop type.
the "echo" function seems to do much more, I had ever expected. But I
doubt,
it is a good idea to allow it introducing new variables living in outer
scope. An output expression should not be allowed to have side effects on
or
be vulnerable by surrounding code, as in most cases it might be used
temporarly for debugging only.
a = 3;
b = 6;
d = 9, // will be superseeded by echo
t6 = echo(c = 2, d = c + 9) abc*d;
echo(t6 = t6);
...
d = 10; // this anywhere in subsequent code, will superseed the output
of
echo
t7 = echo(d=t6+a) d; // this one will win and have a side effect on the
first echo output.
--
View this message in context:
http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16927.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
On 04/03/2016 05:36 PM, doug moen wrote:
echo() is a debugging mechanism. Commenting out an echo() should
not change the meaning of the code.
Well, we can't have echo() then. Any ideas for a good name (which
would then be available as both statement and function and likely
also deprecate the existing echo()).
When we at that, we can also change/remove the existing "ECHO:"
prefix.
Also I'm going to strongly suggest that there will be no
accidental HTML handling as it currently happens due to the
console being able to render that.
ciao,
Torsten.