5

I am using ArcGIS Desktop 10x.

I have a shapefile of 300 points which I need to make groups, each of which will contain exactly 9 points which are closest neighbors.

enter image description here

I tried the 'near' tool, which have added NEAR_FID and NEAR_DIST to the attribute table but couldn't use it to group 9 neighbors. I also tried 'grouping analysis' tool but this only makes 2 groups overall with variable number of members each time.

enter image description here

Anyone have any better idea?

  • The groups you are talking about, you want them to be polygons? Or selections? I assume you want 300 unique groups? One group for each point, right? Or do you want to divide the 300 unique points into 33 groups so that each point is only in one unique group? – LMB Jul 27 '17 at 9:04
  • It'd be best if I have ~33 groups with a group-id assigned to each. The groups at the end wont have 9 members so they can have "no-group id" (ie 999 or something) – blu_sr Jul 27 '17 at 9:08
  • That is quite a problem. Say you start at a point and group it with its 9 nearest neighbors. If you look at another point near the edge of that group (but within it), it has 9 different nearest neighbors. Since points near the edge of that group (but outside it) are nearer than some of the other points in the group. So the distribution of the groups is dependent on which point you use to define your nearest neighbors. Does that make sense? What is the goal of your analysis? Perhaps another method is more suited to the task. – LMB Jul 27 '17 at 9:13
  • I think I get you. My goal is to divide the point-set into a number of groups which will later be used for more localized research. Dividing these points into 'group-of-9' is currently what needed. – blu_sr Jul 27 '17 at 9:45
5

Result of clustering technique suggested by @Albert shown by colours of points in the picture below. Output will greatly depend on physical order of points in a feature class. At some stage it will result in "islands", that are grouped in a very disperse "cluster", e.g. red points in group "C" below. Note that points are labelled by their FID.

Algorithm that I described multiple times (see my comments to this post) successfully negotiates this issue, producing continious clusters. Output shown by colours of rectangles: enter image description here

Picture below shows algorithm applied to 297 points by 9 in groups:

enter image description here

UPDATE:

To produce above result I computed Voronoi polygons for points of interest and followed steps described here. Perhaps you can do the same and see if you like output.

Alternatively: Call your points NODES in the table of content (shapefiles only!).

arcpy.AddGeometryAttributes_management("NODES")
arcpy.SpatialJoin_analysis("NODES", "NODES", "./links.shp", "JOIN_ONE_TO_MANY","INTERSECT", search_radius="1500 Meters")
arcpy.SelectLayerByAttribute_management("links",""""TARGET_FID" = "JOIN_FID"""")
arcpy.DeleteFeatures_management(in_features="links")
arcpy.AddField_management("links", "TIMES", "DOUBLE")
arcpy.CalculateField_management("links", "TIMES", "math.hypot( !POINT_X! - !POINT_X_1!, !POINT_Y!- !POINT_Y_1! )", ."PYTHON_9.3")
arcpy.AddField_management("NODES", "RCVNODE","LONG")
arcpy.AddField_management("NODES", "P2013","LONG")
arcpy.CalculateField_management("NODES", "P2013", "1")

Create tool as shown in hyperlinked post and run it. Check values in field RCVNODE of NODES, this is a group number assigned to your points. If script fails it means that distance in spatial join is too small and you've got islands not connected to the rest of network. Increase distance.

Remember that any solution is only one out of countless possible solutions. If you don't like it try to reorder nodes in the table.

Note that with very little efforts you can visualize your LINKS points into lines connecting NODES:

enter image description here

  • I see you have put some thought into this. It is clearly a much developed an accurate approach and looks like it solves the problem with islands of unnatural clusters – Albert Jul 28 '17 at 9:23
  • Can you please specify the steps. Where do I start? – blu_sr Jul 28 '17 at 14:15
  • I'll my answer later today in a meantime read gis.stackexchange.com/questions/153094/… – FelixIP Jul 28 '17 at 20:52
2

Like LMB said, the groups would differ depending on the seed you use.

You could do this in Python and it's relatively easy. This is the general idea, of course you will need some loops and counters to assign groups.

  1. Create a memory layer with all your points.
  2. Select a starting point manually from your original dataset, ideally a point in a corner.
  3. Calculate its group (group = 1 until you reach 9 recursions, then group = group +1)
  4. Delete the same point ID of the selected point from the memory layer
  5. Find the closest point from the selected point against the memory layer with the near tool
  6. Select this same ID in the original dataset and start again from step 3

The idea is to run the near tool and find the closest point which will be in the same group until you start the following group. The principal thing is deleting the points already assigned when running the near tool again.

  • 1
    I'm not sure if this would work as you would expect. You would jump from each point to each nearest point (but not back) until you reach 9. Say you apply this to the case 9 points on a straight line with a distance of 5 between each point. This method would jump along the straight line. Even if on either side of the line there is a point with a distance of 6 (draw on paper to visualize). This seems couter intuitive. This could be solved by selecting the 8 nearest points at once. And deleting them afterwards. You could say a batch-version of the method proposed by @Albert – LMB Jul 27 '17 at 12:52
  • You are right!! It should look for the 8 closest at once. – Albert Jul 27 '17 at 13:01
  • This will quickly create voids in the middle with disconnected small islands very far from each other – FelixIP Jul 27 '17 at 19:32
  • @FelixIP, that is also true. So I still think manual grouping is your best option time/returns wise. You would miss out on the satisfaction of solving the problem however. – LMB Jul 27 '17 at 19:53
  • It is doable, see my 1st comment and perhaps gis.stackexchange.com/questions/173412/… – FelixIP Jul 27 '17 at 20:19
0

Genetic Algorithms have been found to be useful for clustering. Perhaps the one of these solutions could be constrained to yield clusters of 9 points.

Using Genetic Algorithms in Clustering Problems

Genetic algorithm-based clustering technique

Clustering Genetic Algorithm enter image description here

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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