How to Find Grid Points Nearest to Given Location Using Shell Script

How to find grid points nearest to given location using shell script?

Here is a simple solution in awk. It worked fine at my Linux.
If my answer was useful for you please click the grey tick sign on the left side of my answer.

#!/bin/bash
(($#!=2))&& { echo "Usage $0 1st_file 2nd_file"; exit 1; }
awk '
 BEGIN {p=fx=0; fn=""; maxd=1.1e11;}
 $0~"[^0-9. \t]" || NF!=4 && NF!=3 {next;}          # skip no data lines
 fn!=FILENAME {fx++; fn=FILENAME;}                  # fx: which file
 fx==1 { if(NF!=3){printf("Change the series of two input files\n"); exit 1;}
         x2[p]=$1; y2[p]=$2; d2[p++]=$3;next;}      # save the columns of first file
 fx==2 { mv=maxd; mp=0;                             # search minimal distance
           for(i=0; i<p; i++){
              dx=x2[i]-$2; dy=y2[i]-$3; dd=dx*dx+dy*dy;
              if(dd<mv){mv=dd; mp=i;}               # min value & min place
           }
           printf("%3d %6.2f %6.2f %3d\n", $1, x2[mp], y2[mp], d2[mp]);
         }
' $2 $1                                             # first is the 2nd_file!

Find nearest point from file1 in file2, shell skript

$ cat tst.awk
BEGIN { OFS=", " }
NR==FNR {
    points[NR] = $0
    next
}
{
    min = 0
    for (i in points) {
        split(points[i],coords)

        dist = ($1 - coords[2])^2 + \
               ($2 - coords[3])^2 + \
               ($3 - coords[4])^2

        if ( (i == 1) || (dist <= min) ) {
            min = dist
            point = points[i]
        }
    }
    split(point,p)
    print p[1] " ", "xyz= " p[2], p[3], p[4], "dist= " sqrt(min)
}

$ awk -f tst.awk file2 file1
2036600 , xyz= -3242.417, 635.2612, 1212.527, dist= 2.99713
2095886 , xyz= -1111.889, 738.3486, 833.6354, dist= 4.35812

How to access grid files by coordinate args in a bash script?

Here's a perl solution.

#!/usr/bin/perl
use strict;
use warnings;
use v5.10;
use autodie;
use List::MoreUtils qw(any);

my $data_file = shift;
my %metadata;
my @data;

open my $fh, '<', $data_file;
while (<$fh>) {
    chomp;
    my @F = split;
    if (any {$F[0] eq $_} qw(ncols nrows xllcorner yllcorner cellsize NODATA_value)) {
        $metadata{$F[0]} = $F[1];
    }
    else {
        push @data, \@F;
    }
}
close $fh;

while (@ARGV) {
    my $x = shift;
    my $y = shift;
    my $x_delta = int(($x - $metadata{xllcorner}) / $metadata{cellsize});
    my $y_delta = int(($y - $metadata{yllcorner}) / $metadata{cellsize});
    if ($x_delta < 0 or $y_delta < 0 or not defined $data[$y_delta][$x_delta]) {
        say $metadata{NODATA_value};
    }
    else {
        say $data[$y_delta][$x_delta];
    }
}

Since reading all the data will probably be expensive, you should be able to pass in several pairs of coordinates at one time: that's the while loop consuming @ARGV. This gives you:

$ perl esri.pl elevation.asc 0 0 3356385.137 5800799.818 3356387.137 5800803.818
-9999
31.11266
29.58562

Finding n nearest data points to grid locations

No need to iterate over your data points for each grid location: Your grid locations are inherently ordered, so just iterate over your data points once, and assign each data point to the eight grid locations that surround it. When you're done, some grid locations may have too few data points. Check the data points of adjacent grid locations. If you have plenty of data points to go around (it depends on how your data is distributed), you can already select the 20 closest neighbors during the initial pass.

Addendum: You may want to reconsider other parts of your algorithm as well. Your algorithm is a kind of piecewise-linear interpolation, and there are plenty of relatively simple improvements. Instead of dividing your space into evenly spaced cubes, consider allocating a number of center points and dynamically repositioning them until the average distance of data points from the nearest center point is minimized, like this:

1. Allocate each data point to its closest center point.
2. Reposition each center point to the coordinates that would minimize the average distance from "its" points (to the "centroid" of the data subset).
3. Some data points now have a different closest center point. Repeat steps 1. and 2. until you converge (or near enough).

Getting closest coordinates closest to point in array

I don't know JavaScript, but the following algorithm would be very simple, if you can formulate it with JavaScript.

Let (X0, Y0) be the original point.

Iterate through the array, [(X1, Y1), ..., (XN, YN)], and keep account of the minimum values of

R = Xi - X0 > 0

and

L = X0 - Xi > 0

as you proceed.
At the end of the iteration these values give you the closest points, i.e., X0 + R
and X0 - L.

Do a similar iteration on the vertical line of points.

Find the Nearest Neighbor To A Given Point in a List of Points in Python

The easiest approach would be to use a O(N) check with all the points in your database.

import math
def get_dist(a,b):
  return math.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2)

p = choice(self.rooms) #your point
n = len(self.rooms)
dist = math.inf #(infinity)
for i in range(n):
   d = get_dist(p,self.rooms[i])
   if d<dist and d!=0: # to avoid the same point
      dist =d
      np= self.rooms[i]
print(np) # nearest point

To use this algorithm or not depends on how much data you have, as it is good for small dataset(a sample would be good in the question).

If you want a short implementation, functional approach would be better, like in another answer:

p = choice(self.rooms) #point to compare
dists= [(i,get_dist(p,i)) for i in self.rooms if get_dist(p,i)!=0] #all distances
min_dist = min(dists) #minimum distance
np = list([self.rooms[i] for i,j in dists if j==min_dist])[0] # Corresponding point. 

How to find closest point to grid values

To expand on the comments of @hpaulj and mine... The class you're looking for is scipy.interpolate.NearestNDInterpolator

This class is based on scipy's own scipy.spatial.cKDTree. The cKDTree class implements the k-dimensional space-partition tree, or "k-d tree" data structure, which trades construction time and space for fast search.

To use scipy.interpolate.NearestNDInterpolator, you initialise an instance like

from scipy.interpolate import NearestNDInterpolator
interpolator = NearestNDInterpolator(your_points, your_values_on_the_points)

After creating interpolator, use it to evaluate the interpolant value at random_point by

interpolant = interpolator(random_point)

Once created, interpolator can be reused for different input points, which is a Good Thing (tm). You can also evaluate the interpolant value for multiple points by passing all of them into the call. [1]

If you look at the source, you'll discover how the interpolator is implemented using cKDTree.

[1] Actually there's a potential optimisation: if you need "vectorised" evaluation for many points, the underlying cKDTree's query() method supports parallelisation, done in native C code running in threads. Although scipy's own implementation of NearestNDInterpolator doesn't use this feature, probably catering to greatest common divisor, you can override this by making your own subclass that uses parallelisation with a suitable choice of n_jobs parameter.

Note: the really good thing about using a k-d tree based interpolator is that its application can be extended to a "grid" in arbitrary shape (not necessarily rectangular).

---

EDIT:

Oh, so you meant to use the nearest neighbors for linear interpolation?

Then very sorry, I misread your question!

But then, you have two choices.

1. If your grid is sufficiently regular, and its construction (starting value / ending value / step known to you in all dimensions), it is not hard to write a function findneighbor() that locates the neighbors given the query point's coordinates. Then you do the vanilla linear interpolation.

2. If your "grid" is not very regular, and you just have a lot of grind point coordinates (which may not lie on rectangular lattices), you can still use scipy.spatial.cKDTree to locate N nearest neighbors (possibly N = 1 + (dimension of the grid)). After that, you interpolate on that N points.

---

Related Topics