[toc]

# 几何数据结构

先讨论最简单的多边形数据结构
就是对每个边建立两个顶点间的双向链表

#pragma once 
#include "../Base/Vector.h"
#include "Point.h"

#include <list>
#include <vector>

template<class T,size_t dim>
struct Vertex {
    jmk::Vector<T, dim> point;
    Vertex* next;
    Vertex* prev;

    Vertex(jmk::Vector<T, dim>& _point, Vertex<T, dim>* _next, Vertex<T, dim>* _prev)
    :point(_point), next(_next), prev(_prev),
    {

    }
};

typedef Vertex<float, DIM2> Vertex2d;
typedef Vertex<float, DIM3> Vertex3d;

template<class T,size_t dim = DIM3>
class Polygon {
    std::vector<Vertex<T, dim>*> vertext_list;
public:
    Polygon(std::list<jmk::Vector<T, dim>>& points) {
        const int size = points.size();

        if (size < 3) {
            std::cout << "Not enough points to construct a polygon";
            return;
        }

        //1. 将顶点加入到定点列表
        for (auto _point : points) {
            vertext_list.push_back(new Vertex(_point));
        }

        //2. 每个顶点连接到下一个顶点(双向链表)
        for (size_t i = 0; i < size; ++i) {
            vertext_list[i].next = &vertext_list[(i + 1) % size];

            if (i != 0) {
                vertext_list[i].prev = &vertext_list[i - 1];
            }
            else {
                vertext_list[i].prev = &vertext_list[size - 1];
            }
        }
    }

    std::vector<Vertex<T, dim>*> getVertices() {
        return vertext_list;
    }
};

typedef Polygon<float, DIM3> PolygonS3d;
typedef Polygon<float, DIM2> PolygonS2d;

# Ear Clipping

# Ear Test

Check whether the vertext from a Converx angle (检查是否一个点是来自于凸角)
Line connecting two neighboring vertices hsould be a diagonal (链接相邻的两个顶点出现的边应该是 diagonal 的)

其中 diagonal 是这样的，其中，AE 是 diagpnal 的，AC 不是，DC 也不是 (是否在多边形内部):

仅仅检测连线是否与多边形的边相交是不足以判断这条连线是 diagonal 的，在此基础上，还需要判断这条边在多边形内部

Diagonal Check 总结

首先 连线不能和其他任意边相交

如果开始连线的顶点是一个 convex vertex , 那么其两个邻居顶点应该位于连线的两侧

如果连线开始的顶点是一个 reflex vertex , 那么连线应该位于多边形内部

Convex vertex: 凸顶点是指在凸多边形或凸曲线上的顶点。在凸多边形中，凸顶点是多边形的角的顶点，其内角小于 180 度。凸顶点的特点是无论从该顶点出发画出的任何一条直线，都不会与多边形的边界相交或内部相交。凸顶点对于描述和分析凸多边形的形状和性质非常重要。相反，非凸多边形具有凹顶点，其内角大于 180 度，从该顶点出发画出的直线会与多边形的边界或内部相交。 reflex vertex：凸多边形中内角大于 180° 的顶点

# 实现

完整实现

bool jmk::isDiagonal(const Vertex2d* v1, const Vertex2d* v2, PolygonS2d* poly) {
    bool prospect = true;
    std::vector<Vertex2d*> vertices;

    //先获得所有顶点
    if (poly)
        vertices = poly->getVertices();
    else {
        auto vertex_ptr = v1->next;
        vertices.push_back((Vertex2d*)v1);
        while (vertex_ptr != v1) {
            vertices.push_back(vertex_ptr);
            vertex_ptr = vertex_ptr->next;
        }
    }
    //遍历所有的点,判断是否有线和当前v1v2构成的线相交,有就相交测试失败 
    Vertex2d* current, * next;
    current = vertices[0];
    do {
        next = current->next;
        if (current != v1 && next != v1 && current != v2 && next != v2
            && jmk::Intersection(v1->point, v2->point, current->point, next->point)) {
            prospect = false;
            break;
        }
        current = next;
    } while (current != vertices[0]);
    return prospect && interiorCheck(v1,v2) && interiorCheck(v2,v1);
}

其中 Intersection 函数实现如下，其中 orientation2d 函数实现的是判断 c 点和 a->b 向量的关系 (根据数值求面积 (叉积) 的正负来判断)

bool jmk::Intersection(const jmk::Point2d& a, const jmk::Point2d& b, const jmk::Point2d& c,
    const jmk::Point2d& d) {
    auto ab_c = jmk::orientation2d(a, b, c);
    auto ab_d = jmk::orientation2d(a, b, d);
    auto cd_a = jmk::orientation2d(c, d, a);
    auto cd_b = jmk::orientation2d(c, d, b);

    if (ab_c == BETWEEN  ab_c == ORIGIN  ab_c == DESTINATION
         ab_d == BETWEEN  ab_d == ORIGIN  ab_d == DESTINATION
         cd_a == BETWEEN  cd_a == ORIGIN  cd_a == DESTINATION
         cd_b == BETWEEN  cd_b == ORIGIN  cd_b == DESTINATION) {
        return true;
    }

    return _xor(ab_c == LEFT, ab_d == LEFT) && _xor(cd_a == LEFT, cd_b == LEFT);
}

