Select maximum number of points more than x meters apart

Question

I have a dataset of ~15,000 points that are locations along ROV survey tracks where measurements were taken. These points can be less than 5 meters apart and the survey tracks often cross or can be close to each other (<90 meters apart). We would like to run some analyses on these points, but we would like to select points that are at least 150 meters apart to minimize spatial auto-correlation. Is there a good methodology to find the maximum number of points that would fit this requirement?

Answer 1

I know this is a non-ArcGIS option, but I think you could do this in QGIS (if that is of interest). In the Vector tab, there are two functions that would help, Random Selection and Distance Matrix. First load your points into QGIS, than choose the number of features that you randomly want to choose (you would probably want x% more than you need as some will be removed based on the next criteria).

Then calculate the distance between all of these selected points (Vector -> Analysis Tools -> Distance Matrix).

This produces a .csv file which you can join to your original points using the MMQIS plugin with the feature Attributes Join from CSV File. Then query your data (Right-click on file, and choose query) to filter out any distances <150m.

Answer 2

ArcGIS option:

e: added description

This script will perform Near analysis on the given dataset. This will calculate the distance to the nearest point in the dataset and add the attribute of distance and near point FID to the table. Script then will loop through the dataset deleting each point having a neighbour in proximity smaller than 150 m (if the dataset coordinate systems units are metres!). It will list any point FID that got deleted and check for points with NEAR_DIST < 150 if their NEAR_FID hasn't been already deleted. If it has it means this distance is not true anymore.

Compare this to the solution given by celenius. If you have a pair of points in proximity smaller than 150 m to each other they will both get deleted if such check is not performed.

After getting through whole file the script performs Near analysis again and repeat the whole thing. It's surprisingly quick as well.

Please note, that this is one of my first ever scripts and I know its awful but does the job. Haven't got time to make it better now but I'm happy to answer any questions. Note that coordinate system of your input file needs to have metres as units and you may need to change field names in the script as appropriate to your input. This can get imported to ArcGIS as script tool - the only parameter of it is input feature class.

import arcpy, sys

feature = arcpy.GetParameterAsText(0)

arcpy.gp.overwriteOutput = True

#running NEAR analysis - every point gets attribute of a distance to the nearest point 
#in same feature class
arcpy.AddMessage("running first near analysis")
arcpy.Near_analysis(feature, feature)

arcpy.AddMessage("inserting cursor")
cur = arcpy.UpdateCursor(feature)
row = cur.next()

arcpy.AddMessage("starting loop")

i=0
while row:
    i+=1
    #fids list will store list of deleted points so if any other point will have 
    #deleted one as the nearest and distance < 150 will not get deleted as this
    #distance is no longer true
    fids = []
    while row:
        if row.NEAR_DIST < 150:
            try:
                #it seems I didn't know if .. in .. at the time ;) such a fun to dig
                #this script up! index throws an exception if element is not in the 
                #list
                fids.index(row.NEAR_FID)
                arcpy.AddMessage("OBJECTID = " + str(row.OBJECTID) + " is listed!")
            except:
                arcpy.AddMessage("deleting OBJECTID = " + str(row.OBJECTID))
                fids.append(row.FID)
                cur.deleteRow(row)
                d = 1
        row = cur.next()
    del cur, row, fids
    try:
        #this idiotic test is to break the loop when no points will have 
        #NEAR_DIST < 150, shameful - I know!
        if d == 1:
            pass
    except:
        sys.exit(0)
    d = 0
    arcpy.AddMessage("loop iteration " + str(i))
    #and again we go..
    arcpy.Near_analysis(feature, feature)
    cur = arcpy.UpdateCursor(feature)
    row = cur.next()

e: some editing for better understanding of things has been done.

Answer 3

Thanks for the suggestions on this. My colleagues have decided to use a MatLab script remove the spatially autocorrelated points.

%script to "thin" a point set so that no points are within threshold distance of other points
%note: final thinned point set is dependent on choice of the first point and on ordering of points in the processing list;
% i.e. it is not unique

clear, clc
spts = xlsread('PresenceOnly_Random30perc_ForAccuracyAssessment.xls');    % Read in file
spts(:,33) = 0;             %Placeholder for column 33 (which will be where deleted points tagged)
k = length(spts);           %set total rows of data
mindis = 169;               %Set minimum distance between points
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
for refp = 1:k              %Sets first data point in matrix as reference, iterates through all points
    disp(refp);
    for compt = 1:k        %Starts loop to calculate distance from refp to other points
        if (spts(compt,33) ~= 1)  & (spts(refp,33) ~= 1) & (refp~=compt)     %only looks at points that have not been flagged
            distsq = sqrt(((spts(compt,9)-spts(refp,9))^2 +(spts(compt,10)-spts(refp,10))^2));  %Calculates distance between two points.
            distref(compt,:)=distsq;    %Save distance values in matrix distref
            if distsq < mindis          %If distance is less than min distance
                spts(compt,33)= 1;       %tag col 33 with value of 1 to delete later.
            end
        end
    end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
deletedrows = find(spts(:,33) == 1);    %Find rows with the tag (1), output matrix of indicies
remainingpts = spts;                   %Created matrix that will have exra points deleted
remainingpts(deletedrows,:) = [];                %Clear entire row based on previous matrix
save all_data_tagged.dat spts /ASCII -tabs         %Saves all data, points to be removed = 1 in col33
save remaining_pts.dat remainingpts /ASCII -tabs
plot(spts(:,9),spts(:,10),'b.',remainingpts(:,9),remainingpts(:,10),'r.');
xlabel('Latitude, meters'), ylabel('Longitude, meters'), grid minor