Find the perimeter of a subset of a near-regular grid of points

Question

Let us consider a set of near-regular grids in 2-D. These grids are adjacent (neighbouring grids have one or more same vertices) to the neighbouring grids. Here are the sample of 10 grids with the coordinates of the vertices (longitude,latitude) are as follows

A<-

        lon    lat
        [,1]     [,2]
  [1,] 85.30754 27.91250
  [2,] 85.32862 27.95735
  [3,] 85.34622 27.89880
  [4,] 85.36732 27.94364
  [5,] 85.34958 28.00202
  [6,] 85.38831 27.98830
  [7,] 85.38487 27.88508
  [8,] 85.40598 27.92991
  [9,] 85.42353 27.87134
 [10,] 85.44466 27.91616
 [11,] 85.42698 27.97456
 [12,] 85.46567 27.96081
 [13,] 85.48334 27.90239
 [14,] 85.50437 27.94703
 [15,] 85.48645 28.00502
 [16,] 85.52517 27.99123
 [17,] 85.52198 27.88862
 [18,] 85.54302 27.93325
 [19,] 85.56384 27.97745

The scatter-plot of the above sample set of points (vertices):

The grids are constructed as in the following picture.

My question is how to get the perimeter (red contour passing through all boundary points)??

Note that: The red encircled points (1,3,7,9,10,13,17,18,19,16,15,12,11,6,5,2) in figure 1 are the boundary points.

Note: It is observed the sides of the grids are less than 6000 metres and length of diagonals of all grids are more than 6000 metres.

I am using distHaversine from the geosphere package function in R to find the distance between two points.

Answer 1

One way of solving this problem is to compute the alpha hull around your points.

The alphahull package can do this. The package has excellent documentation, complete with animation, at http://yihui.name/en/2010/04/alphahull-an-r-package-for-alpha-convex-hull/

It is well worth taking a look at this documentation, in particular to understand the meaning of the alpha parameter.

First, replicate your data

A <- read.table(header=TRUE, text="
lon    lat
[1,] 85.30754 27.91250
[2,] 85.32862 27.95735
[3,] 85.34622 27.89880
[4,] 85.36732 27.94364
[5,] 85.34958 28.00202
[6,] 85.38831 27.98830
[7,] 85.38487 27.88508
[8,] 85.40598 27.92991
[9,] 85.42353 27.87134
[10,] 85.44466 27.91616
[11,] 85.42698 27.97456
[12,] 85.46567 27.96081
[13,] 85.48334 27.90239
[14,] 85.50437 27.94703
[15,] 85.48645 28.00502
[16,] 85.52517 27.99123
[17,] 85.52198 27.88862
[18,] 85.54302 27.93325
[19,] 85.56384 27.97745")

Now compute and plot the alpha hull. You have to provide the alpha value. I had to experiment to find a value small enough to capture the ouline.

library("alphahull")
hull <- with(A, ahull(lat, lon, alpha=0.033))
plot(hull)