Re: [Algorithms] Checking normals against an halfplane

[Andreas <and...@st...>]

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

That's me...

> 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) ?

I have heard that quickhull is the fastest, and that its average
time complexity is O(n*lg n), but O(n^2) in worst case.

> 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.

I don't think we can do any better than linear time either, but
that's quite ok considering the problem.

Step 3 computed the normal of the plane, given that such a plane
exist. I realized that it can do wrong sometimes. I tried to
find the central point as fast as possible, but it fails
sometimes. You need to find a better algorithm for this.

--Andreas

> 
> 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
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list