[SciPy-User] Sort geometric data by proximity

[Chris Michalski]

Haven't worked a problem like this, but it seemed to me that combining the fact that nearby points are close in (x,y) position, couldn't you compute two metrics.  The first metric is the measure of distance from each point on the edge to an arbitrary point (which could be inside or outside the boomerang).  Since the distance isn't unique (there could be the same distance to two or three points on the surface) then construct a metric with is the angle to the point. Sort the distance metric.  Then rely on the fact that the angle metric can't change quickly between adjacent points to select from a small range in the sorted distance metric which point is closest.  This should put adjacent points close enough together that the true nearest neighbor involves a search over a only couple of points either side of any individual point.  You might be able to sort both metric and run the search jumping between metrics.

Chris


On May 21, 2010, at 2:46 PM, Anne Archibald wrote:

> On 21 May 2010 17:07,  <DParker at chromalloy.com> wrote:
>> I have a set of geometric data in x, y plane that represents a section of a
>> turbine airfoil. The shape looks something like a fat boomerang with the
>> coordinates wrapping around the entire shape (a completely closed loop). The
>> coordinate points are in a random order and I need to sort or fit them by
>> proximity to develop a dataset containing continuos shape of the airfoil.
>> 
>> I started looking through the interpolation functions but I would need a
>> method that ignores the order of the data (fits based on proximity of the
>> points) and can handle data that forms a closed loop.
>> 
>> The points are spaced closely enough along the airfoil surface so that they
>> could be sorted by nearest neighbor - start with the first point find the
>> next closest point and continue until all the points are "consumed".
>> 
>> Any advice or pointers would be greatly appreciated.
> 
> The most direct approach is to pick a start point at random, then ask
> for its two nearest neighbours. Then pick one, and loop. For each
> point ask for its two nearest neighbours; one should be the last point
> you looked at, and one should be the next point on your curve. If ever
> this isn't true, you've found some place where your points don't
> sample closely enough to clearly describe the turbine shape. When you
> get your first point back, you're done.
> 
> As described, this is a fairly slow process, but the dominating
> operation is not the python looping overhead but the time it takes to
> find each nearest neighbour. Fortunately scipy.spatial includes an
> object designed for this sort of problem, the kd-tree. So the way I'd
> solve your problem is construct a kd-tree from your array of points,
> then run a query asking the the three closest neighbours of each of
> your original points (three because each point is its own closest
> neighbour). Then just write a python loop to walk through the array of
> neighbours as I described above. This process should be nice and fast,
> and will diagnose some situations where you've inadequately sampled
> your object.
> 
> Anne
> 
>> 
>> David Parker
>> _______________________________________________
>> SciPy-User mailing list
>> SciPy-User at scipy.org
>> http://mail.scipy.org/mailman/listinfo/scipy-user
>> 
>> 
> _______________________________________________
> SciPy-User mailing list
> SciPy-User at scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-user