Re: [Algorithms] Checking normals against an halfplane

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

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