Algebraic construction of smooth interpolants on polygonal domains

Elisabeth Anna Malsch (a)  and Gautam Dasgupta (b)


a) Graduate Student: Department of Civil Engineering and Engineering Mechanics,Columbia University
500 West 120th St,New York,NY 10027. Email:malsch@civil.columbia.edu

b) Professor: Columbia University. Email:gd18@columbia.edu

Given a set of nodal points which define a geometry,a smooth and bounded function can be constructed in the interior of the domain. A linear interpolation which distributes the value at any given node over the remaining portion of the domain is formulated using a collection of simple functions. The resulting set of interpolations are smooth within the domain. Within a triangle the behavior is akin to a linear gradient.Unlike conventional gradients,the presented formulation applies to any polygonal shape, convex or concave.  It allows, at minimum,bounded interpolations along the boundary.

•Introduction

There are a wide variety of applications for a smooth and bounded interpolation.The most straight forward application is to computer graphics (Foley:1996). The interpolations can also be employed as test functions for computational modeling (Wachspress,1975). For the finite element they act as shape functions (Courant,1943 and Zienkiewicz,1989). And for the boundary element method,they act as trial functions which satisfy essential linear boundary conditions but not the governing field equation (Brebbia:1978).

•Input Data

The interpolation can be constructed on any two dimensional slice of any higher order dimensional polyhedra.Accordingly,the dimension of the data must be defined,for two dimensions for example:

In[3]:=

xy = {x, y} ;

The nodal locations can then be described using the same form:

In[4]:=

xyn = {xn, yn} ; n = 4 ; (* number of nodes *)  pts = Array[Through[xyn[#]] &, n]

The signed connection must also be defined. For example for a triangle with three nodes:

In[7]:=

connect = {{1, 2, 3}} ;

Or for a triangle with an quadrilateral inclusion and an interior point:

In[8]:=

connect = {{1, 2, 3}, {4}, {5, 6, 7, 8}} ;

For a simple interpolation the quantity which is going to be interpolated must be defined at every nodal point:

In[9]:=

dval = Array[dn, n]

•Geometric measures and support functions

It is useful to construct the interpolation with respect to geometric measures as opposed to nodal locations.  The benefit of such an approach is that it is invariant of coordinate system and dimension.

•The distance function

In[10]:=

Clear[dist] dist[a_, b_] := Sqrt[(a - b) . (a - b)] ;

The function is independent of dimension.

•Example

•The signed area of a triangle function

In[12]:=

Clear[area] area[a_, b_, c_] := (1/2) Det[Map[Append[#, 1] &, {a, b, c}]] /; Length[a] == Length[b] == Length[c] == 2

•Example

•The unsigned area function

In[14]:=

Clear[areaUS] areaUS[a_, b_, c_] := Module[{lths = Apply[dist, Partition[{a, b, c}, 2, 1, {1}], {1}], s}, {s = (1/2) Apply[Plus, lths] ;  Sqrt[s * Apply[Times, (s - lths)]]}[[1]]] ;

•Example

•Minimum functions

[Graphics:HTMLFiles/index_23.gif]

The geometric definitions can be used to define minimum functions.For example,the distance function dist[xy,xyi] is minimum at the point defined by the vector xyi ;and the area function area[xy,xyi,xyj] is zero and minimum along the line connecting point xyi to point xyj.

A function which is strictly zero along the line connecting two points is defined in terms of the perimeter of the triangle:

In[16]:=

perim[xy_, a_, b_] := dist[xy, a] + dist[xy, b] - dist[a, b]

•Example

Interpolation construction

Boundaries  can be defined separately using functions which are minimum and zero at  a line. The requirements for an interpolation are:
    (a) Linear independence
    (b) Smoothness
    (c) Boundedness
Any functions which satisfy the requirements are valid interpolations.  Accordingly, any given interpolation is not unique for any given set of nodal points.

•Display support functions

•Convex Polygon

[Graphics:HTMLFiles/index_40.gif]

[Graphics:HTMLFiles/index_41.gif]

Using the geometric measures the interpolation can be constructed simply.

In[24]:=

Clear[varArea, zeroArea, convex, areas, pts] varArea[x_, y_] := Apply[area[##, {x, y}] &, Partition[pts, 2, 1, {1}], {1}] zeroArea[x_, y_] := Apply[Times, Partition[varArea[x, y], Length[pts] - 2, 1, {Length[pts]}], {1}] convex[x_, y_] := (zeroArea[x, y] * areas)/(zeroArea[x, y] . areas)

Example input data:

In[28]:=

points = {{0, 0}, {1, 0}, {1, 1}} ; connect = {{1, 2, 3}} ;  pts = Part[points, connect[[1]]] ; areas = Apply[area, Partition[pts, 3, 1, {2}], {1}] ;

•Triangle example

•Quadrilateral example

•Pentagon example

•Concave Polygon

[Graphics:HTMLFiles/index_68.gif]

Using the geometric measures the interpolation can similarly be constructed simply. The zeroArea[a,b,c] function is replaced with the zeroPerim[a,b,c] function.

In[84]:=

Clear[varPerim, zeroPerim, concave, pts] varPerim[x_, y_] := Apply[perim[{x, y}, ##] &, Partition[pts, 2, 1, {1}], {1}] zeroPerim[x_, y_] := Apply[Times, Partition[varPerim[x, y], Length[pts] - 2, 1, {Length[pts]}], {1}] concave[x_, y_] := (zeroPerim[x, y])/(Plus @@ zeroPerim[x, y])

Example input data:

In[88]:=

points = {{-1, -1}, {0, 0}, {1, -1}, {0, 1}} ; connect = {{1, 2, 3, 4}} ;  pts = Part[points, connect[[1]]] ; areas = Apply[area, Partition[pts, 3, 1, {2}], {1}] ;

•Quadrilateral example

•Pentagon example

•Conclusion

The resulting interpolations are smooth and bounded within their respective domains.  The sum of any set of interpolations is one:

In[111]:=

Plus @@ convex[x, y] // Simplify

Out[111]=

1

In[112]:=

Plus @@ concave[x, y] // Simplify

Out[112]=

1

The functions are linearly independent.

In[115]:=

convex @@@ pts

Out[115]=

{{1, 0, 0, 0, 0}, {0, 1, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 1, 0}, {0, 0, 0, 0, 1}}

In[116]:=

concave @@@ pts

Out[116]=

{{1, 0, 0, 0, 0}, {0, 1, 0, 0, 0}, {0, 0, 1, 0, 0}, {0, 0, 0, 1, 0}, {0, 0, 0, 0, 1}}

Examples of the  smooth and bounded behavior of the functions is shown in the figures.

•Acknowledgement

This research was supported by a National Science Foundation Grant number CMS:0202232.

Bibliography

C. A. Brebbia. The Boundary Element Method for Engineers. John Wiley and Sons, 1978.

R. Courant. "Variational methods for the solution of problems of equilibrium and vibrations". Bulletin of the American Mathematical Society, 1943.  pp. 1-43

Gatum Dasgupta. " Interpolants within convex polygons: Wachspress' shape functions".  ASCE, February 2002.

James D. Foley, Andries Van Dam, Steven K. Feiner and John F. Hughes. Computer Graphics Principles and Practice. Addison-Wesley, New York, 1996.

E. L. Wachspress. A Rational Fnite Element Basis. Academic Press, 1975.

O. C. Zienkiewicz and R. L. Taylor. The Finite Element Method. 4th Edition. McGraw-Hill, New York, 1989


Converted by Mathematica  (March 7, 2003)