# Dividing polyline layer in clusters with specific requirements in ArcGIS for Desktop?

For my work in ArcGIS 10.2 for Desktop I need to divide line layers into clusters/groups. Currently I am doing this manually, but I like to automate this. The line layers can consist of 50 up to 2500 segments (smaller lines). What I need to achieve is that the line layer is divided in a n of clusters (where n can be set by the user) which meet the following requirements. In order of importance:

1. The first requirement is that a cluster should always consist of 8 or more segments.
2. The second is that the segments should be near each other.
3. The third is that the clusters should have a equal n of segments.

So to explain this order of importance a little bit more I have to examples with pictures:

First example of a line layer to be divided in 24 clusters with a average of 20 segments per cluster. The red arrow is a part of the line layer which consists of 4 segments. So this should form 1 cluster with several segments of the part with the green arrow, so that it is at least 8 segments, but preferable 20 segments. Second example. In case the whole line layer is 60 segments to be divided in 3 layers, the ideal situation would be 3 clusters with each 20 segments which are connected to each other. But if there is a isolated part of the line layer which consists of 10 segments (1) this should be 1 cluster and the other part which consist of 50 segments should be divided in 2 clusters (2 & 3) of 25 segments (see picture)

I tried to achieve this task by looking at some arcgis tools but didn't found a solution yet. For example the grouping analysis tool, but up to now I was not able to customize it enough to meet my requirements. I also found this post which is kind of what I am looking for but not completely: divide polygons in equal number of groups. But as far as I understand this does not meet my requirements completely, especially the order of importance. Thereby the solution of FelixIP is hard for me to understand and therefor I am not able to judge if I can use this.

So, at this point it seems to me that my problem is a difficult mathematical problem to solve, especially with the standard tools in Arc. But maybe anyone does have some good ideas/methods (maybe with a customized python script) to get this task done or at least can get me on the right track?

• Have a look at sDNA, it generates various metrics, there may be a combination of values that could help? For the record, I've not used this software so cannot comment on it. – Hornbydd Oct 2 '15 at 14:52

I posted multiple times on this Q, e.g here. It seems though I did poor explaining of how my method of grouping works, because so many users are struggling to understand it. This is another attempt based on the most basic of all examples I can come up with.

Let's put 6 points on straight line: and try to create 3 groups with equal count of memebers in each.

To do so we'll iterate through all combinations of nodes by two, e.g.(0,1), (0,2), (0,3)...(3,4),(3,5),(4,5). For every combination we'll test remaining nodes/candidates and assume that candidate belongs to 1st node's group if it's distance to 1st node in combination is less than to 2nd node in combination. Otherwise this candidate belongs to 2nd node's group. We'll break when 2nd (big) group is twice the size of 1st (small) group, i.e.

RATIO of group sizes = 3-1 = 2.

Our 1st (small) group will become our 1st cluster.

Table below shows results of iterations As one can see we reached solution (RATIO of 2nd/1st = 2) at step 13 and nodes [3,2] is our first cluster.

We start all over again going through remaining nodes [4,5,0,1] this time trying to achieve RATIO=2-1=1. When RATIO of 1 is achieved, we'll get cluster No 2. The rest is cluster No 3.

Please note if we were less adamant and simply computed ratio of big/small group sizes, we'd achieve solution at 2nd iteration with 1st cluster=[2,3].

So, the only thing needed to implement this method is the ability to calculate shortest distance between any 2 nodes A and B. Also there is no need even to calculate actual distance, it is enough to set it equal to 1 between all immediate neghbours, thus length of travel will become equal to number of links passed while travelling from A to B. There are plenty of shortest algorithms available as separate Python functions. I prefer to use networkx simply because it makes a code shorter. Any geometry (points, polylines and polygons) can represent nodes.

The only thing required is definition of neighbours and in any decent GIS spatial join (nodes to itself) with one to many option does it, i.e. creates a pairs of connected neighbours. The records in this table are links.

I think that method explained above can be easily adapted to solve question in OP. There is just 1 step to add - combine intersecting segments together and treat each such cluster individually, e.g. defining number of sub-groups by

N=int(total_segment_count_in_cluster/20)

If individual cluster contains << 20 segments, leave it for further analysis, with different type of spatial join relationship (within the distance of).

• Thanks for your explanation, the method is more clear to me now. I need to dive into it now to see if I get it done. Especially the 1 step to add and where to add it is not completely clear to me yet. – epke Oct 6 '15 at 14:40
• It's separate question you have to ask – FelixIP Oct 6 '15 at 18:04