在matplot lib中绘制三维凸封闭区域

Question

我试着用3D绘制一个由一组不等式定义的多面体。实际上，我试图在matplotlib中重现这个matlab plotregion库的功能。在

我的方法是得到相交点，构造它们的凸包，然后得到并绘制出结果面（simplice）。在

问题是许多简单化是共面的，它们无缘无故地使绘图变得非常繁忙（请参见下面的图中的所有对角线边）。在

有没有什么简单的方法可以只打印多面体的“外部”边缘，而不需要我自己一个一个地整合所有共面的简单体？在

谢谢你

from scipy.spatial import HalfspaceIntersection
from scipy.spatial import ConvexHull
import scipy as sp
import numpy as np
import matplotlib.pyplot as plt
import mpl_toolkits.mplot3d as a3
import matplotlib.colors as colors


w = np.array([1., 1., 1.])


# ∑ᵢ hᵢ wᵢ qᵢ - ∑ᵢ gᵢ wᵢ <= 0 
#  qᵢ - ubᵢ <= 0
# -qᵢ + lbᵢ <= 0 
halfspaces = np.array([
                    [1.*w[0], 1.*w[1], 1.*w[2], -10 ],
                    [ 1.,  0.,  0., -4],
                    [ 0.,  1.,  0., -4],
                    [ 0.,  0.,  1., -4],
                    [-1.,  0.,  0.,  0],
                    [ 0., -1.,  0.,  0],
                    [ 0.,  0., -1.,  0]
                    ])
feasible_point = np.array([0.1, 0.1, 0.1])
hs = HalfspaceIntersection(halfspaces, feasible_point)
verts = hs.intersections
hull = ConvexHull(verts)
faces = hull.simplices

ax = a3.Axes3D(plt.figure())
ax.dist=10
ax.azim=30
ax.elev=10
ax.set_xlim([0,5])
ax.set_ylim([0,5])
ax.set_zlim([0,5])

for s in faces:
    sq = [
        [verts[s[0], 0], verts[s[0], 1], verts[s[0], 2]],
        [verts[s[1], 0], verts[s[1], 1], verts[s[1], 2]],
        [verts[s[2], 0], verts[s[2], 1], verts[s[2], 2]]
    ]

    f = a3.art3d.Poly3DCollection([sq])
    f.set_color(colors.rgb2hex(sp.rand(3)))
    f.set_edgecolor('k')
    f.set_alpha(0.1)
    ax.add_collection3d(f)

plt.show()

Answer 1

很确定matplotlib中没有本机代码。不过，找到属于一起的脸并不是特别困难。下面实现的基本思想是创建一个图，其中每个节点都是一个三角形。然后连接共面且相邻的三角形。最后，找到图的连接组件，以确定哪些三角形构成面。在

{a1}

import numpy as np
from sympy import Plane, Point3D
import networkx as nx


def simplify(triangles):
    """
    Simplify an iterable of triangles such that adjacent and coplanar triangles form a single face.
    Each triangle is a set of 3 points in 3D space.
    """

    # create a graph in which nodes represent triangles;
    # nodes are connected if the corresponding triangles are adjacent and coplanar
    G = nx.Graph()
    G.add_nodes_from(range(len(triangles)))
    for ii, a in enumerate(triangles):
        for jj, b in enumerate(triangles):
            if (ii < jj): # test relationships only in one way as adjacency and co-planarity are bijective
                if is_adjacent(a, b):
                    if is_coplanar(a, b, np.pi / 180.):
                        G.add_edge(ii,jj)

    # triangles that belong to a connected component can be combined
    components = list(nx.connected_components(G))
    simplified = [set(flatten(triangles[index] for index in component)) for component in components]

    # need to reorder nodes so that patches are plotted correctly
    reordered = [reorder(face) for face in simplified]

    return reordered


def is_adjacent(a, b):
    return len(set(a) & set(b)) == 2 # i.e. triangles share 2 points and hence a side


def is_coplanar(a, b, tolerance_in_radians=0):
    a1, a2, a3 = a
    b1, b2, b3 = b
    plane_a = Plane(Point3D(a1), Point3D(a2), Point3D(a3))
    plane_b = Plane(Point3D(b1), Point3D(b2), Point3D(b3))
    if not tolerance_in_radians: # only accept exact results
        return plane_a.is_coplanar(plane_b)
    else:
        angle = plane_a.angle_between(plane_b).evalf()
        angle %= np.pi # make sure that angle is between 0 and np.pi
        return (angle - tolerance_in_radians <= 0.) or \
            ((np.pi - angle) - tolerance_in_radians <= 0.)


flatten = lambda l: [item for sublist in l for item in sublist]


