0

この質問についてしばらく考えましたが、「エッジ」または「頂点」をグーグルで検索しても、有用なものは何も返されません。

はい、立方体の場合は非常に簡単ですが、3Dの任意の形状の場合はそれほど簡単ではありません。たとえば、凹面のボディ。いくつかの対角線が見つかるかもしれませんが、それはエッジではありません。

4

1 に答える 1

3

この質問のこの一般的な用語は凸包と呼ばれます

GISで広く使用されています

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

そして最も有名なアルゴリズムは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

おもしろい事実：凸面または凹面の船体には特許があります：

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

于 2013-01-08T08:59:16.870 に答える