//a在bc的哪侧
int jmk::orientation2d(const Point2d& a, const Point2d& b, const Point2d& c) {
    auto area = areaTriangle2d(a, b, c);
    if (area > 0 && area < TOLERENCE) 
        area = 0;
    if (area < 0 && area > TOLERENCE)
        area = 0;

    Vector2f ab = b - a;
    Vector2f ac = c - a;

    if (area > 0)
        return LEFT;

    if (area < 0)
        return RIGHT;

    if ((ab[X] * ac[X] < 0)  (ab[Y] * ac[Y] < 0)) {
        return BEHIND;
    }

    if (ab.magnitude() < ac.magnitude()) {
        return BEYOND;
    }

    if (a == c)
        return ORIGIN;
    if (b == c)
        return DESTINATION;


    return BETWEEN;
}

在 isDiagnoal 函数的中间，是对 v1v2 构成的边进行整个多边形的相交检测，如果通过了，再使用 interiorCheck 函数来检查是否满足 Ear Test 其中 interiorCheck 函数的具体实现如下，即检查 v2 是否通过 v1 的 EarTest , 且 v1 也要通过 v2 的 Ear Test

/// <summary>
/// 检查v2v1是否在v1的三个邻接点组成的角的内部
/// </summary>
/// <param name="v1"></param>
/// <param name="v2"></param>
/// <returns></returns>
bool jmk::interiorCheck(const Vertex2d* v1, const Vertex2d* v2) {
    //判定v1是否是convex或者relex顶点,vPrev在v1VNext的哪侧
    if (jmk::leftOrBeyond(v1->point, v1->next->point, v1->prev->point)) {
        //左侧,检测是否是convex,性质: 位于v1v2连线的两侧
        //v1 is convex vertex
        return jmk::left(v1->point, v2->point, v1->prev->point)
            && jmk::left(v2->point, v1->point,v1->next->point);
    }
    //是凹角,则判断是否在relex条件下满足在多边形内部
    //不满足(取反结果):  
    //    1. 检查v1Next是否位于v1->v2 左侧
    //    2. 同时v1Prev位于v1->v2左侧时,不满足relex条件下在多边形内部的条件
    //v1 is relex vertex
    return !(jmk::leftOrBeyond(v1->point, v2->point, v1->next->point)
        && jmk::leftOrBeyond(v2->point, v1->point, v1->prev->point));
}

以 v1 为 start vertex 举例
算法的思路就是根据 v1 是 convex 角还是 relex 角来选择不同的测试方法，
1. 如果是 convex 角，则只需要判断 v1 相邻的两个点是否在 v1v2 向量的不同侧
2. 如果是 relex 角，则取反判断，即判断是否满足 v1v2 不在多边形内部，如果不通过，就代表 v1v2 在多边形内部，通过测试

如上图，判定在 v1 位 relex 角的前提下，v2 在多边形外部 isDiagonal 函数在相交测试、耳测试全通过后才能表明 v2v1 是一条 diagonal(耳边?)

# 耳裁减三角化

伪代码

1. 初始化耳状态  
while(直到只有三个顶点为止){
    2. 选择一个点并且找到一个在两个邻接点之间的diagonal 
    3. 移除选中的点
    4. 更新邻接顶点的耳状态
}

对应的代码如下:

#include "Triangulation.h"
using namespace jmk;

static void initialize_ear_status(PolygonS2d* polygon) {
    Vertex2d* v0, * v1, * v2;
    auto vertices = polygon->getVertices();
    v1 = vertices[0];

    do {
        v0 = v1->prev;
        v2 = v1->next;
        v1->is_ear = isDiagonal(v0, v2);
        v1 = v1->next;
    } while (v1 != vertices[0]);
}

void Triangulate_earclipping(PolygonS2d* poly, std::vector<Edge2d>& edge_list) {
    initialize_ear_status(poly);
    auto vertex_list = poly->getVertices();
    int no_vertex_to_process = vertex_list.size();

    Vertex2d* v0, * v1, * v2, * v3, * v4;

    while (no_vertex_to_process > 3) {
        for (size_t i = 0; i < vertex_list.size(); ++i) {
            v2 - vertex_list[i];
            if (v2->is_ear && !v2->is_processed) {
                v3 = v2->next;
                v4 = v3->next;
                v1 = v2->prev;
                v0 = v1->prev;

                edge_list.push_back(Edge2d(*v1, *v3));
                v2->is_processed = true;

                v1->next = v3;
                v3->prev = v1;

                v1->is_ear = isDiagonal(v0, v3, nullptr);
                v3->is_ear = isDiagonal(v1, v4, nullptr);

                no_vertex_to_process--;
                if (no_vertex_to_process <= 3)
                    break;
            }
        }

    }
}

# 几何数据结构

# Ear Clipping

# Ear Test

# 实现

# 耳裁减三角化

【计算几何】 Art Gallery theorem

【计算几何】 Mesh的图化存储结构 - DCEL(Double Connect Edge List)