Re: O(NlogN) spatial sort & O(logN)? spatial search, no spatial index

The simplest pseudocode to explain hulls is the one for spheres
http://www.mcnett.org/sphere.txt

There's only one "hull" in there, and it's the search query. It could
be any shape, but it probably would be a regular tetrahedron in 3D.

It is very hard to understand the algorithm. This is partly because I am
still not understanding the terminology you use:)

A convex hull, in mathematics, is defined as follows:
Let there be a point set {P_i}. The convex hull of the point set is the
set of points of the form:
C({P_i}) = sum[i=1..n](a_i * P_i)
with
a_i = a real number for all i
sum(a_i) = 1 and
a_i >= 0 for all i.

That is, the convex hull of the point set is the set of all convex
combinations of the point set.

Convex hulls of point sets are convex polygons in 2D and convex
polyhedra in 3D. For a common name, convex polytopes. A convex hull is
always w.r.t to a point set so it does not make sense to only say a hull
or a convex hull.

Is the search range always a convex polytope, regardless of whether
there are spheres or other objects?

Must the search range be a simplex (triangle in 2D, tetrahedron in 3D)
or is any convex polytope ok?

The "plane" values in the hull are like the minx, miny, minz, maxx,
maxy, maxz of an AABB. except it's a bounding tetrahedron, so they are
the mina, minb, minc, mind of a tetrahedron.

Each "plane" value is a signed distance from the plane to the origin.

The geometric configuration is not clear. Along what are the distances
measured? How can the distance be negative? Are the planes possibly
axis-aligned?

Images always help, if possible.


Thanks Kalle, you're helping me to write better documentation!

For simplicity's sake, should I write a version that uses AABB?
Tetrahedra are simpler and have better perfornance, but any convex
hull will work.

If it helps to understand it:)

"dot( median->position, basis[direction] ) - median->radius"

What does this compute, geometrically? (It is from the sphere code). I
guess there is some projection involved but using position vectors
rather than vectors mix up my geometric intuition.

--
Kalle Rutanen
http://kaba.hilvi.org
.

Relevant Pages

  • Re: Probability of a convex hull
    ... calculate the areas where points added will still yield a convex ... hull, these are indeed outside of the current convex hull and should not ... > Assuming you have a 2D space of x and y dimensions and you select ... > what is the probability that all of the n points will exist on ...
    (comp.graphics.algorithms)
  • Rendering of a point cloud
    ... If the domain is convex, ... then use trisurf to display the facets of the hull ... non-convex hull. ...
    (comp.soft-sys.matlab)
  • Re: Howto model decoupled hierarchies?
    ... polygon) or a kD-Tree. ... Convex of Hull: ... How many convex of hulls can a pointX need to store? ...
    (comp.object)
  • Re: 3D surface plot of point cloud
    ... Only if you decide that it should be the convex ... hull or give some other restriction. ... equivalent to a sphere. ... But a non-convex domain may ...
    (comp.soft-sys.matlab)
  • Re: inpolygon in 3D
    ... barycentric coordinates for each point in each simplex. ... convex, so these factors were all importance. ... Given any 4-simplex (tetrahedron) in the 3-d space, ... this unique linear combination. ...
    (comp.soft-sys.matlab)
Loading