Python凸包问题：蛮力算法实现与边界条件处理

陆景行

发布时间：2026-10-13 | 6人浏览过

原创

本文详细介绍使用Python解决平面点集凸包问题的蛮力算法。通过排除法确定凸包顶点，利用直线方程判断点与三角形的位置关系。文章提供了完整的伪代码逻辑、Python实现细节，并重点分析了垂直线、共线等特殊情况下的边界处理，确保算法在密集坐标点下的准确性。

Python凸包算法学习背景

近期在阅读Python算法相关书籍，此前购买的教材一直利用工作间隙学习。虽然内容具有一定难度，且部分代码风格较为炫技、注释不易理解，但通过结合网络资源解决书中涉及的算法问题，是一种有效的学习方式。

以下是凸包问题的具体代码实现示例。


# -*- coding: utf-8 -*-
import turtle
import random
import time
f=open('point.txt','w')
for i in range(100):
 x=random.randrange(-250,250,10)
 y=random.randrange(-200,200,10)
 f.write(str(x)+','+str(y)+'\n')
f.close()
point=[]
 
f=open('point.txt')
for i in f:
 try:
  temp=i.split(',')
  x=float(temp[0]); y=float(temp[1])
  point.append((x,y))
 except :
  print 'a err'
f.close()
 
point=list(set(point))#去除重复的点
 
n=0
for i in range(len(point)):
 if point[n][1]>point[i][1]:
  n=i
 
p0=point[n]
point.pop(n)
def compare(a,b):
 x=[a[0]-p0[0],a[1]-p0[1]]
 y=[b[0]-p0[0],b[1]-p0[1]]
 dx=(x[0]**2+x[1]**2)**0.5
 dy=(y[0]**2+y[1]**2)**0.5
 cosa=x[0]/dx
 cosb=y[0]/dy
 if cosa < cosb:
  return 1
 elif cosa > cosb:
  return -1
 else:
  if dx<dy:
   return -1
  elif dx>dy:
   return 1
  else:
   return 0
 
point.sort(compare)
point.insert(0,p0)
ep=point[:]#复制元素，操作ep不会对point产生影响
tag=0
while tag==0:
 tag=1
 l=len(ep)
 for i in range(l):
  i1,i2,i3=(i,(i+1)%l,(i+2)%l)
  x,y,z=(ep[i1],ep[i2],ep[i3])
  a1,a2=((y[0]-x[0],y[1]-x[1]),(z[0]-y[0],z[1]-y[1]))
  if a1[0]*a2[1]-a1[1]*a2[0] < 0:
   tag=0
   ep.pop(i2)
   break
  elif a1[0]*a2[1]-a1[1]*a2[0]==0 and a1[0]*a2[0]<0:
   #==0应改写,360度的情况
   tag=0
   ep.pop(i2)
   break
 
 
def drawpoint(point,color,line):
 p=turtle.getturtle()
 p.hideturtle()
 turtle.delay(1)
 if(line=='p'):
  p.speed(0)
  for i in point:
   p.pu()
   p.color(color)
   p.goto(i)
   p.pd()
   p.dot()
 elif(line=='l'):
  p.pu()
  p.speed(1)
  for i in point:
   p.color(color)
   p.goto(i)
   p.pd()
   p.dot()
  p.goto(point[0])
 
drawpoint(point,'black','p')
drawpoint(ep,'red','l')
time.sleep(1)

蛮力算法原理与几何判定

补充知识：凸包问题的蛮力算法及Python实现

蛮力法的基本思想是先通过排除法确定凸包的顶点，随后按逆时针顺序输出这些顶点。在判断点P是否为凸包顶点时，依据以下性质：

给定平面点集S，若P、Pi、Pj、Pk是S中四个不同的点，且P位于由Pi、Pj、Pk构成的三角形内部或边界上，则P不是S的凸包顶点。

如何判断点P是否在三角形内部或边界上？对于平面上的两点A和B，若直线方程g(A,B,P)=0，则P位于直线上；若g(A,B,P)>0或g(A,B,P)<0，则P分别位于直线的两侧。

判断点P是否在三角形内部或边界上，只需依次检查P与三角形的每个顶点是否位于由三角形另外两个顶点确定的直线的同一侧，即判断以下条件：

t1=g(pj,pk,p)*g(pj,pk,pi)>=0 , t2=g(pi,pk,p)*g(pi,pk,pj)>=0, t3=g(pj,pi,p)*g(pj,pi,pk)>=0

是否同时成立。

算法伪代码与流程

凸包问题的蛮力算法伪代码如下：

BruteForce(S)：

输入：平面n个点的集合S

输出：按逆时针顺序输出S的凸包的所有顶点

If n=3 Then 以逆时针顺序输出S的顶点，算法结束找到S中纵坐标最小的点P，该点一定位于凸包上

For S中任意三点Pi,Pj,Pk Do If Pi,Pj,Pk 一点位于其他两点与P构成的三角形内 Then 删除该点

找出S中横坐标最小的点A和横坐标最小的点B

将S划分问直线AB上方点集SU,直线AB下方点集SL，A,B两点属于SL

将SL按横坐标递增排序，SU按横坐标递减排序顺序输出SL,SU

首先随机生成点集S

Python代码实现与可视化


import random
import itertools

def generate_num(n):
  random_list = list(itertools.product(range(1, 100), range(1, 100)))
  lists=random.sample(random_list, n)
  return lists

边界条件与特殊情况处理

