Dear Roger,

Apologies for the late reply.

Your suggestion was a life saver, the computation time by which RANN produces 
nearest neighbour indexes and distances is incredible. Even with more than 
1.5million points it took only a minute to compute 30 neighbours and their 
distance for each pair.

The only problem I faced with the RANN approach is that one arrives with the 
nearest points first. Meaning that if a point is surrounded by lets say 30 
other points within a distance of 500 meter, one will never arrive with a pair 
that is in distance of 5000 meter. To overcome this one can only increase the 
number of k neighbours, which in my case would mean minimum k=100, leading to 
100million combinations of which I then sampled randomly the amount necessary 
to proceed.

Still the best and fastest option. Thanks for your help!


Kimon Krenz

PhD Researcher
MSc SDAC Course 
Space Syntax Laboratory<>

phone.    0044 7784 329089

Bartlett School of Architecture<>
140 Hampstead Road
London     NW1 2BX     UK

On 06 Oct 2016, at 13:32, Roger Bivand 
<<>> wrote:

Just a partial suggestion: the RANN package will let you index the points 
byk-neighbourness, avoiding some of the burden of searching for points within 
your 100-1000m band.

Hope this helps,


On Wed, 5 Oct 2016, Krenz, Kimon-Vincent wrote:

Dear All,

I started a week ago to use R to solve a problem I am currently facing in my 
Apologies in advance for the long-winded explanation of my problem.

I am trying to generate a random planar graph with approximately 1 million 
edges, where:

A) nodes (points) feature spatial coordinates
B) the network has a given boundary

C) edges (lines) are created if two points fall within a given distance (e.g. 
100 - 1000 metres)

D) degree (connectivity) ranges between given k max and min (e.g. k ≤ 5)
E) edges do not intersect

This will result in something one might want to compare to a random street 

I am following a method proposed here: Masucci, A. P., Smith, D., Crooks, A., & 
Batty, M. (2009). Random planar graphs and the London street network. European 
Physical Journal B, 71(2), 259–271. 
link to paper:

Masucci et al.: "We first introduce a random model for a static planar graph. 
... To build an ERPG we start with a Poisson distribution of N points in a 
plane and we choose a distance r. To build the first segment, we randomly pick 
up two points of the distribution that have a distance less then r and we 
connect them. Then we continue to randomly pick up pairs of points P and Q in 
the given points distribution that have a distance less then r. If the segment 
PQ does not intersect any other line of the graph, we add it to the graph. The 
process ends when we add the desired number of edges E.”

I hence, started with generating random points using the Poisson distribution 
in a given spatial box (A and A):

w <- as.owin(list(xrange=c(32275175,32475175),yrange=c(5611910,5811910)))
Y <- rpoispp(0.00001, win=w)
Ydata <- data.frame(Y)

That seems to be quite straightforward in R.
I then followed the proposed method and wrote a simple loop, that selects two 
points from Ydata
based on a random sample and adds the projection of the coordinate system.

#399717 is = N from the rpoispp

repeat {
l1 <- sample(1:399717, 2, replace=F)

Ydata.sp<-Ydata[l1, c('x','y')]
crs.geo <- CRS("+init=epsg:4647 +proj=tmerc +lat_0=0 +lon_0=9 +k=0.9996 
+x_0=32500000 +y_0=0 +ellps=GRS80 +towgs84=0,0,0,0,0,0,0 +units=m +no_defs")
proj4string(Ydata.sp) <- crs.geo

L = SpatialLines(list(Lines(list(Line(coordinates(Ydata.sp))),"X")))
if (SpatialLinesLengths(L)<=4000){

This fulfils the requirement of C) and I have not yet reached the point to deal 
with D) and E).
My problem here is that the process takes way too long for a single pair 
(approx 20 seconds, resulting in 250 days computational time).

Is there a quicker way solve this in a more efficient manner?

I have thought about selecting the first point by random and the second one 
randomly based on an evaluation
of all points within a given radius to the first point, rather than two 
complete random points.

This would at least cut down the test of several thousand meaningless 
combinations. However, I couldn't find a way to do this.
Another option might be gDistance from the (rgeos), but with 400k points, the 
result seems to be not computable.

I am also happy for any suggestions regarding requirements D and E, or help 
with the task in general.


Kimon Krenz

PhD Researcher
MSc SDAC Course 
Space Syntax Laboratory<>

phone.    0044 7784 329089

Bartlett School of Architecture<>
140 Hampstead Road
London     NW1 2BX     UK

[[alternative HTML version deleted]]

R-sig-Geo mailing list<>

Roger Bivand
Department of Economics, Norwegian School of Economics,
Helleveien 30, N-5045 Bergen, Norway.
voice: +47 55 95 93 55; fax +47 55 95 91 00

        [[alternative HTML version deleted]]

R-sig-Geo mailing list

Reply via email to