CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

The simplest but probably not the faster is to use Search_traits_adapter
with Search_traits_2 and a property map that creates 2D points on the
fly from 3D points.

You are right that [1] is longer to write but will be faster.

Sebastien.

http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Spatial_searching/Chapter_main.html#Subsection_61.3.5

On 04/29/2013 03:11 PM, Matti Lehtonen wrote:
> 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.