CGAL users discussion list

[Andreas Fabri <>]

Hello Catalin,

Is it correct that your finite elements do not overlap, or at most on
their boundary.

If on the boundary, must they then share an entire edge, or can edges
partially overlap?

Are the finite elements of more or less homogeneous size, or can you
have elements that traverse a huge fraction of the domain?

Do you know all query points in advance?

I ask this as there is the package http://www.cgal.org/Pkg/BoxIntersectionD
which would allow you to apply a callback on all pairs of bounding
boxes of the query points and the finite elements.

You might also generate a Constrained triangulation of your input,
(http://www.cgal.org/Pkg/Triangulation2 ) perform a spatial sort of your
points ( http://www.cgal.org/Pkg/SpatialSorting ), and then run a point 
location
for the sorted points, where you start your i+1st search at the face
where the i-th point is located. With as many points as you have you
will always be rather close.

best regards,

andreas






 wrote:
> no, but I'll be happy to know the outcome of your experiment. BW, there 
> is a batch point location, which is based on the sweep-line framework. 
> It is more efficient for many query points, but you have to know them 
> ahead.
>
> Quoting "Catalin Suvei" 
> <>:
>
> > Hi,
> > Thanks very much, I'll look into that. I'll probably have to issue 
> > about 34 million queries on an arrangement formed by 3250 of 4 nodded 
> > faces, any idea, roughly, how long it would take?
> > Catalin
> >
> > -----Original Message-----
> > From: 
> >
> >  
> > [mailto:]
> > Sent: 16 November 2009 21:22
> > To: 
> >
> > Subject: Re: [cgal-discuss] point location
> >
> >
> > Quoting "Catalin Suvei" 
> > <>:
> >
> > > Hi,
> > >
> > > I am a new user and consider using CGAL to help me with the point 
> > > location
> > > problem. I am going to use it in a finite element program; I presume 
> > > that I
> > > could build up the arrangement by adding the lines that make up each 
> > > element
> >
> > yes
> >
> > > (a question is if there is a method to add faces directly);
> >
> > no
> >
> > then I employ a
> > > point location strategy and use it for a given point. My problem is 
> > > that I
> > > cannot map the object returned by this query (which can be a vertex, 
> > > edge or
> > > a face) to my finite element (consisting of nodes and elements). Any
> > > suggestions? Ideally, I should be able to create a CGAL object 
> > > representing
> > > my finite element, store a pointer in this object to my finite 
> > > element, then
> > > add it to the arrangement and the point location query would return 
> > > me the
> > > CGAL object from where I could retrieve my finite element (or line/point
> > > forming the finite element) and do something useful with it. Thanks a 
> > > lot.
> >
> > You probably need to extend the features of the dcel to store
> > information regarding the originating elements. Look for a chapter in
> > the doc. titled "Extending the Dcel". There are also examples that you
> > can start playing with.
> >
> > > Catalin
> > >
> > >
> > > --
> > > You are currently subscribed to cgal-discuss.
> > > To unsubscribe or access the archives, go to
> > > https://lists-sop.inria.fr/wws/info/cgal-discuss
> >
> >
> >
> > --
> > You are currently subscribed to cgal-discuss.
> > To unsubscribe or access the archives, go to
> > https://lists-sop.inria.fr/wws/info/cgal-discuss
> >
> >
> >
> > --
> > You are currently subscribed to cgal-discuss.
> > To unsubscribe or access the archives, go to
> > https://lists-sop.inria.fr/wws/info/cgal-discuss