10 - 多边形的三角剖分 - 单调划分

1. 相关概念

• 单调多边形链：
  
  点集 $P = \{P_0, P_1, P_2, P_3, P_4, P_5, P_6\}$ 在某条直线 L 上的投影分别为 $P' = \{P_0', P_1', P_2', P_3', P_4', P_5', P_6'\}$ ，若对应投影的次序没有改变，则可以说 该多边形链相对于直线 L 是单调的 。

_

• 单调多边形：
  单调多边形由两条单调多边形链组成（两条单调多边形链都是相对于同一条直线单调），

2. 算法思路

2.1 将单调多边形三角剖分

1. 对顶点依据 Y 坐标进行排序，即使用一条水平扫描线对点集进行扫描

   • 整个单调多边形是由两条单调多边形链组成，只需要对两条链进行 merge - $O(n)$

2. 对已经扫描过的但暂时还未进行处理的点，可以使用一个栈存储起来，此时我们定义三种点

   • C ：current vertex，当前正在扫描的点
   • T ：the top，当前栈顶的点
   • N ：the vertex next to the top vertex，栈顶的点下一个点

3. 显然，会需要以下的一致性：

   • 栈中存储的点必须为同一条单调多边形链上的，即在多边形上是同一侧的
   • 所有的点按照高度进行的排序（依据 Y 坐标进行排序的情况下）
   • 栈中所存的点，任意相邻的三点对应的内角必然是大于 180° 的，即是凹的
   • 待扫描的点 C 只会有以下两种情况
     • 与栈顶的点 T 直接相连（与栈中元素同链）
     • 与栈底的点 bottom 直接相连（与栈中元素异链）

4. 依据三种点的位置关系，分为三种情况：

   • 同链凹关系（SameSide + Reflex）：点 C 与点 T 和 N 同链，且 T 是凹的
     • 将点 C 压入栈中，继续扫描

   

   • 同链凸关系（SameSide + Convex）：点 C 与点 T 和 N 同链，且 T 是凸的

     • 将 $\vartriangle CTN$ 切除，将凸点 T 弹出，此时点 N 变成了点 T；
     • 同时，继续对栈进行遍历，若栈顶的点依然为凸点，就继续切除三角形；
     • 直到栈顶点 T 为一个凹点，或者栈中的元素只有 1，遍历停止；
     • 结束时，把扫描点 C 压入栈中，扫描继续。

     T = S.top;
     
     while( T == Convex && S.size() >= 2)
     {
         ChopOffTriangle(C, T, N);
     
         T = S.pop();
     }
     
     S.push(C);

     

   • 异链关系（OppositeSide）：点 C 与点 T 和 N 异链

     • 将 $\vartriangle CTN$ 切除，将凸点 T 弹出，此时点 N 变成了点 T；
     • 此时的遍历过程中，栈顶的点 T 必定都是凸的，可以直接逐步切除，直到栈中元素的数量小于2；
     • 结束时，将扫描点 C 和开始遍历时的栈顶元素 stT 压入栈中，扫描继续。

     T = S.top;
     
     // 将当前的 T 存储起来
     stT = T;
     
     while(S.size() >= 2)
     {
         ChopOffTriangle(C, T, N);
     
         T = S.pop();
     }
     
     // 此时栈中剩下的一个元素为 bottom ，将其弹出，弹出后栈空
     S.pop();
     
     // 将开始时的栈顶元素 tempT 与 C 压入栈中
     S.push(stT);
     S.push(C);

     
     NOTE：显然，在切之前，点 stT 与点 C 是异链的；而在将三角形全部切除之后，二者变成了同链。

2.1.1 EXAMPLE

N	T	C	State	OUT	Stack
$P_0$	$P_1$		init		$P_0$, $P_1$
$P_0$	$P_1$	$P_2$	SameSide + Reflex		$P_0$, $P_1$, $P_2$
$P_1$	$P_2$	$P_3$	SameSide + Reflex		$P_0$, $P_1$, $P_2$, $P_3$
$P_2$	$P_3$	$P_4$	SameSide + Convex <1>	{$P_2$ , $P_3$ , $P_4$}	$P_0$, $P_1$, $P_2$, ($P_3$)
$P_1$	$P_2$	$P_4$	SameSide + Convex <2>	{$P_1$ , $P_2$ , $P_4$}	$P_0$, $P_1$, ($P_2$)
$P_0$	$P_1$	$P_4$	SameSide + Convex <end>		$P_0$, $P_1$, $P_4$
$P_1$	$P_4$	$P_5$	OppositeSide <1>	{$P_1$ , $P_4$ , $P_5$}	$P_0$, $P_1$, ($\stackrel{stT}{P_4}$)
$P_0$	$P_1$	$P_5$	OppositeSide <2>	{$P_0$ , $P_1$ , $P_5$}	$P_0$, ($P_1$)
	$P_0$	$P_5$	OppositeSide <end>		$\stackrel{stT}{P_4}$, $P_5$
