Convex Hull

一、凸性质 (Convexity)

1. 引入

1. 颜色混合
   
   我们可以使用几种只包含R，G的颜色来进行混合从而得到第三种颜色，但是第三种颜色是否可以用这几种颜色勾兑，我们只有从数学上进行尝试，下面我们使用代码进行处理。

def cal_porp_two(color1, color2, resultColor):
    for i in range(1, 10):
        for j in range(1, 10):
            if ((color1[0] * i + color2[0] * j) % resultColor[0] == 0 and
                (color1[1] * i + color2[1] * j) % resultColor[1] == 0):
                print("two kind of colors mix proportion: color1", i, ", color2: ", j)


def cal_porp_three(color1, color2, color3, resultColor):
    for i in range(1, 10):
        for j in range(1, 10):
            for k in range(1, 10):
                mixed_color = tuple(map(lambda color1_i, color2_i, color3_i: i * color1_i + j * color2_i + k * color3_i, color1, color2, color3))
                if (mixed_color[0] % resultColor[0] == 0 and
                    mixed_color[1] % resultColor[1] == 0):
                    print("three kind of colors mix proportion: color1", i, ", color2: ", j, ", color3: ", k)


if __name__ == "__main__":
    color1 = (10, 35)
    color2 = (16, 20)
    color3 = (7, 15)
    result_color = (12, 30)
    cal_porp_two(color1, color2, result_color)
    cal_porp_three(color1, color2, color3, (13, 22))

也即是通过穷举混合比例来进行判断我们是否可以通过混合得到第三种颜色，从代码也可以看出这种方法的时间复杂度是非常高的，三种的时间复杂度为，如果要是4种、5种甚至更多呢？

接下来我们可以通过几何的方式来对数据进行解释，来尝试降低时间复杂度

1. 几何解释 (颜色空间)
   

将上述的颜色转换为几何上的坐标，从图上可以看出对于使用两种颜色就可以勾兑出第三种颜色的情况，在几何上第三种颜色必定会在两种颜色之间；对于需要使用三种颜色才能勾兑出的颜色那么勾兑出的颜色也必须在三种颜色组成的三角形内部或者三角形的边上。

通过上述转换，我们就将从三种颜色的随意组合问题转换为了线性问题也就是判断需要勾兑的颜色是否在三角形的内部，就可以得知需要的颜色是否可以被勾兑出来。

另外，我们知道并非每一种颜色都有资格作为颜色空间的”基颜色”而存在的，这个就像我们在笛卡尔坐标系中的解释是一样的，在二维笛卡尔坐标系中的每个点都可以使用两个基向量进行“勾兑”出来，所以在这个颜色混合的问题中我们也要提取出“基颜色”。从笛卡尔坐标系中我们得知基向量都是相互垂直不存在相关关系的一组向量而构成的，所以这里的“基颜色”也是互不相关，也即无法通过组合而得到的颜色而构成的，在凸问题中我们称这种“基颜色”为凸无关，而能够被组合出来的颜色所代表的点我们称之为凸相关。

1. 凸组合 (Covex Combination)
   

这里给出了凸组合的概念。凸组合需要满足两个条件

• 组合系数需要大于等于0
• 组合系数之和等于1

这里无需给出更多的解释，从几何解释中我们就可以理解为什么这样定义。

凸相关的点其实并不被我们在凸的性质中需要，从几何解释中我们可以看到这些点被包裹在凸的内部并不会对我们处理问题给出任何的优势。

二、极点 (Extreme Points)

1. 什么是极点

极点从字面理解也就是一些在边界或者不再有其他点在其前面的点，称为极点。

给出一个形式上的定义

2. 如何判断极点

一个点是否是极点，从形式上理解就是判断这个点是否在两侧都有点，如果都有点，那么这个点就不是极点，因为没有“极性”。

如何判断一个点是否是极点呢？这就需要结合前面我们定义的“凸”的概念了，我们把所有不可被其他点通过各种插值组合出来的点成为凸无关的点，我们把空间用基本图元三角形进行分割，每个三角形将空间分为七份

如果一个点的坐标可以被组合出来，那么这个点就不是极点，结合凸无关的定义我们可以得知，如果一个点落到了一个三角形的内部或者是边上，那么这个点的坐标就是可以组合出来的，比如上图的7，如果不落在三角形的边上和内部而是落在其他的位置例如上图的1~6，那么就是无法被组合出来的，这个也可以通过插值的定义去理解。

如果判断点无法落在给定的任意一个三角形的内部则这个点就是极点。

2.1 In-Triangle Test

