Distance Queries

Distance queries give the distance to a geometric object or the distance between objects. Usually the minimum distance is of interest. Collision detection is a special case distance query - collision occurs when the minimum distance is zero. Distance measures are of interest in path planning, robotics, assembly operations, and data fitting, to name just a few areas.

Table of Contents

Closest Point on Polyline

This constuctor returns the closest point on a polyline to a point in space. It works by projecting the space point onto each line segment of the polyline, and returning the closest projection.

closestPtPolyline( Point, Polyline )
Returns
<e3Pt> Create a 3D point that is the closest point on the polyline to the space point.
Point
<e3Pt> A point in space.
Polyline
<polyline> A polyline in space.
Here is an example:

  

# The polyline in space.
l : polyline(   pt( 0, 0, 0),
                pt( 0.5, 0.5, 0.0),
                pt( 1.0, -0.2, 0.0),
                pt( 1.0, 0.2, 0.4) );
# The space point
sp : pt( 0.5, 0.7, 0.0 );

# The closest point on the polyline to sp.
d : closestptpolyline( sp, l );

show(l,sp,d,polyline(sp,d));

Closest Point on Crv

This constuctor returns the parametric value of the closest point on a curve to a point in space. It works by computing the symbolic distance curve and solving for roots using a combination of subdivision and numerical methods.
closestPtCrv( Point, Curve )
Returns
<e3Pt> Returns a real number that is the parametric value of the closest point on the curve to the space point.
Point
<e3Pt> A point in space.
Polyline
<curve> A curve in space.

Closest Point on Srf

This constuctor returns the parametric value of the closest point on a surface to a point in space. It works by computing the symbolic distance surface and solving for roots using a combination of subdivision and numerical methods.
closestPtSrf( Srf, Point, Eps )
Returns
<e3Pt> Returns a parametric point that is the parametric value of the closest point on the surface to the space point.
Srf
<surface> A surface in space.
Point
<e3Pt> A point in space.
Eps
<number> A tolerance number.

Barycentric Coordinates

Barycentric coordinates are coordinates relative to possibly non-orthogonal axis. They are useful in things like texture mapping and mapping projections in the space of a triangle - for example, interpolating between vertices of a control mesh. For a given triangle, defined by a set of three points, and a space point in the plane of the triangle, there are three barycentric coordinates that weight each vertex of the triangle to give the space point.

 

baryCoords( Triangle, Point )
Returns
<e3Pt> Create a 3D point that holds the 3 barycentric coordinates of the point in the triangle.
Triangle
<arrayOf point> An array of 3 points defining the triangle.
Point
<e3Pt> The point in the plane of the triangle.
Here is an example:

  

t1 : pt(0,0,0);
t2 : pt(1,0,0);
t3 : pt(0,0.8,0);

tri : polyline( t1, t2, t3, t1 );

p : pt( 0.5, 0.3, 0.0 );

show( tri, p );

bary : baryCoords( array( t1, t2, t3 ), p );

backToEuclidSpace : ptBlend( array( t1, t2, t3 ),
                             array( bary.x, bary.y, bary.z ));

# This should be the same point as p
show( backToEuclidSpace );

Closest Point on Triangle

This function returns a point that is the closest point on a triangle to a arbitrary point in space. This is different than just projecting onto the plane of the triangle, since the triangle boundaries must be taken into account. 
closestPtOnTri( Triangle, Point )
Returns
<e3Pt> Create the point on the triangle closest to Point.
Triangle
<arrayOf point> An array of 3 points defining the triangle.
Point
<e3Pt> The point in space.
Here is an example:

  

t1 : pt(0,0,0);
t2 : pt(1,0,0);
t3 : pt(0,0.8,0);

tri : polyline( t1, t2, t3, t1 );

p : pt( 0.5, 0.3, 0.5 );

show( tri, p );

closest : closestPtOnTri( array( t1, t2, t3 ), p );

closestline : polyline( p, closest );

show( closestline );

p : pt( 0.8, 0.8, 0.5 );

Closest Point on Triangle Model

