SED navigation bar go to SED home page go to Dataplot home page go to NIST home page SED Home Page SED Staff SED Projects SED Products and Publications Search SED Pages
Dataplot Vol 2 Vol 1

NEAREST NEIGHBOR

Name:
    NEAREST NEIGHBOR
Type:
    LET Subcommand
Purpose:
    Compute 2-dimensional nearests neighbors.
Description:
    Given a set of points, it is often desirable to determine the nearest neighbor of each point. It may also be desirable to compute the distances between the nearest neigbors. In some cases, there may be two separate lists of points and we want the nearest neighbor in list one for each point in list two.

    Dataplot provides several different commands to accomodate these different cases. Note that currently only the 2-dimensional case is considered.

Syntax 1:
    LET <yindex> = NEAREST NEIGHBOR INDEX <y> <x>
                            <SUBSET/EXPCEPT/FOR qualification>
    where <y> is a variable containing the y-coordinates of the data set;
                <x> is a variable containing the x-coordinates of the data set;
                <yindex> is a variable that will contain the index of the nearest neighor for each point;
    and where the <SUBSET/EXCEPT/FOR qualification> is optional.

    Given a set of points, this syntax returns the index of the point that is nearest neighbor to each point in the list (i.e., the output variable will have the same number of rows as the input variable.

Syntax 2:
    LET <ydist> = NEAREST NEIGHBOR DISTANCE <y> <x>
                            <SUBSET/EXPCEPT/FOR qualification>
    where <y> is a variable containing the y-coordinates of the data set;
                <x> is a variable containing the x-coordinates of the data set;
                <ydist> is a variable that will contain the distance of the nearest neighor for each point;
    and where the <SUBSET/EXCEPT/FOR qualification> is optional.

    Given a set of points, this syntax returns the distance between each point and its nearest neighbor.

Syntax 3:
    LET <yindex> <ydist> = NEAREST NEIGHBOR <y> <x>
                            <SUBSET/EXPCEPT/FOR qualification>
    where <y> is a variable containing the y-coordinates of the data set;
                <x> is a variable containing the x-coordinates of the data set;
                <yindex> is a variable that will contain the index of the nearest neighor for each point;
                <ydist> is a variable that will contain the distance of the nearest neighor for each point;
    and where the <SUBSET/EXCEPT/FOR qualification> is optional.

    Given a set of points, this syntax returns both the index of the point that is nearest neighbor to each point in the list and the distance between the point and its nearest neighbor.

Syntax 4:
    LET <y2> <x2> <tag2> = NEAREST NEIGHBOR JOIN <y1> <x1> <yindex>
                            <SUBSET/EXPCEPT/FOR qualification>
    where <y1> is a variable containing the y-coordinates of the data set;
                <x1> is a variable containing the x-coordinates of the data set;
                <yindex> is a variable containing the index of the nearest neighor for each point;
                <y2> is a variable that will contain the y-coordinates of nearest neighors;
                <x2> is a variable that will contain the x-coordinates of nearest neighors;
                <tag2> is a variable that will contain a tag identifying which points in <x2> and <y2> are connected;
    and where the <SUBSET/EXCEPT/FOR qualification> is optional.

    This command is useful if you want to plot the nearest neighbors. It connects each point in (,) with its nearest neighbor where the Syntax 1 command is typically run first to obtain . This is demonstrated in the Program 1 example below.

Syntax 5:
    LET <y3> <x3> <dist> = FIRST NEAREST NEIGHBOR <y1> <x1> <y2> <x2>
                            <SUBSET/EXPCEPT/FOR qualification>
    where <y1> is a variable containing the y-coordinates of the first data set;
                <x1> is a variable containing the x-coordinates of the first data set;
                <y2> is a variable containing the y-coordinates of the second data set;
                <x2> is a variable containing the x-coordinates of the second data set;
                <y3> is a variable that will contain the y-coordinate of the nearest neighor;
                <x3> is a variable that will contain the x-coordinate of the nearest neighor;
                <dist> is a variable that will contain the distance of the nearest neighor;
    and where the is optional.

    This command works on two sets of points. For each point in (<x2>,<y2>), the points in (<x1>,<y1>) are searched to determine the nearest neighbor. The coordinates of the nearest neighbor are saved in (<x3>,<y3>). In addition, the distance between the nearest neighbors are also saved.

Syntax 6:
    LET <y3> <x3> <dist> <tag1> <tag2> = ALL NEAREST NEIGHBORS
                            <y1> <x1> <y2> <x2>
                            <SUBSET/EXPCEPT/FOR qualification>
    where <y1> is a variable containing the y-coordinates of the first data set;
                <x1> is a variable containing the x-coordinates of the first data set;
                <y2> is a variable containing the y-coordinates of the second data set;
                <x2> is a variable containing the x-coordinates of the second data set;
                <y3> is a variable that will contain the y-coordinate of the nearest neighor;
                <x3> is a variable that will contain the x-coordinate of the nearest neighor;
                <dist> is a variable that will contain the distance of the nearest neighor;
                <tag1> is a variable that identifies the row number of the second data set;
                <tag2> is a variable that identifies the nearest neighbor index;
    and where the <SUBSET/EXCEPT/FOR qualification> is optional.

    This command works on two sets of points. For each point in (<x2>,<y2>), the points in (<x1>,<y1>) are searched to determine a sorted list of nearest neighbors. The coordinates of the nearest neighbors are saved in (<x3>,<y3>). In addition, the distance between the nearest neighbors are also saved.

    The <tag1> variable identifies the row number in the second data set. The <tag2> variable identifies the index in the sorted list of nearest neighbors (i.e., a value of 1 identifies the first nearest neighbor, a value of 2 identifies the second nearest neighbor, and so on).

    This syntax is useful if you want to determine not just the first nearest neighbor but the second or third (and so on) nearest neighbors. If N1 is the number of rows in the first data set and N2 is the number of rows in the second data set, then the output variables will have N1*N2 rows.

Examples:
    LET YINDEX = NEAREST NEIGHBOR INDEX Y X
    LET YDIST = NEAREST NEIGHBOR DISTANCE Y X
    LET Y3 X3 DIST = FIRST NEAREST NEIGHBOR Y1 X1 Y2 X2
    LET Y3 X3 DIST TAG1 TAG2 = ALL NEAREST NEIGHBORS Y1 X1 Y2 X2
Note:
    These nearest neighbor commands are currently implemented using brute force algorithms. Although these algorithms are not particularly efficient, they should be adequate for small to moderate size 2d data sets.
Default:
    None
Synonyms:
    LET YINDEX = NEAREST NEIGBOR Y X is a synonym for LET YINDEX = NEAREST NEIGBOR INDEX Y X.
Related Commands: Applications:
    Computational Geometry, Spatial Statistics
Implementation Date:
    2013/9
Program 1:
     
    skip 25
    read convhull.dat x y
    .
    let yindex = nearest neighbor y x
    let y3 x3 tag3 = nearest neighbor join y x yindex
    .
    title case asis
    title offset 2
    title Nearest Neighbor Map
    y1label Y
    x1label X
    tic offset units screen
    tic offset 3 3
    .
    character circle all
    character hw 0.5 0.375 all
    character fill on all
    .
    plot y3 x3 tag3
        

    plot generated by sample program

Program 2:
     
    dimension 40 columns
    skip 25
    read convhull.dat x y
    .
    read x2 y2
     0  0
     1  1
     1 -1
    -1 -1
    -1  1
    end of data
    .
    let y4 x4 dist4 = first nearest neighbor y x y2 x2
    set write decimals 2
    write x2 y2 x4 y4 dist4
        
    The following output is generated
     
     ---------------------------------------------------------------------------
                  X2             Y2             X4             Y4          DIST4
     ---------------------------------------------------------------------------
                0.00           0.00           0.10           0.10           0.14
                1.00           1.00           0.50           0.50           0.70
                1.00          -1.00          -0.60           0.60           0.56
               -1.00          -1.00          -0.80          -0.80           0.28
               -1.00           1.00           0.70          -0.70           0.42
        
Program 3:
     
    dimension 40 columns
    skip 25
    read convhull.dat x y
    .
    read x2 y2
     0  0
     1  1
     1 -1
    -1 -1
    -1  1
    end of data
    .
    let y4 x4 dist4 tag1 tag2 = all nearest neighbor y x y2 x2
    set write decimals 2
    write x2 y2
    write x4 y4 dist4 tag1 tag2
        
    The following output is generated
     
     ------------------------------
                  X2             Y2
     ------------------------------
                0.00           0.00
                1.00           1.00
                1.00          -1.00
               -1.00          -1.00
               -1.00           1.00
      
      
     ---------------------------------------------------------------------------
                  X4             Y4          DIST4           TAG1           TAG2
     ---------------------------------------------------------------------------
                0.10           0.10           2.00           1.00           1.00
               -0.20           0.20           1.99           1.00           2.00
                0.30          -0.30           1.99           1.00           3.00
               -0.40          -0.40           2.00           1.00           4.00
                0.50           0.50           0.14           1.00           5.00
               -0.60           0.60           1.99           1.00           6.00
                0.70          -0.70           0.28           1.00           7.00
               -0.80          -0.80           1.99           1.00           8.00
                1.00           1.73           0.42           1.00           9.00
               -1.73           1.00           2.00           1.00          10.00
               -1.00          -1.73           0.56           1.00          11.00
                1.00          -1.73           2.00           1.00          12.00
               -1.73          -1.00           0.70           1.00          13.00
                1.73           1.00           1.99           1.00          14.00
               -1.00           1.73           0.84           1.00          15.00
                1.73          -1.00           1.99           1.00          16.00
                0.00          -2.00           0.98           1.00          17.00
                0.00           2.00           1.99           1.00          18.00
                2.00           0.00           1.13           1.00          19.00
               -2.00           0.00           1.99           1.00          20.00
                0.50           0.50           1.41           2.00           1.00
                1.00           1.73           2.12           2.00           2.00
                1.73           1.00           0.73           2.00           3.00
                0.10           0.10           1.41           2.00           4.00
                0.00           2.00           1.27           2.00           5.00
                2.00           0.00           3.38           2.00           6.00
               -0.20           0.20           1.44           2.00           7.00
                0.30          -0.30           2.73           2.00           8.00
               -0.60           0.60           1.47           2.00           9.00
                0.70          -0.70           3.16           2.00          10.00
               -0.40          -0.40           1.97           2.00          11.00
                1.73          -1.00           3.16           2.00          12.00
               -1.00           1.73           0.70           2.00          13.00
               -0.80          -0.80           0.73           2.00          14.00
               -1.73           1.00           1.64           2.00          15.00
                1.00          -1.73           2.12           2.00          16.00
                0.00          -2.00           1.72           2.00          17.00
               -2.00           0.00           3.38           2.00          18.00
               -1.00          -1.73           2.54           2.00          19.00
               -1.73          -1.00           2.73           2.00          20.00
               -0.60           0.60           1.41           3.00           1.00
               -1.73           1.00           0.73           3.00           2.00
               -1.00           1.73           2.73           3.00           3.00
               -0.20           0.20           3.16           3.00           4.00
                0.00           2.00           1.42           3.00           5.00
               -2.00           0.00           2.12           3.00           6.00
                0.10           0.10           1.13           3.00           7.00
               -0.40          -0.40           3.38           3.00           8.00
                0.50           0.50           1.83           3.00           9.00
               -0.80          -0.80           1.41           3.00          10.00
                0.30          -0.30           1.52           3.00          11.00
                1.00           1.73           3.16           3.00          12.00
               -1.73          -1.00           1.58           3.00          13.00
                0.70          -0.70           2.12           3.00          14.00
                1.73           1.00           0.56           3.00          15.00
               -1.00          -1.73           3.38           3.00          16.00
                2.00           0.00           2.40           3.00          17.00
                0.00          -2.00           2.73           3.00          18.00
                1.00          -1.73           1.81           3.00          19.00
                1.73          -1.00           0.73           3.00          20.00
               -0.80          -0.80           3.16           4.00           1.00
               -1.73          -1.00           2.73           4.00           2.00
               -1.00          -1.73           3.38           4.00           3.00
               -0.40          -0.40           3.16           4.00           4.00
               -2.00           0.00           1.55           4.00           5.00
                0.00          -2.00           0.73           4.00           6.00
               -0.20           0.20           1.44           4.00           7.00
                0.30          -0.30           2.12           4.00           8.00
                0.10           0.10           1.47           4.00           9.00
               -0.60           0.60           1.41           4.00          10.00
                0.70          -0.70           0.84           4.00          11.00
                0.50           0.50           1.41           4.00          12.00
               -1.73           1.00           2.12           4.00          13.00
                1.00          -1.73           3.38           4.00          14.00
                1.73          -1.00           1.64           4.00          15.00
               -1.00           1.73           2.73           4.00          16.00
                2.00           0.00           1.72           4.00          17.00
                0.00           2.00           0.73           4.00          18.00
                1.00           1.73           0.28           4.00          19.00
                1.73           1.00           2.12           4.00          20.00
                0.70          -0.70           3.16           5.00           1.00
                1.73          -1.00           3.38           5.00           2.00
                1.00          -1.73           2.12           5.00           3.00
                0.30          -0.30           1.41           5.00           4.00
                0.00          -2.00           1.42           5.00           5.00
                2.00           0.00           2.73           5.00           6.00
                0.10           0.10           1.69           5.00           7.00
               -0.40          -0.40           0.73           5.00           8.00
                0.50           0.50           0.98           5.00           9.00
               -0.20           0.20           3.16           5.00          10.00
               -0.80          -0.80           1.52           5.00          11.00
                1.73           1.00           1.41           5.00          12.00
               -1.00          -1.73           1.58           5.00          13.00
               -0.60           0.60           2.73           5.00          14.00
               -1.73          -1.00           2.26           5.00          15.00
                1.00           1.73           0.73           5.00          16.00
                0.00           2.00           0.42           5.00          17.00
               -2.00           0.00           2.12           5.00          18.00
               -1.00           1.73           1.81           5.00          19.00
               -1.73           1.00           3.38           5.00          20.00
        

Privacy Policy/Security Notice
Disclaimer | FOIA

NIST is an agency of the U.S. Commerce Department.

Date created: 12/11/2013
Last updated: 12/11/2013

Please email comments on this WWW page to alan.heckert@nist.gov.