三角形测试用于判定一个点在三角形内部还是三角形外部，三角形测试又可被拆分为点相对应于边的位置的测试。如果一个点在三角形的外部那么这个点一定落在三角形三条边所在直线的同一侧，这是一个充要条件，从下图也可以判断出，除了点7以外，其他点相对于三条边一定在同一侧，反之也对。这样理解下来我们首先将整个点集的测试分割为多个三角形的测试再分割为多条边的测试，这就是分治的思想。

接下来，我们将三角形的三个顶点进行逆时针排列或者顺时针排列定义为：A,B,C，待测试点定义为E，我们分别测试E点相对于边AB，边BC,边CA的位置，这个测试叫做to left测试。

我们对于to left测试用的方法是计算由E和三角形的任意两个顶点组成的三角形的有向面积，在这里有一个条件就是三角形的顶点一定要按顺时针或者逆时针和待测试点组成三角形，不然有向面积的方向也不一致。

这里有个小的tip，就是这个行列式的推导方式，我看到了一种比较简单的推导方式与大家共享，我们有一个小前提就是要知道两个向量的叉乘的意义：向量的叉乘求的就是两个向量形成的平行四边形的面积

其中为垂直于和所在平面的法向单位向量，方向由右手定则给出。

对应到平行四边形面积计算公式为

所以，而由、和构成的三角形面积为S的一半。

上述方式是从向量的角度给出的计算方式，还有另外一种从行列式角度给出的叉乘的定义:

• 定义(逆时针向量)

从这个方面推出了行列式的形式，不过是凑出来的，但是好记。

这里还有一个我写的一个随机生成的点的三角形测试，但是没有做优化

三、极边 (Extreme Edges)

在极点的判别算法中，我们先对除了当前点以外的点构造三角形，然后将这个点结合所有三角形进行判别当前点是否为极点，这样我们的时间复杂度为, 在这个构造过程中我们发现，我们判别的过程的最小子问题是判别点和边的关系，判别点是否在三角形的三条边的同侧，如果是则为极点。我们现在反过来想，如果我们现有一条边，然后判别其余的顶点是否在这条边的同一侧是否也能达到相同的目的呢？是的，那这样我们就可以将先构造三角形在判断点是否在三角形三条边的同侧的问题又变为了判断剩余顶点是否在一条边的一边，如果除了当前边的两个顶点外其他顶点都在这条边的一侧，那这条边就是极边，极边上的点也一定为极点。

相比于三角形测试我们消除了计算量，现在我们先找除了待判断点外的所有的边，然后判读点和所有边的关系，所以我们的时间复杂度变为了，从到多出的计算量去哪了，在三角形的重复的边的判断上，两个相邻的三角形公用一条边，而这条边对于所有点会判断两侧，除了最外侧的极边，其余的边每条都会被判断两次，而这个边的数量就是n-1，所以这个n就出现在这里。

理解了极点的判断，极边的判断更简单了，我们先选出一个待检测点，然后用剩余的顶点构造所有的边，将顶点集合中的所有点执行这个过程，即可得到极边。

import random
import math

def calculate_distance(point1, point2):
    square_distance = (point1[0] - point2[0])**2 + (point1[1] - point2[1]) ** 2
    return math.sqrt(square_distance)

# 左侧顶点测试, 测试直线point1-->point2
def to_left_test(point1, point2, point3)-> bool:
    # 叉积刚好是由两个向量所在的平行四边形面积的两倍
    value = point1[0] * (point2[1] - point3[1]) + point2[0] * (point3[1] - point1[1]) + point3[0] * (point1[1] - point2[1])
    if value >= 0:
        return True
    else:
        return False

'''
测试点集和有向线段的关系
'''
def test_line_points(points, line) -> bool:
    side = [False, False]
    for point in points:
        # 如果点为线段的两个顶点之一则跳过
        d1 = calculate_distance(point, line[0])
        d2 = calculate_distance(point, line[1])
        if  d1 < 1e-6 or d2 < 1e-6:
            continue
        
        test_result = to_left_test(line[0], line[1], point)
        if False == test_result:
            side[0] = True
        else:
            side[1] = True
        
        # 有点同时出现在了线段的两侧，所以直接返回False，测试失败
        if side[0] + side[1] == 2:
            return False
        
    return True

x_list = [random.uniform(-10, 10) for i in range(-10, 10)]
y_list = [random.uniform(-10, 10) for i in range(-10, 10)]

for x, y in zip(x_list, y_list):
    print("x: ", x, ", y: ", y)

import matplotlib.pyplot as plt
%matplotlib auto
plt.figure(figsize=(8, 8))
points = tuple(zip(x_list, y_list))
pass_lines = []

