[SciPy-User] Sort geometric data by proximity

[Anne Archibald]

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
>
>