4.2_CRD ._SENT Algorithm_NN1 overview_NN1 
In_PRP Fig._NN1 10_CRD ,_PUN a_AT0 simple_AJ0 overview_NN1 of_PRF the_AT0 algorithm_NN1 to_TO0 build_VVI the_AT0 accessibility-based_AJ0 graph_NN1 is_VBZ shown_VVN with_PRP four_CRD main_AJ0 functions_NN2 described_VVN in_PRP the_AT0 following_AJ0 sections_NN2 ._SENT The_AT0 algorithm_NN1 initializes_VVZ with_PRP the_AT0 user_NN1 parameters_NN2 and_CJC geometry_NN1 objects_NN2 that_CJT remain_VVB in_PRP a_AT0 global_AJ0 scope_NN1 ._SENT Overall_AV0 ,_PUN the_AT0 algorithm_NN1 iterates_VVZ through_PRP a_AT0 queue_NN1 of_PRF nodes_NN2 that_CJT are_VBB continually_AV0 added_VVN to_PRP the_AT0 queue_NN1 in_PRP a_AT0 breadth-first_ORD manner_NN1 from_PRP the_AT0 starting_NN1 location_NN1 𝜏_NN1 within_PRP the_AT0 environment_NN1 (_PUL buildGraph_NN1 )_PUR ._SENT While_CJS checking_VVG each_DT0 item_NN1 of_PRF the_AT0 queue_NN1 ,_PUN getNodes_NP0 iteratively_AV0 finds_VVZ the_AT0 valid_AJ0 neighbor_NN1 nodes_NN2 by_PRP calling_VVG checkChild_NN1 on_PRP each_DT0 potential_AJ0 neighbor_NN1 ._SENT The_AT0 final_AJ0 function_NN1 in_PRP the_AT0 process_NN1 ,_PUN getConnection_NN1 ,_PUN determines_VVZ if_CJS an_AT0 edge_NN1 can_VM0 exist_VVI between_PRP two_CRD nodes_NN2 based_VVN on_PRP the_AT0 input_NN1 parameters_NN2 ,_PUN and_CJC if_CJS so_AV0 ,_PUN the_AT0 type_NN1 of_PRF movement_NN1 required_VVN between_PRP the_AT0 original_AJ0 and_CJC potential_AJ0 child_NN1 node_NN1 ._SENT Once_CJS an_AT0 edge_NN1 is_VBZ determined_VVN to_TO0 be_VBI possible_AJ0 ,_PUN the_AT0 movement_NN1 type_NN1 is_VBZ returned_VVN (_PUL likewise_AV0 for_PRP all_DT0 connections_NN2 for_PRP the_AT0 original_NN1 queued_VVD item_NN1 )_PUR ._SENT Before_PRP the_AT0 breadth-first_ORD process_NN1 continues_VVZ to_PRP the_AT0 next_ORD item_NN1 in_PRP the_AT0 queue_NN1 ,_PUN the_AT0 graph_NN1 is_VBZ updated_VVN with_PRP vertices_NN2 ,_PUN edges_NN2 ,_PUN and_CJC weights_NN2 ._SENT 
4.2.1_CRD ._SENT Breadth-first_ORD process_NN1 
The_AT0 generation_NN1 of_PRF common_AJ0 surface_NN1 and_CJC graph_NN1 information_NN1 methods_NN2 regarding_PRP navigation_NN1 takes_VVZ into_PRP account_NN1 the_AT0 entire_AJ0 environment_NN1 at_PRP once_AV0 ._SENT Breadth-first_ORD search_NN1 allows_VVZ for_PRP the_AT0 fast_AJ0 completion_NN1 of_PRF the_AT0 graph_NN1 generation_NN1 when_CJS no_AT0 accessible_AJ0 locations_NN2 are_VBB found_VVN (_PUL Appendix_NN1 A_ZZ0 )_PUR ._SENT This_DT0 feature_NN1 is_VBZ particularly_AV0 useful_AJ0 in_PRP the_AT0 planning_NN1 and_CJC design_NN1 phase_NN1 of_PRF a_AT0 building_NN1 or_CJC environment_NN1 as_CJS it_PNP offers_VVZ immediate_AJ0 numerical_AJ0 and_CJC visual_AJ0 feedback_NN1 about_PRP the_AT0 features_NN2 that_CJT are_VBB blocking_VVG accessibility_NN1 ._SENT The_AT0 quick_AJ0 ending_NN1 to_PRP the_AT0 graph_NN1 generation_NN1 benefits_VVZ the_AT0 calculation_NN1 time_NN1 in_PRP practical_AJ0 use_NN1 cases_NN2 (_PUL e.g._AV0 ,_PUN the_AT0 starting_NN1 location_NN1 being_VBG a_AT0 ramp_NN1 that_DT0 is_VBZ too_AV0 steep_AJ0 )_PUR ._SENT 
Generating_VVG the_AT0 graph_NN1 begins_VVZ with_PRP a_AT0 valid_AJ0 starting_NN1 location_NN1 where_AVQ start_NN1 point_NN1 𝜏_NN1 is_VBZ above_AV0 a_AT0 valid_AJ0 surface_NN1 geometry_NN1 in_PRP 𝛤_NP0 ._SENT The_AT0 algorithm_NN1 begins_VVZ with_PRP an_AT0 empty_AJ0 graph_NN1 𝐷_NN1 and_CJC an_AT0 ordered_AJ0 set_NN1 𝑄_NN1 representing_VVG the_AT0 queue_NN1 of_PRF vertices_NN2 that_CJT remain_VVB to_TO0 be_VBI checked_VVN for_PRP validity_NN1 in_PRP 𝑃_NP0 ._SENT At_PRP initialization_NN1 𝑄_NP0 =_NP0 {_PUL 𝜏_NP0 }_PUR ,_PUN with_PRP the_AT0 algorithm_NN1 completing_VVG when_CJS 𝑄_NP0 =_NP0 ∅_NP0 ._SENT 
Generating_VVG the_AT0 graph_NN1 can_VM0 be_VBI seen_VVN in_PRP Algorithm_NN1 1_CRD line_NN1 8_CRD ,_PUN where_AVQ a_AT0 parent_NN1 node_NN1 𝑝_NN1 is_VBZ removed_VVN from_PRP the_AT0 queue_NN1 𝑄_NN1 ._SENT The_AT0 valid_AJ0 children_NN2 nodes_NN2 are_VBB assigned_VVN to_TO0 set_VVI 𝐶_NN1 and_CJC if_CJS a_AT0 child_NN1 node_NN1 is_VBZ not_XX0 already_AV0 defined_VVN as_PRP a_AT0 parent_NN1 node_NN1 ,_PUN it_PNP is_VBZ added_VVN to_PRP 𝑄_NN1 ._SENT Once_CJS the_AT0 set_NN1 of_PRF valid_AJ0 children_NN2 are_VBB returned_VVN ,_PUN the_AT0 weight_NN1 vector_NN1 containing_VVG step_NN1 type_NN1 is_VBZ stored_VVN in_PRP the_AT0 weight_NN1 set_NN1 (_PUL line_NN1 10_CRD )_PUR ._SENT This_DT0 pseudocode_NN1 shows_VVZ the_AT0 method_NN1 in_PRP which_DTQ weights_NN2 are_VBB calculated_VVN during_PRP graph_NN1 construction_NN1 ,_PUN and_CJC therefore_AV0 ,_PUN during_PRP the_AT0 iteration_NN1 over_PRP the_AT0 child_NN1 set_NN1 ,_PUN a_AT0 function_NN1 setEdgeCost_NN1 (_PUL )_PUR on_PRP line_NN1 12_CRD calculates_VVZ a_AT0 directional_AJ0 edge_NN1 cost_NN1 between_PRP the_AT0 two_CRD nodes_NN2 and_CJC stores_VVZ it_PNP in_PRP 𝑊_NN1 ._SENT This_DT0 function_NN1 can_VM0 be_VBI used_VVN to_TO0 set_VVI multiple_AJ0 types_NN2 of_PRF edge_NN1 costs_NN2 ,_PUN such_DT0 as_PRP distance_NN1 ,_PUN slope_NN1 ,_PUN and_CJC energy_NN1 ,_PUN as_CJS discussed_VVN later_AV0 ._SENT After_PRP the_AT0 directed_AJ0 edge_NN1 of_PRF a_AT0 parent_NN1 and_CJC child_NN1 is_VBZ stored_VVN ,_PUN the_AT0 child_NN1 node_NN1 is_VBZ checked_VVN for_PRP existence_NN1 in_PRP the_AT0 parent_NN1 set_NN1 ._SENT If_CJS the_AT0 node_NN1 is_VBZ not_XX0 in_PRP the_AT0 existing_AJ0 parent_NN1 set_VVB it_PNP is_VBZ added_VVN to_PRP 𝑄_NP0 ._SENT 
Two_CRD main_AJ0 functions_NN2 are_VBB defined_VVN that_CJT determine_VVB the_AT0 validity_NN1 of_PRF a_AT0 child_NN1 node_NN1 within_PRP the_AT0 getNodes_NN2 (_PUL )_PUR function_NN1 (_PUL called_VVN in_PRP Alg_NP0 ._SENT 1_CRD and_CJC later_AV0 defined_VVN in_PRP Alg_NP0 ._SENT 2_CRD )_PUR ._SENT The_AT0 function_NN1 inter_AJ0 (_PUL 𝑛𝑖_NP0 ,_PUN 𝑛𝑗_NP0 )_PUR is_VBZ defined_VVN as_PRP returning_VVG the_AT0 distance_NN1 𝑛⃖⃖⃖⃖𝑛⃖⃖⃗_NN1 intersects_VVZ 𝐵_NN1 in_PRP the_AT0 environment_NN1 and_CJC dst_NN1 (_PUL 𝑛_NP0 ,_PUN 𝑛_NP0 )_PUR returns_VVZ 𝑖𝑗𝑖𝑖𝑗_NP0 ‖_NP0 𝑛⃗_NP0 −_NP0 𝑛⃗_NP0 ‖_NP0 ._SENT 𝑖𝑗_NP0 
Fig._NN1 11_CRD shows_VVZ the_AT0 node_NN1 evaluation_NN1 in_PRP the_AT0 (_PUL 𝑥𝑧_AJ0 )_PUR plane_NN1 where_AVQ the_AT0 ray_NN1 cast_NN1 direction_NN1 is_VBZ −𝑧̂_AJ0 ._SENT As_CJS the_AT0 graph_NN1 is_VBZ in_PRP relation_NN1 to_PRP physical_AJ0 space_NN1 ,_PUN −𝑧̂_NP0 corresponds_VVZ to_PRP the_AT0 direction_NN1 of_PRF gravity_NN1 ._SENT The_AT0 parameters_NN2 and_CJC labels_NN2 used_VVN are_VBB those_DT0 described_VVN in_PRP 4.1.3_CRD ._SENT The_AT0 surfaces_NN2 illustrated_VVN provide_VVB examples_NN2 of_PRF a_AT0 step_NN1 ,_PUN faceted_AJ0 surface_NN1 ,_PUN and_CJC natural_AJ0 topography_NN1 (_PUL e.g._AV0 ,_PUN a_AT0 hill_NN1 or_CJC mountain_NN1 )_PUR ._SENT When_CJS a_AT0 possible_AJ0 node_NN1 is_VBZ invalid_AJ0 ,_PUN it_PNP is_VBZ not_XX0 added_VVN to_PRP 𝑄_NN1 ,_PUN and_CJC in_PRP the_AT0 simple_AJ0 example_NN1 within_PRP the_AT0 figure_NN1 ,_PUN the_AT0 graph_NN1 completes_VVZ ._SENT To_TO0 simplify_VVI the_AT0 illustration_NN1 ,_PUN Fig._NN1 11_CRD is_VBZ a_AT0 two-dimensional_AJ0 example_NN1 is_VBZ given_VVN and_CJC only_AV0 the_AT0 directed_AJ0 relation_NN1 from_PRP the_AT0 left_NN1 to_PRP right_NN1 is_VBZ discussed_VVN ._SENT 
In_PRP 11_CRD (_PUL a_AT0 )_PUR ,_PUN a_AT0 ray_NN1 is_VBZ cast_VVN in_PRP −𝑧̂_NP0 starting_VVG at_PRP 𝑛1_NN1 ._SENT As_CJS the_AT0 node_NN1 found_VVN from_PRP inter_AJ0 (_PUL 𝑛3_CRD ,_PUN 𝑛3_CRD −_NP0 𝑧̂_NP0 )_PUR <_NP0 𝑏𝑢_NP0 ,_PUN 𝑛3_NN1 is_VBZ considered_VVN valid_AJ0 ._SENT When_CJS checking_VVG 𝑛4_CRD ,_PUN h_ZZ0 is_VBZ reset_VVN based_VVN on_PRP the_AT0 previous_AJ0 node_NN1 (_PUL 𝑛3_CRD )_PUR ._SENT To_TO0 demonstrate_VVI the_AT0 use_NN1 of_PRF 𝛤_NP0 ,_PUN three_CRD objects_NN2 ,_PUN 𝛤_NP0 =_NP0 {_PUL 𝐵1_CRD ,_PUN 𝐵2_CRD ,_PUN 𝐵3_CRD }_PUR are_VBB represented_VVN in_PRP the_AT0 illustration_NN1 where_AVQ they_PNP are_VBB all_DT0 walkable_AJ0 surfaces_NN2 ._SENT The_AT0 last_ORD node_NN1 ,_PUN 𝑛7_CRD ,_PUN is_VBZ shown_VVN in_PRP red_AJ0 as_CJS inter_AJ0 (_PUL 𝑛7_CRD ,_PUN 𝑛7_CRD −_NP0 𝑧̂_NP0 )_PUR >_NP0 𝑏𝑢_NP0 ,_PUN ending_VVG the_AT0 graph_NN1 generation_NN1 ._SENT In_PRP the_AT0 down_AVP step_NN1 case_NN1 for_PRP parameter_NN1 𝑏𝑑_NN1 ,_PUN 11_CRD (_PUL b_ZZ0 )_PUR illustrates_VVZ the_AT0 intersection_NN1 point_NN1 for_PRP 𝑛5_NN0 falling_VVG outside_PRP the_AT0 threshold_NN1 ._SENT Finally_AV0 a_AT0 node_NN1 𝑛7_CRD is_VBZ invalid_AJ0 in_PRP 11_CRD (_PUL c_ZZ0 )_PUR as_CJS the_AT0 angle_NN1 created_VVN from_PRP 𝑛6_AJ0 and_CJC inter_AJ0 (_PUL 𝑛7_CRD ,_PUN 𝑛7_CRD −_NP0 𝑧̂_NP0 )_PUR >_NP0 𝑠𝑢_NP0 ._SENT Furthermore_AV0 ,_PUN the_AT0 relative_AJ0 positioning_NN1 in_PRP 𝑍_NN1 of_PRF parent_NN1 –_PUN child_NN1 nodes_NN2 can_VM0 be_VBI seen_VVN by_PRP the_AT0 height_NN1 variation_NN1 relative_AJ0 to_PRP the_AT0 previous_AJ0 node_NN1 ._SENT 
Algorithm_NN1 2_CRD implements_VVZ this_DT0 process_NN1 in_PRP three-dimensions_NN2 ._SENT The_AT0 function_NN1 getNodes_NN2 (_PUL p_ZZ0 )_PUR takes_VVZ an_AT0 input_NN1 node_NN1 𝑝_NN1 and_CJC tests_NN2 for_PRP its_DPS children_NN2 in_PRP the_AT0 directions_NN2 contained_VVN in_PRP a_AT0 given_AJ0 set_NN1 of_PRF an_AT0 even_AJ0 grid_NN1 in_PRP the_AT0 (_PUL 𝑥_NP0 ,_PUN 𝑦_NP0 )_PUR plane_NN1 (_PUL i.e._AV0 ,_PUN Fig._NN1 8_CRD )_PUR ,_PUN represented_VVN in_PRP the_AT0 set_NN1 𝛷_NP0 =_NP0 {_PUL −1_CRD ,_PUN 0_CRD ,_PUN 1_CRD }_PUR ×_PRP {_PUL −1_CRD ,_PUN 0_CRD ,_PUN 1_CRD }_PUR ._SENT With_PRP these_DT0 directions_NN2 ,_PUN a_AT0 45_CRD deg_NN0 angle_NN1 is_VBZ a_AT0 limiting_AJ0 factor_NN1 for_PRP a_AT0 path_NN1 connecting_VVG nodes_NN2 ._SENT To_TO0 decrease_VVI this_DT0 angle_NN1 ,_PUN 𝛷_NP0 can_VM0 incorporate_VVI additional_AJ0 locations_NN2 ,_PUN i.e._AV0 ,_PUN (_PUL −2_CRD ,_PUN −1_CRD )_PUR ,_PUN which_DTQ would_VM0 correspond_VVI to_PRP node_NN1 𝑣3_NN1 connecting_VVG to_PRP 𝑣8_NN1 in_PRP Fig._NN1 8._CRD An_AT0 alternative_AJ0 approach_NN1 to_PRP expanding_VVG the_AT0 neighboring_AJ0 nodes_NN2 could_VM0 be_VBI to_TO0 iteratively_AV0 expand_VVI while_CJS some_DT0 condition_NN1 remains_VVZ true_AJ0 ,_PUN such_DT0 as_PRP no_AT0 stepping_NN1 ,_PUN through_PRP an_AT0 adaptive_AJ0 highway_NN1 graph_NN1 ._SENT Algorithm_NN1 1_CRD and_CJC 2_CRD describe_VVB the_AT0 three-dimensional_AJ0 breadth-first_ORD process_NN1 in_PRP general_AJ0 terms_NN2 ._SENT On_PRP line_NN1 4_CRD ,_PUN a_AT0 point_NN1 𝑐_NN1 is_VBZ composed_VVN of_PRF the_AT0 𝑥_NN1 ,_PUN 𝑦_NP0 ,_PUN 𝑧_AJ0 values_NN2 of_PRF 𝑝_NN1 ,_PUN offset_VVN in_PRP the_AT0 directions_NN2 of_PRF 𝛷_NN1 ._SENT 
The_AT0 process_NN1 for_PRP determining_VVG the_AT0 return_AJ0 value_NN1 of_PRF checkChild_NN1 (_PUL p_ZZ0 ,_PUN c_ZZ0 )_PUR begins_VVZ with_PRP the_AT0 description_NN1 of_PRF Fig._NN1 11_CRD and_CJC is_VBZ expanded_VVN to_TO0 define_VVI edge_NN1 weights_NN2 and_CJC determine_VVB criteria_NN2 for_PRP an_AT0 edge_NN1 connection_NN1 in_PRP the_AT0 following_AJ0 section_NN1 ._SENT 
4.2.2_CRD ._SENT Determining_VVG accessibility_NN1 
As_CJS discussed_VVN in_PRP the_AT0 previous_AJ0 section_NN1 ,_PUN each_DT0 (_PUL 𝑝_NP0 ,_PUN 𝑐_NP0 )_PUR is_VBZ checked_VVN against_PRP a_AT0 set_NN1 of_PRF parameters_NN2 and_CJC criteria_NN2 ._SENT 𝑁𝐷+_NP0 (_PUL 𝑝_NP0 )_PUR is_VBZ constructed_VVN in_PRP Alg_NP0 ._SENT 2_CRD ,_PUN represented_VVN by_PRP the_AT0 returned_AJ0 set_NN1 𝐶_NN1 ._SENT One_CRD aspect_NN1 of_PRF accessibility_NN1 is_VBZ a_AT0 minimum_AJ0 width_NN1 or_CJC region_NN1 a_AT0 valid_AJ0 path_NN1 can_VM0 traverse_VVI through_AVP ._SENT Algorithm_NN1 2_CRD can_VM0 be_VBI expanded_VVN to_TO0 force_VVI accessible_AJ0 edges_NN2 in_PRP path-finding_NN1 to_TO0 only_AV0 pass_VVI through_PRP nodes_NN2 that_CJT are_VBB connected_VVN to_PRP at_PRP least_AV0 some_DT0 user-defined_AJ0 number_NN1 of_PRF neighbors_NN2 ._SENT On_PRP line_NN1 12_CRD of_PRF Alg_NP0 ._SENT 2_CRD ,_PUN rather_AV0 than_CJS returning_VVG 𝐶_NN1 ,_PUN a_AT0 check_NN1 can_VM0 be_VBI done_VDN to_TO0 see_VVI if_CJS |_NP0 𝐶_NP0 |_NP0 is_VBZ greater_AJC than_CJS some_DT0 minimum_AJ0 connectivity_NN1 and_CJC if_CJS not_XX0 ,_PUN return_VVB an_AT0 empty_AJ0 set_NN1 ._SENT For_PRP example_NN1 ,_PUN if_CJS 𝛷_NP0 is_VBZ the_AT0 set_NN1 of_PRF 8_CRD neighboring_AJ0 directions_NN2 ,_PUN return_NN1 𝐶_NP0 ⟺_NP0 |_NP0 𝐶_NP0 |_NP0 =_NP0 8._CRD 
For_PRP 𝑐_NP0 ∈_NP0 𝐶_NP0 ,_PUN 𝑐_NP0 is_VBZ determined_VVN to_TO0 be_VBI valid_AJ0 by_PRP function_NN1 checkChild_NN1 (_PUL p_ZZ0 ,_PUN c_ZZ0 )_PUR ,_PUN shown_VVN in_PRP Alg_NP0 ._SENT 3._CRD First_ORD ,_PUN the_AT0 distance_NN1 to_PRP the_AT0 closest_AJS 𝐵𝑖_NN1 ∈_NN1 𝛤_NN1 is_VBZ found_VVN by_PRP inter_AJ0 (_PUL 𝑐_NP0 ,_PUN 𝑐_NP0 −_NP0 𝑧̂_NP0 )_PUR ._SENT Given_VVN no_AT0 labeled_AJ0 geometry_NN1 in_PRP 𝛤_NP0 ,_PUN 𝐵𝑤_NP0 is_VBZ the_AT0 same_DT0 set_NN1 of_PRF objects_NN2 as_PRP 𝛤_NP0 ._SENT For_PRP labeled_AJ0 geometry_NN1 consisting_VVG of_PRF walkable_AJ0 and_CJC non-walkable_AJ0 surfaces_NN2 ,_PUN a_AT0 set_NN1 of_PRF walkable_AJ0 surfaces_NN2 are_VBB defined_VVN as_PRP 𝐵𝑤_NP0 ⊂_NP0 R3_CRD ._SENT If_CJS the_AT0 closest_AJS distance_NN1 is_VBZ to_PRP 𝐵𝑖_NP0 ∉_NP0 𝐵𝑤_NP0 the_AT0 node_NN1 is_VBZ not_XX0 valid_AJ0 ._SENT The_AT0 connection_NN1 type_NN1 𝑡_NN1 between_PRP 𝑝_NP0 and_CJC 𝑐′_NP0 is_VBZ calculated_VVN by_PRP getConnection_NN1 (_PUL p_ZZ0 ,_PUN 𝑐′_NN0 )_PUR and_CJC if_CJS valid_AJ0 ,_PUN the_AT0 step_NN1 and_CJC slope_NN1 parameters_NN2 are_VBB verified_VVN ._SENT In_PRP implementation_NN1 ,_PUN the_AT0 relational_AJ0 information_NN1 of_PRF connection_NN1 types_NN2 between_PRP the_AT0 parent_NN1 and_CJC child_NN1 nodes_NN2 is_VBZ stored_VVN during_PRP the_AT0 graph_NN1 construction_NN1 ,_PUN and_CJC the_AT0 function_NN1 returns_VVZ the_AT0 connection_NN1 type_NN1 (_PUL 𝑡_NP0 )_PUR and_CJC valid_AJ0 node_NN1 (_PUL 𝑐′_NP0 )_PUR ._SENT 
The_AT0 type_NN1 of_PRF connection_NN1 between_PRP two_CRD nodes_NN2 is_VBZ determined_VVN as_PRP one_CRD of_PRF five_CRD possible_AJ0 cases_NN2 (_PUL Fig._NN1 12_CRD )_PUR :_PUN No_AT0 Step_NN1 12_CRD (_PUL a_AT0 )_PUR ,_PUN Step_NN1 Over_PRP 12_CRD (_PUL b_ZZ0 )_PUR ,_PUN Step_VVB Up_AVP 12_CRD (_PUL c_ZZ0 )_PUR ,_PUN Step_NN1 Down_NP0 12_CRD (_PUL d_ZZ0 )_PUR ,_PUN Invalid_AJ0 12_CRD (_PUL e_ZZ0 )_PUR ._SENT The_AT0 reference_NN1 to_TO0 '_PUQ '_PUQ No_AT0 Step_NN1 '_POS '_PUQ is_VBZ specifically_AV0 regarding_PRP a_AT0 geometry_NN1 that_CJT protrudes_VVZ off_AVP of_PRF the_AT0 ground_NN1 surface_NN1 ,_PUN which_DTQ would_VM0 require_VVI a_AT0 foot_NN1 ,_PUN wheelchair_NN1 ,_PUN or_CJC other_AJ0 aid_NN1 to_TO0 lose_VVI contact_NN1 with_PRP the_AT0 ground_NN1 during_PRP traversal_NN1 ._SENT The_AT0 '_PUQ '_PUQ No_AT0 Step_NN1 '_POS '_PUQ is_VBZ referred_VVN to_PRP as_PRP a_AT0 direct_AJ0 connection_NN1 ,_PUN which_DTQ works_VVZ in_PRP both_AV0 flat_AJ0 and_CJC inclined_AJ0 ground_NN1 as_PRP the_AT0 height_NN1 offset_VVN between_PRP nodes_NN2 is_VBZ also_AV0 stored_VVN ._SENT Therefore_AV0 ,_PUN future_AJ0 queries_NN2 of_PRF the_AT0 relationship_NN1 between_PRP nodes_NN2 (_PUL such_DT0 as_PRP defining_VVG edge_NN1 cost_NN1 )_PUR returning_VVG both_DT0 a_AT0 height_NN1 offset_NN1 and_CJC direct_AJ0 connection_NN1 allow_VVB for_PRP a_AT0 specific_AJ0 categorization_NN1 such_DT0 as_PRP an_AT0 incline_NN1 instead_AV0 of_PRF a_AT0 step_NN1 ._SENT This_DT0 method_NN1 provides_VVZ a_AT0 similar_AJ0 but_CJC more_AV0 detailed_AJ0 approach_NN1 to_PRP determining_VVG node_NN1 connections_NN2 as_PRP the_AT0 edge_NN1 culling_VVG in_PRP [_PUL 54_CRD ]_PUR or_CJC the_AT0 edge_NN1 connectivity_NN1 determination_NN1 of_PRF a_AT0 visibility_NN1 graph_NN1 ._SENT 
Given_VVN the_AT0 first_ORD connection_NN1 type_NN1 being_VBG false_AJ0 ,_PUN a_AT0 second_ORD ray_NN1 ,_PUN referred_VVN to_PRP in_PRP the_AT0 figure_NN1 as_PRP 𝑑2_CRD ,_PUN is_VBZ calculated_VVN and_CJC used_VVN to_TO0 check_VVI for_PRP a_AT0 connection_NN1 ._SENT Depending_VVG on_PRP the_AT0 height_NN1 relationship_NN1 between_PRP 𝑝_NP0 and_CJC 𝑐_NP0 ,_PUN the_AT0 translated_AJ0 start_NN1 position_NN1 of_PRF the_AT0 ray_NN1 is_VBZ determined_VVN by_PRP 𝑏𝑢_NP0 or_CJC 𝑏𝑑_NP0 as_PRP the_AT0 directed_AJ0 edge_NN1 is_VBZ either_AV0 stepping_VVG up_AVP or_CJC down_AVP ._SENT The_AT0 special_AJ0 case_NN1 is_VBZ for_PRP when_CJS the_AT0 two_CRD nodes_NN2 are_VBB equal_AJ0 in_PRP height_NN1 with_PRP an_AT0 obstruction_NN1 between_PRP them_PNP ,_PUN requiring_VVG a_AT0 step_NN1 over_PRP the_AT0 obstruction_NN1 (_PUL Fig._NN1 12_CRD (_PUL b_ZZ0 )_PUR )_PUR ,_PUN which_DTQ has_VHZ a_AT0 ray_NN1 start_NN1 point_NN1 calculated_VVD the_AT0 same_DT0 as_CJS a_AT0 step_NN1 up_AVP ._SENT 
Algorithm_NN1 4_CRD demonstrates_VVZ the_AT0 process_NN1 for_PRP calculating_VVG the_AT0 rays_NN2 and_CJC connection_NN1 types_NN2 ._SENT After_PRP the_AT0 connection_NN1 type_NN1 and_CJC parameters_NN2 of_PRF 𝐶_NN1 is_VBZ determined_VVN ,_PUN the_AT0 algorithm_NN1 returns_VVZ to_PRP buildGraph_NN1 (_PUL D_ZZ0 ,_PUN Q_ZZ0 )_PUR on_PRP line_NN1 5._CRD At_PRP that_DT0 point_NN1 ,_PUN for_PRP the_AT0 given_AJ0 𝑝_NN1 passed_VVN to_PRP getNodes_NN2 ,_PUN the_AT0 subgraph_NN1 of_PRF 𝑝_NN1 can_VM0 be_VBI constructed_VVN (_PUL 𝐷_NP0 [_PUL 𝐸𝐷+_NP0 (_PUL 𝑝_NP0 )_PUR ]_PUR )_PUR ._SENT 
4.3_CRD ._SENT Edge_NN1 costs_NN2 
The_AT0 cost_NN1 of_PRF traveling_VVG from_PRP one_CRD node_NN1 to_PRP another_DT0 is_VBZ defined_VVN by_PRP the_AT0 mapping_NN1 of_PRF the_AT0 weights_NN2 from_PRP set_NN1 𝑊_NN1 as_CJS shown_VVN in_PRP Section_NN1 4.1.1_CRD ._SENT While_CJS the_AT0 significance_NN1 of_PRF the_AT0 method_NN1 and_CJC resulting_AJ0 graph_NN1 is_VBZ the_AT0 straightforward_AJ0 application_NN1 to_PRP a_AT0 variety_NN1 of_PRF human_AJ0 factors_NN2 ,_PUN a_AT0 few_DT0 weight_NN1 categories_NN2 previously_AV0 discussed_VVN in_PRP the_AT0 literature_NN1 will_VM0 be_VBI defined_VVN here_AV0 ._SENT Especially_AV0 at_PRP the_AT0 urban_AJ0 scale_NN1 ,_PUN the_AT0 inclusion_NN1 of_PRF varying_AJ0 ground_NN1 conditions_NN2 to_PRP walkability_NN1 analysis_NN1 can_VM0 better_AV0 predict_VVI the_AT0 human_AJ0 experience_NN1 ,_PUN with_PRP comfort_NN1 ,_PUN timing_NN1 ,_PUN and_CJC fatigue_NN1 being_VBG realized_VVN ._SENT 
Two_CRD cases_NN2 exist_VVB for_PRP defining_VVG the_AT0 cost_NN1 of_PRF an_AT0 edge_NN1 :_PUN 
1._CRD Cost_NN1 of_PRF mobility_NN1 along_PRP the_AT0 edge_NN1 
2._CRD Cost_NN1 of_PRF moving_VVG to_PRP a_AT0 node_NN1 
In_PRP the_AT0 first_ORD group_NN1 ,_PUN metrics_NN2 related_VVN to_PRP mobility_NN1 itself_PNX are_VBB included_VVN ;_PUN 𝛹𝑐_NP0 (_PUL 𝑒𝑖𝑗_NP0 )_PUR =_NP0 Cross-slope_NP0 ,_PUN 𝛹𝑑_NP0 (_PUL 𝑒𝑖𝑗_NP0 )_PUR =_AJ0 Metric_AJ0 Distance_NN1 ,_PUN 𝛹𝑠_NP0 (_PUL 𝑒𝑖𝑗_NP0 )_PUR =_NP0 Slope_NP0 ,_PUN 𝛹𝑒_NP0 (_PUL 𝑒𝑖𝑗_NP0 )_PUR =_NN1 Energy_NN1 Expenditure_NN1 ,_PUN 𝛹𝑡_NP0 (_PUL 𝑒𝑖𝑗_NP0 )_PUR =_NN1 Step_NN1 Type_NN1 ._SENT 
In_PRP the_AT0 second_ORD group_NN1 ,_PUN attributes_NN2 not_XX0 able_AJ0 to_TO0 be_VBI calculated_VVN by_PRP the_AT0 path_NN1 in_PRP isolation_NN1 ,_PUN but_CJC rather_AV0 as_CJS values_NN2 calculated_VVD cohesively_AV0 with_PRP the_AT0 built_VVN environment_NN1 are_VBB considered_VVN ._SENT These_DT0 highly_AV0 localized_AJ0 parameters_NN2 are_VBB easily_AV0 missed_VVN in_PRP maximal_AJ0 edge_NN1 connected_VVN graphs_NN2 (_PUL e.g._AV0 ,_PUN [_PUL 58_CRD ]_PUR )_PUR and_CJC rely_VVB on_PRP the_AT0 dense_AJ0 set_NN1 of_PRF nodes_NN2 throughout_PRP the_AT0 environment_NN1 ._SENT In_PRP this_DT0 approach_NN1 ,_PUN an_AT0 edge_NN1 weight_NN1 is_VBZ defined_VVN by_PRP some_DT0 properties_NN2 or_CJC attributes_NN2 of_PRF the_AT0 end_NN1 points_NN2 (_PUL nodes_NN2 )_PUR of_PRF the_AT0 edge_NN1 ._SENT For_PRP example_NN1 ,_PUN a_AT0 directed_AJ0 edge_NN1 with_PRP a_AT0 start_NN1 node_NN1 located_VVN on_PRP concrete_NN1 and_CJC end_NN1 node_NN1 located_VVN on_PRP sand_NN1 is_VBZ given_VVN a_AT0 higher_AJC cost_NN1 than_CJS the_AT0 reverse_NN1 as_PRP that_DT0 node_NN1 should_VM0 be_VBI avoided_VVN ._SENT This_DT0 weight_NN1 mapping_NN1 can_VM0 include_VVI 𝛹𝑘_NN1 (_PUL 𝑒𝑖𝑗_NP0 )_PUR =_NN1 Type_NN1 of_PRF Surface_NN1 the_AT0 end_NN1 node_NN1 is_VBZ on_PRP ,_PUN with_PRP further_AJC types_NN2 ;_PUN 𝛹𝑙_NP0 (_PUL 𝑒𝑖𝑗_NP0 )_PUR =_NN1 Light_NN1 Intensity_NN1 from_PRP Opposite_AJ0 Direction_NN1 ,_PUN 𝛹h_NP0 (_PUL 𝑒𝑖𝑗_NP0 )_PUR =_NN1 Light_NN1 Difference_NN1 Between_PRP Nodes_NN2 ,_PUN 𝛹𝑓_NN1 (_PUL 𝑒𝑖𝑗_NP0 )_PUR =_NN1 Probability_NN1 of_PRF Falling_VVG ,_PUN 𝛹𝑣_NP0 (_PUL 𝑒𝑖𝑗_NP0 )_PUR =_NN1 Percentage_NN1 of_PRF View_NN1 to_PRP Greenspace_NP0 ,_PUN 𝛹𝑤_NP0 (_PUL 𝑒𝑖𝑗_NP0 )_PUR =_AJ0 Surrounding_AJ0 Width_NN1 ._SENT 
Some_DT0 edge_NN1 cost_NN1 definitions_NN2 such_DT0 as_PRP the_AT0 metric_AJ0 distance_NN1 ,_PUN 𝛹𝑑_NP0 (_PUL 𝑒𝑖𝑗_NP0 )_PUR =_NP0 |_NP0 𝑛𝑖_NP0 −𝑛𝑗_NP0 |_NP0 ,_PUN are_VBB straight_AV0 forward_AV0 while_CJS others_NN2 𝛹𝑙_NN1 (_PUL 𝑒𝑖𝑗_NP0 )_PUR are_VBB based_VVN on_PRP the_AT0 implemented_AJ0 simulation_NN1 technique_NN1 ._SENT The_AT0 two_CRD most_AV0 notable_AJ0 costs_NN2 related_VVN to_PRP the_AT0 focus_NN1 of_PRF this_DT0 paper_NN1 are_VBB 𝛹𝑐_NP0 (_PUL 𝑒𝑖𝑗_NP0 )_PUR and_CJC 𝛹𝑒_NP0 (_PUL 𝑒𝑖𝑗_NP0 )_PUR and_CJC are_VBB therefore_AV0 defined_VVN in_PRP full_AJ0 ._SENT 𝛹𝑐_NP0 (_PUL 𝑒𝑖𝑗_NP0 )_PUR is_VBZ the_AT0 mapping_NN1 of_PRF weights_NN2 to_PRP edge_NN1 costs_NN2 in_PRP the_AT0 graph_NN1 relating_VVG to_PRP the_AT0 cross_NN1 slope_NN1 and_CJC 𝛹𝑡_NP0 (_PUL 𝑒𝑖𝑗_NP0 )_PUR is_VBZ the_AT0 mapping_NN1 consisting_VVG of_PRF an_AT0 identifier_NN1 for_PRP the_AT0 step_NN1 type_NN1 found_VVN in_PRP Alg_NP0 ._SENT 4._CRD 
Calculating_VVG the_AT0 cross-slope_AJ0 score_NN1 𝛹𝑐_NN1 (_PUL 𝑒𝑖𝑗_NP0 )_PUR is_VBZ done_VDN by_PRP considering_VVG the_AT0 edges_NN2 to_PRP 𝑢𝑖𝑗_NP0 (_PUL using_VVG the_AT0 mapping_NN1 defined_VVN in_PRP Section_NN1 4.1.1_CRD )_PUR that_CJT are_VBB orthogonal_AJ0 in_PRP the_AT0 𝑥𝑦_NP0 plane_NN1 ,_PUN denoted_VVN by_PRP 𝑥𝑦⊥_NP0 ._SENT The_AT0 maximum_AJ0 difference_NN1 in_PRP height_NN1 between_PRP the_AT0 nodes_NN2 of_PRF orthogonal_AJ0 edges_NN2 is_VBZ used_VVN as_PRP the_AT0 score_NN1 :_PUN 
Definition_NN1 8._CRD equation_NN1 
The_AT0 requirement_NN1 for_PRP 𝛹𝑡_NP0 (_PUL 𝑒𝑖𝑘_NP0 )_PUR =_NP0 𝑡𝙳𝙸𝚁𝙴𝙲𝚃_NP0 corresponds_VVZ to_PRP the_AT0 connection_NN1 type_NN1 defined_VVN in_PRP Alg_NP0 ._SENT 4_CRD line_NN1 3_CRD as_PRP a_AT0 direct_AJ0 connection_NN1 with_PRP no_AT0 step_NN1 ._SENT 
Additionally_AV0 ,_PUN a_AT0 function_NN1 defining_VVG energy_NN1 expenditure3_NN1 of_PRF walking_VVG on_PRP slopes_NN2 as_CJS shown_VVN in_PRP Fig._NN1 4_CRD is_VBZ used_VVN for_PRP 𝑤𝑒_NP0 ._SENT 
