## RE: [Algorithms] Bounding cones.

 RE: [Algorithms] Bounding cones. From: Tom Forsyth - 2004-01-28 11:07:25 ```Aha: "It can be shown that the central axis of such a cone has the following property: if one associates a point on the unit sphere with each face = normal in the cluster, and computes the 3D convex hull of this pointset, must = pass through the closest point from the origin to that convex hull." I guess that makes sense - the 2D version of the same thing "obviously works", but my brain doesn't find the 3D version as obvious. Not all that sure I want to try constructing the convex hull of circles = at runtime though - sounds expensive. ... Argh. I worked out a lovely O(n) algorithm where you only ever track at = most three cones that make up the bounding hull feature closest to the origin (either an edge or a plane) as you go along (similar to what Nick was saying). Problem is, that's not enough. You can never guarantee to throw away information and still get an optimal hull. Imagine a regular n-gon of cones of the same radius (Ci). Then place = another cone (C0) quite a way off. So the bounding cone is now formed by C0 and = one or two of Ci - the ones furthest from C0. But depending where you put = C0, it's a different Ci. So until you have C0, you can never throw away any = Ci, no matter how big n is. Which means that although Nick is (probably) right when he says that any bounding cone is formed by at most three cones, adding another cone may produce a new bounding cone that uses a _completely different three_. = Which is a pain. However, I suspect the number you actually need to track will be = reasonable in practice - you should be able to throw most of them away (anything = that is inside the hull is definately never going to be part of the hull in future). So this is certainly a plausable avenue of attack. Got me some maths to do. TomF. > -----Original Message----- > From: gdalgorithms-list-admin@...=20 > [mailto:gdalgorithms-list-admin@...] On=20 > Behalf Of Peter-Pike Sloan > Sent: 28 January 2004 05:50 > To: gdalgorithms-list@... > Subject: RE: [Algorithms] Bounding cones. >=20 >=20 > I haven't been following this thread that closely, but pedro=20 > sander did > a very nice job of computing optimnal sphere/cone hiearchies for his > Silhouette Clipping paper: >=20 > http://pedrosander.com/publications/ >=20 > (section 5 in the above paper) >=20 > -Peter-Pike Sloan >=20 > -----Original Message----- > From: gdalgorithms-list-admin@... > [mailto:gdalgorithms-list-admin@...] On Behalf Of > Jonathan Blow > Sent: Tuesday, January 27, 2004 7:27 PM > To: gdalgorithms-list@... > Subject: Re: [Algorithms] Bounding cones. >=20 > > However, you might have something there. If I simply took n points=20 > > around the edge of each cone, where n is about 3-6 (could=20 > even change=20 > > the number according to the size of the cone - typically I=20 > will have=20 > > cones of widely varying sizes, since the objects vary=20 > widely in size,=20 > > and are at very different distances to the light). Then=20 > cluster them,=20 > > and use that as a starting guess. As long as the initial guess is=20 > > fairly accurate, I think it's true to say you can then do the=20 > > one-at-a-time merging and still get a very good bounding cone at the > end. >=20 > The covariance stuff is really fast, once you have the initial values > inside the covariance matrices; you can just transform them=20 > and add them > after that. > And actually, you can compute the closed-form covariance of a=20 > cone, and > evaluating that would probably be faster than using individual points. > So my original 1000 points idea was overzealous and unnecessary. >=20 > By default when using such closed-form covariance, big cones would be > favored, but you can compensate for this just by scaling up=20 > the density > of the small cones. >=20 > I'm not saying it's the best solution for your problem, but it's worth > trying if yer gonna investigate various solutions. >=20 >=20 >=20 > ------------------------------------------------------- > The SF.Net email is sponsored by EclipseCon 2004 Premiere=20 > 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_id=3D6188 >=20 >=20 > ------------------------------------------------------- > 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 >=20 ```