$P_4$	$P_5$	$P_6$	SameSide + Convex <1>	{$P_4$ , $P_5$ , $P_6$}	$P_4$, ($P_5$)
	$P_4$	$P_6$	SameSide + Convex <end>		$P_4$, $P_6$
$P_4$	$P_6$	$P_7$	OppositeSide <1>	{$P_4$ , $P_6$ , $P_7$}	$P_4$, ($\stackrel{stT}{P_6}$)
	$P_4$	$P_7$	OppositeSide <end>		$\stackrel{stT}{P_6}$, $P_7$
$P_6$	$P_7$	$P_8$	SameSide + Convex <1>	{$P_6$ , $P_7$ , $P_8$}	$P_6$, ($P_7$)
	$P_6$	$P_8$	SameSide + Convex <end>		$P_6$, $P_8$
$P_6$	$P_8$	$P_9$	OppositeSide <1>	{$P_6$ , $P_8$ , $P_9$}	$P_6$, ($\stackrel{stT}{P_8}$)
	$P_6$	$P_9$	OppositeSide <end>		$\stackrel{stT}{P_8}$, $P_9$
$P_8$	$P_9$	$P_{10}$	END	{$P_8$ , $P_9$ , $P_{10}$}

2.2 时间复杂度 $O(n \cdot logn)$

• 单调多边形的三角划分 - $O(n)$
  1. 扫描线扫点排序：一个单调多边形是由两条单调链组成，每条单调链上的点已经依据Y坐标（以扫描线为水平线为例）进行了排序，而对整个单调多边形的端点进行排序时，只需要将这两条链进行 Merge 操作，这一过程为 $O(n)$
  2. 栈操作：每个端点最多只会进行两次压栈操作，显然这部分操作也不会超过线性时间，即 $O(n)$
     • C：
     • T：
  3. 三角剖分：n 个端点的多边形，最终会切成 (n-2) 个三角形，每次切割为 $O(1)$

3. 示例代码

3.1 MonotonePartitioningAlgorithm 类

3.1.1 三角剖分

public static ArrayList<Triangle> triangulate(Polygon p) {

    // 将多边形分成若干个单调多边形
    ArrayList<Polygon> monotonePartitioning = makeMonotone(p);
    
    ArrayList<Triangle> res = new ArrayList<Triangle>();
    
    // 对每个单调多边形进行三角剖分，然后将获得的三角形集合进行合并
    for (Polygon m : monotonePartitioning) {
        res.addAll(triangulateMonotonePolygon(m));
    }
    
    return res;
}

3.1.2 使单调

public static ArrayList<Diagonal> makeMonotone(Polygon p) {
    
    // 算法需要逆时针方向
    p.makeCounterClockwise();
    
    // 构造优先级队列，对顶点进行排序
    PriorityQueue<Vertex> Q = new PriorityQueue<Vertex>
                                (p.size(), new VertexComparator());
    for (int i = 0; i < p.size(); i++) {
        Q.add(new Vertex(p, i));
    }
    
    // 初始化二叉树
    TreeMap<Integer, Edge> T = new TreeMap<Integer, Edge>();
    
    // 按对角线分割
    ArrayList<Diagonal> D = new ArrayList<Diagonal>();
    
    // 处理顶点
    while (! Q.isEmpty()) {
        try {
            handleVertex(Q.poll(), T, D);
        } catch(Exception e) {
            System.out.print("!");
        }
    }
    
    return D;
}

3.1.3 对单调多边形进行三角剖分

private static ArrayList<Triangle> triangulateMonotonePolygon(Polygon p) {
    
}

3.1.4 处理顶点

