We closed this forum 18 June 2010. It has served us well since 2005 as the ALPHA forum did before it from 2002 to 2005. New discussions are ongoing at the new URL http://forum.processing.org. You'll need to sign up and get a new user account. We're sorry about that inconvenience, but we think it's better in the long run. The content on this forum will remain online.
IndexProgramming Questions & HelpSyntax Questions › drawing shape around points
Page Index Toggle Pages: 1
drawing shape around points (Read 940 times)
drawing shape around points
Aug 27th, 2009, 2:44pm
 
So, let me start with the usual newbie intro. Yes... I am, and I appreciate any assistance.

My question is this.  Given a set of points (could be any number, random locations, ie, not known in advance), how might you go about connecting the outer points such that a shape incompasses them (identifying  all the outermost vertexis so I can use begin/endshape.)   Thanks for your help!

Bruce




Re: drawing shape around points
Reply #1 - Aug 27th, 2009, 3:09pm
 
Hey, for a noob you sure ask tricky questions :P

If you have a bunch of points, represents as (x,y)s, and they're scattered randomly all over your sketch, you can define their distance from the center point as:

dist( x, y, width/2, height/2 );

provided your points are stored in an array, probably most conveniently a Pvector[], you then need to run through the list repeatedly, finding the points with the greatest distance and adding them to your chain, and marking them as checked so the next run finds the next-most-distant point.

First tricky part: how to tell when you've got enough points to encompass all the others  I.e. you could run through the loop to select the 100 most distant points, or only 3.  3 points will probably not encompass all the others, and 100 will probably include too many "inner" points.  I don't have a quick answer to that, other than testing the shape at each iteration to see if all the other points lie within its borders, which alone is a tricky feat for which most people bring in an outside library like http://ricardmarxer.com/geomerative/.

Then you have to connect the points you've selected as "outer" points,  which is a little easier: make a list of the outer points, pick one to start with, and link it to the point in the list that is closest.  Remove both points from the list and continue linking the closest point to the chain until the list is empty, and draw the shape with endShape(CLOSE); to connect to the first point.  (I think this would work, anyway.)

Needless to say, it would be a lot easier to write a routine to put random points within a given border.  But, what's it for  Maybe there is another way to get the effect you're after.  Or, maybe there's a really clever way to do what you describe.

--Ben

PS: links from friends:
http://en.wikipedia.org/wiki/Delaunay_triangulation
http://en.wikipedia.org/wiki/Convex_hull

Oh, and check out:
http://www.leebyron.com/else/mesh/
Re: drawing shape around points
Reply #2 - Aug 27th, 2009, 3:26pm
 
Thanks for the suggestion Ben.  I don't know the coordinates ahead of time (well I do, but I need a programmatic solution for drawing as I will be using this with many datasets).

the first possible solution I thought of (but being a newbie it is a solution I haven't figured out how to code yet), goes something like this.
1. find the top left point (but i suppose you could start anywhere) - this is easy enough to do
2. look to see if any points exist along a path extending straight up from this point. if no, adjust the angle one degree to the right, check along this new path, and so on till next point is found
3. when point is found from the above, repeat the same process from the newly found point to find the next point.

think this would work? any idea what the code would look like for this Smiley

thanks again!
Bruce
Re: drawing shape around points
Reply #3 - Aug 27th, 2009, 7:58pm
 
I think that method will give you a lot of trouble in practice, partly because the lines are pretty much guaranteed to miss distant points, sometimes.  Even if the angle increment is very small, the lines will diverge as you travel away from the starting point.  It also assumes entirely convex shapes -- do you want to be able to "shrinkwrap" into concave areas

It does matter why you want the shape: for example, if you want a crude method of obtaining an outline and don't care how long it takes, you could just make a giant polygon by connecting each point to all the others, first with a black strokeWeight of 4 or so, then another on top with no stroke, all filled with white, for the illusion of a single black-outlined white shape.  (Again, like most solutions, this doesn't give you concave areas.)

Here's an example of what I mean:
http://benhem.com/dev/pointGroup

Computational cost  a mere [number of points] !  * 2
Edit: whoops, not actually that extreme.  The cost is really n*((n+1)/2) where n is the number of points.   *2 again because it's being drawn twice.  I was thinking of it as 100*99*98... instead of 100+99+98....

--Ben
Page Index Toggle Pages: 1