Polygon using relative points rather than absolute?

classic Classic list List threaded Threaded
35 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Polygon using relative points rather than absolute?

droftarts
I'm trying to draw a complex shape with the polygon tool, and find it would be easier to build the correct shape if I could place each successive point in the polygon referenced from the previous point, rather than the origin as it normally is when using 'polygon'. This just makes resolving where each point is easier, as it's just [+x,+y] from the previous point, rather than having to add up all the previous points. However, as usual, how to actually program this escapes me! For example, a simple shape would be:

points_absolute = [[0,0],[10,0],[15,10],[10,20],[0,20],[-5,10]];
polygon (points_absolute);

I'd like points to be:
points_relative = [[0,0],[10,0],[5,10],[-5,10],[-10,0],[-5,-10]];

so that each subsequent point is calculated by adding up the proceeding points.

I think there are a number of ways of doing this. Probably the easiest is to iterate through the array, stepping through each point, and adding up the proceeding points in a loop, and creating a new array with them added together. I'm sure this is actually quite trivial, but I just can't quite seem to get it right! Can anyone help?

Ian S
Reply | Threaded
Open this post in threaded view
|

Re: Polygon using relative points rather than absolute?

nophead
Not very efficient as O(n^2) but

points_relative = [[0,0],[10,0],[5,10],[-5,10],[-10,0],[-5,-10]];

function sum_points(list, i) = i >= 0 ? list[i] + sum_points(list, i - 1) : [0, 0];

function rel_to_abs(list) = [
    for(i = [0 : len(list) - 1]) sum_points(list, i)
    ];

points_absolute = rel_to_abs(points_relative);  
echo(points_absolute);
   
polygon(points_absolute);



On 24 May 2016 at 13:08, droftarts <[hidden email]> wrote:
I'm trying to draw a complex shape with the polygon tool, and find it would
be easier to build the correct shape if I could place each successive point
in the polygon referenced from the previous point, rather than the origin as
it normally is when using 'polygon'. This just makes resolving where each
point is easier, as it's just [+x,+y] from the previous point, rather than
having to add up all the previous points. However, as usual, how to actually
program this escapes me! For example, a simple shape would be:

points_absolute = [[0,0],[10,0],[15,10],[10,20],[0,20],[-5,10]];
polygon (points_absolute);

I'd like points to be:
points_relative = [[0,0],[10,0],[5,10],[-5,10],[-10,0],[-5,-10]];

so that each subsequent point is calculated by adding up the proceeding
points.

I think there are a number of ways of doing this. Probably the easiest is to
iterate through the array, stepping through each point, and adding up the
proceeding points in a loop, and creating a new array with them added
together. I'm sure this is actually quite trivial, but I just can't quite
seem to get it right! Can anyone help?

Ian S



--
View this message in context: http://forum.openscad.org/Polygon-using-relative-points-rather-than-absolute-tp17414.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Polygon using relative points rather than absolute?

droftarts
Damn, that was quick! It'll take me longer than that to work out what you actually did... Thanks, nophead!

Ian S
Reply | Threaded
Open this post in threaded view
|

Re: Polygon using relative points rather than absolute?

Parkinbot
In reply to this post by nophead
nophead wrote
Not very efficient as O(n^2) but
Yeah, summing up things with OpenSCAD is not real fun.
Reply | Threaded
Open this post in threaded view
|

Re: Polygon using relative points rather than absolute?

nophead
Here is a better version that should be O(n) and tail recursive, I think. Perhaps easier to understand as well as it is more like a procedural loop.

points_relative = [[0,0],[10,0],[5,10],[-5,10],[-10,0],[-5,-10]];

function rel_to_abs(list, i = 0, sum = [0,0], result = []) =
    i == len(list) ? result : rel_to_abs(list, i + 1, sum + list[i], concat(result, [sum + list[i]]));