plt.ion()
ims = []
for i in range(len(x_list)):
    for j in range(i+1, len(x_list)):
        plt.clf()
        line = \
        [
            [x_list[i], y_list[i]], 
            [x_list[j], y_list[j]]
        ]

        test_result = test_line_points(points, line)
        if True == test_result:
            pass_lines.append(line)
        test_line_points(points, line)
        
        # 绘制每一次的结果
        plt.plot([line[0][0], line[1][0]], [line[0][1], line[1][1]], marker="o")
        
        for line in pass_lines:
            xs = [line[0][0], line[1][0]]
            ys = [line[0][1], line[1][1]]
            plt.plot(xs, ys, marker="o")

        for x, y in zip(x_list, y_list):
            plt.scatter(x, y, marker="o")
        
        plt.pause(0.1)
plt.ioff()
plt.show(block=True)

四、增量构建 (Incremental Construction)

1. 构造的粗略过程

在使用寻找极边的形式构造凸包的方式，我们需要首先查找所有的可能的边，这个过程需要的时间复杂度为，然后使用每一条边都要去查探非边上的顶点是否在边的同一侧，这个过程中也需要。我们再次反转过来想，如果我们不再已边为主，而是以点为主，判断点是否在凸包之上，这里看似我们回到了已寻找极点的方式构造凸包，在寻找极点的方式构造凸包中，我们需要检查顶点是否在任意的三角形内部，这也是需要构造三角形。

如果这里我们先构造一个任意的三角形，但是我们不再多次构造这个三角形，一个三角形在初次构造时相对于自己的顶点集合()必定为凸包，我们再将整个顶点集合()中不在三角形内部的顶点置为待测试的顶点()，我们只需要持续的测试中的顶点是否能够满足凸包的要求，如果满足则将顶点插入到中，不断的进行，直到所有中的顶点测试完成则凸包构造完毕。

2. 测试规则描述

在构造过程中，我们需要测试中的点是否满足凸包的要求，这个测试过程需要结合我们在极点方式和极边方式构造过程中使用的一些功能，例如to_left_test。我们要求所有的顶点都要逆序排列，这个和极边的探测要求是一致的，只有为逆序排列我们才能完成规则测试，规则描述为：

• 所有的顶点需逆序排列，构成凸包顶点序列
• 将每个顶点在逆序排列的序列中的前驱顶点称为pre_point,将后继顶点称为next_point
• 将由待测试点指向当前凸包点的有向射线称为support line
• 将处于support line左边的顶点设置为L，将support line右侧的顶点设置为R
• 对任意一个凸包的顶点的前驱和后继分别做to_left_test，将所得的结果命名为当前凸包顶点的状态，例如前驱为L，后继为R则当前凸包顶点的状态为L+R，
• 将L+R状态的顶点从凸包集合中去除，并将当前顶点插入到凸包中，插入位置为状态为R+R的顶点的下一个位置
• 持续测试待测试顶点

3. 实现算法

from common import (
    in_triangle_test, 
    to_left_test,
    pattern_in_turn,
    colinear_test,
    generate_random_point
    )

import random
import matplotlib.pyplot as plt
import matplotlib

def draw_polyline(center_point, prev_point, next_point, drawer: plt):
    plt.plot([center_point[0], prev_point[0]], [center_point[1], prev_point[1]], color="black", linewidth = 1, label=" previous point test")
    plt.plot([center_point[0], next_point[0]], [center_point[1], next_point[1]], color="black", linewidth = 1, label="next point test")


def draw_convex_polygon(point_set, convex_polygon, drawer: plt):
    for index, point in enumerate(point_set):
        if index not in convex_polygon:
            plt.scatter(point[0], point[1], marker="o", label="test point", color="black") 
        else:
            plt.scatter(point[0], point[1], marker="o", label="test point", color="red") 

    for index in range(len(convex_polygon) - 1):
        point1 = point_set[convex_polygon[index]]
        point2 = point_set[convex_polygon[index+1]]

        plt.plot([point1[0], point2[0]], [point1[1], point2[1]], color="blue", label="convex polygon")
    
    first_point = point_set[convex_polygon[0]]
    last_point = point_set[convex_polygon[-1]]

    plt.plot([first_point[0], last_point[0]], [first_point[1], last_point[1]], color="blue", label="convex polygon")
    

