470,594 Members | 1,644 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 470,594 developers. It's quick & easy.

Algorithm to identify point connection

The dataset contains geodesic points, even spaced, which show elevations for each point. The goal identify the number of islands in the dataset. Say for a dataset which represents a map of the united kingdom there would be 2 (major islands) + a number of smaller island as the result.

What is a good way to algorithmically acheive this?
Oct 14 '16 #1
1 2829
983 Expert 512MB

You will have to use an adaptive algorithm that finds disjoint sets. The algorithm is recursive...

Algorithmically, I would try the following:
Expand|Select|Wrap|Line Numbers
  1. Create three sets - non-sampled points, water, and islands. 
  2. non-sampled points and water are sets of raw data.
  3. islands is a set of sets, each entry will be an island. 
  5. Find-Water
  6. For each point in non-sampled, if elevation is zero, move to water set. 
  8. Find-Island: 
  9. Select a point from non-sampled points, this will be part of a unique island.  
  10. Remove this point from non-sampled points 
  11. Add this point to temporary-set of island-points 
  12. For each adjacent location, do Extend-Island(point, island-points)
  14. Extend-Island(point, island-points): 
  15. If point is in non-sampled points Then
  16.   Remove point from non-sampled points
  17.   Add point to island-points
  18.   For Each adjacent location, do Extend-Island(point, island-points)
  19. Endif
Oct 15 '16 #2

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

4 posts views Thread by kevin.hall | last post: by
5 posts views Thread by Fred Zuckerman | last post: by
10 posts views Thread by Brian Conway | last post: by
4 posts views Thread by Josh Carlisle | last post: by
4 posts views Thread by csgraham74 | last post: by
1 post views Thread by Ghada Al-Mashaqbeh via DotNetMonster.com | last post: by
2 posts views Thread by Shum | last post: by
3 posts views Thread by Airslash | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.