Writing a function to group locations

I have a large data set of locations. Currently these data are organized as a distance in meters and bearing in degrees from a common point. I need a function that will go through and group all of these locations based on how close they are to each other. I want to go through and call any locations within 100m and 30 degrees of each other the "same location". I want the function to label all spots that are in the same location with the same number. So I get out a vector categorizing each place as Place 1, Place 2, and so forth.

Is this possible?

x = vector of distance in meters from reference; az = vector of bearing in degrees from reference

output = vector grouping all places within 100m and 30 degrees as 1, 2, 3, etc.

[Walter Roberson]

In a follow-up question, Erik J writes,

I have a large matrix representing points in a Euclidean plane. I need to group together all points which are within 100meters of each other and call these points the "same place."

I have created a 15000x15000 inter-point distance matrix that has the distance between each point and any other point. I need to figure out a way to loop through this data and group together all points within 100m of each other and return something like "Points 1, 5, 312, 534, and 10452 are all within 100m of each other so this is Place 1."

Any ideas? I am quite stuck on this problem.

Answer 1

[Chad Greene]

I would convert the distance and azimuth vectors to cartesian coordinates by pol2cart, then find inter-point distances with John D'Errico's ipdm function. That way you could define an absolute distance between points, rather than needing to say points must be within a certain distance and angle.

[Erik J]

Thanks. I did this and I think it's a good approach. I have the inter-distance matrix, but I'm still not sure how to go through and group the points. See above.

Answer 2

[Walter Roberson]

You could use ismembertol() to find values within a range.

However, "within 30 m of each other" is not transitive, and that can be a serious problem. Consider 10 25 50 . Both 10 and 50 are within 30 of 25, but 10 is not within 30 of 50.

[Erik J]

Good point, I think the inter-distance matrix I've created solves this problem.

[Walter Roberson]

Since you have the difficulty of that membership in the group is not transitive, you probably want to find the largest possible subsets that are all within range of each other. That is the Clique problem.

You can find an implementation at https://www.mathworks.com/matlabcentral/fileexchange/30413-bron-kerbosch-maximal-clique-finding-algorithm or https://www.mathworks.com/matlabcentral/fileexchange/47524-find-maximal-cliques-for-large---sparse-network

Note that the answers are not unique, so you will get back results that typically involve any given node in a number of cliques. There is no real way of distinguishing between the solutions -- though you might be able to go further and find a maximal subset of maximal cliques, that together involve the greatest number of points.