CGAL users discussion list

["Catalin Suvei" <>]

Hi,

I created an arrangement object like this:
Arrangement_2 arr;
and a point location strategy and attach it to the arrangement like this:
Landmarks_pl landmarks_pl;
landmarks_pl.attach (arr);
then I insert each edge of each element into the arrangement using 
CGAL::insert() function. Then I the use point_location_query() function for 
the points I am interested in (34,076,160 of them). This took hours to solve.

Catalin


-----Original Message-----
From: Andreas Fabri 
[mailto:]
Sent: 24 November 2009 19:22
To: 

Subject: Re: [cgal-discuss] point location


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


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