points_absolute = rel_to_abs(points_relative);  
echo(points_absolute);
   
polygon(points_absolute);


On 24 May 2016 at 14:35, Parkinbot <[hidden email]> wrote:
nophead wrote
> Not very efficient as O(n^2) but

Yeah, summing up things with OpenSCAD is not real fun.



--
View this message in context: http://forum.openscad.org/Polygon-using-relative-points-rather-than-absolute-tp17414p17417.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Polygon using relative points rather than absolute?

Ronaldo
@nophead
The original problem is O(n^2). There are n*(n+1)/2 sums to be done, where n is the size of the array of points. So there is no O(n) algorithm for it.
Your first solution is better because it is clearer. To avoid recursion, you may consider:
    function sum_list(list, to=0) =
    [ for(i=[0:len(list)-1]) (i<=to) ? 1 : 0 ] * list ;
which is very general and applies to list of numbers, vectors, matrices, etc.
But that is a question of taste. :)
Reply | Threaded
Open this post in threaded view
|

Re: Polygon using relative points rather than absolute?

Ronaldo
Sorry, my analysis is completely wrong. The problem is O(n).
Reply | Threaded
Open this post in threaded view
|

Re: Polygon using relative points rather than absolute?

Ronaldo
However, rel_to_abs may be defined with less parameters:
function rel_to_abs2(list, result = []) =
    len(result) == len(list) ?
        result :
        rel_to_abs2(list, concat(result,
            len(result)==0 ?
                [ list[0] ] :
                [result[len(result)-1] + list[len(result)]]));
Reply | Threaded
Open this post in threaded view
|

Re: Polygon using relative points rather than absolute?

nophead
That is an interesting way of summing a vector by using a dot product with a vector of ones.

I think the tail recursive version will be the fastest because my understanding is OpenScad will optimise it into a loop. It is equivalent to

i = 0;
sum = [0, 0];
result = [];
while(i < len(list))  {
    result = concat(result, sum + list[i]);
    sum = sum + list([i]);
    i = i + 1;
}

Yes you can use less parameters but it makes it less readable and less efficient. Is there any advantage?
 

On 24 May 2016 at 17:55, Ronaldo <[hidden email]> wrote:
However, rel_to_abs may be defined with less parameters:

> function rel_to_abs2(list, result = []) =
>     len(result) == len(list) ?
>         result :
>         rel_to_abs2(list, concat(result,
>             len(result)==0 ?
>                 [ list[0] ] :
>                 [result[len(result)-1] + list[len(result)]]));





--
View this message in context: http://forum.openscad.org/Polygon-using-relative-points-rather-than-absolute-tp17414p17421.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
tp3
Reply | Threaded
Open this post in threaded view
|

Re: Polygon using relative points rather than absolute?

tp3
Using the c-style for() this can be expressed by:

pr = [[0,0],[10,0],[5,10],[-5,10],[-10,0],[-5,-10]];

points = [ for (idx = 0, p = pr[0];idx < len(pr);idx = idx + 1, p = p + pr[idx]) p ];
polygon(points);

Note that this is an experimental feature in the dev snapshots
and needs to be enabled in the preferences ("lc-for-c").

ciao,
  Torsten.

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
-- Torsten
Reply | Threaded
Open this post in threaded view
|

Re: Polygon using relative points rather than absolute?

droftarts
Wow, not surprising I was having trouble with this! I know there is a lot of functionality in functions, but I really don't have the programming skills to make this work, and barely understand the logic behind what you guys have written anyway! However, I'll take a good look at it with the Openscad manual in hand, and work out what you've done, as a way of educating myself (slowly).

Thanks!

Ian S
Reply | Threaded
Open this post in threaded view
|

Re: Polygon using relative points rather than absolute?

Ronaldo
In reply to this post by nophead
nophead wrote
That is an interesting way of summing a vector by using a dot product with
a vector of ones.

