math - 对于一个立方体，给定 8 个顶点坐标，如何获得 12 条边的坐标对？

Question

我想了一会儿这个问题，谷歌搜索“边缘”或“顶点”并没有返回任何有用的信息。

是的，对于三次方来说非常简单，但对于 3D 中的任意形状来说并不那么容易。例如凹形体。您可能会发现一些对角线，但它不是边缘。

Answer 1

这个问题的通用术语称为Convex Hull

广泛应用于GIS

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

最著名的算法是由 ACM 的 Graham Scan 完成的

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