0

I thought about this quesion for a while, and googling "edge" or "vertices" does not return anything useful.

Yes it's very simple for cubic, but not so easy for arbitrary shape in 3D. E.g. a concave body. You might find some diagonal lines but it's not the edge.

BoltClock
  • 700,868
  • 160
  • 1,392
  • 1,356
est
  • 11,429
  • 14
  • 70
  • 118

1 Answers1

3

This general term for this question is called Convex Hull

It's widely used in GIS

https://gis.stackexchange.com/questions/1200/concave-hull-definition-algorithms-and-practical-solutions

And the most famous algorithm is done by Graham Scan from ACM

GRAHAM_SCAN(Q)

Find p0 in Q with minimum y-coordinate (and minimum x-coordinate if there are ties).
Sorted the remaining points of Q (that is, Q ? {p0}) by polar angle in counterclockwise order with respect to p0.
TOP [S] = 0                ? Lines 3-6 initialize the stack to contain, from bottom to top, first three points.
PUSH (p0, S)
PUSH (p1, S)
PUSH (p2, S)
for i = 3 to m             ? Perform test for each point p3, ..., pm.
    do while the angle between NEXT_TO_TOP[S], TOP[S], and pi makes a nonleft turn  ? remove if not a vertex
                do POP(S)
         PUSH (S, pi)
return S

http://en.wikipedia.org/wiki/Graham_scan

http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/ConvexHull/GrahamScan/grahamScan.htm

Fun fact: convex OR concave hull has a patent:

https://stackoverflow.com/a/2241263/41948

Community
  • 1
  • 1
est
  • 11,429
  • 14
  • 70
  • 118
  • Please, the patent mentioned is related only to concave hull, so we can already exclude it has any attempt to patent convex hull algorithms. The patent is only for an specific algorithm related to concave hull, so it is not like you can't use, for example, alpha-shapes (1983) from Edelsbrunner, Kirkpatrick and Seidel. The patent explicitly mentions the prior existence of other concave hull algorithms, and also briefly mentions some of them are more closely related to surface reconstruction (this includes alpha-shapes). – mmgp Jan 08 '13 at 16:07
  • 1
    So, no, convex OR concave hull are not covered in any general way in the mentioned patent. The patent covers only a specific implementation, which is described in the more complete description. Reading the summary of a patent is misleading sometimes. – mmgp Jan 08 '13 at 16:09