I think the tail recursive version will be the fastest because my
understanding is OpenScad will optimise it into a loop. It is equivalent to
I have understood you are comparing here my proposal of sum_list without recursion with your recursive sum_points.
First of all, your sum_points is not tail recursive and always returns [0,0]. A tail recursive version of it might be:
function sum_points2(list, i, sum=[0,0]) =
    i < 0 ?
        sum:
        sum_points2(list, i - 1, sum + list[i]);
I could not compare the running time of both alternatives (tail recursion X non recursion) because my sum_list is limited to lists of less than 1000000 points due to the for inside. Thats is an advantage of a tail-recursive solution indeed.

I did compared the running time of my rel_to_abs2 with your rel_to_abs. They both required approximately the same running time. However, what bugged me was that the running time seems to be a lot more than O(n). May be O(n^2).

Anyway, ll those alternatives are toys compared with the Torsten's code! It runs a lot faster and I could not find a limit of it.
Reply | Threaded
Open this post in threaded view
|

Re: Polygon using relative points rather than absolute?

Ronaldo
In reply to this post by droftarts
droftarts wrote
However, I'll take a good look at it with the Openscad manual in hand, and work out what you've done, as a way of educating myself (slowly).
Ian, to understand the codes people have posted in the thread I would suggest that you study the following topics and their examples:
a) OpenSCAD User Manual/For C/Java/Python Programmers
b) user defined functions,
c) list comprehension

List comprehension is very powerful specially combined with recursive functions and there are some basic techniques of its use that should be learned. Study people code from other threads as well.

To understand Torsten's code you will need to understand the experimental features of the latest snapshot version.

Finally, to understand tail recursion technique in OpenSCAD read the thread on Tail recursion.
Reply | Threaded
Open this post in threaded view
|

Re: Polygon using relative points rather than absolute?

Parkinbot
In reply to this post by tp3
Thorsten,

you are cheating. You use the only imperative backdoor OpenSCAD is equipped with ;-)
Giving examples like this might suck all desperate OpenSCAD programmers forever into a little black hole. Once pandora's box has been opened ...
I can see endlessly nested and expanded C-style for-loops coming up like black clouds on the horizon.

Rudolf
tp3
Reply | Threaded
Open this post in threaded view
|

Re: Polygon using relative points rather than absolute?

tp3
> Von: Parkinbot <[hidden email]>
> you are cheating. You use the only imperative backdoor OpenSCAD
> is equipped with ;-)
>
Nah, if lisp can have a loop macro, we should also have
something controversial to discuss about :-).

> Giving examples like this might suck all desperate OpenSCAD
> programmers forever into a little black hole. Once pandora's
> box has been opened ... I can see endlessly nested and
> expanded C-style for-loops coming up like black clouds on
> the horizon.
>
Yeah, it's possible to abuse it and make horrible code, but
that's probably true for most constructs in pretty much all
languages.
Right now the feature is still marked as experimental so it
would not go automatically into the next release, so there's
still a chance to discuss it. But it seems to help expressing
some things easily that require much more effort from people
who are not so much into functional programming.

You also said: "Yeah, summing up things with OpenSCAD is
not real fun."

Which language construct could make it fun again? With
the current list of language changes, it might be easy
to just add another change if it makes things easier.

ciao,
  Torsten.

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
-- Torsten
Reply | Threaded
Open this post in threaded view
|

Re: Polygon using relative points rather than absolute?

Kenneth Sloan
There’s an old saying: “It is possible to write FORTRAN programs in *any* language”.

Kenneth Sloan
Vision is the art of seeing what is invisible to others.

On May 25, 2016, at 11:13, Torsten Paul <[hidden email]> wrote:

Von: Parkinbot <[hidden email]>
you are cheating. You use the only imperative backdoor OpenSCAD
is equipped with ;-)

Nah, if lisp can have a loop macro, we should also have
something controversial to discuss about :-).

