Simple polygon triangulation
To put my simple polygon triangulation in use, I need to check before whether
the polygon is in fact simple and warn the user otherwise. I wrote a simple
version of a simple polygon check. I thought it would be O(n^2) for there is
two nested loops of constant time edge-edge intersection tests. However, my
time tests have shown a much greater order, even bigger than O(n^3). I
attached the code with the hope that someone could show me the mistake of
my time analysis.
simple_polygon_test.scad
http://forum.openscad.org/file/n16983/simple_polygon_test.scad
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16983.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
In OpenSCAD, 'x || y' has shortcut evaluation semantics. y is not evaluated
if x is true.
Similarly, 'x && y' has shortcut evaluation semantics. y is not evaluated
if x is false.
This matters not just for performance, but also because functions can abort
if passed bad arguments. So you may want to write 'in_range(x) && f(x)' in
some cases, testing that x is in range before calling f (so that f doesn't
abort on the argument x).
Currently this happens due to recursion and iteration limits, but OpenSCAD
is adding an assert() expression so that you can explicitly test for bad
function arguments and abort with a message that's useful for debugging.
There is an 'assert' expression in the pipeline, in a recent pull request
from Torsten.
So we have two features that compromise mathematical purity: shortcut
evaluation, and partial functions (functions which abort when passed a bad
argument). As a result, the || and && operators are not fully commutative.
But, all of the general purpose pure functional programming languages make
the same compromise, which I think is necessary for practical reasons.
On 6 April 2016 at 08:25, G. Wade Johnson gwadej@anomaly.org wrote:
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:
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
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
https://en.wikipedia.org/wiki/Short-circuit_evaluation#Support_in_common_programming_languages
has a nice table of the languages that support short-circuit evaluation vs
"eager" evaluation of boolean operations. Many support both types of
evaluation but the majority just use short-circuit evaluation.
Cheers,
Len.
On 7 April 2016 at 05:33, doug moen doug@moens.org wrote:
In OpenSCAD, 'x || y' has shortcut evaluation semantics. y is not
evaluated if x is true.
Similarly, 'x && y' has shortcut evaluation semantics. y is not evaluated
if x is false.
This matters not just for performance, but also because functions can
abort if passed bad arguments. So you may want to write 'in_range(x) &&
f(x)' in some cases, testing that x is in range before calling f (so that f
doesn't abort on the argument x).
Currently this happens due to recursion and iteration limits, but OpenSCAD
is adding an assert() expression so that you can explicitly test for bad
function arguments and abort with a message that's useful for debugging.
There is an 'assert' expression in the pipeline, in a recent pull request
from Torsten.
So we have two features that compromise mathematical purity: shortcut
evaluation, and partial functions (functions which abort when passed a bad
argument). As a result, the || and && operators are not fully commutative.
But, all of the general purpose pure functional programming languages make
the same compromise, which I think is necessary for practical reasons.
On 6 April 2016 at 08:25, G. Wade Johnson gwadej@anomaly.org wrote:
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:
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
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
doug.moen wrote
In OpenSCAD, 'x || y' has shortcut evaluation semantics. y is not
evaluated
if x is true.
I know that, and it is easy to test out. Shortcut evaluation is common (but
misleading semantics with many caveats) in procedural languages. In a
functional language such an assumption about implementation is not allowed,
as it can break code, when automatically parallelized. Think about a
multithreaded version of OpenSCAD, which I hope will be available sooner or
later ;-)
So why not implement a mighty pattern like a 'breaking for-loop' immediately
with neutral semantics.
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16991.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
On 04/06/2016 08:57 PM, Parkinbot wrote:
So why not implement a mighty pattern like a 'breaking for-loop'
immediately with neutral semantics.
Did you have a look at the c-style for loop? As mentioned before,
I think that should allow breaking the loop based on a condition
for most cases.
Looking at the commit history that should be available in all
dev snapshots (merged 2016-01-26). It needs to be enabled in the
Preferences->Features.
echo([ for (a = 0;a < 10 && rands(0, 1, 1)[0] > 0.2;a = a + 1) a ]);
ciao,
Torsten.
Do you mean Lisp is not really functional language? :-)
From: Discuss [discuss-bounces@lists.openscad.org] on behalf of Parkinbot [rudolf@parkinbot.com]
Sent: 06 April 2016 21:57
To: discuss@lists.openscad.org
Subject: Re: [OpenSCAD] Simple polygon triangulation
doug.moen wrote
In OpenSCAD, 'x || y' has shortcut evaluation semantics. y is not
evaluated
if x is true.
I know that, and it is easy to test out. Shortcut evaluation is common (but
misleading semantics with many caveats) in procedural languages. In a
functional language such an assumption about implementation is not allowed,
as it can break code, when automatically parallelized. Think about a
multithreaded version of OpenSCAD, which I hope will be available sooner or
later ;-)
So why not implement a mighty pattern like a 'breaking for-loop' immediately
with neutral semantics.
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16991.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
Ah yes, thanks, I got that and was happy about it.
The comment you cited was just an answer to the tail-recursive scheme of
Ronaldo.
The thread is holding to many themes now - so confusion grows.
tp3 wrote
Did you have a look at the c-style for loop? As mentioned before,
I think that should allow breaking the loop based on a condition
for most cases.
Looking at the commit history that should be available in all
dev snapshots (merged 2016-01-26). It needs to be enabled in the
Preferences->Features.
echo([ for (a = 0;a < 10 && rands(0, 1, 1)[0] > 0.2;a = a + 1) a ]);
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16994.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
Ronaldo, this code is hard to understand and indeed not at all as simple as
it could be - so it would find 'false' when applied to itself ;-)
A simple polygon is not self-intersecting. So, if there are no two lines
that intersect, the predicate will find a 'true'. I guess this is, what you
are testing.
It was easier for me to implement it, to also get acquainted with the new
breakable C style for-loop, Thorsten had pointed out. The code is fully
iterative and in my tests I found the expected O(n²) behavior.
The idea is (as already mentioned in an earlier answer), that if two lines
AB and CD intersect, the polygon ACBD will be convex in a CW or CCW sense.
This is linearly tested by the function is_intersecting(), which simply
recurres to is_left(). The rest is just a double breaking for-loop around
this convexity test.
P = test_polygon(N,M, 30, 15, 60);
polygon(P);
echo(is_simple(P));
// true if polygon S is simple
function is_simple(S) =
let(n=len(S))
n<4?true:
n==4?is_intersecting(S, 0, 2) || is_intersecting(S, 1, 3):
let (res = [for(i=0; i
<
n-2 && is_simpleline(S, i); i=i+1) 1])
len(res)==n-2;
// true if segment S[a]S[a+1] is not intersecting any other segment in S
function is_simpleline(S, a) =
let(n=len(S))
let(res = [for(i=a+2; i<a+n-2 && !is_intersecting(S, a%n,
i%n); i=i+1) 1])
len(res)==n-4;
// true, if lines S[a]S[a+1] and S[b]S[b+1] intersect, convexity test
function is_intersecting(S, a, b) =
let(n=len(S), P=[S[a%n], S[b%n], S[(a+1)%n], S[(b+1)%n]])
let (sum = [for(i=[0:3]) if (is_left(P[i%4], P[(i+1)%4], P[(i+2)%4]))
1])
len(sum) == 4 || len(sum) == 0;
// true if c is left of a---
>
b
function is_left(a, b, c) = (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-tp16755p16996.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
Parkinbot wrote
Ronaldo, this code is hard to understand and indeed not at all as simple
as it could be - so it would find 'false' when applied to itself ;-)
You are right, my code is a lot more complex than yours. And it is not easy
to follow. But there is a reason for that. And it is simple. :)
Your code use loop escapes when it finds two intersecting polygon edges.
But, if the polygon is simple, each pair of edges will be tested with the
time consuming function is_intersecting(). So the worst case for your method
is a simple polygon which is, by the way, my most common case.
I included a lot of previous simple tests before the hard part
is_intersecting() is called. The sorted data structure the code builds is
intended to allow the elimination of far away edges without lengthy
geometrical tests.
As yours, my algorithm is O(n^2). It has exactly the same loops. However, I
am able to escape the loops eventually before all pairs is considered even
with simple polygons. Comparing times: my method takes 60sec in my machine
to approve as simple the test case with 1000 vertices; your method took
107sec. It is not a good advantage.
I found two reasons for my code is so slow. First, I was not exploring the
full potential of the data structure. But I found a very simple test that
speed up the method a lot. And I found also that the implementation of
quicksort I use is far from efficient. And, as it is not tail-recursive, it
generates a stack overflow for more than 2000 records.
So, I seached for other sorting methods which would allow tail recursion.
And I could code a version of the merge sort where the merge process is
tail-recursive. I tested it with arrays of 20000 elements without stack
overflow. And it is very fast, sorting a random array of 20000 elements in
32sec.
With this sorting method and a best elimination rule in the simple polygon
test, my method got a new life. It is able to identify a simple polygon
(from my test case) with 8000 edges in 15sec. A huge gain!
If you or anyone is interested in this new version, I can make it available
here. I will discuss my experience with the implementation of the sorting
methods in another thread.
I am sure there are methods a lot better and with a lower order. But any of
them would need a very complex implementation even in C. So, code complexity
sometimes is favorable.
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16997.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
I thought it would be O(n^2) for there is two nested loops of constant
time edge-edge intersection tests. However, my time tests have shown a
much greater order, even bigger than O(n^3).
From this, I thought you are trying to find a O(n^2) version of a general
is_simple test.
But what you write now, sounds interesting. I still haven't fully understood
the short cutting idea behind your code and how it takes advantage of
quicksort in general. Or does it just show its advantages to the subset of
polynoms you are considering for, and you are exploiting a know structural
feature?
To learn from your approach would you elaborate on its ideas?
--
View this message in context: http://forum.openscad.org/Simple-polygon-triangulation-tp16755p16998.html
Sent from the OpenSCAD mailing list archive at Nabble.com.