def reorder(vertices):
    """
    Reorder nodes such that the resulting path corresponds to the "hull" of the set of points.

    Note:
      -
    Not tested on edge cases, and likely to break.
    Probably only works for convex shapes.

    """
    if len(vertices) <= 3: # just a triangle
        return vertices
    else:
        # take random vertex (here simply the first)
        reordered = [vertices.pop()]
        # get next closest vertex that is not yet reordered
        # repeat until only one vertex remains in original list
        vertices = list(vertices)
        while len(vertices) > 1:
            idx = np.argmin(get_distance(reordered[-1], vertices))
            v = vertices.pop(idx)
            reordered.append(v)
        # add remaining vertex to output
        reordered += vertices
        return reordered


def get_distance(v1, v2):
    v2 = np.array(list(v2))
    difference = v2 - v1
    ssd = np.sum(difference**2, axis=1)
    return np.sqrt(ssd)

应用于您的示例：

^{pr2}$

注意

经过深思熟虑，函数reordered可能需要更多的工作。非常肯定这会打破奇怪/非凸形状，我甚至不能百分之百肯定它会永远适用于凸形状。不过，休息应该没问题。在

Answer 2

以下是我的解决方案。它类似于@Paul的解决方案，它获取三角形，按它们所属的面分组，然后将它们连接到一个面上。在

区别主要在于此解决方案不使用nx或{}。许多必要的操作是通过重新编制索引、广泛使用unique和一些线性代数来执行的。
最终面顶点的顺序由ConvexHull决定。我认为这不应该是一个限制，因为（我认为）任何半空间的交集只能产生凸形。但是，我还添加了另一种方法，如果形状不是凸的（基于this question的思想）。在

from scipy.spatial import HalfspaceIntersection
from scipy.spatial import ConvexHull
import numpy as np
import matplotlib.pyplot as plt
import mpl_toolkits.mplot3d as a3

w = np.array([1., 1., 1.])
# ∑ᵢ hᵢ wᵢ qᵢ - ∑ᵢ gᵢ wᵢ <= 0 
#  qᵢ - ubᵢ <= 0
# -qᵢ + lbᵢ <= 0 
halfspaces = np.array([
                    [1.*w[0], 1.*w[1], 1.*w[2], -10 ],
                    [ 1.,  0.,  0., -4],
                    [ 0.,  1.,  0., -4],
                    [ 0.,  0.,  1., -4],
                    [-1.,  0.,  0.,  0],
                    [ 0., -1.,  0.,  0],
                    [ 0.,  0., -1.,  0]
                    ])
feasible_point = np.array([0.1, 0.1, 0.1])
hs = HalfspaceIntersection(halfspaces, feasible_point)
verts = hs.intersections
hull = ConvexHull(verts)
simplices = hull.simplices

org_triangles = [verts[s] for s in simplices]

class Faces():
    def __init__(self,tri, sig_dig=12, method="convexhull"):
        self.method=method
        self.tri = np.around(np.array(tri), sig_dig)
        self.grpinx = list(range(len(tri)))
        norms = np.around([self.norm(s) for s in self.tri], sig_dig)
        _, self.inv = np.unique(norms,return_inverse=True, axis=0)

    def norm(self,sq):
        cr = np.cross(sq[2]-sq[0],sq[1]-sq[0])
        return np.abs(cr/np.linalg.norm(cr))

    def isneighbor(self, tr1,tr2):
        a = np.concatenate((tr1,tr2), axis=0)
        return len(a) == len(np.unique(a, axis=0))+2

    def order(self, v):
        if len(v) <= 3:
            return v
        v = np.unique(v, axis=0)
        n = self.norm(v[:3])
        y = np.cross(n,v[1]-v[0])
        y = y/np.linalg.norm(y)
        c = np.dot(v, np.c_[v[1]-v[0],y])
        if self.method == "convexhull":
            h = ConvexHull(c)
            return v[h.vertices]
        else:
            mean = np.mean(c,axis=0)
            d = c-mean
            s = np.arctan2(d[:,0], d[:,1])
            return v[np.argsort(s)]

    def simplify(self):
        for i, tri1 in enumerate(self.tri):
            for j,tri2 in enumerate(self.tri):
                if j > i: 
                    if self.isneighbor(tri1,tri2) and \
                       self.inv[i]==self.inv[j]:
                        self.grpinx[j] = self.grpinx[i]
        groups = []
        for i in np.unique(self.grpinx):
            u = self.tri[self.grpinx == i]
            u = np.concatenate([d for d in u])
            u = self.order(u)
            groups.append(u)
        return groups


f = Faces(org_triangles)
g = f.simplify()

ax = a3.Axes3D(plt.figure())

colors = list(map("C{}".format, range(len(g))))

pc = a3.art3d.Poly3DCollection(g,  facecolor=colors, 
                                   edgecolor="k", alpha=0.9)
ax.add_collection3d(pc)

ax.dist=10
ax.azim=30
ax.elev=10
ax.set_xlim([0,5])
ax.set_ylim([0,5])
ax.set_zlim([0,5])
plt.show()