private static void handleVertex(Vertex v_i, TreeMap<Integer, Edge> T, ArrayList<Diagonal> D) {
    
    int i = v_i.getIndex();
    int i_1 = (i == 0) ? (v_i.getPolygon().size()-1) : (i-1);
    
    Edge e_i, e_j, e_i_1, temp;
    Vertex helper_e_i_1, helper_e_j;
    
    switch (v_i.getVertexType()) {
        
        case START:
            e_i = new Edge(v_i.getPolygon(), i);
            e_i.setHelper(v_i);
            T.put(i, e_i);
            
            break;
            
        case END:
            
            e_i_1 = T.get(i_1);
            
            helper_e_i_1 = e_i_1.getHelper();
            if (helper_e_i_1.getVertexType() == VertexType.MERGE) {
                D.add(new Diagonal(i, helper_e_i_1.getIndex()));
            }
            
            //T.remove(i_1);
            
            break;
            
        case SPLIT:
            e_j = null;
            // TODO: Improve to O(log(n))!
            for (int j : T.keySet()) {
                temp = T.get(j);
                if (temp.intersectsWithSweepLine(v_i.getY()) &&
                        temp.liesOnTheLeftSideof(v_i)) {
                    if (e_j == null) {
                        e_j = temp;
                    } else if (temp.liesOnTheRightSideof(e_j, v_i.getY())) {
                        e_j = temp;
                    }
                }
            }
            
            D.add(new Diagonal(i, e_j.getHelper().getIndex()));
            
            e_j.setHelper(v_i);
            
            e_i = new Edge(v_i.getPolygon(), i);
            T.put(i, e_i);
            e_i.setHelper(v_i);
            
            break;
            
        case MERGE:
            
            e_i_1 = T.get(i_1);
            helper_e_i_1 = e_i_1.getHelper();
            
            if (helper_e_i_1.getVertexType() == VertexType.MERGE) {
                D.add(new Diagonal(i, helper_e_i_1.getIndex()));
            }
            
            //T.remove(i_1);
            
            e_j = null;
            // TODO: Improve to O(log(n))!
            for (int j : T.keySet()) {
                temp = T.get(j);
                if (temp.intersectsWithSweepLine(v_i.getY()) &&
                        temp.liesOnTheLeftSideof(v_i)) {
                    if (e_j == null) {
                        e_j = temp;
                    } else if (temp.liesOnTheRightSideof(e_j, v_i.getY())) {
                        e_j = temp;
                    }
                }
            }
            
            helper_e_j = e_j.getHelper();
            
            if (helper_e_j.getVertexType() == VertexType.MERGE) {
                D.add(new Diagonal(i, helper_e_j.getIndex()));
            }
            
            e_j.setHelper(v_i);                
            
            break;
            
        case REGULAR:
            
            if (v_i.polygonInteriorLiesToTheRight()) {
                
                e_i_1 = T.get(i_1);
                helper_e_i_1 = e_i_1.getHelper();

                if (helper_e_i_1.getVertexType() == VertexType.MERGE) {
                    D.add(new Diagonal(i, helper_e_i_1.getIndex()));
                }
                
                //T.remove(i_1);
                
                e_i = new Edge(v_i.getPolygon(), i);
                T.put(i, e_i);
                e_i.setHelper(v_i);
                
            } else {
                
                e_j = null;
                // TODO: Improve to O(log(n))!
                for (int j : T.keySet()) {
                    temp = T.get(j);
                    if (temp.intersectsWithSweepLine(v_i.getY()) &&
                        temp.liesOnTheLeftSideof(v_i)) {
                        if (e_j == null) {
                            e_j = temp;
                        } else if (temp.liesOnTheRightSideof(e_j, v_i.getY())) {
                            e_j = temp;
                        }
                    }
                }
                
                helper_e_j = e_j.getHelper();
            
                if (helper_e_j.getVertexType() == VertexType.MERGE) {
                    D.add(new Diagonal(i, helper_e_j.getIndex()));
                }

                e_j.setHelper(v_i); 
            }
            
            break;
    }
}

3.2 顶点类型

枚 举	含 义
START	开始
END	结束
REGULAR	通常
SPLIT	分裂
MERGE	合并

static enum VertexType {
    START,
    END,
    REGULAR,
    SPLIT,
    MERGE
}

3.3 内部静态类

3.3.1 Vertex 类

• 顶点类

成 员	含 义
polygon	该顶点所在多边形的多边形编号
index	该顶点在多边形中的顶点编号

static class Vertex {
    
    public Vertex(Polygon p, int i) {
        polygon = p;
        index = i;
    }
    
    public int getIndex() {
        return index;
    }
    
