Janak - 6 months ago 27

R Question

Let us consider a 2-D (latitude, longitude) point set. The points in the set are equispaced (approx.) with mutual distance 0.1 degree \times 0.1 degree . Each point in the set is the centre of a square grid of side length 0.1 degree (i.e., intersect point of two diagonals of the square). Each square is adjacent to the neighbouring squares.

Our **goal** is to get the coordinates of the **outline polygon** formed by the bounding sides of the square grids with given direction (will be illustrated with a figure). This polygon has **no hole** inside.

Let us consider a sample data set of size 10 (point set).

`lat_x <- c(21.00749, 21.02675, 21.00396, 21.04602, 21.02317,`

21.06524, 21.00008, 21.04247, 21.08454, 21.0192)

and

`lon_y <- c(88.21993, 88.25369, 88.31292, 88.28740, 88.34669,`

88.32118, 88.40608, 88.38045, 88.35494, 88.43984)

Here is the rough plot of the above points followed by some illustration,

The black points are the (lat,lon) points in the above sample.

The blue square boxes are the square grid.

The given directions (\theta) of the squares are $theta$=50 degree.

Our goal is to get the ordered (clockwise or counter clockwise) co-ordinates of the outline polygon (in yellow colour).

I would gratefully appreciate any suggestion, java or R codes or helpful reference given by anyone solving the above problem.

Answer

I would do it like this:

**may be some 2D array point grouping to match the grid**that should speed up all the following operations.

**compute average grid sizes (img1 from left)**as two vectors

**create blue points (img2)**as:

`gray_point (+/-) 0.5*blue_vector`

**create red points (img3)**as:

`blue_point (+/-) 0.5*red_vector`

**create list of gray lines (img4)**take all 2 original (gray) points that have distance close to average grid distance and add line for them

**create list of red lines (img4)**take all 2 original (gray) points that have distance close to average grid distance and add line for them if it is not intersecting any line from gray lines

**reorder line points to match polygon winding ...****angle**

compute angle of red vector (via atan2)

compute angle of blue vector (via atan2)

return the one with smaller absolute value

**[edit1] response to comments**

**grid size**

find few points that are closest to each other so pick any point and find all closest points to it. The possible distances should be near:

```
sqrt(1.0)*d,sqrt(1+1)*d,sqrt(1+2)*d,sqrt(2+2)*d,...
```

where `d`

is the grid size so compute `d`

for few picked points. Remember the first smallest `d`

found and throw away all that are not similar to smallest one. Make average of them and let call it `d`

**grid vectors**

Take any point `A`

and find closest point `B`

to it with distance near `d`

. For example `+/-10%`

comparison: `|(|A-B|-d)|<=0.1*d`

Now the grid vector is `(B-A)`

. Find few of them (picking different `A,B`

) and group them by sign of `x,y`

coordinates into 4 groups.

Then join negative direction groups together by negating one group vectors so you will have 2 list of vectors (red,blue direction) and make average vectors from them (red,blue vectors)

**shifting points**

You take any point `A`

and add or substract half of red or blue **vector** to it (not its size!!!) for example:

```
A.x+=0.5*red_vector.x;
A.y+=0.5*red_vector.y;
```

**line lists**

Make 2 nested `for`

s per each 2 point combination `A,B`

(original for gray lines,shifted red ones for red outline lines) and add condition for distance

```
|(|A-B|-d)|<=0.1*d
```

if it is `true`

add line `(A,B)`

to the list. Here pseudo C++ example:

```
int i,j,N=?; // N is number of input points in pnt[]
double x,y,d=?,dd=d*d,de=0.1*d; // d is the avg grid size
double pnt[N][2]=?; // your 2D points
for (i=0;i<N;i++) // i - all points
for (j=i+1;j<N;j++) // j - just the rest no need to test already tested combinations
{
x=pnt[i][0]-pnt[j][0];
y=pnt[i][1]-pnt[j][1];
if (fabs((x*x)+(y*y)-dd)<=de) ... // add line pnt[i],pnt[j] to the list...
}
```