Theme and Variations

Saturday, October 29, 2011

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
 

No comments:

Post a Comment

If your thinking about something.

Type it here.

Purpose: Ecological Services

To promote
Biodiversity, Resilience, Complexity, feedback
In
Neighborhoods, Communities, Regions
For
Waste assimilation, recycling, reusing, economy, animal habitat, food production, carbon sequestering, water and land quaility
By
Investing in pre-existing systems, entrepreneurial methods, creating ecocentric communities