Giving examples like this might suck all desperate OpenSCAD
programmers forever into a little black hole. Once pandora's
box has been opened ... I can see endlessly nested and
expanded C-style for-loops coming up like black clouds on
the horizon.

Yeah, it's possible to abuse it and make horrible code, but
that's probably true for most constructs in pretty much all
languages.
Right now the feature is still marked as experimental so it
would not go automatically into the next release, so there's
still a chance to discuss it. But it seems to help expressing
some things easily that require much more effort from people
who are not so much into functional programming.

You also said: "Yeah, summing up things with OpenSCAD is
not real fun."

Which language construct could make it fun again? With
the current list of language changes, it might be easy
to just add another change if it makes things easier.

ciao,
 Torsten.

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Polygon using relative points rather than absolute?

nophead
In reply to this post by Ronaldo


On 25 May 2016 at 13:48, Ronaldo <[hidden email]> wrote:
nophead wrote
> That is an interesting way of summing a vector by using a dot product with
> a vector of ones.
>
> I think the tail recursive version will be the fastest because my
> understanding is OpenScad will optimise it into a loop. It is equivalent
> to

I have understood you are comparing here my proposal of sum_list without
recursion with your recursive sum_points.
First of all, your sum_points is not tail recursive and always returns
[0,0]. A tail recursive version of it might be:

> function sum_points2(list, i, sum=[0,0]) =
>     i < 0 ?
>         sum:
>         sum_points2(list, i - 1, sum + list[i]);

No I was comparing my second version of rel_2_abs with the first version with your non-recursive sum_list.
 

I could not compare the running time of both alternatives (tail recursion X
non recursion) because my sum_list is limited to lists of less than 1000000
points due to the for inside. Thats is an advantage of a tail-recursive
solution indeed.

I did compared the running time of my rel_to_abs2 with your rel_to_abs. They
both required approximately the same running time. However, what bugged me
was that the running time seems to be a lot more than O(n). May be O(n^2).

That is probably because adding to the end of a list is proportional to the length of the list when it involves a new memory allocation and then a copy. I expect that becomes dominant when the list gets big.
 

Anyway, ll those alternatives are toys compared with the Torsten's code! It
runs a lot faster and I could not find a limit of it.

Perhaps list comprehensions have some way of growing the list without copying it as the list being built is expected to grow.




--
View this message in context: http://forum.openscad.org/Polygon-using-relative-points-rather-than-absolute-tp17414p17427.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Polygon using relative points rather than absolute?

Parkinbot
In reply to this post by tp3
tp3 wrote
Yeah, it's possible to abuse it and make horrible code, but
that's probably true for most constructs in pretty much all
languages.
Ok, but this languages offer proper constructs, which are neglected for horribleness, OpenSCAD doesn't.

tp3 wrote
Which language construct could make it fun again? With
the current list of language changes, it might be easy
to just add another change if it makes things easier.
Good point. Seriously spoken, I'd be happy to have this imperative backdoor as a feature to do exactly what you do, but NOT within the head of the forloop. Say as a feature of let:

<code>
echo (pandora(10));  

function pandora(n) =
 let(a = 1)
 [for (i=[1:n])
   let(a = a+i) [i, a]];
</code>

Currently this code answers with functional semantics:
[[1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7], [7, 8], [8, 9], [9, 10], [10, 11]]
so it uses outer scope 'a' as R-value set an inner scope L-value 'a'.

with imperative semantics you'd obviously get (and that's the aim of the game):
[[1, 2], [2, 4], [3, 7], [4, 11], [5, 16], [6, 22], [7, 29], [8, 37], [9, 46], [10, 56]]

To discriminate between definition (with implicit declaration) and (now forbidden) update of a local outer (or even inner) scope variable, pandora could introduce a 'set' keyword for the new semantics. And the expression with imperative semantics would be:

