Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] how to extend kd-tree to range-query user defined point?

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] how to extend kd-tree to range-query user defined point?


Chronological Thread 
  • From: yanyajie <>
  • To: <>
  • Subject: Re: [cgal-discuss] how to extend kd-tree to range-query user defined point?
  • Date: Thu, 31 Mar 2011 00:16:35 +0800
  • Importance: Normal

?Oh! I see... There are just so many things in CGAL I need to explore further. Thanks again!

-----原始邮件----- From: Sebastien Loriot (GeometryFactory)
Sent: Thursday, March 31, 2011 12:07 AM
To:

Subject: Re: [cgal-discuss] how to extend kd-tree to range-query user defined point?

yanyajie wrote:
?But how can the existing fuzzy object know if it contains my point or
not? Isn't there supposed to be some new "bool contain(PointType p)"
which does this?
It uses the functor Construct_cartesian_const_iterator_d.

S.


-----原始邮件----- From: Sebastien Loriot (GeometryFactory)
Sent: Wednesday, March 30, 2011 11:45 PM
To:

Subject: Re: [cgal-discuss] how to extend kd-tree to range-query user
defined point?

yanyajie wrote:
?Dear S,

I see. Just to be sure: practiacally I need to provide a new query item
(box or sphere), my new point type, and wrap them in a new SearchTraits,
right?

Not a new fuzzy object, as you can provide your traits as
template parameter to CGAL::Fuzzy_sphere and CGAL::Fuzzy_iso_box.

you simply need to define
struct Search_traits_with_my_point{
typedef XXX Cartesian_const_iterator_d;
typedef XXX Construct_cartesian_const_iterator_d;
typedef XXX Point_d;
typedef XXX Iso_box_d;
typedef XXX Sphere_d;
typedef XXX Construct_iso_box_d;

typedef XXX Construct_min_vertex_d;
typedef XXX Construct_max_vertex_d;
typedef XXX Construct_center_d;
typedef XXX Compute_squared_radius_d;
typedef XXX FT;

};

For the details see:
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Spatial_searching_ref/Concept_SearchTraits.html


S.

Yan.

-----原始邮件----- From: Sebastien Loriot (GeometryFactory)
Sent: Wednesday, March 30, 2011 8:42 PM
To:

Subject: Re: [cgal-discuss] how to extend kd-tree to range-query user
defined point?

There is a bug in the documentation we are aware of and that should be
fixed in the 3.9 release. Search_traits is not a real model of the
SearchTraits concept as it cannot be used for range-search queries.

It should not be hard to define your own traits class using this concept
page:
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Spatial_searching_ref/Concept_SearchTraits.html#Cross_link_anchor_1634




For a concise view you can also have a look at
include/CGAL/Search_traits_2.h (which simply contains types that
need to be defined)

Basically you simply have to define more functors than in the example
here:

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




S.





yanyajie wrote:
Hi,

I have a specific point type, known as surfel. I would like to build a
kd-tree for a bunch of surfels and to do range-query specified by a
sphere queryitem. How can I extend the kd-tree to achieve my goal?

I examined the search() routine in kd_tree_node.h and found kd_tree
heavily rely on the query item’s contains() member to do actual query.
Does that mean all I have to do is just implement my own extended
version of query item, like a sphere, so that it can determine whether
or not a surfel is contained in? Or do I have to provide another
distance class as exemplified in the example?

Really need some help here. Thanks in advance!!!

Yan.



-------------------------------------------------------------------------------------


* The State Key Labratory of Virtual Reality and Technology
* School of Computer Science and Engineering
* Beijing University Aeronautics and Astronautics (Beihang Univ.)
-------------------------------------------------------------------------------------








--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss




Archive powered by MHonArc 2.6.16.

Top of Page