2

I have two point clouds, one with demographic and one with electoral data. Points in both clouds represent the same empirical entity (say, a village, or an urban neighbourhood), but are not in the exact same lat/long (different datasources, GPS inaccuracies, etc). Moreover, one village can have several points in each cloud. I am looking for a cluster or nearest neighbor algorithm which allows me to merge both point clouds. I have thought about two strategies:

a) do a nearest neighbor matching, starting from the first point cloud and adding a variable to each point that directs me to the respective closest point in the second point cloud. The problem is that no method for nearest neighbor matching which I found (GRASS, SAGA, R) ensures that all points in the second cloud are picked at least once as this "respective closest point" for the first cloud. A neverending circle which could probably approximately be optimized - but I have no idea how. Any suggestions welcome.

b) the second strategy sees it as a clustering problem, in which I attempt to recreate the underlying empirical entity "village", which might contain multiple electoral and demographic points, but must contain at least one of each type. In other words, I would need a bottom-up hierarchical cluster algorithm which groups points together based on their spatial proximity, but simultaneously (!) ensures that each cluster contains at least one point from the electoral point cloud and one point from the demographic point cloud. Again: any suggestions welcome.

c) there are probably other solutions that I am unaware of - I am truly a beginner here...

It would be marvellous if somebody could point me in the right direction.

closed as too broad by PolyGeo Apr 20 at 12:49

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • Do you have any information regarding the amount of precision differences between the two point clouds? For example, does Village A have GPS coordinates within .001 decimal degrees in both point clouds? My thousandths value is just a value, however the smaller the better. If the two point cloud coordinates for the same location are not "too" far off, you may be able to alter a copy of the coordinates values so that they in fact match (perhaps by rounding), without overlapping other features within the same point cloud, of course. – evv_gis Mar 13 '14 at 20:17
  • Just to add a bit of clarification of where I am going - if eventually you could have a unique identifier for one point cloud, and exact matching values in the second point cloud, you'll have the ground work done for doing a one-to-many join of the data. I recommended the coordinates because it's very simple to round decimals to the nearests N'th, and hopefully not create duplicate values. – evv_gis Mar 13 '14 at 20:20
  • Well, its not uniform - but they can be far enough off that they appear closer to the next village - so I would need an algorithm which only does one-to-one matching, so that in case the next village (to which a point is closer) is already taken (by another point which is even closer), it would revert to the original village. Does this make sense? – Raphael Mar 13 '14 at 22:07
  • Yes, I believe I understand. Hmmm, I'm going to need a minute to rethink this. – evv_gis Mar 14 '14 at 13:01
  • I will be thankful for any suggestion, even if not thought through to a perfect solution yet... – Raphael Mar 14 '14 at 13:53
2

One way to do this is the following:

  1. Create voronoi polygons of both the point layers

  2. Overlay the two voronoi layers and calculate percent overlap between them, once from the perspective of layer A, once from the perspective of layer B (i.e. "80% of voronoi of point X in layer A overlap with voronoi of point Y in layer B", while "20% of point Y in layer B overlap with voronoi of point X in layer A")

  3. Add up the two percentages to a "joint overlap" value, and sort the table so that matches with maximum joint overlap come first

  4. Move from top to bottom of the table and execute matches until all points from layer A and all points from layer B have been matched at least once

Given the unique properties of voronois (being the area closer to a specific point than to its next neighbors), the complete coverage (no leftover gaps), and the transfer of the problem into a higher dimension (area rather than proximity line), it is possible to get a matching solution that is optimized both ways - bingo!

Not the answer you're looking for? Browse other questions tagged or ask your own question.