<s> """<STR_LIT>""" <EOL> import vmath <EOL> __version__ = '<STR_LIT>' <EOL> __dependencies__ = [ '<STR_LIT>' ] <EOL> class Node ( object ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , vertex_index , split_axis ) : <EOL> self . vertex_index = vertex_index <EOL> self . split_axis = split_axis <EOL> self . left_child = None <EOL> self . right_child = None <EOL> def points_within_uv_distance ( self , positions , position , position_tolerance , uvs , uv , uv_tolerance ) : <EOL> """<STR_LIT>""" <EOL> def __points_within_distance ( node , results ) : <EOL> """<STR_LIT>""" <EOL> if not node : <EOL> return <EOL> vertex_index = node . vertex_index <EOL> this_position = positions [ vertex_index ] <EOL> this_uv = uvs [ vertex_index ] <EOL> if vmath . v3equal ( this_position , position , position_tolerance ) and vmath . v2equal ( this_uv , uv , uv_tolerance ) : <EOL> results . append ( vertex_index ) <EOL> split_axis = node . split_axis <EOL> v_axis = this_position [ split_axis ] <EOL> p_axis = position [ split_axis ] <EOL> if ( p_axis + position_tolerance ) < v_axis : <EOL> __points_within_distance ( node . left_child , results ) <EOL> elif ( p_axis - position_tolerance ) > v_axis : <EOL> __points_within_distance ( node . right_child , results ) <EOL> else : <EOL> __points_within_distance ( node . left_child , results ) <EOL> __points_within_distance ( node . right_child , results ) <EOL> results = [ ] <EOL> __points_within_distance ( self , results ) <EOL> return results <EOL> def points_within_distance ( self , vertexes , point , distance ) : <EOL> """<STR_LIT>""" <EOL> def __points_within_distance ( node , results ) : <EOL> """<STR_LIT>""" <EOL> if not node : <EOL> return <EOL> vertex_index = node . vertex_index <EOL> vertex = vertexes [ vertex_index ] <EOL> if vmath . v3equal ( point , vertex , distance ) : <EOL> results . append ( vertex_index ) <EOL> split_axis = node . split_axis <EOL> v_axis = vertex [ split_axis ] <EOL> p_axis = point [ split_axis ] <EOL> if ( p_axis + distance ) < v_axis : <EOL> __points_within_distance ( node . left_child , results ) <EOL> elif ( p_axis - distance ) > v_axis : <EOL> __points_within_distance ( node . right_child , results ) <EOL> else : <EOL> __points_within_distance ( node . left_child , results ) <EOL> __points_within_distance ( node . right_child , results ) <EOL> results = [ ] <EOL> __points_within_distance ( self , results ) <EOL> return results <EOL> def build_kdtree ( vertexes ) : <EOL> """<STR_LIT>""" <EOL> return build_kdtree_nodes ( vertexes , range ( len ( vertexes ) ) ) <EOL> def build_kdtree_nodes ( vertexes , indexes , depth = <NUM_LIT:0> ) : <EOL> """<STR_LIT>""" <EOL> if not indexes : <EOL> return <EOL> split_axis = depth % <NUM_LIT:3> <EOL> indexes . sort ( key = lambda v : vertexes [ v ] [ split_axis ] ) <EOL> median = len ( indexes ) / <NUM_LIT:2> <EOL> node = Node ( indexes [ median ] , split_axis ) <EOL> node . left_child = build_kdtree_nodes ( vertexes , indexes [ <NUM_LIT:0> : median ] , depth + <NUM_LIT:1> ) <EOL> node . right_child = build_kdtree_nodes ( vertexes , indexes [ median + <NUM_LIT:1> : ] , depth + <NUM_LIT:1> ) <EOL> return node <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> import random <EOL> NUM = <NUM_LIT:1000> <EOL> VERTEXES = [ ( random . random ( ) , random . random ( ) , random . random ( ) ) for x in range ( NUM ) ] <EOL> ROOT = build_kdtree ( VERTEXES ) <EOL> POINT = ( <NUM_LIT> , <NUM_LIT:0.5> , <NUM_LIT> ) <EOL> DISTANCE = <NUM_LIT:0.1> <EOL> RESULTS = ROOT . points_within_distance ( VERTEXES , POINT , DISTANCE ) <EOL> RESULTS . sort ( ) <EOL> for r in RESULTS : <EOL> print "<STR_LIT>" % ( r , VERTEXES [ r ] , POINT ) <EOL> print "<STR_LIT:=>" * <NUM_LIT> <EOL> for i , x in enumerate ( VERTEXES ) : <EOL> if vmath . v3equal ( x , POINT , DISTANCE ) : <EOL> print "<STR_LIT>" % ( i , x , POINT ) </s>
