CGAL users discussion list

[Andreas Fabri <>]

Catalin Suvei wrote:
> Hi,
>
> No, the elements are not necessarily rectangular nor they formed a perfect 
> grid. I tried CGAL in this example and it took hours to solve it.

Hello Catalin,

You took what of CGAL, and you used it in which way.
We pointed out at least three different approaches.

best regards,

andreas

> Catalin
>
> -----Original Message-----
> From: Andreas Fabri 
> [mailto:]
> Sent: 24 November 2009 08:38
> To: 
>
> Subject: Re: [cgal-discuss] point location
>
>
>
> Hello,
>
> sory for that it took so long before I come back to you.
> I guess what you say with the bridge is just an example,
> that is the elements are not necessarily all rectangular
> and form a perfect grid.
>
> If they formed a perfect grid, it would boil down to
> sorting qeuery and grid points, and all data structures
> we mentioned are just an overkill.
>
> best regards,
>
> andreas
>
>
> Catalin Suvei wrote:
> > Hi,
> >
> > Yes, the elements don't overlap, they just share edges and they have similar 
> > size.
> > Basically the mesh is for bridge decks and we are modelling vehicles moving 
> > on these; so the query point would represent the wheel. Imagine a 150m x 24m 
> > bridge, meshed with 1m x 1m quad finite elements; the way we model the 
> > movement a vehicle is that we place the vehicle at every point in a grid of 
> > points, 0.25m apart in each direction; at every grid point we calculate the 
> > effect that vehicle has on the bridge, so that's why we need to find the 
> > finite element that contains wheel (point); once the vehicle is placed at a 
> > point, i could issue the query for all the wheels at once. So in my example, 
> > if there are 65,280 grid points and you have to check 87 vehicles, each 
> > having 6 wheels, you get 65,280 x 87 x 6 = 34,076,160 query points. I know If 
> > you are wondering why we need the finite element that contains the point is 
> > because we need to use the shape functions of that element to interpolate the 
> > value at that point.
> > Sorry if I went into much detail, but I thought you might find it interesting.
> >
> > Catalin
> >
> > -----Original Message-----
> > From: Andreas Fabri 
> > [mailto:]
> > Sent: 17 November 2009 19:26
> > To: 
> >
> > Subject: Re: [cgal-discuss] point location
> >
> >
> >
> > 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