Sorting a vector of points

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

Sorting a vector of points

gounthar
Hi there,

I'd like to "sort" a vector of points, to avoid too many "if" in my code.
I've seen that you can  sort
<https://en.wikibooks.org/wiki/OpenSCAD_User_Manual/The_OpenSCAD_Language#Sorting_a_vector>  
a 1D vector.
What I'd like to do is to have the points ordered such as the second point
has a higher X or Y than the first, and so on.
My goal is to create some kind of "mesh" to link existing parts.
<http://forum.openscad.org/file/t2607/EJ85XU4e7o.png>
I think I could write this with a little amount of sweat but... Could it be
already part of the OpenSCAD toolbox, or have you seen it already written
somewhere?

Thanks a bunch.

Bruno



--
Sent from: http://forum.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: Sorting a vector of points

TLC123
Need more details here





--
Sent from: http://forum.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: Sorting a vector of points

TLC123
In reply to this post by gounthar
Sounds like you want to sort a list of [[x,y],[x,y],[x,y]...] by the x+y?
<http://forum.openscad.org/file/t1678/sortx%2By.png>
Sorting by x> or y> doesn't make hole lot of sense to me.
it would look weird.
<http://forum.openscad.org/file/t1678/sortxory.png>




--
Sent from: http://forum.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: Sorting a vector of points

Ronaldo
An alternative is a lexicographic sort where 

  x[i]>x[i-1] or y[i]>=y[i-1]  for all i>0

You may find a lexicographic sort in the library BOSL2:



Em qua., 30 de dez. de 2020 às 07:08, TLC123 <[hidden email]> escreveu:
Sounds like you want to sort a list of [[x,y],[x,y],[x,y]...] by the x+y?
<http://forum.openscad.org/file/t1678/sortx%2By.png>
Sorting by x> or y> doesn't make hole lot of sense to me.
it would look weird.
<http://forum.openscad.org/file/t1678/sortxory.png>




--
Sent from: http://forum.openscad.org/

_______________________________________________
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: Sorting a vector of points

gounthar
In reply to this post by TLC123
Thanks for your answer TLC123, I'll try to do a quicksort by hand then.
It's maybe a stupid idea to sort my data this way; I'll implement it and see
if that answers my issue.



--
Sent from: http://forum.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: Sorting a vector of points

gounthar
In reply to this post by Ronaldo
On Wed, Dec 30, 2020 at 3:09 PM Ronaldo Persiano <[hidden email]> wrote:
> An alternative is a lexicographic sort where
>   x[i]>x[i-1] or y[i]>=y[i-1]  for all i>0
> You may find a lexicographic sort in the library BOSL2:
> https://github.com/revarbat/BOSL2/wiki/arrays.scad#sort
Thanks a lot Ronaldo, that sounds really good for my use case.

Bruno

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

Re: Sorting a vector of points

lar3ry
In reply to this post by TLC123
TLC123 wrote
> Sounds like you want to sort a list of [[x,y],[x,y],[x,y]...] by the x+y?
> &lt;http://forum.openscad.org/file/t1678/sortx%2By.png&gt; 
> Sorting by x> or y> doesn't make hole lot of sense to me.
> it would look weird.
> &lt;http://forum.openscad.org/file/t1678/sortxory.png&gt; 

It only looks weird if you want to build something with a sorted list.
Could it be used as a function in preview to build a bounding box?





--
Sent from: http://forum.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: Sorting a vector of points

adrianv
If you want to make a bounding box from a list you need to treat the x and y
coordinates independently.  Mixing them together with addition isn't useful.  

The idea of sorting by x+y is like sorting on the distance your points are
away from the line y=-x.  Could be useful for something, but note that
points on lines with slope -1 are all "equal, so [0,0] and [-1000,1000] are
"equal" and would hence have indeterminate order unless you impose a
secondary ordering.  This is analogous to sorting just on x and ignoring
y---you just rotate by 45 deg before doing the sort.  

You could sort on distance from a point, e.g. norm([x,y]-p) for some point
p.  Then circles will be "equal".  

Lexicographic sort (noted by Ronaldo) is how words are sorted in a
dictionary: you sort on the first vector component ("letter") that doesn't
match.  It doesn't make geometrical sense, but it puts an order on every
vector---two vectors are "equal" in this sorting only if they match at every
entry.  



