Writing a function to group locations

2 次查看（过去 30 天）
Erik J
Erik J 2017-2-4
评论： Walter Roberson 2017-2-5
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.
  1 个评论
Walter Roberson
Walter Roberson 2017-2-5
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.

请先登录，再进行评论。

请先登录，再回答此问题。

回答（2 个）

Chad Greene
Chad Greene 2017-2-4
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.
  1 个评论
Erik J
Erik J 2017-2-5
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.

请先登录，再进行评论。

Walter Roberson
Walter Roberson 2017-2-4
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.
  2 个评论
Erik J
Erik J 2017-2-5
Good point, I think the inter-distance matrix I've created solves this problem.
Walter Roberson
Walter Roberson 2017-2-5
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.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Automated Driving Toolbox 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by