algorithm - computing 3D reduced convex hull -


i'm looking algorithm provides call "shrunken convex hull" (as distinct "reduced convex hull") in 3d. defining shrunken hull, h', volume of space has, no less d distance original convex hull, h.

analytically, can formed moving each plane of h inwards along normal d, computing convex hull (if exists) of resultant planes. tricky bit planes might trimmed or dropped, others may move past other planes, , entirely "snipped" out due normal reversal (if d big enough). i’m bit fuzzy on how algorithm, have badly thought out ideas below.

i doing identify subset of points in dataset guaranteed no less given distance surface of original point set (which assumed convex, , have this). remove surface effects disrupting our signal in calculations doing.

i'm looking name, or examples of doing this, or way compute this. ideally good-old open code great, think problem far niche.

i found reduced convex hulls, seems different idea. current closest thing can find "hausdorff cores" - seems more complicated case of non-convex polygons, , pretty damned dense.


do not read beyond here, unless really want to.

current, incomplete/badly thought out algorithm

the slow way (i.e. current way) of identifying reduced point set compute signed distance points, , reject less given distance. however, pretty damned slow, number of points can 100m. think operating on original hull generate shrunken hull, , computing aabb , spherical bb, retaining inside shrunken hull might faster (i hope -willing accept comments saying stupid).

i think should possible, don't strictly need full distance information each point, d_point > d. once know should able stop.

i can see how shrunken hull might done in 2d, @ each vertex, use analytical solution constant velocity eikonal, move vertex along vector derived each corner.

however, situation more complex 3d version, afaics, there multiple facets (>2) each vertex . current plan @ each edge pair individually, work there (somehow - create half spaces , union them?) build hull.

what thinking of downscaling 3d convex hull, works downscaling 2d image, except how angle

outline algorithm (in 2d) looks this:

1. compute convex hull. 2. each point, p, in convex hull: 3.     find hull points before , after, p 4.     bisect angle formed obtain angle, a, required. 5.     create new point, p', along angle @ distance, d, `p`. 7.     add p' scaled-down (shrunken) convex hull. 

the difference in 3d occurs in lines 3 , 4. in 3d, step 3 obtains 3 points. in step 4, 3d angle used. you'll find fair bit of benefit in using 3d transforms in graphics/geometry libary, math may tricky.


Comments

Popular posts from this blog

Payment information shows nothing in one page checkout page magento -

tcpdump - How to check if server received packet (acknowledged) -