Convex Hulls and More

Math 282 Computational Geometry

(Based on code from Joseph O’Rourke.)

Draw a paraboloid and a shifted tangent plane

First, we draw a paraboloid.

domain=8; (* controls how much of the xy-plane to draw *)
paraboloid=Plot3D[x^2 + y^2, {x,-domain,domain},{y,-domain,domain}, PlotStyle->Directive[Opacity[0.7]],BoxRatios->{1,1,2}]

The point (a, b, (a^2)+(b^2)) lies on the paraboloid.

a=3;b=2;
pt={a,b,a^2+b^2};

The tangent plane at this point is given by z=2a x +2 b y -(a^2)-(b^2). We will shift this plane upwards by (r^2), where r is a parameter.

r=4;
plane=Plot3D[2 a x + 2 b y - (a^2 + b^2 )+r^2, {x,-domain,domain},{y,-domain,domain}, PlotStyle->Directive[Opacity[0.7],Green]]

Now draw the paraboloid and tangent plane together.

Show[paraboloid,plane]

What do you notice about the intersection of the paraboloid and the plane?

Now draw a cylinder

Now we will plot the point (a, b, (a^2)+(b^2)) on the paraboloid and its projection (a,b,0) onto the xy-plane. We will also draw a cylinder of radius r whose central axis goes through these two points.

pt2={a,b,0};
tube=Graphics3D[{Point[{pt,pt2}],Line[{pt,pt2}],CapForm[None],Opacity[0.5],Tube[{{a,b,0},{a,b, 2(a^2+b^2+r^2)}},r]},ImageSize->Small]

Plot everything together:

Show[paraboloid,plane,tube]

Rotate the graph and observe that the intersection of the paraboloid and plane, when projected to the xy-plane, is a circle.

Dynamic Exploration

We will create a module that draws the 3D graph for a user-defined value of r. This relies on some data objects from the code above, but it redraws plane and cylinder for each value of r.

paraboloidExploration[r_]:=Module[{plane,tube,graph},
plane=Plot3D[2 a x + 2 b y - (a^2 + b^2 )+r^2, {x,-domain,domain},{y,-domain,domain}, PlotStyle->Directive[Opacity[0.5],Green]];
tube=Graphics3D[{Point[{pt,pt2}],Line[{pt,pt2}],CapForm[None],Opacity[0.5],Tube[{{a,b,0},{a,b, 2(a^2+b^2+r^2)}},r]},ImageSize->Small];
graph=Show[paraboloid,plane,tube]
]

Now we will use the Manipulate command to produce the dynamic exploration. Adjust the value of r and rotate the graph to see that the intersection of the paraboloid and plane is always an ellipse, which projects to the xy-plane as a circle.

Manipulate[paraboloidExploration[r],{r,0,8}]

Convex Hulls and Delaunay Triangulations

Generate some points in the plane:

numPoints=12;
points=RandomReal[{-domain,domain},{numPoints,2}];
Graphics[{Blue,PointSize[0.02],Point[points]},Frame->True]

Project each point onto the parabola:

projectedPoints={#[[1]],#[[2]],#[[1]]^2+#[[2]]^2}&/@points;
lines={{#[[1]],#[[2]],0},{#[[1]],#[[2]],#[[1]]^2+#[[2]]^2}}&/@points;
points0={#[[1]],#[[2]],0}&/@points;
projections=Graphics3D[{Blue,PointSize[0.02],Point[points0],Green,Point[projectedPoints],Gray,Line[lines]}];
Show[paraboloid,projections]

Compute the convex hull of the projected sites:

hull=ConvexHullMesh[projectedPoints];
Show[paraboloid,hull,projections]

We want the lower hull, which consists of only those faces of the convex hull whose outward-pointing normal vector has negative z-coordinate. Before we can compute this, we need to compute outward-pointing normal vectors.

The following function returns a the vertex coordinates of the ith face of the hull.

getFaceVertices[i_]:=MeshCoordinates[hull][[MeshCells[hull,2][[i,1]]]]

The following function computes a normal vector of a triangle, specified by the coordinates of its vertices. Since ConvexHullMesh stores face vertices in counterclockwise order when viewed from outside the hull, this function will produce an outward-pointing normal vector.

computeNormal[triangle_]:=Module[{u,v},
u =triangle[[2]]-triangle[[1]];
v=triangle[[3]]-triangle[[1]];
Cross[u,v] (* return the cross product of u and v *)
]

Now we can compute the lower hulls, which we will store as a list of triangles:

lowerHullTriangles={};
c=MeshCellCount[hull,2];
Do[
t=getFaceVertices[i];
z=computeNormal[t][[3]];
If[z<0,AppendTo[lowerHullTriangles,Triangle[t]]]
,{i,c}]

Visualize the lower hull:

lowerHull=Graphics3D[{Green,Opacity[0.6],lowerHullTriangles},Boxed->True,Axes->True,AxesLabel->{"x","y","z"}];
Show[paraboloid,lowerHull,projections]

Now we project the lower hull down to the xy-plane. To do this, we take all vertices of all triangles in the lower hull and set their z-coordinates to zero.

projectedHullTriangles=Map[
Function[tri,
Triangle[Map[Function[verts,{verts[[1]],verts[[2]],0}],tri[[1]]]]
],
lowerHullTriangles
];
projectedHull=Graphics3D[{Cyan,Opacity[0.8],projectedHullTriangles},Boxed->True,Axes->True,AxesLabel->{"x","y","z"},ViewPoint->{0,0,10}]

Here is the 3D diagram showing the paraboloid, the lower hull, and the projection of the lower hull onto the xy-plane:

Show[paraboloid,lowerHull,projections,projectedHull]

What do you notice about the triangulation in the xy-plane?

Tangent Planes and Voronoi Diagrams

Now we will compute and visualize the tangent planes to the paraboloid at all of the points that we projected onto the paraboloid:

tangentPlanes=Plot3D[
Evaluate[2 #[[1]]x + 2 #[[2]] y - (#[[1]]^2 + #[[2]]^2 )&/@points],
 {x,-domain,domain},{y,-domain,domain}]

Consider the top-down view of the tangent planes, together with the projected points:

Show[tangentPlanes,Graphics3D[{PointSize[0.02],Point[projectedPoints]}],ViewPoint->{0,0,10}]

What do you notice about this view of the tangent planes?