    public double getX() {
        return polygon.get(index).getX();
    }
    
    public double getY() {
        return polygon.get(index).getY();
    }
    
    public Polygon getPolygon() {
        return polygon;
    }
    
    // 获得顶点类型
    public VertexType getVertexType() {
        
        Point pCur = polygon.get(index);
        Point pPrev = polygon.get((index - 1 + polygon.size()) % polygon.size());
        Point pNext = polygon.get((index + 1) % polygon.size());
        
        if (pPrev.getY() < pCur.getY() &&
                pNext.getY() < pCur.getY()) {
            if (polygon.isConvex(index)) {
                return VertexType.START;
            } else {
                return VertexType.SPLIT;
            }
        } else if (pPrev.getY() > pCur.getY() &&
                    pNext.getY() > pCur.getY()) {
            if (polygon.isConvex(index)) {
                return VertexType.END;
            } else {
                return VertexType.MERGE;
            }
        } else {
            return VertexType.REGULAR;
        }
    }

    // 多边形内部向右
    public boolean polygonInteriorLiesToTheRight() {
        
        Point pCur = polygon.get(index);
        Point pPrev = polygon.get((index - 1 + polygon.size()) % polygon.size());
        Point pNext = polygon.get((index + 1) % polygon.size());
        
        // pPrev -> pCur -> pNext
        // pPrev.Y > pCur.Y > pNext.Y
        if (pPrev.getY() > pCur.getY() &&
                pNext.getY() < pCur.getY()) {
            return true;
        } else {
            return false;
        }
    }
    
    private Polygon polygon;
    private int index;
}

• (pPrev.Y < pCur.Y) && (pNext.Y < pCur.Y)
  • 若点 pCur 为凸点 : START（开始）
  • 若点 pCur 为凹点 : SPLIT（分裂）
• (pPrev.Y > pCur.Y) && (pNext.Y > pCur.Y)
  • 若点 pCur 为凸点 : END（结束）
  • 若点 pCur 为凹点 : MERGE（合并）
• ELSE
  • REGULAR（通常）

3.3.2 Edge 类

成 员	含 义
polygon	该顶点所在多边形的多边形编号
index	该边在多边形中的边编号 <index , index + 1>

static class Edge {
    
    public Edge(Polygon p, int i) {
        polygon = p;
        index = i;
    }
    
    public void setHelper(Vertex v) {
        helper = v;
    }
    
    public Vertex getHelper() {
        return helper;
    }
    
    public int getIndex() {
        return index;
    }
    
    public Vertex getA() {
        return new Vertex(polygon, index);
    }
    
    public Vertex getB() {
        return new Vertex(polygon, (index+1)%polygon.size());
    }
    
    // 是否与扫描线相交
    public boolean intersectsWithSweepLine(double sweepY) {
        return (sweepY >= getA().getY() && sweepY <= getB().getY()) ||
                (sweepY >= getB().getY() && sweepY <= getA().getY());
    }
    
    // 返回直线
    public Line getLine() {
        return new Line(polygon.get(index), polygon.get((index+1)%polygon.size()));
    }
    
    // 该边 this 是否在传入边 e 的右侧
    public boolean liesOnTheRightSideof(Edge e, double Y) {
        return this.getLine().XforY(Y) > e.getLine().XforY(Y);
    }
    
    // 该边 this 是否在传入点 v 的右侧
    public boolean liesOnTheLeftSideof(Vertex v) {
        return this.getLine().XforY(v.getY()) < v.getX();
    }
    
    private Polygon polygon;        
    private Vertex helper;
    private int index;
}

3.3.3 Diagonal 类

对角线

static class Diagonal {
    
    public Diagonal(int i1, int i2) {
        index1 = i1;
        index2 = i2;
    }
    
    public int getA() {
        return index1;
    }
    
    public int getB() {
        return index2;
    }
    
    int index1, index2;
}

3.3.4 VertexComparator 类

定义端点 Vertex 之间的比较规则：

• 先依据 Y 坐标进行比较
• 若 Y 坐标相等
  • 依据 X 坐标进行比较

static class VertexComparator implements Comparator<Vertex> {

    @Override
    public int compare(Vertex v1, Vertex v2) {

        if (v1.getY() > v2.getY() ||
                v1.getY() == v2.getY() &&
                v1.getX() > v2.getX())
            return -1;
        
        else return 1;
    }
}

参考资料

视频参考示例：B站_计算几何_邓俊辉_单调多边形划分