randomly sample as many points as possible where each point has a min set distance from one another

1 view (last 30 days)
Phillip Maire on 15 Apr 2020
Commented: Phillip Maire on 16 Apr 2020
So I solved this problem using a for loop which, starting with a random point, finds the next closest point >= some threshold. then uses that next point to do the same thing. It works as you can test with the below code but I was curious to know if anyone knows of some mathmatic truism or formula that can solve this problem for arbitrarily larger sets of points. To be clear I do not NEED to do this with more points, I could find a workaround for more points (e.g. for each point find the distance between it and all of its partners instead of using matrix operations with say 10000X10000 which would run out of memory)
even if you know a term for this or a better way to define what this is it would be helpful i might post on a math forum too! thank for your help!
numPoints = 1000;
poleDistances = round(rand(numPoints, 2)*100);
removePtsCloserThan = 10;
numPoints = size(poleDistances, 1);
x = poleDistances(:, 1);
y = poleDistances(:, 2);
d = sqrt((x(:) - x(:)').^2 + (y(:) - y(:)').^2);
c = size(d, 1);
dIndex = 1:c+1:numel(d);
d(dIndex) = inf;
k = randsample(numPoints, 1);
keepPoints = k;
d(k, :) = nan;
while true
% k = find(isnan(diag(d)), 1, 'first');
pnt1 = d(:, k);
farEnough = abs(pnt1)>=removePtsCloserThan & abs(pnt1)<inf;
pnt1(~farEnough) = inf;
[sdfg, k] = nanmin(abs(pnt1));
% if isinf(sdfg)
% keyboard
% end
d([k; find(~farEnough)], :) = nan;
if all(isnan(d(:)))
break
end
keepPoints(end+1) = k;
end
figure; hold on
circSize = repmat(removePtsCloserThan*2, length(keepPoints), 1);
pos = [poleDistances(keepPoints, 1)-removePtsCloserThan, poleDistances(keepPoints, 2)-removePtsCloserThan,circSize,circSize,];
for k = 1:length(keepPoints)
r = rectangle('Position',pos(k, :),'Curvature',[1 1])
r.FaceColor = [0 .5 .5];
end
scatter(poleDistances(:, 1), poleDistances(:, 2), 'bo');
scatter(poleDistances(keepPoints , 1), poleDistances(keepPoints , 2), 'filled', 'MarkerFaceColor','r');
%
x = poleDistances(keepPoints, 1);
y = poleDistances(keepPoints, 2);
d = sqrt((x(:) - x(:)').^2 + (y(:) - y(:)').^2);
d(d==0) = nan
min(d(:))
3 CommentsShow 1 older commentHide 1 older comment
Phillip Maire on 16 Apr 2020
Edited: Phillip Maire on 16 Apr 2020
you can change
removePtsCloserThan = 70;
I just changed it to 10 in the edit to make it more apparent what im talking about. So I want to sample as many points as possible while also making sure those dots are a min distance away from each other
so
numPoints = 1000;
poleDistances = round(rand(numPoints, 2)*100); % this is simulating real position of objects
removePtsCloserThan = 10; % this is the min distance
Phillip Maire on 16 Apr 2020
shoot I thought I said this the point are data and you have to select points form the data no make up your own.

Categories

Find more on Creating and Concatenating Matrices in Help Center and File Exchange

R2019b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!