判断点P在三角形内部或边界上，即判断点P是否在凸包上

在具体的判断过程中，尤其时坐标点比较密集的情况下，还有有三种比较特殊的情况

组成直线的两点垂直于x轴

除点P外其余三点在一条直线上时，不应删除点P，因为此时点P可能时凸包上的点

除点P外其余三点在一条直线上且垂直于x轴时，不应删除点P，因为此时点P可能时凸包上的点

核心判定函数实现


#判断pi是否位于pj,pk,p0组成三角形内，返回t1,t2,t3三个变量
def isin(pi,pj,pk,p0):
 x1 = float(p0[0])
 x2 = float(pj[0])
 x3 = float(pi[0])
 x4 = float(pk[0])
 y1 = float(p0[1])
 y2 = float(pj[1])
 y3 = float(pi[1])
 y4 = float(pk[1])

 k_j0=0
 b_j0=0
 k_k0=0
 b_k0=0
 k_jk=0
 b_jk=0
 perpendicular1=False
 perpendicular2 = False
 perpendicular3 = False
 #pj,p0组成的直线，看pi,pk是否位于直线同一侧

 if x2 - x1 == 0:
 #pj,p0组成直线垂直于X轴时
  t1=(x3-x2)*(x4-x2)
  perpendicular1=True
 else:
  k_j0 = (y2 - y1) / (x2 - x1)
  b_j0 = y1 - k_j0 * x1
  t1 = (k_j0 * x3 - y3 + b_j0) * (k_j0 * x4 - y4 + b_j0)

 #pk,p0组成的直线，看pi,pj是否位于直线同一侧

 if x4 - x1 == 0:
 #pk,p0组成直线垂直于X轴时
  t2=(x3-x1)*(x2-x1)
  perpendicular2=True
 else:
  k_k0 = (y4 - y1) / (x4 - x1)
  b_k0 = y1 - k_k0 * x1
  t2 = (k_k0 * x3 - y3 + b_k0) * (k_k0 * x2 - y2 + b_k0)

 # pj,pk组成的直线，看pi,p0是否位于直线同一侧

 if x4 - x2 == 0:
 # pj,pk组成直线垂直于X轴时
  t3=(x3-x2)*(x1-x2)
  perpendicular3 = True
 else:
  k_jk = (y4 - y2) / (x4 - x2)
  b_jk = y2 - k_jk * x2
  t3 = (k_jk * x3 - y3 + b_jk) * (k_jk * x1 - y1 + b_jk)
 #如果pk，p0,pj，三点位于同一直线时，不能将点删除
 if (k_j0 * x4 - y4 + b_j0)==0 and (k_k0 * x2 - y2 + b_k0)==0 and (k_jk * x1 - y1 + b_jk)==0 :
   t1=-1
 #如果pk，p0,pj，三点位于同一直线时且垂直于X轴，不能将点删除
 if perpendicular1 and perpendicular2 and perpendicular3:
   t1=-1

 return t1,t2,t3

接下来是实现算法主要部分，用来找出凸包上的点

凸包集合构建逻辑


import isintriangle

def force(lis,n):
 #集合S中点个数为3时，集合本身即为凸包集
 if n==3:
  return lis
 else:
  #集合按纵坐标排序，找出y最小的点p0
  lis.sort(key=lambda x: x[1])
  p0=lis[0]
  #除去p0的其余点集合lis_brute
  lis_brute=lis[1:]
  #temp是用来存放集合需要删除的点在lis_brute内的索引，四个点中如果有一个点在其余三个点组成的三角形内部，则该点一定不是凸包上的点
  temp=[]
  #三重循环找到所有这样在三角形内的点
  for i in range(len(lis_brute)-2):
   pi=lis_brute[i]
   #如果索引i已经在temp中，即pi一定不是凸包上的点，跳过这次循环
   if i in temp:
    continue
   for j in range(i+1,len(lis_brute) - 1):
    pj=lis_brute[j]
    #如果索引j已经在temp中，即pj一定不是凸包上的点，跳过这次循环
    if j in temp:
     continue
    for k in range(j + 1, len(lis_brute)):
     pk=lis_brute[k]

     #如果索引k已经在temp中，即pk一定不是凸包上的点，跳过这次循环
     if k in temp:
      continue
     #判断pi是否在pj,pk,p0构成的三角形内
     (it1,it2,it3)=isintriangle.isin(pi,pj,pk,p0)
     if it1>=0 and it2>=0 and it3>=0:
      if i not in temp:
       temp.append(i) 
     # 判断pj是否在pi,pk,p0构成的三角形内
     (jt1,jt2,jt3)=isintriangle.isin(pj,pi,pk,p0)
     if jt1>=0 and jt2>=0 and jt3>=0:

      if j not in temp:
       temp.append(j)

     # 判断pk是否在pj,pi,p0构成的三角形内
     (kt1, kt2, kt3) = isintriangle.isin(pk, pi, pj, p0)
     if kt1 >= 0 and kt2 >= 0 and kt3 >= 0:

      if k not in temp:
       temp.append(k)
  #listlast是最终选出的凸包集合
  lislast=[]
  for coor in lis_brute:
   loc = [i for i, x in enumerate(lis_brute) if x == coor]
   for x in loc:
    ploc = x
   if ploc not in temp:
    lislast.append(coor)
  #将p0加入凸包集合
  lislast.append(p0)
  return lislast

最后将凸包集合输出就不多说了，按照伪码上实现就可以，凸包蛮力算法在点集大小为1000时结果