#NEWLINE# def simplifyDouglasPeucker( points , tolerance ) : #NEWLINE# #INDENT# length = len ( points ) #NEWLINE# markers = ( [ 0 ] * length ) #NEWLINE# first = 0 #NEWLINE# last = ( length - 1 ) #NEWLINE# first_stack = [ ] #NEWLINE# last_stack = [ ] #NEWLINE# new_points = [ ] #NEWLINE# markers [ first ] = 1 #NEWLINE# markers [ last ] = 1 #NEWLINE# while last : #NEWLINE# #INDENT# max_sqdist = 0 #NEWLINE# for i in range ( first , last ) : #NEWLINE# #INDENT# sqdist = getSquareSegmentDistance ( points [ i ] , points [ first ] , points [ last ] ) #NEWLINE# if ( sqdist > max_sqdist ) : #NEWLINE# #INDENT# index = i #NEWLINE# max_sqdist = sqdist #NEWLINE# #UNINDENT# #UNINDENT# if ( max_sqdist > tolerance ) : #NEWLINE# #INDENT# markers [ index ] = 1 #NEWLINE# first_stack . append ( first ) #NEWLINE# last_stack . append ( index ) #NEWLINE# first_stack . append ( index ) #NEWLINE# last_stack . append ( last ) #NEWLINE# #UNINDENT# if ( len ( first_stack ) == 0 ) : #NEWLINE# #INDENT# first = None #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# first = first_stack . pop ( ) #NEWLINE# #UNINDENT# if ( len ( last_stack ) == 0 ) : #NEWLINE# #INDENT# last = None #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# last = last_stack . pop ( ) #NEWLINE# #UNINDENT# #UNINDENT# for i in range ( length ) : #NEWLINE# #INDENT# if markers [ i ] : #NEWLINE# #INDENT# new_points . append ( points [ i ] ) #NEWLINE# #UNINDENT# #UNINDENT# return new_points