Traverse Line With Multiple Vertices

Command Line Execute of Path Tracing Program

Path With Multiple Vertices's, After Traveling Halfway Down

Close Up Of Location After Running Program

 

Way-point finding algorithm

            The 'path' is a multi-segment line, 'poly-line', each segment is composed of a start and end vertices. The more detailed the path the more segments are needed to describe the shape of the poly-line.  The poly-line for the Echo::System project was relatively coarse (in comparison to the 75881 meters that path traversed) using 30 vertices (ie pairs of x and y coordinates); however,  30 vertices is adequate. The goal is to 1) render the current location on a map and 2) use the new coordinates to perform a spatial query of a database, with a 100 meter buffer. The spatial query was an intersection of the geometry in the database with a circle buffer around the way-point. 

            The Algorithm to find a 'way point' for any distance along the path  is a combination of the pythagorean theorem, a line interpolation function, and a few if statements to handle the fringe cases.  The algorithm takes a distance and returns the coordinates of the way-point, ie the current location.  The way-point can then be rendered, after scaling, in a graphic interface or the way-point is used, with-out scaling, to query the spatial database. 

            All the vertices were captured by hand digitization in a GIS (Geographic Information System).  Here, the vertices that are found in this report are accurate when used in the projection system  UTM 27 12N (The 1927 standard of projection, in central Arizona 12N.   However, any means of capturing or simply writing  a set of coordinates would work—depending of the application and subsequent utilization of the way point geometry. For example, to simply render a moving object through a Cartesian coordinate system, one could simply write the coordinates of that system in two arrays—one for x and one for y and then apply the algorithm iteratively to have an object traverse the set of vertices.

 

**PYTHON CODE**




**Though this is python syntax, the algorithm and structure of data is easy to read and simple to convert to any language.**




import math

import sys

"""THE X AND Y ARRAY< UTM COORIDINATES NAD27 12N"""

XCOORD = [412289.298439, 412726.272491,412762.686995, 412981.174021, 421975.556587, 422011.971091, 421866.313074, 422011.971091,421793.484065, 421731.148716, 421811.604292, 421802.707074, 421724.811872, 421684.240552, 423213.649734, 429386.697708, 430136.355440, 430751.452127, 432353.690317, 433591.783463, 434028.757515, 435048.363636, 442985.698246, 451179.989048, 451088.439122, 450488.113466, ]

YCOORD = [3698314.413159, 3698277.998655, 3697622.537577, 3697404.050552, 3697404.050552, 3694873.242502, 3694509.097458, 3693926.465389, 3693198.175303, 3682258.321551, 3681768.668214, 3681288.218442, 3681146.205408, 3674025.938781, 3673133.783425, 3666978.075473, 3665894.790950, 3664813.069189, 3664194.022616, 3662701.027939, 3660916.717227, 3658731.846969, 3651541.523362, 3651428.170527, 3649901.843337, 3649790.545163,]

#needs length of line, and distance

def getPercentPosition(d, l):                             

            p = d/l                                                  #percent of line travelled

            return p                                     #returns a fraction of distance/totalLength (ie .5 halfway)

# coordinates of segment ((a1,b1)(a2,b2)) and how far we are inbetween

def getCoordinatesOnLine(a1, a2, b1, b2, percentPosition):       

            p = percentPosition

            w1 = (a1 * (1-p)) + b1 * p                                               # for the x coordinate

            w2 = (a2 * (1-p)) + b2 * p                                                # for the y coordinate

            return w1, w2                                                    

# good ol' pythagorean, length of line in 2 dimensions

def getLengthOfLine(a1,a2,b1,b2):                                            

            l = math.sqrt(math.pow((b1-a1),2)+(math.pow((b2-a2),2)))

            return l

#make an array for each of the segment ((XCOOR,YCOOR)(XCOOR+1,YCOOR+1))

def buildLengthTable():                                                 

            totalLength = 0.0                                               #total length of arcs:

            for i in range(0, len(XCOORD)-1):          

                        l = getLengthOfLine(XCOORD[i], YCOORD[i], XCOORD[i+1], YCOORD[i+1])

                        segmentLength.append(l)

                        totalLength = l + totalLength

def segmentByCount(distance):

            distanceToTravelonSegment = distance

            for segment in segmentLength:              # go through each element in segmentLength[].

                        # if the distance to travel is less than the first segment, then your done.

                        if distanceToTravelonSegment

                                    # we've arrived at the segment where we will stop.

                                    break                                       

                        # if the distance to travel is greater than the current segment.

                        if distanceToTravelonSegment>segment:           

                                    # the segment is traveled, the distanceToTravel is lessened.

                                    distanceToTravelonSegment =  distanceToTravelonSegment - segment   

                                    count = count + 1

            return distanceToTravelonSegment, count

def main(distance):

            distanceToTravel = sys.argv[1]   # The argument provided by the caller

            segmentLength = []                               # array of all the segment lengths

            totalLength = 0.0                                   # total length of all arcs (nice to know)

            distanceToTravel= 0.0                # the distance that will be traveled

            w1 = 0.0                                                # coordinates on line after distance traveled

            w2 = 0.0                                                # coordinates on line after distance traveled

            count = 0

            buildLengthTable()

            distanceToTravel, count = segmentBYCount(distance)

            positionOnline = getPercentPosition(distanceToTravel,segmentLength[count])

            w1, w2 = getCoordinatesOnLine(XCOORD[count], YCOORD[count], XCOORD[count+1], YCOORD[count+1], positionOnline)

            print "UTM coordinates: ", w1, w2