CGAL users discussion list

["Catalin Suvei" <>]

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.

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
>>>
>>
>>
> 
> 


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