Creating laps in ArcGIS for Desktop?

I have one layer of roads(polylines) and another one that marks the intersections(points) of those roads.

The task is to create laps(one circuit of a racecourse or track) of 2000m, 5000m and so on. They have to be rounds so the startng point is the same as the endpoint.

I have built a network in ArcMap and I did a spatial join between these two layers, but I don't know how to go from there or if I'm even on the right track.

I'd like a solution for ArcMap 10.2.2.

Answer

I tested the following seemingly weird idea:

1. Take a NODE of a dangle-free graph


2. Find set of nodes that are closer than half of required total length (L), count of them = N


3. Create lap/path NODE=>permutation of (N,2)=>NODE.


4. Prohibit using the travelled edges and nodes


5. Calculate length of lap (l)


6. Break if abs(L-l)/L < tolerance and select relevant edges/nodes, otherwise set NODE to next node in the graph and go to 1.

Try this idea on below graph and you’ll see that most of all possible lap lengths (3,4,5,6) can be found rather quickly. The only exception is 7.

Strange, but true, it works for much larger networks.

Script below designed to work as a tool to be run from active mxd. It expects to have two layers called “NODES” and “LINKS” in the mxd. The fields that matter are shown below:

Field “fi” in links table stores FID of node at the start of the link, “ti” – the same for end of line.

I tested script (you’ll need networkx module installed) on a graph with 750 edges and 509 nodes. Note: result greatly depends on first node(s) location, unless user set findBest equal True. One of the lines shown below was derived using findBest=True option and the same L = 4000 m and it took significantly more time to compute:

Script:

import arcpy, traceback, os, sys
import itertools as itt

sys.path.append(r'C:\Users\felix_pertziger\AppData\Roaming\Python\Python27\site-packages')
import networkx as nx

try:
    def showPyMessage():
        arcpy.AddMessage(str(time.ctime()) + " - " + message)
## RUN SETTINGS
    TARGET=4000
    TOLERANCE=0.05
##  SET TO TRUE TO FIND BEST POSSIBLE SOLUTION

    findBest=False
##  FIND LAYERS and FIELDS
    mxd = arcpy.mapping.MapDocument("CURRENT")
    theNodesLayer=arcpy.mapping.ListLayers(mxd,"NODES")[0]
    result=arcpy.GetCount_management(theNodesLayer)
    nNodes=int(result.getOutput(0))
    theLinksLayer=arcpy.mapping.ListLayers(mxd,"LINKS")[0]
    arcpy.SelectLayerByAttribute_management(theLinksLayer, "CLEAR_SELECTION")        
    linksFromI,linksToI="fi","ti"
##  CREATE GRAPH

    G=nx.Graph()
    with arcpy.da.SearchCursor(theLinksLayer, ("FID",linksFromI,linksToI,"Length")) as cursor:
        for m, f,t,c in cursor:
            G.add_edge(f,t,weight=c)
            G[f][t]['rw']=c
            G[f][t]['no']=m
##  INITIAL CONDITIONS
    arcpy.SetProgressor("default")
    Found=False;ratioMax=100
##  MAIN LOOP

    for ij, node in enumerate(G.nodes()):
        arcpy.AddMessage("Processing %i out of %i" %(ij,nNodes))
        aBmNodes=[]
        for other in G.nodes():
            L=nx.dijkstra_path_length(G,node,other)
            if L>TARGET/2:continue
            aBmNodes.append(other)
        aBmNodes.remove(node)
        for chain in itt.permutations(aBmNodes, 2):
            arcpy.SetProgressorPosition()

            aList=list(chain)
            one=node; aList.append(one)
            lTotal=0; path=[one]
            for two in aList:
                gL=nx.dijkstra_path(G,one,two)
##              BLOCKING ATTEMPT to TAKE THE SAME ROAD
                for i,t in enumerate(gL):
                    if i==0:
                        f=t; continue
                    lTotal+=G[f][t]['weight']

                    path.append(t)
                    G[f][t]['weight']=1e6
                    f=t
                one=two
            f=path.pop(0)
##          BLOCKING ATTEMPT to GO THROUGH SAME NODE
            control=path[:]
            if len(path)>len(set(control)):
                continue
##          RESTORE ORIGINAL WEIGHTS

            for t in path:
                G[f][t]['weight']=G[f][t]['rw']
                f=t
            ratioCur=abs(TARGET-lTotal)/TARGET
            if ratioCur                bestList=aList[:]
                bestPath=path[:]
                ratioMax=ratioCur
                arcpy.AddMessage('Best match so far %i' %lTotal)
            if abs(TARGET-lTotal)/TARGET<=TOLERANCE:

                Found=True
                if not findBest:break
        if Found and not findBest:break
## SELECT NODES TRIO and LINKS for LAP
    quer='"FID" IN '+str(tuple(bestList))
    arcpy.SelectLayerByAttribute_management(theNodesLayer, "NEW_SELECTION", quer)        
    f=bestPath[-1]; ListOfLinks=[]
    for t in bestPath:
        ListOfLinks.append(G[f][t]['no'])
        f=t

    quer='"FID" IN '+str(tuple(ListOfLinks))
    arcpy.SelectLayerByAttribute_management(theLinksLayer, "NEW_SELECTION", quer)        
except:
    message = "\n*** PYTHON ERRORS *** "; showPyMessage()
    message = "Python Traceback Info: " + traceback.format_tb(sys.exc_info()[2])[0]; showPyMessage()
    message = "Python Error Info: " +  str(sys.exc_type)+ ": " + str(sys.exc_value) + "\n"; showPyMessage()