Re: convex hulls

In article <1169192158.799267.75990@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Rij <rij.ghosh@xxxxxxxxx> wrote:
anybody knows how to find tangent to a convex hull at a given point?
also, how do you test if a point is inside or outside the hull?

These tasks are straightforward if the convex hull is represented as
an intersection of half-spaces, i.e., a list of inequalities of the
form u.x <= c where u is a given vector and c is a given scalar. To
check whether a point is inside the hull, run down the list of inequalities
and check each one. If it satisfies all the inequalities then it is in
the convex hull; if it violates any inequality then it's not. If you
find that u.x is actually equal to c (this is guaranteed to happen at least
once if x is on the surface of the convex hull), then the plane u.x = c is
a tangent to your point.

If the convex hull is represented as a list of points, then I think the
best thing to do is still to convert it to the half-space representation
first, and then proceed as above. My favorite package for doing this is
cdd+, which you can easily find on the web.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.