构造多边形的轮廓(特别是三角剖分)

Question

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

从I'm reading over here来看，这似乎正是三角测量问题的逆问题。你知道关于这类问题的文章吗？

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

Answer 1

我猜你的数据是由三个点组成的，它们构成了一个“填充的”三角形，这些三角形是沿着边相连的，并且作为完整形状的角点的所有顶点也是接触到这个点的所有三角形的顶点。然后，您只需找到所有不重复的边，即不属于两个相邻三角形的边。

Answer 2

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

例如:您可以创建一个半边数据结构。假设你在边界上(正确地)插入了半边，那么迭代边界轮廓就像在边界上定位一个半边一样简单，然后迭代它的“下一个”指针，直到你回到开始时的半边。

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

Answer 3

这里是一个在三角形网格上操作的实现，找到并连接所有非双边，也在this answer中解释。

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