4

私が取り組んでいる統計問題では、計算幾何学で「オフライン直交範囲カウント」として知られていることを行う必要があるようです。

n個のポイントのセットがあるとします（今のところ、平面内に）。ポイントiとjのすべてのペアについて、対角線が端点iとjを持つセグメントである長方形にあるセット内の残りのポイントの数を数えたいと思います。全体の出力は、それぞれ[0, 1, 2, ... , n-2]のn(n-1)値のベクトルです。

この問題 (または少なくとも非常に類似した問題) に関する豊富な文献が存在することを見てきましたが、実装が見つかりません。R (統計計算言語) パッケージの方がいいと思いますが、それは多すぎると思います。オープン ソースの C/C++ 実装も機能します。

ありがとう。

4

1 に答える 1

0

あなたの問題をよく理解していることを願っています。ここでは package を使用した R での実装geometryです。 mesh.drectangleポイント p から長方形の境界までの符号付き距離を計算する関数を使用します。

  1. を使用してすべてのポイントの組み合わせを作成しますcombn
  2. 組み合わせの各ポイントpについて、長方形rect_pから他のポイントまでの距離を計算します
  3. 距離 < 0 の場合、ポイントを選択します。

例えば

library(geometry)
## I generate some data 
set.seed(1234)
p.x <- sample(1:100,size=30,replace=T)
p.y <- sample(1:100,size=30,replace=T)
points <- cbind(p.x,p.y)

## the  algortithm
ll <- combn(1:nrow(points),2,function(x){
     x1<- p.x[x[1]]; y1 <- p.y[x[1]]
     x2<- p.x[x[2]]; y2 <- p.y[x[2]]
     p <- points[-x,]
     d <- mesh.drectangle(p,x1,y1,x2,y2)
     res <- NA
     if(length(which(d <0))){
        points.in = as.data.frame(p,ncol=2)[ d < 0 , ]
       res <- list(n = nrow(points.in), 
                    rect = list(x1=x1,x2=x2,y1=y1,y2=y2),
                    points.in = points.in)
     }
     res
},simplify=F)
ll <- ll[!is.na(ll)]

## the result
nn <- do.call(rbind,lapply(ll,'[[','n'))

結果を視覚化するために、たとえば 5 つの点を持つ四角形をプロットします。

ここに画像の説明を入力

library(grid)
grid.newpage()
vp <- plotViewport(xscale = extendrange(p.x),
                          yscale = extendrange(p.y))
pushViewport(vp)
grid.xaxis()   
grid.yaxis()
grid.points(x=points[,'p.x'],y=points[,'p.y'],pch='*')
cols <- rainbow(length(ll))
ll <- ll[nn == 5]           ## here I plot only the rectangle with 5 points 
lapply(seq_along(ll),function(i){
            x <- ll[[i]]
            col <- sample(cols,1)
            x1<- x$rect$x1; x2<- x$rect$x2
            y1<- x$rect$y1; y2<- x$rect$y2
            grid.rect(x=(x1+x2)*.5,y=(y1+y2)*.5,
                      width= x2-x1,height = y2-y1,
                      default.units ='native',
                      gp=gpar(fill=col,col='red',alpha=0.2)
                      )
            grid.points(x=x$points.in$p.x,y=x$points.in$p.y,pch=19,
                        gp=gpar(col=rep(col,x$n))) 

 }
)
upViewport()
于 2013-02-11T03:57:17.377 に答える