Hi All,

I have a matrix of points in x,y coordinate, and I need to eliminate

the points that are closer than a threshold value to each other. i.e

if my matrix is like:

A= [2,2; 2,2.1; 5,5; 5.4,5; 10,4; 13,7] (each row representing a

point) and my threshold value is .5, then I need to eliminate ((2,2)

or (2,2.1)) and ((5,5) or (5.4,5)), so that no point in the matrix are

closer than .5 to each other.

The code I wrote for this problem is an unefficient and slow one and I

would be grateful for any idea for a better performance.

Here is my code:

%points matrix contains point coordinates

pointDist = pdist(points);

iPoint = 1;

i=0;

while (i+1<=size(points,1)-1)

i = i + 1;

j = 1;

while (j<=size(points,1)-i)

if (pointDist(iPoint)<threshold)

points(i+j,:) = [];

pointDist = pdist(points);

i = 0;

iPoint = 1;

break;

end

iPoint = iPoint + 1;

j = j+1;

end

end

There's no reason to call pdist inside the loop. When

you call it the first time, you've already calculated the distance

between all pairs that exist in your set of points.

That's the main reason this loop takes so much time.

Instead of removing your points one at a time, I would

use the loop to build up a set of indexes corresponding

to the rows you want to remove, based on your precalculated

pointDist. Then use that list at the end to remove all the

rows at once.

For instance, suppose "remove_rows" is a list of

rows to remove. Then

points(remove_rows, :) = [];

will remove them all at once.

- Randy

I wonder: what you want to remove of you have a cluster of

points that are close to each other?

P1=(0,0)

P2=(0,0.4)

P3=(0.0.8)

...

- Do you keep P1 and P3? or

- Do you keep only one of the three, e.g. P1?

Otherwise, you can use delaunay triangulation, and check

only on distances between two vertexes of the same triangle.

This would accelerate the calculation.

And finally avoid to use loop in MATLAB if you could.

Bruno

Thanks a lot to Randy and Bruno for quick responses.

Randy, the method you talked about was the first method I tried to

use, but since I couldn't find an algorithm to do that, I used that

simple but inefficient method in my first message, just to achieve a

result. "Building up a set of indexes corresponding to the rows I want

to remove" as you said, is my main problem, and I wonder if anybody

knows a built-in function that would help with solving my problem.

Bruno, the goal is to have a cluster, with no point in the cluster,

closer than the threshold value to each other, so in your example any

2 of the 3 points must be removed.

I will work on delaunay triangulation, and post the result if I can

find a solution, thanks for the suggestion.

You have a set of pairs. There is a distance associated

with each pair. You search for all the pairs whose distance

is less than that value.

Where does the difficulty arise?

Perhaps the difficulty is in this clustering part of the

algorithm?

Other than that, I can't see why you abandoned your

first approach. You have a vector of distances, and each

element of that vector corresponds to a particular (i,j).

What stumbling blocks did you run into in an algorithm

that said:

for each distance

if distance < 0.5, mark something for removal

end

- Randy

OK, the problem is very easily fixed. The problem was, it was not very

easy to work on the pointDist vector. But when I turn that vector into

a square matrix with squareform function, close points are easily

removed by the following function:

function [a] = distance(a)

aDist = squareform(pdist(a));

i = 1;

while (i<size(aDist,1))

j=i+1;

while(j<=size(aDist,1))

if(aDist(i,j)<.5)

a(j,:)=[];

aDist(:,j) = [];

aDist(j,:) = [];

end

j = j+1;

end

i=i+1;

end

1. tunnel point to point vs physical point to point

2. wireless point to point (multi point)

3. Scenario 5: IS-IS routing on Frame Relay Multi-point and Point-to-Point

4. How to find closest point(s) around a specific point in point cloud?

5. triangle-point triangle-line segment and triangle-triangle closes point question

6. From point A to point B to... point Z

7. How to find closest point(s) around a specific point in point cloud?

8. Make one point larger than the rest of points in a point series

9. find close points in a point cloud

10. xp point-to-point-to-point settings

11. The Matrix constructor Matrix(Rectangle, Points[])

12. Closing a document without closing Power Point

13. Dot points / indexing points

14. How to remove "Microsoft point to point adapter" ?

15. Adjusting a points points GDI+ C++

6 post • Page:**1** of **1**