単調増加観測の凸包を描く・多列のソートも

• 2次元平面に単調増加な観測点があるとする
• 事情があって、この点を結んだ折れ線には垂直な部分と水平な部分とが、それなりに頻発しているものとする
• まずはそのような点を適当に作ってみる

Np<-20
x<-runif(Np)
y<-runif(Np)

Ndup<-10
x<-c(x,sample(x,Ndup,replace=TRUE))
y<-c(y,sample(y,Ndup,replace=TRUE))
x<-sort(x)
y<-sort(y)
plot(x,y,type="b")

• ここで凸包を描くとする
• こちらにあるように、ある点から、他の点への直線の傾きに着目すると凸包が得られるから

# 関数内でreshapeパッケージのsort_df()関数を使う
# ソート済みのデータのときはよいが、そうなっていないかもしれないから
# xもyも昇順に並べるため
library(reshape)
ConvexROC<-function(x,y){
	ord<-sort_df(data.frame(X=x,Y=y),c("X","Y"))
	X<-ord$X
	Y<-ord$Y
	xs<-c(X[1])
	ys<-c(Y[1])
	cnt<-1
	Max<-length(X)
	while(cnt<Max){
		g<-(Y[(cnt+1):Max]-ys[length(ys)])/(X[(cnt+1):Max]-xs[length(xs)])
		maxid<-which(g==max(g))
		cnt<-maxid[length(maxid)]+cnt
		xs<-c(xs,X[cnt])
		ys<-c(ys,Y[cnt])
	}
	list(X=xs,Y=ys)
}
convex.hull<-ConvexROC(x,y)

plot(x,y,type="b")
par(new=TRUE)
plot(convex.hull$X,convex.hull$Y,type="l",col=2)