This constuctor returns the closest point on a triangle-based model. It works by projecting the space point onto each triangle facet of the model, and returning the closest projection. Triangle models are often read in with the polyfromtri command.

closestPtTriPolyObj( Point, Polyline )
Returns
<e3Pt> Create a 3D point that is the closest point on the polyline to the space point.
Point
<e3Pt> A point in space.
Polyline
<polyline> A polyline containing triangles.
Here is an example:

  

# The polyline in space.
l : polyfromtri("/res/alpha1/src/a1src/data/tri_models/bun1.tri")$;
# The space point
sp : pt( 5, 7, 10.0 );

# The closest point on the polyline to sp.
d : closestpttripolyobj( sp, l );

show(l,sp,d,polyline(sp,d));

Minimum Separation for Two Convex Sets

Given two convex sets defined as a set of vertices, this function will find the two points, one on each convex object, that define the minimum separation of the objects. 
closestPtConvexSets( Set1, Set2 )
Returns
<group> Construct a group of the two points that define the minimum separation.
Set1
<arrayOf point> An array holding the vertices of a convex set.
Set2
<arrayOf point> An array holding the vertices of a convex set.
Here is an example:

  

a : pt(0,0,0.2);
b : pt(1,0,0);
c : pt(0,0.8,0);
d : pt(0.5, 0.3, 0.3 );
s1 : polyline(a,b,c,a,d,c,d,b);

x : pt( 1.1, 0.7, -0.2 );
y : pt( 0.7, 0.5, 0.1 );
z : pt( 0.7, 0.2, 0.5 );
w : pt( 0.8, 0.7, 0.2 );

s2 : polyline( x,y,z,x,w,y,w,z );

show( s1, s2 );

clpts : closestPtConvexSets( array(a,b,c,d), array(x,y,z,w) );
minSepLine : polyline( clpts[0], clpts[1] );

show( minSepLine );

Closest Point on a Control Mesh

The returns the closest point on a control mesh to a space point. This is a little funny, because a control mesh is made up of bilinear patches, and this function returns the closest point on the tesselation of the the control mesh. The tesselation is not unique, though - the diagonals added to the patches can go in two directions. For most applications, this is what you want, though. 
closestPtCtlMesh( Srf, Point )
Returns
<e3Pt> Construct a point that is the closest point on the control mesh of Srf to Point.
Srf
<surface> A surface with a ctl mesh.
Point
<e3Pt> A space point.
Here is an example:

  

flat : flatsrf( 3, 3,10,5)$;
warp : warp( flat, vec(0.0,0.0,0.9), pt( 0.0, 0.0, 0.0 ), 1.15, 0.9, 1 )$;

pt : pt( 0.4, 0.5, 0.9);

meshpt : closestptctlmesh( warp, pt );

# Use display parameters to look at the ctl mesh of warp.
show( warp, pt, meshpt );

Nodal Map a Point onto a Surface

This maps a space point onto a surface using nodal mapping. The point is projected onto the control mesh of the surface. The node values of the surface associated with the corners of the facet of the control mesh that the point is projected onto are used to associate a parametric value with that projected point. The u,v values are returned as a point. This is really a first order approximation to the closest point on the surface. It can also be used to do weird things like remap textures onto different parametrized objects. 
nodalMap( Srf, Point )
Returns
<e3Pt> Construct a point that holds the u,v nodal mapping of the Point on the Srf.
Srf
<surface> A surface with a ctl mesh.
Point
<e3Pt> A space point.
Here is an example:

  

flat : flatsrf( 3, 3,10,5)$;
warp : warp( flat, vec(0.0,0.0,0.9), pt( 0.0, 0.0, 0.0 ), 1.15, 0.9, 1 )$;

pt : pt( 0.4, 0.5, 0.9);

uvpt : nodalmap(warp, pt);
srfpt : srfeval(warp, uvpt.x, uvpt.y );

# Use display parameters to look at the ctl mesh of warp.
show( warp, pt, srfpt );
C_Shape_Edit User's Manual Home Page 
Alpha_1 User's Manual.
Copyright © 1998, University of Utah
a1-web@gr.cs.utah.edu