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

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;
}