CGAL users discussion list

[orxshi <>]

In need a data structure which is capable of performing intersection
detection of geometries with different topologies. For example, consider a
hybrid mesh composed of non-overlapping mesh elements (quadrilaterals and
triangles). Algorithm should find which quad or triangle a query point
resides in. In general geometries compared against are (point, segment) vs
(triangle, quad) and segment vs segment. Note that mesh topology is static
so it is good to store mesh elements in the tree. Actually the name of the
data structure is Alternating Digital Tree
(http://onlinelibrary.wiley.com/doi/10.1002/nme.1620310102/abstract). ADT is
similar to kd-tree but also assigns a mesh element to each node and also
stores element's AABB at the same node. This makes it capable of point
containment query.

Intersecting Sequences of dD Iso-oriented Boxes performs intersection
detection of boxes which store handles to actual geometries. In this case, I
would need to create a box for each geometry (even for points). Also, in my
case the mesh topology is static so desired data structure should store mesh
elements. I am not sure if box_intersection_d stores static data structure
or constructs hierarchy at each call.

kd-tree and range tree are very similar to ADT but they offer only neighbor
and range search but not intersection detection.

Segment tree and Interval skip list offer point containment search only for
segments/intervals. 

AABB tree (3D Fast Intersection and Distance Computation) support
intersection queries include line objects (rays, lines, segments) against
sets of triangles, or plane objects (planes, triangles) against sets of
segments. So no triangle vs triangle or point vs triangle.

Is there a data structure suitable for ADT in CGAL?



--
View this message in context: 
http://cgal-discuss.949826.n4.nabble.com/Alternating-Digital-Tree-tp4662135.html
Sent from the cgal-discuss mailing list archive at Nabble.com.