Simple polygon triangulation
Meanwhile I've tested a polygon with 900 points and it took 10s. So, we are
talking about efficiency now.
Letting OpenSCADs poor data manipulation ability and unnessecary copies when
cycling aside, it is the algorithm that takes O(n²) steps, because the ear
cut method relies on testing all the rest of the points in the polygon with
each new candidate.
You can cut that down by implementing the second simple scheme Kenneth
mentioned, because recursively cutting a polygon into two, reduces the
complexity by splitting the set of points to be tested by a division factor
and not only by 1. The method is similar to Quicksort.
You start to split with a guess:
- put floor(n/2) points into a first set, and the rest into a second set.
(Alternatively a random split can be used) - test if all points (except the first one) in the first set are left with
respect to the vector that connects the first points of the sets. - if the test is true, recurse both sets separately until done. If not,
cycle your split (or do alternatively another random guess) and continue
with 2.
There are other schemes mentioned in
https://en.wikipedia.org/wiki/Polygon_triangulation#Ear_clipping_method
which are even faster, but wasn't it you who wanted an implementation with a
small footage?
- Rudolf -
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16863.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
I suspect your algorithm may be O(n^4) and not O(n^2). Testing should resolve this.
Getting it to O(n^3) is easy; getting to O(n^2) is a bit harder.
As long as you are doing recursion, instead of iteration, stepping up to the general subdivision by a chord is probably worthwhile. If you do that, try to bias the selection of the chord to divide the polygon into two more-or-less equal pieces.
Kenneth Sloan
KennethRSloan@gmail.com
Vision is the art of seeing what is invisible to others.
On Mar 31, 2016, at 14:48 , Parkinbot rudolf@parkinbot.com wrote:
Meanwhile I've tested a polygon with 900 points and it took 10s. So, we are
talking about efficiency now.
Letting OpenSCADs poor data manipulation ability and unnessecary copies when
cycling aside, it is the algorithm that takes O(n²) steps, because the ear
cut method relies on testing all the rest of the points in the polygon with
each new candidate.
You can cut that down by implementing the second simple scheme Kenneth
mentioned, because recursively cutting a polygon into two, reduces the
complexity by splitting the set of points to be tested by a division factor
and not only by 1. The method is similar to Quicksort.
You start to split with a guess:
- put floor(n/2) points into a first set, and the rest into a second set.
(Alternatively a random split can be used) - test if all points (except the first one) in the first set are left with
respect to the vector that connects the first points of the sets. - if the test is true, recurse both sets separately until done. If not,
cycle your split (or do alternatively another random guess) and continue
with 2.
There are other schemes mentioned in
https://en.wikipedia.org/wiki/Polygon_triangulation#Ear_clipping_method
which are even faster, but wasn't it you who wanted an implementation with a
small footage?
- Rudolf -
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16863.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
Kenneth Sloan wrote
I suspect your algorithm may be O(n^4) and not O(n^2). Testing should
resolve this.
You are right, it might be even worse ;-). But OpenSCAD is not well enough
equipped for implementing iterative solutions. You have random read access
to vector elements, but a random write forces you to do a full copy of the
whole structure. You can't break a for loop, have no while loop, can't even
sum up anything within a for loop - the only way: do it recusively. The full
curse of functional programming :-)
I might give it a try for the second approach tomorrow, but I wouldn't spend
any minute to tweek an algorithm written in OpenSCAD for speed.
- Rudolf -
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16865.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
I am not expert on this but I estimated that the method we are discussing is
O(n^3). The valid_ears() search is O(n^2), due to two nested for loops. The
recursive triangulation has depth n and call valid_ears() once for each
found triangle. I wouldn't blame OpenSCAD language for the low efficiency;
an implementation of this algorithm in C will be faster but it will have
the same asymptotic complexity.
I have tested it with polygons up to 1600 vertices ( a 313 sec run without
display) and it behaved as O(n^2) which is poor for so small cases. The test
polygon I have used has only four ears even in the intermediate steps which
seems to be the worst case for it. This is the starting CCW polygon:
N = 1600;
M = 5;
function test_polygon(N,M,c,r,a) =
concat(
[ for(i=[ a:-2a/N:-a]) [ c - 1.5rcos(i), rsin(i) ] ],
[ for(i=[ -a: 2a/M: a]) [ -c + 1.5rcos(i), rsin(i) ] ] );
p = test_polygon(N,M, 30, 15, 60);
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16869.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
Parkinbot wrote:
OpenSCAD is not well enough equipped for implementing iterative solutions.
You have random read access
to vector elements, but a random write forces you to do a full copy of the
whole structure. You can't break a for loop, have no while loop, can't even
sum up anything within a for loop - the only way: do it recusively. The
full
curse of functional programming :-)
Thanks for pointing this out. General purpose functional languages have a
better set of control structures, and can efficiently update a single
element of an array. It would be reasonable to add array update to
OpenSCAD. We just need a good syntax. I'll think about this.
How do you update an array element without mutable data?
On 1 April 2016 at 11:19, doug moen doug@moens.org wrote:
Parkinbot wrote:
OpenSCAD is not well enough equipped for implementing iterative
solutions. You have random read access
to vector elements, but a random write forces you to do a full copy of the
whole structure. You can't break a for loop, have no while loop, can't
even
sum up anything within a for loop - the only way: do it recusively. The
full
curse of functional programming :-)
Thanks for pointing this out. General purpose functional languages have a
better set of control structures, and can efficiently update a single
element of an array. It would be reasonable to add array update to
OpenSCAD. We just need a good syntax. I'll think about this.
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Abstractly, we could provide a function upd(a,i,x) where a is an array, i
is an index, and x is the new value to store in a[i]. The result is a copy
of a in which a[i] is set to x.
There are various ways to implement this efficiently. There is a field of
study called "functional data structures" which provides solutions. In the
OpenSCAD implementation, values are reference counted. A simple approach is
to check if a has a reference count of 1: If so, we destructively update a,
and return it. If not, we return a copy of a with element i changed to x.
That would be good enough.
On 1 April 2016 at 06:31, nop head nop.head@gmail.com wrote:
How do you update an array element without mutable data?
On 1 April 2016 at 11:19, doug moen doug@moens.org wrote:
Parkinbot wrote:
OpenSCAD is not well enough equipped for implementing iterative
solutions. You have random read access
to vector elements, but a random write forces you to do a full copy of
the
whole structure. You can't break a for loop, have no while loop, can't
even
sum up anything within a for loop - the only way: do it recusively. The
full
curse of functional programming :-)
Thanks for pointing this out. General purpose functional languages have a
better set of control structures, and can efficiently update a single
element of an array. It would be reasonable to add array update to
OpenSCAD. We just need a good syntax. I'll think about this.
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
I see, so fine to mutate variables as long as no other references exist.
Unless it is a literal or a temporary expression result, won't it always be
bound to at least a local variable?
When calling a function and passing a variable as an argument you would
need look ahead and see that the variable was not used again and then
decrement the reference count artificially early.
On 1 April 2016 at 11:52, doug moen doug@moens.org wrote:
Abstractly, we could provide a function upd(a,i,x) where a is an array, i
is an index, and x is the new value to store in a[i]. The result is a copy
of a in which a[i] is set to x.
There are various ways to implement this efficiently. There is a field of
study called "functional data structures" which provides solutions. In the
OpenSCAD implementation, values are reference counted. A simple approach is
to check if a has a reference count of 1: If so, we destructively update a,
and return it. If not, we return a copy of a with element i changed to x.
That would be good enough.
On 1 April 2016 at 06:31, nop head nop.head@gmail.com wrote:
How do you update an array element without mutable data?
On 1 April 2016 at 11:19, doug moen doug@moens.org wrote:
Parkinbot wrote:
OpenSCAD is not well enough equipped for implementing iterative
solutions. You have random read access
to vector elements, but a random write forces you to do a full copy of
the
whole structure. You can't break a for loop, have no while loop, can't
even
sum up anything within a for loop - the only way: do it recusively. The
full
curse of functional programming :-)
Thanks for pointing this out. General purpose functional languages have
a better set of control structures, and can efficiently update a single
element of an array. It would be reasonable to add array update to
OpenSCAD. We just need a good syntax. I'll think about this.
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
@nop.head: Yes, those are good points. Testing if a variable isn't
referenced again is a standard operation in an optimizing compiler. It
could also be used to optimize away unnecessary reference count
manipulations in function calls. If you are calling f(x), and there are no
further references to x, then you could eliminate an increment of x's
reference count when f is called, and a decrement of x's reference count
after f returns. These optimizations would be easier to implement if we had
a compiler.
On 1 April 2016 at 07:15, nop head nop.head@gmail.com wrote:
I see, so fine to mutate variables as long as no other references exist.
Unless it is a literal or a temporary expression result, won't it always
be bound to at least a local variable?
When calling a function and passing a variable as an argument you would
need look ahead and see that the variable was not used again and then
decrement the reference count artificially early.
On 1 April 2016 at 11:52, doug moen doug@moens.org wrote:
Abstractly, we could provide a function upd(a,i,x) where a is an array, i
is an index, and x is the new value to store in a[i]. The result is a copy
of a in which a[i] is set to x.
There are various ways to implement this efficiently. There is a field of
study called "functional data structures" which provides solutions. In the
OpenSCAD implementation, values are reference counted. A simple approach is
to check if a has a reference count of 1: If so, we destructively update a,
and return it. If not, we return a copy of a with element i changed to x.
That would be good enough.
On 1 April 2016 at 06:31, nop head nop.head@gmail.com wrote:
How do you update an array element without mutable data?
On 1 April 2016 at 11:19, doug moen doug@moens.org wrote:
Parkinbot wrote:
OpenSCAD is not well enough equipped for implementing iterative
solutions. You have random read access
to vector elements, but a random write forces you to do a full copy of
the
whole structure. You can't break a for loop, have no while loop, can't
even
sum up anything within a for loop - the only way: do it recusively.
The full
curse of functional programming :-)
Thanks for pointing this out. General purpose functional languages have
a better set of control structures, and can efficiently update a single
element of an array. It would be reasonable to add array update to
OpenSCAD. We just need a good syntax. I'll think about this.
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Would it be such an offense to the functional paradigma of OpenSCAD, which I
guess makes a lot of sense for CSG, but not at all for number crunching, to
allow value altering for local variables within function scope?
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16889.html
Sent from the OpenSCAD mailing list archive at Nabble.com.