CGAL users discussion list

[Matti Lehtonen <>]

Hi,

what is the most efficient way to do nearest neighbourhood search among 3D points with a 2D distance (Z is ignored)? And unfortunately, the Z component is needed after the nearest point is found, so pure 2D solution is out of question :/


There seems to be several ways to do it, like
a) CGAL::Search_traits<NT,Point,CartesianIterator,ConstructCartesianIterator,ConstructMinVertex,ConstructMaxVertex>

 // Tree - 3D points used like 2D points
typedef CGAL::Search_traits<FT,
                            Multi_Classified_Point,
                            Multi_Classified_Kernel::Cartesian_const_iterator_2,
                            Multi_Classified_Kernel::Construct_cartesian_const_iterator_3>
                                                                            MC_TreeTraits_2;
typedef CGAL::Orthogonal_incremental_neighbor_search<MC_TreeTraits_2> MC_Neighbor_search_xy_2;
typedef MC_Neighbor_search_xy_2::Tree MCPointSet_xy_2;

except the distance calculation includes the Z component, like this test case proves:
        MCPointSet_xy_2            test;
        Multi_Classified_Point    test1 = Multi_Classified_Point( ASPRS_Labels::NEVER_CLASSIFIED, 0.0, 0.0, 10.0 );
        Multi_Classified_Point    test2 = Multi_Classified_Point( ASPRS_Labels::NEVER_CLASSIFIED, 1.0, 1.0, 10.0 );
        Multi_Classified_Point    test3 = Multi_Classified_Point( ASPRS_Labels::NEVER_CLASSIFIED, 1.0, 1.0, 100000.0 );

        test.insert( test1 );
        test.insert( test3 );
        MC_Neighbor_search_xy_2            nearest( test, test2 );
       
        std::pair<Multi_Classified_Point,FT> const    result = *nearest.begin();

        std::cerr << "Nearest point is <"
                  << result.first.x() << ","
                  << result.first.y() << ","
                  << result.first.z()
                  << "> for point <"
                  << test2.x() << ","
                  << test2.y() << ","
                  << test2.z()
                  << "> with distance of "
                  << result.second
                  << std::endl;

with output "Nearest point is <0,0,10> for point <1,1,10> with distance of 2"

b)  CGAL::Search_traits_adapter<Key,PointPropertyMap,BaseTraits>  and  GAL::Distance_adapter<Key,PointPropertyMap,Base_distance>

How ever this approach seems to be used for points with coordinates stored as tuples.


c) CGAL::Distance_xy_2<I>

Thought similar purpose like CGAL::Triangulation_euclidean_traits_xy_3, except this one is undocumented and contain couple errors (reported by GCC 4.7.2), like get_point(#) should be replaced with this->get_point(#) and there are no search traits, which define "Point"

d) Example 61.3.5

Error prone, because quite lot of code must be copy & pasted.

Regards,

Matti L

--
Life is complex. It has real and imaginary parts.