       Re: Using Nearest on a group of points

• To: mathgroup at smc.vnet.net
• Subject: [mg117623] Re: Using Nearest on a group of points
• From: Peter Pein <petsie at dordos.net>
• Date: Thu, 24 Mar 2011 06:32:42 -0500 (EST)
• References: <im9sk8\$g5j\$1@smc.vnet.net>

```Am 22.03.2011 11:11, schrieb Martin VavpotiÄ?:
> Hello. I need some help with the function Nearest.
>
> I have a groups of points, each with two coordinates (x,y), describing
> a connected shape (the last point is a neighbor to the first one). The
> initial order of these points is completely scrambled but I need them
> to follow one another so their sequence describes a combined shape. I
> thought of using the Nearest function but there is a problem.
> Somewhere in the middle of my shape is a large gap where no points
> reside. I fear that if I use Nearest, the function will find the wrong
> point.
>
> What I need is for function Nearest to ignore points already sorted
> and search only for points that have not been used yet.
>

I've got two possible solutions; one is ugly and the other is probably slow:

get some "separated" random data:
In:= pts = RandomSample[Union[RandomReal[{0, 1},
{5, 2}], RandomReal[{5, 6}, {5, 2}]], 10]
Out=
{{5.05492,5.67991},{5.26878,5.95573},{0.845357,0.827223},{5.1551,5.96676},{5.27177,5.52867},{0.159596,0.353401},{0.317545,0.944187},{5.20924,5.85889},{0.68395,0.738788},{0.866587,0.699483}}

have a look at the mess:
In:= ListPlot[pts, Joined -> True]
(* output deleted *)

use a brain twister using anonymous functions and a temporary variable:
(starting at the origin; could be any point in the plane)
In:= sorted = Rest[First[NestWhile[
Block[{tmp}, {Join[#1[],
tmp = Nearest[#1[], #1[[1,-1]]]],
DeleteCases[#1[], tmp[]]}] & ,
{{{0, 0}}, pts}, #1[] =!= {} & , 1]]]
Out=
{{0.159596,0.353401},{0.317545,0.944187},{0.68395,0.738788},{0.845357,0.827223},{0.866587,0.699483},{5.05492,5.67991},{5.20924,5.85889},{5.26878,5.95573},{5.1551,5.96676},{5.27177,5.52867}}

and look at the result:
In:= ListPlot[sorted, Joined -> True]

or apply a rule repeatedly:

In:= sort2=Rest[First[{{{0.,0.}},pts}//.
{{s1___List,s2:{__Real}},remain:{r1___,rn:{__Real},r2___}}/;{rn}==Nearest[remain,s2]:>{{s1,s2,rn},{r1,r2}}]];

and the results are the same:
In:= sorted === sort2
Out= True

hth,
Peter

```

• Prev by Date: Writing images from manipulate
• Next by Date: Re: Chop in Mathematica 8.0.1
• Previous by thread: Re: Using Nearest on a group of points
• Next by thread: Re: Using Nearest on a group of points