def contruct_convex_polygon(point_set):
    # 1. 随机选择三个不共线的点构成凸包
    
    plt.figure(figsize=(8, 8))
    plt.ion()

    print(f"point set's size: {len(point_set)}")
    # 点的个数小于3，无法构成凸包
    if len(point_set) < 3:
        return

    convex_polygon = [0, 1]

    # 寻找第三个和前两个不共线的点加入到集合中
    for i in range(2, len(point_set)):
        colinear_test_result = colinear_test(
            point_set[convex_polygon[0]],
            point_set[convex_polygon[1]], 
            point_set[i]
            )
        to_left_test_result = to_left_test(
            point_set[convex_polygon[0]],
            point_set[convex_polygon[1]], 
            point_set[i]
        )
        if False == colinear_test_result and True == to_left_test_result:
            print(f"test colinear: index: {i} false")

            convex_polygon.append(i)
            break
        print(f"test colinear: index: {i} true")
    
    print(f"initialized convex polygon: {convex_polygon}\n")

    draw_convex_polygon(point_set, convex_polygon, plt)


    # 待测试列表
    test_list = [ x for x in list(range(0, len(point_set))) if x not in convex_polygon]

    print(test_list)
    for test_index, i in enumerate(test_list):

        test_point = point_set[i]        
        patterns = []
        for index, j in enumerate(convex_polygon):
            plt.clf()
            plt.text(0, 0, f"test point index:{j}", size=15, color="red")
            plt.scatter(test_point[0], test_point[1], s=10, c="red", label="test point")

            current_convex_point = point_set[j]
            pre_point = []
            next_point = []
            # 如果是第一个元素，则前驱点为列表的最后一个点，后继为正常后继点
            print(f"convex polygon: {convex_polygon}")
            if index == 0:
                print(f"previous point index: {convex_polygon[-1]}, next point index: {convex_polygon[index + 1]}")
                pre_point = point_set[convex_polygon[-1]]
                next_point = point_set[convex_polygon[index + 1]]
            # 如果是最后一个元素，则前驱点为正常前驱点，后继为第一个点
            elif index == len(convex_polygon) - 1:
                print(f"previous point index: {convex_polygon[index - 1]}, next point index: {convex_polygon[0]}")
                pre_point = point_set[convex_polygon[index - 1]]
                next_point = point_set[convex_polygon[0]]
            else:
                print(f"previous point index: {j - 1}, next point index: {j + 1}")
                pre_point = point_set[convex_polygon[index - 1]]
                next_point = point_set[convex_polygon[index + 1]]
            draw_polyline(test_point, pre_point, next_point, plt)
            plt.plot([test_point[0], point_set[j][0]], [test_point[1], point_set[j][1]], color="red")
            draw_convex_polygon(point_set, convex_polygon, plt)
            print(f"index: {index}")

            pattern_result = pattern_in_turn(pre_point, next_point, [test_point, current_convex_point])
            style = dict(size=15, color="red")

            # 所有的测试结果
            patterns.append(pattern_result)

            if 3 == pattern_result:
                plt.text(point_set[j][0], point_set[j][1], "L+L", **style)

            elif 0 == pattern_result:
                plt.text(point_set[j][0], point_set[j][1], "R+R", **style)

            elif 1 == pattern_result:
                plt.text(point_set[j][0], point_set[j][1], "R+L", **style)

            else:
                plt.text(point_set[j][0], point_set[j][1], "L+R", **style)
            plt.title("convex polygon construction: incremental construction")
            plt.pause(1)

        remove_list = []
        point_set_T_index = -1
        T_index = -1
        S_index = -1
        for index, pattern in enumerate(patterns):
            if pattern == 0: # T
                point_set_T_index = convex_polygon[index]
                plt.text(point_set[convex_polygon[index]][0], point_set[convex_polygon[index]][1], "T", size=15, color="red")
            elif pattern == 3:
                S_index = index
                plt.text(point_set[convex_polygon[index]][0], point_set[convex_polygon[index]][1], "S", size=15, color="red")
            elif pattern == 2: 
                remove_list.append(convex_polygon[index])
        
        if point_set_T_index != -1:
            convex_polygon = [x for x in convex_polygon if x not in remove_list]
            convex_polygon.insert(convex_polygon.index(point_set_T_index)+1, i)
        
        plt.title("convex polygon construction: incremental construction")
        plt.pause(2)
    
        plt.clf()
        draw_convex_polygon(point_set, convex_polygon, plt)
        plt.title("convex polygon construction: incremental construction")
        plt.pause(1)
    
    

    plt.ioff()

    plt.show()


if __name__ == "__main__":
    point_set = list(zip(*generate_random_point([-3, 3], [-3, 3], 20)))
    """
    point_set = [
        [2, 1],
        [3, 1],
        [2, 2],
        [1, 2]
    ]
    """
    print(f"generated point_set: {point_set}")
    contruct_convex_polygon(point_set)

五、Javis March

六、Lower Bound

七、Graham Scan: Alogrithm

八、Graham Scan: Example

九、Graham Scan: Correctness

十、Graham Scan: Analysis

十一、Divide-And-Conquer

十二、Wrap-up