nearest neighbor 3d point pattern

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

nearest neighbor 3d point pattern

Carsten Neumann
Dear list members,

after searching R mailing lists, I wonder if there is a R function that
can find the nearest neighbor/or just euclidean distance of points in
one 3D coordinate system to points in another 3D coordinate system. The
function nncross {spatstat} can only deal with 2D point pattern. Any
idea or experiences with such procedures?

######################Test Data############################
point1<-array(c(seq(0,1,0.1),seq(0,1,0.1),seq(0,1,0.1)),dim=c(11,11,11))
point2<-array(c(0.8,0.3,0.5),dim=c(1,1,1))
#########################################################
question: where is point2 in point1?


Thanks in advance

Carsten

--

Carsten Neumann
Telegrafenberg, A 17 01.13
14473 Potsdam
-------------------------------------------------------
Helmholtz Centre Potsdam
GFZ German Research Centre for Geosciences
Department 1 - Section 1.4 - Remote Sensing
-------------------------------------------------------
Tel.: +49 (0) 331 288 1766
e-mail: [hidden email]

_______________________________________________
R-sig-Geo mailing list
[hidden email]
https://stat.ethz.ch/mailman/listinfo/r-sig-geo
Reply | Threaded
Open this post in threaded view
|

Re: nearest neighbor 3d point pattern

Marcel
This post has NOT been accepted by the mailing list yet.
This post was updated on .
Hello Carsten,

maybe crossdist.pp3 in the package spatstat will help.

http://www.inside-r.org/packages/cran/spatstat/docs/crossdist.pp3



       
Reply | Threaded
Open this post in threaded view
|

Re: nearest neighbor 3d point pattern

Rolf Turner
In reply to this post by Carsten Neumann
On 27/06/13 23:40, Carsten Neumann wrote:

> Dear list members,
>
> after searching R mailing lists, I wonder if there is a R function that
> can find the nearest neighbor/or just euclidean distance of points in
> one 3D coordinate system to points in another 3D coordinate system. The
> function nncross {spatstat} can only deal with 2D point pattern. Any
> idea or experiences with such procedures?
>
> ######################Test Data############################
> point1<-array(c(seq(0,1,0.1),seq(0,1,0.1),seq(0,1,0.1)),dim=c(11,11,11))
> point2<-array(c(0.8,0.3,0.5),dim=c(1,1,1))
> #########################################################
> question: where is point2 in point1?

You are correct in that nncross() has not (yet) been extended to three
dimensional point patterns.  However a workaround can be found by
using crossdist.pp3().

E.g.:

     set.seed(42)
     X     <- ppx(data.frame(x=rnorm(20),y=rnorm(20),z=rnorm(20)))
     Y      <- ppx(data.frame(x=0,y=0,z=0))
     M     <- crossdist(Y,X)
     min(M)
     which.min(M)

This will tell you that the nearest point in X to c(0,0,0) is point
number 15
and the distance from c(0,0,0) to this point is 0.5299162.

I'm afraid I could not comprehend your example.  The object point1 is
a 3-dimensional array (11 x 11 x 11).  How is this to be interpreted as
a 3-dimensional *point pattern*?  And point2 is a single number --- 0.8,
and not actually a point in 3-space.

Furthermore what does the question "where is point2 in point1?" mean?
I cannot parse this question.

Perhaps (quite possibly) I am just being stupid.  If so, please
enlighten me.

     cheers,

         Rolf Turner

_______________________________________________
R-sig-Geo mailing list
[hidden email]
https://stat.ethz.ch/mailman/listinfo/r-sig-geo
Reply | Threaded
Open this post in threaded view
|

nearest neighbor 3d point pattern

Adrian Baddeley

Further to Rolf's comment:

The next release of spatstat (1.32-0) will include new methods nncross.pp3 and nncross.ppx
for this purpose.

(spatstat already contains the C code routines for nearest neighbours in arbitrary dimensions,
so it is only necessary to write the R interface.)

Adrian

Prof Adrian Baddeley FAA
University of Western Australia  /and/ CSIRO Mathematics, Informatics & Statistics
Mail: <cet.uwa.edu.au>             Skype: adrian.baddeley
________________________________________
From: Rolf Turner [[hidden email]]
Sent: Friday, 28 June 2013 7:34 AM
To: Carsten Neumann
Cc: [hidden email]; Adrian Baddeley
Subject: Re: [R-sig-Geo] nearest neighbor 3d point pattern

On 27/06/13 23:40, Carsten Neumann wrote:

> Dear list members,
>
> after searching R mailing lists, I wonder if there is a R function that
> can find the nearest neighbor/or just euclidean distance of points in
> one 3D coordinate system to points in another 3D coordinate system. The
> function nncross {spatstat} can only deal with 2D point pattern. Any
> idea or experiences with such procedures?
>
> ######################Test Data############################
> point1<-array(c(seq(0,1,0.1),seq(0,1,0.1),seq(0,1,0.1)),dim=c(11,11,11))
> point2<-array(c(0.8,0.3,0.5),dim=c(1,1,1))
> #########################################################
> question: where is point2 in point1?

You are correct in that nncross() has not (yet) been extended to three
dimensional point patterns.  However a workaround can be found by
using crossdist.pp3().

