CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

If the boxes are axis aligned, the test is pretty simple, just check
each cartesian coordinates to that of the bounding planes of the box (up 
to 6 comparison of double).
The usual approch is then to use a hierarchical data-structure to locate 
efficiently the point in the mesh.

If it match your hexa-mesh constraints, in CGAL we have a kd-tree:
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Spatial_searching_ref/Class_Kd_tree.htm

HTH,

Sebastien.


On 02/28/2012 03:03 PM, Tomislav Maric wrote:
> Well, the mesh is hexahedral and arbitrary. To be sure, by arbitrary I mean 
> this:
>
> - mesh is a set of cells with boundary patches (lists of labels (IDs) to the 
> total face list, corresponding to the boundary faces)
> - a cell is a list of labels referring to an array of faces
> - a face is a list of (counterclockwise counted) labels referring to an array 
> of points
>
> The mesh connectivity is computed accross the faces: there is an owner-neighbour 
> relationship which is defined by the cell ID (needed for the communication: which cell 
> needs to communicate data to which Polyedron_3 point, and vice-versa). The cells with 
> lower IDs "own" the faces. Each face represents a boundary between max two 
> cells.
>
> This kind of construction is used as an unstructured mesh used for a Finite 
> Volume numerical method solution. In its basis, the mesh is consisted of 
> waterproof (logical: faces are not checked for planarity) polyhedra, but I am 
> interested only in hexagonal cell geometry, for now.
>
> The boxes are axis alligned, because the cells of the mesh are axis alligned.
>
> Because I need to perform communications between the Polyhedron_3 and this Mesh, I'm 
> thinking in the direction of an implementation of the BoxIntersectionBox_d concept, 
> that will inherit from the "cell" class of the Mesh and provide the 
> requirements needed by the concept. This way, I can re-use the info from the Mesh, and 
> call CGAL algorithms on it. Either this, or build the Box from the array of points of 
> each cell (min, max) + cell ID.
>
>
> Thanks a lot!
>
> Tomislav
>
>
> > ----- Original Message -----
> > From: Sebastien Loriot (GeometryFactory)
> > Sent: 02/28/12 02:45 PM
> > To: 
> >
> > Subject: Re: [cgal-discuss] Polyhedron_3 points / Array of boxes
> >
> > How is you hexa-mesh? is it regular or arbitrary? are the boxes
> > axis-aligned?
> >
> > A screenshot can be helpful too if you have one.
> >
> > Sebastien.
> >
> > On 02/28/2012 11:22 AM, Tomislav Maric wrote:
> > > Hi everyone,
> > >
> > > what would be the fastest way to compute something like "point in box" for 
> > > the points of the Polyhedron_3? I have an array of boxes (extremely large, well over 
> > > hundreds of thousands) and a rather large Polyhedron_3 depicting a surface mesh. What I 
> > > am aiming at is a fast way of communicating data between an underlying hexahedral mesh 
> > > (array of boxes) and the vertices of the Polyhedron..
> > >
> > > I've read the chapter on Intersecting sequences of d-Dimensional boxes, and 
> > > I'm thinking about this:
> > >
> > > 1) Create an array of boxes for the Polyhedron_3 facets (triangular mesh)
> > > 2) Create an array of boxes for the hex mesh.
> > > 3) Compute the intersection test.
> > > 4) Sub process: go through every triangle, take the point of the triangle and 
> > > find the box (out of the candidates given by the intersection test) within 
> > > which the point is located.
> > >
> > > This sounds a bit... slow... so any advice is appreciated! :)
> > >
> > > Thanks!
> > >
> > > Tomislav
> >
> >
> > --
> > You are currently subscribed to cgal-discuss.
> > To unsubscribe or access the archives, go to
> > https://lists-sop.inria.fr/wws/info/cgal-discuss