CGAL users discussion list

[Hansjoerg Seybold <>]

hi,
i have a similar problem see cgal post some time ago

point location/interpolation on a 2d mesh

My idea was to use point location on the mesh triangulation and then interpolate
with the three points from the corresponding triangle applying a somple formula for
interpolation on a triangle. The triangles which are lying outside of the domain are 
marked with a flag, such that i can distinguish medium and hole.

I didn't do the implementation yet, so i am not sure if it works, but should be in principle.

Let me know if you have solved your problem
cheers hj

On Thu, Feb 10, 2011 at 5:23 AM, mturner <> wrote:

Hello,

We are using the CGAL libraries to help analyze
surface motions of geological features on the Earth.
The geometry of the features define the boundary
and interior of specific surface regions.

Because our geographic regions are small,
and to keep things simple for now,
we consider the positions and motions only in 2D,
using coordinates of Latitude and Longitude.

Each geologic feature is defined by a basic geometry (point, line, or
polygon),
and each geometry contributes to either the boundary of the region, or the
interior.

Following the example code in Chapter 35 "2D Triangulations",
we use the vertices from the feature geometry, to build a series of
triangulations:

- Delaunay Triangulation    ( CGAL::Delaunay_triangulation_2<...> ),
- Constrained Triangulation (
CGAL::Constrained_Delaunay_triangulation_2<...> ),
- Mesh Triangulation        ( CGAL::Delaunay_mesher_2<...> ).

We have posted images showing an example region,
with the various feature geometry components,
and the resulting triangulations here:

http://web.gps.caltech.edu/~mturner/cgal_post/

Figure 1 shows the basic feature data:
the boundary of the region is defined by intersections of five lines
(two red lines at the top, purple line on the right, red line at the bottom,
green line on left).
The Interior elements are defined by three points, three lines, and two
polygons inside that region.

Figure 2 shows the Delaunay Triangulation from that data in black,
including the convex hull triangles formed where the boundary is concave.

Figure 3 shows the Constrained Triangulation in gray.

Figure 4 shows the Mesh Triangulation in light green,
with areas outside the total outer boundary un-meshed;
and areas inside the interior polygons un-meshed.

The interior holes were generated by adding seed points and calling
the constrained mesher's set_seeds(...) function.

Then the Mesh was generated with a call to:
constrained_mesher->refine_mesh();

This aspect of using CGAL to create triangulations and meshes
has been very successful for both test examples and real world data.


Now we would like to use the final meshes to perform interpolation.

We have measurements of surface velocity for the basic feature data,
and we would like to use a refined CGAL mesh to interpolate
that velocity data for any given test point inside the region.

Following the example code in Chapter 68 "2D and Surface Function
Interpolation",
we have successfully used the interpolation functions on the Delaunay
Triangulation,
using the functions such as:
CGAL::natural_neighbor_coordinates_2,
CGAL::sibson_gradient_fitting,
CGAL::Data_access, etc.

Figure 5 shows the measured velocity at the feature vertices with white
arrows,
and the interpolated velocity at the sample test points with black arrows.

Unfortunately, interpolating with the Delaunay Triangulation
allows for interpolation outside the region (as shown by the left black
arrow),
and inside the holes of the mesh (as shown inside).

We would like to use the Mesh Triangulation for interpolation,
not only because it is more refined,
but also because the mesh is able to exclude, or 'mask out',
the interior polygon areas and external concave areas.

However, I cannot find an example using a CGAL Mesh to interpolate.

Is there a way to connect the CGAL interpolation code with the mesh code?

It seems like there must be a way to utilize the refined mesh
to perform interpolation, but I could not find a way to make it work...


Thanks for any help or guidance you can provide,

Mark Turner
California Institute of Technology
Division of Geological and Planetary Sciences, Mail Code 100-23
Pasadena, CA 91125
Phone: 626-395-4543

--
View this message in context: http://cgal-discuss.949826.n4.nabble.com/interpolation-on-a-mesh-tp3298868p3298868.html
Sent from the cgal-discuss mailing list archive at Nabble.com.

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