<s> """<STR_LIT>""" <EOL> from __future__ import division <EOL> import numpy as np <EOL> from skimage import img_as_bool <EOL> def rdp_indexes ( points , eps2 , dist2 = None ) : <EOL> """<STR_LIT>""" <EOL> dist2 = point_line_dist2 if dist2 is not None else point_line_dist2 <EOL> N = len ( points ) <EOL> keep = [ <NUM_LIT:0> , N - <NUM_LIT:1> ] <EOL> stack = [ ( <NUM_LIT:0> , N - <NUM_LIT:1> ) ] <EOL> for i in xrange ( N ** <NUM_LIT:2> ) : <EOL> if not stack : <EOL> return sorted ( keep ) <EOL> i0 , i1 = stack . pop ( ) <EOL> if i1 <= i0 + <NUM_LIT:1> : <EOL> continue <EOL> d = dist2 ( points [ i0 + <NUM_LIT:1> : i1 ] , points [ i0 ] , points [ i1 ] ) <EOL> i = np . argmax ( d ) <EOL> dmax = d [ i ] <EOL> i += i0 + <NUM_LIT:1> <EOL> if dmax > eps2 : <EOL> keep . append ( i ) <EOL> stack += [ ( i0 , i ) , ( i , i1 ) ] <EOL> assert False <EOL> def point_line_dist2 ( p , l1 , l2 ) : <EOL> """<STR_LIT>""" <EOL> p , l1 , l2 = np . asarray ( p ) , np . asarray ( l1 ) , np . asarray ( l2 ) <EOL> ap = l1 - p <EOL> n = l2 - l1 <EOL> n /= np . sqrt ( sum ( n ** <NUM_LIT:2> ) ) <EOL> dist = ap - np . outer ( n , np . dot ( ap , n ) ) . T <EOL> return np . sum ( dist ** <NUM_LIT:2> , <NUM_LIT:1> ) <EOL> def img2line ( img ) : <EOL> """<STR_LIT>""" <EOL> img = img_as_bool ( img ) <EOL> Ns = sum ( img , axis = <NUM_LIT:1> ) <EOL> N = sum ( Ns ) <EOL> ni , nj = img . shape <EOL> jrange = np . arange ( nj ) <EOL> iseq = np . zeros ( N , dtype = int ) <EOL> jseq = np . zeros ( N , dtype = int ) <EOL> ii = iseq <EOL> jj = jseq <EOL> for i , n in enumerate ( Ns ) : <EOL> ii , ii [ : n ] = ii [ : n ] , i <EOL> jj , jj [ : n ] = jj [ : n ] , jrange [ img [ i , : ] == <NUM_LIT:1> ] <EOL> assert not ii <EOL> assert not jj <EOL> return iseq , jseq </s>
