构造多边形的轮廓（特别是三角剖分）

Question

我将如何构建仅由三角形组成的二维多边形的轮廓，它可以有孔，外部轮廓可以是凹/凸的，孔也可以是凹/凸的。

从我在这里读到来看，这似乎正是三角测量问题的反演。 您知道有哪些文章可以解决此类问题吗？

八叉树/四叉树与此相关吗？

Answer 1

我猜您拥有三个点集形式的数据，这三个点构成了一个“填充”三角形，这些三角形沿边相邻，并且将成为完整形状的角的所有顶点也是所有三角形的顶点触及这一点。 然后，您只需找到所有未加倍的边，即不属于两个相邻三角形的边。

Answer 2

我认为您可以通过创建一个拓扑数据结构来表示三角形集，然后使用该结构按顺序迭代位于边界上的三角形边来解决您的问题。

例如：您可以创建半边数据结构。 假设您甚至在边界上插入半边（正确），则迭代边界轮廓就像在边界上定位一个半边一样简单，然后迭代它的“下一个”指针，直到回到开始的半边。

与半边类似，您可以使用其他拓扑结构，例如翼边等，但概念是相同的。

Answer 3

这是在三角形网格上运行的实现，查找并连接所有非双边，如此答案中所述。

#include <list>
#include <map>
#include <set>
#include <vector>
#include <iostream>

typedef int Vertex;

class Triangle {
public:
    const Vertex& operator [] (size_t i) const {
        return p[i];
    }
    Vertex p[3];
};

std::list<std::list<Vertex>> find_contours(const std::vector<Triangle>& triangles) {

    std::set<std::pair<Vertex, Vertex>> edges;
    std::map<Vertex, Vertex> neighbors;
    for(const auto& t : triangles) {
        edges.insert(std::make_pair(t[0], t[1]));
        edges.insert(std::make_pair(t[1], t[2]));
        edges.insert(std::make_pair(t[2], t[0]));
    }
    for(const auto& t : triangles) {
        edges.erase(std::make_pair(t[1], t[0]));
        edges.erase(std::make_pair(t[2], t[1]));
        edges.erase(std::make_pair(t[0], t[2]));
    }
    for(const auto& t : triangles) {
        if (edges.find(std::make_pair(t[0], t[1])) != edges.end()) {
            neighbors[t[0]] = t[1];
        }
        if (edges.find(std::make_pair(t[1], t[2])) != edges.end()) {
            neighbors[t[1]] = t[2];
        }
        if (edges.find(std::make_pair(t[2], t[0])) != edges.end()) {
            neighbors[t[2]] = t[0];
        }
    }
    std::list<std::list<Vertex>> result;
    while(!neighbors.empty()) {
        std::list<Vertex> contour;
        auto v0 = neighbors.begin()->first;
        auto v = v0;
        while(neighbors.find(v) != neighbors.end()) {
            contour.push_back(v);
            auto old_v = v;
            v = neighbors.at(v);
            neighbors.erase(old_v);
        }
        if (v != v0) {
            throw std::runtime_error("Contour is not closed");
        }
        neighbors.erase(v);
        result.push_back(contour);
    }
    return result;
}

int main() {
    int v00 = 0;
    int v10 = 1;
    int v01 = 2;
    int v11 = 3;
    std::vector<Triangle> v{
        {v00, v10, v11},
        {v00, v11, v01}};
    for(const auto& c : find_contours(v)) {
        for(const auto& v : c) {
            std::cerr << v << " | ";
        }
        std::cerr << std::endl;
    }
    std::cerr << std::endl;
    return 0;
}