[SciPy-User] Sort geometric data by proximity

[Charles R Harris]

On Sat, May 22, 2010 at 8:38 PM, Charles R Harris <charlesr.harris at gmail.com
> wrote:

>
>
> On Sat, May 22, 2010 at 6:46 PM, Gary Ruben <gruben at bigpond.net.au> wrote:
>
>> I've previously done something similar to David's suggestion - used a
>> Delaunay triangulation to get the points, then used NetworkX (NX) to
>> turn this into a Euclidean/Geometric graph structure (Google
>> delaunay2d_nx.py). The minimum spanning tree of this graph can be found
>> and traversed by NX to visit all the nodes in the correct order. I used
>> the NX dfs_preorder() traversal algorithm, culled off the side branches
>> and spline fit the remaining ordered nodes. You could probably use
>> astar_path() instead - I don't think this was available when I did it.
>> Either way, you would also want to duplicate the first or last node to
>> close the path.
>>
>>
> That's interesting. From the homological point of view there are two
> cycles, an inner one and an outer one. I suppose the orientation of any
> triangle would then be the sign of the determinant of the matrix formed from
> the vectors of it's vertices in some given order, although there is probably
> a more efficient way to assign orientations. Remove the edges that cancel
> out and it should be easy to find a cycle. I'll bet there is software out
> there for that problem.
>
>
Umm, boundaries, not cycles ;)

Chuck
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.scipy.org/pipermail/scipy-user/attachments/20100522/7ce8a56d/attachment.html>