## RE: [Algorithms] Bounding cones.

 RE: [Algorithms] Bounding cones. From: Nick Carter - 2004-01-28 01:40:57 ```Tom, You have a way to compute the exact, minimal bounding cone for a set of 2 cones. Can you figure out a way to compute an exact, minimal bounding cone of 3 cones? I ask because the following seems to be true: that, given a arbitrary collection of 4 cones, one of the cones can be removed from the collection without changing the minimal bounding cone of the collection. Thus, (I postulate) from any collection C of cones, it suffices to select three "pivot cones" c1, c2, c3 from C, such that MinimumBoundingCone({c1,c2,c3}) is a cone that strictly contains every element of C. Or, conjectured another way, the minimum bounding cone of a cone-set C is the cone of maximum size from the collection of minimum bounding cones formed by triplets from C. If my reasoning is correct, this should lead to a straightforward search: init: // * number of cones in C int n // * array of cones that we're trying to compute the MBC of array C // * triplet vector we're trying to compute value T= // * boolean valued function that returns true iff cone is completely // within boundingcone function Contains(boundingcone,cone) // * a fast, cone-valued function that computes a minimum bounding cone of three cones // based on some algebraic definition. function MBC3(cone,cone,cone) loop: for k=0 to n { if (!Contains(MBC3(T[0],T[1],T[2]),C[k])) { // we want to insert C[k] into the triplet T if (Contains( MBC3(C[k], T[1], T[2]), T[0] )) T = ; goto loop; // throw out T[0] else if (Contains( MBC3(C[k], T[0], T[2]), T[1] )) T = ; goto loop; // throw out T[1] else if (Contains( MBC3(C[k], T[0], T[1]), T[2] )) T = ; goto loop; // throw out T[2] else // numerical wonkiness, or else I'm fatally // wrong in my conjecture assert(0); } } // if we get here, MBC3(T) is a MBC of C. Thoughts? - nick carter > -----Original Message----- > From: Tom Forsyth [mailto:tom.forsyth@...] > Sent: Tuesday, January 27, 2004 4:05 PM > To: gdalgorithms-list@... > Subject: RE: [Algorithms] Bounding cones. > > > Oooh - so close. Got me all excited. I eventually found a > paper that summarised (and even corrected!) the Sederberg & > Meyers paper, but it's just the same one I found - it adds > one cone at a time to an overall cone, and has the same > properties. They admit it's sub-optimal, but it's still a > good early-out culler. Except that's fine for their case - > the difference between culling perfectly and what they have > is an extra 1% - tiny. In my case, I have twice the pixels to > render :-( > > Ah well - good try though. Your citeseer-fu is strong. Cheers. > > TomF. > > > -----Original Message----- > > From: gdalgorithms-list-admin@... > > [mailto:gdalgorithms-list-admin@...] On > > Behalf Of Mark Duchaineau > > Sent: 27 January 2004 23:32 > > To: gdalgorithms-list@... > > Subject: Re: [Algorithms] Bounding cones. > > > > > > There is a nice result by Sederberg and Meyers, but it is old > > and thus only > > available in libraries: > > > http://citeseer.nj.nec.com/context/178634/0 > > This link gives a number of papers that reference it, so > perhaps some of them will give a useful summary. > > Cheers, > > --Mark D. > > Tom Forsyth wrote: > > I have a bunch of circular-cross-section cones in 3D space, all > originating > > from a single point (assume it's the origin). > > > > > > ------------------------------------------------------- > The SF.Net email is sponsored by EclipseCon 2004 > Premiere Conference on Open Tools Development and Integration > See the breadth of Eclipse activity. February 3-5 in Anaheim, > CA. http://www.eclipsecon.org/osdn > _______________________________________________ > GDAlgorithms-list mailing list GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: http://sourceforge.net/mailarchive/forum.php?forum_ida88 > ```