lar3ry wrote

> TLC123 wrote
>> Sounds like you want to sort a list of [[x,y],[x,y],[x,y]...] by the x+y?
>> &lt;http://forum.openscad.org/file/t1678/sortx%2By.png&gt; 
>> Sorting by x> or y> doesn't make hole lot of sense to me.
>> it would look weird.
>> &lt;http://forum.openscad.org/file/t1678/sortxory.png&gt; 
>
> It only looks weird if you want to build something with a sorted list.
> Could it be used as a function in preview to build a bounding box?
>
>
>
>
>
> --
> Sent from: http://forum.openscad.org/
>
> _______________________________________________
> OpenSCAD mailing list

> Discuss@.openscad

> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org





--
Sent from: http://forum.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: Sorting a vector of points

lar3ry
adrianv wrote
> If you want to make a bounding box from a list you need to treat the x and
> y
> coordinates independently.  Mixing them together with addition isn't
> useful.  

Right. Sorry, I should have mentioned that I was referring to TLC123's
"Sorting by x> or y>", with emphasis on the OR.

After I posted, I realized that since we don't  keep track of geometry in
preview, it means that the bounding boxes would have to be calculated from a
point on each object, and talking tinto account every translation,
extrusion, mirror, rotation, etc. Clearly not conducive to having it display
the preview sometime in the coming week.

But then I wondered... During a preview, it has to draw everything. How much
overhead would it cause to compare and keep the maximum values on each axis
as it is being drawn. I know this would have to take into account
difference(), but I don't know what else might be a problem.





--
Sent from: http://forum.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: Sorting a vector of points

adrianv
I think that "x> or y>" was a terse restatement of lexicographic sort,
meaning that you apply the compound condition, not one condition or the
other one.  

I'm not sure what you want the bounding box of.  If you have a point set you
can get its bounding box.  If you're doing operations to the point set that
give you a new point set you would calculate the bounding box from the final
results.  Note that it is possible to compute a bounding box geometrically.
(BOSL2 has a module that does this.)  I'm not sure how fast it is, though.  


lar3ry wrote

> adrianv wrote
>> If you want to make a bounding box from a list you need to treat the x
>> and
>> y
>> coordinates independently.  Mixing them together with addition isn't
>> useful.  
>
> Right. Sorry, I should have mentioned that I was referring to TLC123's
> "Sorting by x> or y>", with emphasis on the OR.
>
> After I posted, I realized that since we don't  keep track of geometry in
> preview, it means that the bounding boxes would have to be calculated from
> a
> point on each object, and talking tinto account every translation,
> extrusion, mirror, rotation, etc. Clearly not conducive to having it
> display
> the preview sometime in the coming week.
>
> But then I wondered... During a preview, it has to draw everything. How
> much
> overhead would it cause to compare and keep the maximum values on each
> axis
> as it is being drawn. I know this would have to take into account
> difference(), but I don't know what else might be a problem.
>
>
>
>
>
> --
> Sent from: http://forum.openscad.org/
>
> _______________________________________________
> OpenSCAD mailing list

> Discuss@.openscad

> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org





--
Sent from: http://forum.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: Sorting a vector of points

lar3ry
adrianv wrote
> I think that "x> or y>" was a terse restatement of lexicographic sort,
> meaning that you apply the compound condition, not one condition or the
> other one.  

OK. I took it as meaning single axes, and I was thinking that this could
produce a bounding box.

<quote.
I'm not sure what you want the bounding box of.  If you have a point set you
can get its bounding box.  If you're doing operations to the point set that
give you a new point set you would calculate the bounding box from the final
results.  Note that it is possible to compute a bounding box geometrically.
(BOSL2 has a module that does this.)  I'm not sure how fast it is, though.  
&lt;/quote>

Not sure what you mean by a "point set". I'm definitely a novice in this
area.

I'd like a bounding box of the final object or objects, but after preview.
So an ideal result would be to be able to echo nMin, nMax, (where n is an
axis), and/or the length of the objects axes.

It's easy enough to do with a program run against an ASCII stl, but it would
be nice if it could be done in OpenSCAD.

Barring that, a center parameter for import() would be nice. That's mostly
what I would use a bounding box for.




--
Sent from: http://forum.openscad.org/

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