E.g.:

     set.seed(42)
     X     <- ppx(data.frame(x=rnorm(20),y=rnorm(20),z=rnorm(20)))
     Y      <- ppx(data.frame(x=0,y=0,z=0))
     M     <- crossdist(Y,X)
     min(M)
     which.min(M)

This will tell you that the nearest point in X to c(0,0,0) is point
number 15
and the distance from c(0,0,0) to this point is 0.5299162.

I'm afraid I could not comprehend your example.  The object point1 is
a 3-dimensional array (11 x 11 x 11).  How is this to be interpreted as
a 3-dimensional *point pattern*?  And point2 is a single number --- 0.8,
and not actually a point in 3-space.

Furthermore what does the question "where is point2 in point1?" mean?
I cannot parse this question.

Perhaps (quite possibly) I am just being stupid.  If so, please
enlighten me.

     cheers,

         Rolf Turner

_______________________________________________
R-sig-Geo mailing list
[hidden email]
https://stat.ethz.ch/mailman/listinfo/r-sig-geo
Reply | Threaded
Open this post in threaded view
|

Re: nearest neighbor 3d point pattern

Carsten Neumann
In reply to this post by Rolf Turner
Thank you very much Rolf,

an enlightening example for me! To my example: the 3D array should be
interpreted as a regular point pattern just as a reproducible example
(number of points = 11*11*11 / 1. coordinate = 0,0,0.1 / 2. coordinate =
0,0,0.2 etc.). The second point has the same structure than the first
(number of points = 1*1*1 coordinates = 0.8,0.3,0.5). Maybe this type of
example depiction is some kind of confusing!? So my question was meant,
which coordinates of points 2 are closest to coordinates of point 1. I
know, for a regular Grid pattern like my array example no big question.
But in case of real irregular geographic point pattern your example is a
beginning (I need to translate this for 23 billion points).

Best

Carsten

On 06/28/2013 01:34 AM, Rolf Turner wrote:

> On 27/06/13 23:40, Carsten Neumann wrote:
>> Dear list members,
>>
>> after searching R mailing lists, I wonder if there is a R function that
>> can find the nearest neighbor/or just euclidean distance of points in
>> one 3D coordinate system to points in another 3D coordinate system. The
>> function nncross {spatstat} can only deal with 2D point pattern. Any
>> idea or experiences with such procedures?
>>
>> ######################Test Data############################
>> point1<-array(c(seq(0,1,0.1),seq(0,1,0.1),seq(0,1,0.1)),dim=c(11,11,11))
>> point2<-array(c(0.8,0.3,0.5),dim=c(1,1,1))
>> #########################################################
>> question: where is point2 in point1?
>
> You are correct in that nncross() has not (yet) been extended to three
> dimensional point patterns.  However a workaround can be found by
> using crossdist.pp3().
>
> E.g.:
>
>     set.seed(42)
>     X     <- ppx(data.frame(x=rnorm(20),y=rnorm(20),z=rnorm(20)))
>     Y      <- ppx(data.frame(x=0,y=0,z=0))
>     M     <- crossdist(Y,X)
>     min(M)
>     which.min(M)
>
> This will tell you that the nearest point in X to c(0,0,0) is point
> number 15
> and the distance from c(0,0,0) to this point is 0.5299162.
>
> I'm afraid I could not comprehend your example.  The object point1 is
> a 3-dimensional array (11 x 11 x 11).  How is this to be interpreted as
> a 3-dimensional *point pattern*?  And point2 is a single number --- 0.8,
> and not actually a point in 3-space.
>
> Furthermore what does the question "where is point2 in point1?" mean?
> I cannot parse this question.
>
> Perhaps (quite possibly) I am just being stupid.  If so, please
> enlighten me.
>
>     cheers,
>
>         Rolf Turner
>
>

--

Carsten Neumann
Telegrafenberg, A 17 01.13
14473 Potsdam
-------------------------------------------------------
Helmholtz Centre Potsdam
GFZ German Research Centre for Geosciences
Department 1 - Section 1.4 - Remote Sensing
-------------------------------------------------------
Tel.: +49 (0) 331 288 1766
e-mail: [hidden email]

_______________________________________________
R-sig-Geo mailing list
[hidden email]
https://stat.ethz.ch/mailman/listinfo/r-sig-geo
Reply | Threaded
Open this post in threaded view
|

Re: nearest neighbor 3d point pattern

Seth Myers
In reply to this post by Carsten Neumann
I am having a problem understanding the question fully due to text formatting, etc.

Is this what you are after?

You have a list (List1) of points and each point has an x,y, and z value that places it somewhere in that 3-D coordinate system.  You also have a second list of points (List2), also with x,y,Z values.  For the points in List1, you would like to know the closest point in List2.  Is this the case?  Now, is it the case that the coordinate system for List1 and List2 are the same?  By the same, I mean that the origin (where x,y, and z values are all equal to zero) is in the same location and the dimensions extend identically.

Unless you are worried about time of execution and need a clever way to speed up execution, this seems like the type of function that you could write in a few hours or less.

Have you tried writing a function utilizing a simple nested for loop structure and this was somehow not sufficient?  I imagine with several billion points that the obvious way of doing what you'd like would take quite a while and use of a large amount of computer resources.