Re: [Algorithms] Checking normals against an halfplane

[Pierre T. <p.t...@wa...>]

Your name reminds me of something.... you wrote a thesis about ROAM, don't
you ? :)

This method seems to work. Unfortunately I don't feel like computing the
convex hull of the vertex cloud before starting the real work. BTW what is
the fastest known algorithm to compute a convex hull? Should be quickhull I
think, but I don't remember, is it O(n*lg n) ?

Point 2) looks slow as well. Is there any fast method to check a vertex is
inside a convex polytope? I can see how to do that in O(n) time, nothing
really better.

Pierre

----- Original Message -----
From: Andreas Ögren <and...@st...>
To: <gda...@li...>
Sent: Wednesday, August 16, 2000 9:35 AM
Subject: Re: [Algorithms] Checking normals against an halfplane


> I haven't encountered that problem earlier, so I don't know if
> the following (high-level) algorithm is the fastest (or even
> correct). But consider doing something like:
>
> 1. Find the convex hull of all normals (considered as points).
> 2. Check if the origin is within this convex hull. If so, there
> is no such plane.
> 3. Compute the normal of the plane as the vector from the origin
> to the average point of all points at the edge of the convex
> hull. If the special case that the average point is zero, just
> compute the cross product of two normals at the convex hull
> edge.
>
> --Andreas
>
> Pierre Terdiman wrote:
> >
> > Ok, another little algorithm I'm fighting with.
> >
> > Say I have a set of N normals, centered at the origin, in random
directions.
> > The goal is to:
> > 1) check all of them lie on the same side of a plane passing through the
> > origin
> > 2) find such a plane
> >
> > That plane is unknown when the routine is called. I must determine
whether
> > such a plane can exist (this is not always the case). Needless to say,
it
> > must be done in a quick way.
> >
> > I don't expect a light-speed algorithm to exist, but I know you people
> > sometimes come up with amazing solutions. Hence, worth trying.
> >
> > Pierre
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list