当前位置:   article > 正文

凸包算法(高级算法设计与分析实验1)_给n个点求凸包

给n个点求凸包

凸包问题

求解凸包问题:输入是平面上n个点的集合Q,凸包问题是要输出一个Q的凸包。其中,Q的凸包是一个凸多边形P,Q中的点或者在P上或者在P中。

实现基于枚举方法的凸包求解算法

提示:考虑Q中的任意四个点A、B、C、D,如果A处于BCD构成的三角形内部,那么A一定不属于凸包P的顶点集合。

这一方法属于暴力解法,任意枚举点集中的四个点,如果有一个点在其他三个点构成的三角形内部,则将这个点从点集中剔除。实验主要是通过python来实现的,先定义一个平面点类。代码自动生成二维平面[0,0]到[100,100]的数据集,四重循环逐一进行判断。列举关键代码如下:

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y  
        self.angle=0
  • 1
  • 2
  • 3
  • 4
  • 5
'
运行
from Point import Point
import random
import matplotlib.pyplot as plt

#判断p4是否在p1,p2,p3构成的三角形中
def istriangle(a,b,c,p):

    signOfTrig = (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
    signOfAB = (b.x - a.x)*(p.y - a.y) - (b.y - a.y)*(p.x - a.x);
    signOfCA = (a.x - c.x)*(p.y - c.y) - (a.y - c.y)*(p.x - c.x);
    signOfBC = (c.x - b.x)*(p.y - b.y) - (c.y - b.y)*(p.x - b.x);

    d1 = (signOfAB * signOfTrig > 0)
    d2 = (signOfCA * signOfTrig > 0)
    d3 = (signOfBC * signOfTrig > 0)

    return d1 and d2 and d3

def generate_data(size,data,data_o):
    for i in range(size):
        #x=random.randint(0,100)
        #y=random.randint(0,100)
        x=random.uniform(0,100)
        y=random.uniform(0,100)
        p=Point(x,y)
        data_o.append(p)
    return data,data_o

def d(A,B,P):
     ans=(B.x - A.x)*(P.y - A.y) - (B.y - A.y)*(P.x - A.x)
     return ans

def BruteForceCH(size,data,data_o):
    
    L=[]
    R=[]
    flag = [0 for x in range(size)]

    for i in range(size-3):
        if flag[i]==1:
            continue
        for j in range(i+1,size-2):
            if flag[j]==1:
                continue
            for k in range(j+1,size-1):
                if flag[k]==1:
                    continue
                for l in range(k+1,size):
                    if flag[l]==1:
                        continue
                    elif istriangle(data_o[i],data_o[j],data_o[k],data_o[l]):
                        flag[l]=1
                        continue
                    elif istriangle(data_o[l],data_o[j],data_o[k],data_o[i]):
                        flag[i]=1
                        continue
                    elif istriangle(data_o[i],data_o[l],data_o[k],data_o[j]):
                        flag[j]=1
                        continue
                    elif istriangle(data_o[i],data_o[j],data_o[l],data_o[k]):
                        flag[k]=1
    for i in range(size):
        if flag[i]==0:
            data.append(data_o[i])
    data=sorted(data,key = lambda point: (point.x,point.y))

    A=data[0]
    B=data[-1]
    del data[0]
    del data[-1]
    for P in data:
        if(d(A,B,P)>0):
            L.append(P)
        elif(d(A,B,P)<0):
            R.append(P)
    Lr=L.reverse()
    
   # '''
    for p in data_o:
        plt.scatter(p.x, p.y, c='g', marker='.')

    plt.scatter(A.x, A.y, c='r', marker='.')
    plt.plot([A.x,R[0].x],[A.y,R[0].y], color='r')
    for i in range(len(R)-1):
        plt.scatter(R[i].x, R[i].y, c='r', marker='.')
        plt.plot([R[i].x,R[i+1].x],[R[i].y,R[i+1].y], color='r')
    plt.scatter(R[-1].x, R[-1].y, c='r', marker='.')
    plt.plot([R[-1].x,B.x],[R[-1].y,B.y], color='r')
    plt.scatter(B.x, B.y, c='r', marker='.')
    plt.plot([B.x,L[0].x],[B.y,L[0].y], color='r')
    for i in range(len(L)-1):
        plt.scatter(L[i].x, L[i].y, c='r', marker='.')
        plt.plot([L[i].x,L[i+1].x],[L[i].y,L[i+1].y], color='r')
    plt.scatter(L[-1].x, L[-1].y, c='r', marker='.')
    plt.plot([L[-1].x,A.x],[L[-1].y,A.y], color='r')
    plt.show()
   # '''
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97

实现基于Graham-Scan的凸包求解算法

在这里插入图片描述具体实现方法就是,先找到点集中纵坐标最小的点,再此基础上再找横坐标最小的点,把这个点作为基点,这里需要遍历一遍点集,需要 O ( n ) O(n) O(n)的时间复杂度。之后再遍历一遍点集,计算每个点与基点的逆时针角度,按照逆时针角度对点集进行排序,这里需要 O ( n l o g n ) O(nlogn) O(nlogn)的时间开销。之后依次按照逆时针方向计算是否为凸包。

from Point import Point
import random
import matplotlib.pyplot as plt
import math

def generate_data(size,data):
    for i in range(size):
        #x=random.randint(0,100)
        #y=random.randint(0,100)
        x=random.uniform(0,100)
        y=random.uniform(0,100)
        p=Point(x,y)
        data.append(p)
    return data
def judge(a,b,c):
    ans=(c.x - a.x)*(b.y - a.y) - (c.y - a.y)*(b.x - a.x)
    if ans>=0:
        return True
    else:
        return False
def GrahamScanCH(size,data):
    p0=Point(101,101)
    for p in data:
        if p.y<p0.y:
            p0=p
        elif p.y==p0.y and p.x<p0.x:
            p0=p
    data.remove(p0)
    for p in data:
        if p.x==p0.x:
            p.angle=math.pi/2
        elif p.x>p0.x:
            p.angle=math.atan((p.y-p0.y)/(p.x-p0.x))
        else:
            p.angle=math.atan((p0.x-p.x)/(p.y-p0.y))+math.pi/2
    data=sorted(data,key = lambda point: (point.angle))
    stack=[]
    stack.append(p0)
    stack.append(data[0])
    stack.append(data[1])
    for i in range(2,len(data)):
        while judge(stack[-2],stack[-1],data[i]):
            stack.pop(-1)
        stack.append(data[i])
    #'''
    plt.scatter(p0.x,p0.y,c='g',marker='.')
    for p in data:
        plt.scatter(p.x, p.y, c='g', marker='.')
    for i in range(len(stack)-1):
        plt.scatter(stack[i].x, stack[i].y, c='r', marker='.')
        plt.plot([stack[i].x,stack[i+1].x],[stack[i].y,stack[i+1].y], color='r')
    plt.scatter(stack[-1].x, stack[-1].y, c='r', marker='.')
    plt.plot([stack[-1].x,p0.x],[stack[-1].y,p0.y], color='r')
    plt.show()
    #'''
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55

实现基于分治思想的凸包求解算法

分治算法主要是解决如何划分和合并的问题,划分采用方法是选择点集中横坐标的中位数,小于中位数的点集和大于中位数的点集分别进行子问题的计算。划分至点集小于等于三个点。合并的过程是基于Graham-Scan算法。

from Point import Point
import random
import matplotlib.pyplot as plt
import math

def generate_data(size,data):
    for i in range(size):
        #x=random.randint(0,10)
        #y=random.randint(0,10)
        x=random.uniform(0,100)
        y=random.uniform(0,100)
        p=Point(x,y)
        data.append(p)
    return data

def judge(a,b,c):
    ans=(c.x - a.x)*(b.y - a.y) - (c.y - a.y)*(b.x - a.x)
    if ans>=0:
        return True
    else:
        return False

def divide(data):
    maxn=-1
    minn=101
    data1=[]
    data2=[]
    for p in data:
        if p.x<minn:
            minn=p.x
        if p.x>maxn:
            maxn=p.x
    minddle=(maxn+minn)/2
    for p in data:
        if p.x<=minddle:
            data1.append(p)
        else:
            data2.append(p)
    return data1,data2


def conquer(data1,data2):
    if len(data1)==0:
        return data2
    if len(data2)==0:
        return data1
    #求纵坐标最小的点
    if data1[0].y<=data2[0].y:
        p0=data1[0]
        data1.remove(p0)
        flag=1
    else:
        p0=data2[0]
        data2.remove(p0)
        flag=0
    #计算每一个点相对于p0的极角
    p0.angle=0
    for p in data1:
        if p.x==p0.x:
            p.angle=math.pi/2
        elif p.x>p0.x:
            p.angle=math.atan((p.y-p0.y)/(p.x-p0.x))
        else:
            p.angle=math.atan((p0.x-p.x)/(p.y-p0.y))+math.pi/2
    for p in data2:
        if p.x==p0.x:
            p.angle=math.pi/2
        elif p.x>p0.x:
            p.angle=math.atan((p.y-p0.y)/(p.x-p0.x))
        else:
            p.angle=math.atan((p0.x-p.x)/(p.y-p0.y))+math.pi/2
    #利用data1和data2逆时针排序的特点,在线性时间内将所有点按极角大小排好序
    min1=10
    max1=-1
    min2=10
    max2=-1
    if flag==0:
        minindex=-1
        maxindex=-1
        for i in range(len(data1)):
            if(data1[i].angle>max1):
               max1=data1[i].angle
               maxindex=i
            if(data1[i].angle<min1):
               min1=data1[i].angle
               minindex=i
        if minindex<=maxindex:
            data3=data1[minindex:maxindex+1]
            data4=[]
            if minindex!=0:
                data4=data4+data1[minindex-1::-1]
            if maxindex!=len(data1)-1:
                data4=data4+data1[-1:maxindex:-1]
        else:
            data3=data1[minindex:maxindex:-1]
            data4=[]
            data4=data4+data1[minindex+1:]
            data4=data4+data1[0:maxindex+1]
        data5=[]
        i=0
        j=0
        while i<len(data3) and j<len(data4):
            if data3[i].angle<=data4[j].angle:
                data5.append(data3[i])
                i=i+1
            else:
                data5.append(data4[j])
                j=j+1
        while i<len(data3):
            data5.append(data3[i])
            i=i+1
        while j<len(data4):
            data5.append(data4[j])
            j=j+1
        data6=[]
        i=0
        j=0
        while i<len(data2) and j<len(data5):
            if data2[i].angle<=data5[j].angle:
                data6.append(data2[i])
                i=i+1
            else:
                data6.append(data5[j])
                j=j+1
        while i<len(data2):
            data6.append(data2[i])
            i=i+1
        while j<len(data5):
            data6.append(data5[j])
            j=j+1
    else:
        maxindex=-1
        minindex=-1
        for i in range(len(data2)):
            if(data2[i].angle>max2):
               max2=data2[i].angle
               maxindex=i
            if(data2[i].angle<min2):
               min2=data2[i].angle
               minindex=i
        if minindex<=maxindex:
            data3=data2[minindex:maxindex+1]
            data4=[]
            if minindex!=0:
                data4=data4+data2[minindex-1::-1]
            if maxindex!=len(data2)-1:
                data4=data4+data2[-1:maxindex:-1]
        else:
            data3=data2[minindex:maxindex:-1]
            data4=[]
            data4=data4+data2[minindex+1:]
            data4=data4+data2[0:maxindex+1]
        data5=[]

        i=0
        j=0
        while i<len(data3) and j<len(data4):
            if data3[i].angle<=data4[j].angle:
                data5.append(data3[i])
                i=i+1
            else:
                data5.append(data4[j])
                j=j+1
        while i<len(data3):
            data5.append(data3[i])
            i=i+1
        while j<len(data4):
            data5.append(data4[j])
            j=j+1
        data6=[]
        i=0
        j=0
        while i<len(data1) and j<len(data5):
            if data1[i].angle<=data5[j].angle:
                data6.append(data1[i])
                i=i+1
            else:
                data6.append(data5[j])
                j=j+1
        while i<len(data1):
            data6.append(data1[i])
            i=i+1
        while j<len(data5):
            data6.append(data5[j])
            j=j+1
    #洗牌,生成新的凸包
    if len(data6)<=1:
        return [p0]+data6
    stack=[]
    stack.append(p0)
    stack.append(data6[0])
    stack.append(data6[1])
    if len(data6)==2:
        return stack
    for i in range(2,len(data6)):
        while judge(stack[-2],stack[-1],data6[i]):
            stack.pop(-1)
        stack.append(data6[i])
    return stack

def divide_and_conquer(data):
    if len(data)<=1:
        return data
    if len(data)==2:
        return sorted(data,key = lambda point: (point.y,point.x))
    elif len(data)==3:
        p0=Point(101,101)
        for p in data:
            if p.y<p0.y:
                p0=p
            elif p.y==p0.y and p.x<p0.x:
                p0=p
        data.remove(p0)
        for p in data:
            if p.x==p0.x:
                p.angle=math.pi/2
            elif p.x>p0.x:
                p.angle=math.atan((p.y-p0.y)/(p.x-p0.x))
            else:
                p.angle=math.atan((p0.x-p.x)/(p.y-p0.y))+math.pi/2
        res=[]
        res.append(p0)
        if data[0].angle<=data[1].angle:
            res.append(data[0])
            res.append(data[1])
        else:
            res.append(data[1])
            res.append(data[0])
        return res
    data1,data2=divide(data)
    data1=divide_and_conquer(data1)
    data2=divide_and_conquer(data2)
    data=conquer(data1,data2)
    return data

def DivideCH(size,data):

    
    
    #plt.show()
    stack=divide_and_conquer(data)
   
    #'''
    for p in data:
        plt.scatter(p.x, p.y, c='g', marker='.')
    for i in range(len(stack)-1):
        plt.scatter(stack[i].x, stack[i].y, c='r', marker='.')
        plt.plot([stack[i].x,stack[i+1].x],[stack[i].y,stack[i+1].y], color='r')
    plt.scatter(stack[-1].x, stack[-1].y, c='r', marker='.')
    plt.plot([stack[-1].x,stack[0].x],[stack[-1].y,stack[0].y], color='r')
    plt.show()
    #'''
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230
  • 231
  • 232
  • 233
  • 234
  • 235
  • 236
  • 237
  • 238
  • 239
  • 240
  • 241
  • 242
  • 243
  • 244
  • 245
  • 246
  • 247
  • 248
  • 249
  • 250
  • 251
  • 252

算法实现效果:
在这里插入图片描述

声明:本文内容由网友自发贡献,转载请注明出处:【wpsshop】
推荐阅读
相关标签
  

闽ICP备14008679号