<code>
function pandora(n) =
 let(a = 1)
 [for (i=[1:n])
   set(a = a+i) [i, a]];
</code>

Reply | Threaded
Open this post in threaded view
|

Re: Polygon using relative points rather than absolute?

doug.moen
Hi Parkinbot. I have accepted your challenge, and designed a way to add mutable variables to OpenSCAD without violating the declarative semantics.

The benefit is: it's easier to port traditional algorithms to OpenSCAD, because now you can use standard imperative idioms. For example, you can implement an efficient quicksort with in-place array update.

The drawback is: more language complexity. OpenSCAD is now a hybrid of a declarative language with an imperative language.

I honestly don't know if we actually want to make this change. Do we want to turn OpenSCAD into a general purpose programming language? However, it's worth having the discussion, since the topic is often raised in the forum, so I wrote a design paper to show people what this would look like.


Doug Moen.

On 25 May 2016 at 16:22, Parkinbot <[hidden email]> wrote:
tp3 wrote
> Yeah, it's possible to abuse it and make horrible code, but
> that's probably true for most constructs in pretty much all
> languages.

Ok, but this languages offer proper constructs, which are neglected for
horribleness, OpenSCAD doesn't.


tp3 wrote
> Which language construct could make it fun again? With
> the current list of language changes, it might be easy
> to just add another change if it makes things easier.

Good point. Seriously spoken, I'd be happy to have this imperative backdoor
as a feature to do exactly what you do, but NOT within the head of the
forloop. Say as a feature of let:

<code>
echo (pandora(10));

function pandora(n) =
 let(a = 1)
 [for (i=[1:n])
   let(a = a+i) [i, a]];
</code>

Currently this code answers with functional semantics:
[[1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7], [7, 8], [8, 9], [9, 10],
[10, 11]]
so it uses outer scope 'a' as R-value set an inner scope L-value 'a'.

with imperative semantics you'd obviously get (and that's the aim of the
game):
[[1, 2], [2, 4], [3, 7], [4, 11], [5, 16], [6, 22], [7, 29], [8, 37], [9,
46], [10, 56]]

To discriminate between definition (with implicit declaration) and (now
forbidden) update of a local outer (or even inner) scope variable, pandora
could introduce a 'set' keyword for the new semantics. And the expression
with imperative semantics would be:

<code>
function pandora(n) =
 let(a = 1)
 [for (i=[1:n])
   set(a = a+i) [i, a]];
</code>





--
View this message in context: http://forum.openscad.org/Polygon-using-relative-points-rather-than-absolute-tp17414p17436.html
Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org




_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
Reply | Threaded
Open this post in threaded view
|

Re: Polygon using relative points rather than absolute?

Parkinbot
Hi Doug,

that's a great paper. Thanks for accepting the challenge. It reads interesting and I can almost smell the wind of progress, it will bring into the language. I never really understood, why functions in OpenSCAD shouldn't be imperative, as they provide a well defined interface to interact with modules in a purely functional context. Your paper shows, that this path is viable.

I'm not as deep into the matter as you are, so allow me some questions and thoughts concerning some 'redundancies'.  
 
valof{ expr};
marks 'expr' as imperative. I understand it as the central modifier (context switch) to annouce imperative code. However, as I read it, it will allow for 'mixed' semantics, which makes things complicated. For this reason more markers have to be introduced.

var x := expr;
marks 'x' as mutable and will be allowed only within valof{} expressions. Isn't 'valof{}' + 'var' + ':=' kind of triple marking? 'var' is ok in a function/procedure prototype to mark output variables.
In a non-mixed context 'let' and  '=' might have just overloaded semantics, like in 'for' headers (more obvious in C-style), where mutable variables also may be declared in common style.  

do{list};
is it used as a separator between both worlds? Wouldn't it be obsolet in a non-mixture enviroment?

To be able to define functional semantics code within an imperative context, some counterpart modifier could be introduced ...

Rudolf

12