凸包算法

R版本

# 导入数据
test<-read.csv(file = file.choose(), header = T, sep = ",")
head(test);names(test)

#朴素版出图-------------------------------------------------------------------------------------
library(grDevices) # load grDevices package
df<-data.frame(X = test[,2], 
               Y = test[,3]) # store X,Y together

con.hull.pos<-chull(df) # find positions of convex hull

con.hull<-rbind(df[con.hull.pos,],df[con.hull.pos[1],]) # get coordinates for convex hull

plot(Y ~ X, data = df, xlim = c(-3, 7), ylim = c(-3, 7)) # plot data

lines(con.hull) # add lines for convex hull


# 图形叠加++++++++++++++++++++++++++++++++++++++++++++++++++++++++
par(new=TRUE) 
df2<-data.frame(X = test[,4], 
                Y = test[,5]) # store X,Y together
con.hull.pos2<-chull(df2) # find positions of convex hull
con.hull2<-rbind(df2[con.hull.pos2,],df2[con.hull.pos2[1],]) # get coordinates for convex hull

plot(Y ~ X, data = df2, xlim = c(-3, 7), ylim = c(-3, 7)) # plot data

lines(con.hull2) # a
# 带边框和颜色========================
dat<-as.data.frame(test); names(dat)

X = test[,1]
Y = test[,2] 

library(grDevices)
#Compute the convex hull. THis returns the index for the X and Y coordinates
c.hull<-chull(dat)

#You need five points to draw four line segments, so we add the fist set of points at the end
c.hull <- c(c.hull, c.hull[1])

#Here's how we get the points back
#Extract the points from the convex hull. Note we are using the row indices again.
dat[c.hull ,]

#Make a pretty plot
with(dat, plot(X,Y))
lines(dat[c.hull ,], col = "pink", lwd = 3)

###Note if you wanted the bounding box
if(!suppressWarnings(require(spatstat)))
{
  install.packages('spatstat')
  require(spatstat)
}
library(spatstat)
box <- bounding.box.xy(dat)
plot(box, add = TRUE, lwd = 3)

#Retrieve bounding box points
with(box, expand.grid(xrange, yrange))

#获得凸包内的点===========
getPerpPoints <- function(mat) {
  # mat: 2x2 matrix with first row corresponding to first point
  #      on the line and second row corresponding to second
  #      point on the line
  #
  # output: two points which define the line going from the side
  #         to the origin
  
  # store the inputs more conveniently
  x <- mat[,1]
  y <- mat[,2]
  
  # define a new matrix to hold the output
  out <- matrix(0, nrow = 2, ncol = 2)
  
  #  handle special case of vertical line
  if(diff(x) == 0) {
    xnew <- x[1]
  }
  else {
    # find point on original line
    xnew <- (diff(y) / diff(x)) * x[1] - y[1]
    xnew <- xnew / (diff(y) / diff(x) + diff(x) / diff(y))
  }
  ynew <- -(diff(x) / diff(y)) * xnew
  
  # put new point in second row of matrix
  out[2,] <- c(xnew, ynew)
  
  return(out = out)
}

for(i in 1:4) {
  lines(getPerpPoints(con.hull[i:(i+1),]))
}
#注意：以上用于二维判断

python版本

# -*- coding: utf-8 -*-
"""
Created on Thu Sep  5 14:50:07 2019

@author: xllix
"""

import numpy as np 
import pandas as pd 
import matplotlib.pyplot as plt 
from sklearn import datasets 

data = datasets.load_iris() 
#create a DataFrame 
df = pd.DataFrame(data.data, columns=data.feature_names) 
df['Target'] = pd.DataFrame(data.target) 
df.head()

plt.clf()
plt.figure(figsize = (10, 6))
names = data.target_namescolors = ['b','r','g']
label = (data.target).astype(np.int)
plt.title('Petal Width vs Petal Length')
plt.xlabel(data.feature_names[2])
plt.ylabel(data.feature_names[3])
for i in range(len(names)): 
    bucket = df[df['Target'] == i] 
    bucket = bucket.iloc[:,[2,3]].values 
    plt.scatter(bucket[:, 0], 
                bucket[:, 1], 
                label=names[i]) 
    plt.legend()
    plt.show() 
    


from scipy.spatial import ConvexHull 
plt.clf()
plt.figure(figsize = (10, 6))
names = data.target_nameslabel = (data.target).astype(np.int)
colors = ['b','r','g']
plt.title('Petal Width vs Petal Length')
plt.xlabel(data.feature_names[2])
plt.ylabel(data.feature_names[3])
for i in range(len(names)): 
    bucket = df[df['Target'] == i] 
    bucket = bucket.iloc[:,[2,3]].values 
    hull = ConvexHull(bucket) 
    plt.scatter(bucket[:, 0], 
                bucket[:, 1], 
                label=names[i]) 
    for j in hull.simplices: 
        plt.plot(bucket[j,0], 
                 bucket[j,1], 
                 colors[i])
        plt.legend()
        plt.show()