다각형과 점 사이의 거리를 계산 R

Question

볼록하지 않은 볼록 다각형과 교점이없는 다각형과이 다각형 밖에있는 점이 있습니다. 2 차원 공간에서 유클리드 거리를 가장 효율적으로 계산하는 방법이 궁금합니다. R에 표준 방법이 있습니까?

첫 번째 아이디어는 다각형의 모든 선의 최소 거리를 계산하고 (선 조각이 아닌 선이므로 무한히 확장 한 후) 선의 시작점을 사용하여 점에서 각 개별 선까지의 거리를 계산하는 것이 었습니다 조각과 피타고라스.

효율적인 알고리즘을 구현하는 패키지에 대해 알고 있습니까?

Answer 1

rgeos package 및 gDistance 메서드를 사용할 수 있습니다. 이것은 당신이 가지고있는 데이터로부터 spgeom 오브젝트를 생성하여 지오 메트릭을 준비 할 것을 요구할 것입니다 (나는 그것이 data.frame이거나 이와 비슷한 것으로 가정합니다).

pt1 = readWKT("POINT(0.5 0.5)") 
pt2 = readWKT("POINT(2 2)") 
p1 = readWKT("POLYGON((0 0,1 0,1 1,0 1,0 0))") 
p2 = readWKT("POLYGON((2 0,3 1,4 0,2 0))") 
gDistance(pt1,pt2) 
gDistance(p1,pt1) 
gDistance(p1,pt2) 
gDistance(p1,p2) 

readWKT이뿐만 아니라 rgeos에 포함되어 다음 rgeos 문서이는 gDistance 문서에서 하나의 관련 예입니다,합니다 (CRAN 페이지에서 패키지의 PDF 설명서 참조) 매우 상세한입니다.

Rgeos는 기하학 컴퓨팅의 사실상 표준 중 하나 인 GEOS 라이브러리를 기반으로합니다. 바퀴를 다시 발명하려는 느낌이 들지 않는다면, 이것은 좋은 방법입니다. 그렇지 않으면

Answer 2

:

p2poly <- function(pt, poly){ 
    # Closing the polygon 
    if(!identical(poly[1,],poly[nrow(poly),])){poly<-rbind(poly,poly[1,])} 
    # A simple distance function 
    dis <- function(x0,x1,y0,y1){sqrt((x0-x1)^2 +(y0-y1)^2)} 
    d <- c() # Your distance vector 
    for(i in 1:(nrow(poly)-1)){ 
     ba <- c((pt[1]-poly[i,1]),(pt[2]-poly[i,2])) #Vector BA 
     bc <- c((poly[i+1,1]-poly[i,1]),(poly[i+1,2]-poly[i,2])) #Vector BC 
     dbc <- dis(poly[i+1,1],poly[i,1],poly[i+1,2],poly[i,2]) #Distance BC 
     dp <- (ba[1]*bc[1]+ba[2]*bc[2])/dbc   #Projection of A on BC 
     if(dp<=0){ #If projection is outside of BC on B side 
      d[i] <- dis(pt[1],poly[i,1],pt[2],poly[i,2]) 
      }else if(dp>=dbc){ #If projection is outside of BC on C side 
       d[i] <- dis(poly[i+1,1],pt[1],poly[i+1,2],pt[2]) 
       }else{ #If projection is inside of BC 
        d[i] <- sqrt(abs((ba[1]^2 +ba[2]^2)-dp^2)) 
        } 
     } 
    min(d) 
    } 

예 :

pt <- c(3,2) 
triangle <- matrix(c(1,3,2,3,4,2),byrow=T, nrow=3) 
p2poly(pt,triangle) 
[1] 0.3162278 

Answer 3

난 그냥 후손에 대한 반환 및 이론적 인 솔루션을 쓰기로했다. 이것은 가장 간결한 예가 아니지만 이와 같은 문제를 손으로 해결하는 방법을 알고 자하는 사람들에게는 완전히 투명합니다.

이론적 인 알고리즘

첫째, 우리의 가정.

1. 우리는 다각형의 정점이 시계 방향 또는 반 시계 방향 및 교차 할 수없는 다각형의 라인을가는 회전 순서로 다각형의 점을 지정 가정합니다. 이것은 우리가 정상적인 기하학적 폴리곤을 가지며 이상하게 정의 된 벡터 그래픽 모양이 아니라는 것을 의미합니다.
2. 이것은 2 차원 평면상의 위치를 ​​나타내는 'x'와 'y'값을 사용하여 직교 좌표 집합이라고 가정합니다.
3. 포인트가 다각형의 내부 영역 외부에 있어야한다고 가정합니다.
4. 마지막으로 원하는 거리는 점과 다각형의 경계에있는 무한 수의 모든 점 사이의 최소 거리라고 가정합니다.

코딩하기 전에 우리는 우리가하고 싶은 것을 기본 용어로 써야합니다. 다각형과 꼭지점 사이의 최단 거리는 항상 두 가지 중 하나, 즉 다각형의 꼭지점 또는 두 꼭지점 사이의 선상에있는 점이라고 가정 할 수 있습니다.이를 염두에두고 다음 단계를 수행합니다.

1. 모든 정점과 대상 점 사이의 거리를 계산합니다.
2. 대상 점에 가장 가까운 두 개의 꼭짓점을 찾습니다.
3. 어느 경우 는 (a) 2 개의 가장 인접한 꼭지점에 인접하지 않거나 (b)는 두 벡터 중 내부 각이 크거나 90도 동일하다 다음 가장 가까운 정점 가장 가까운 포인트이다. 가장 가까운 지점과 목표 지점 사이의 거리를 계산하십시오.
4. 그렇지 않으면 두 점 사이에 형성된 삼각형의 높이를 계산하십시오.

기본적으로 정점이 점에 가장 가까이 있는지 또는 선의 한 점이 점에 가장 가까운지를보고 있습니다. 이 작업을 수행하려면 몇 가지 trig 함수를 사용해야합니다. 다각형 정점의 전체 목록을 볼 때

코드

은 우리가 어떤 루프 '에 대한'피하려고 만 벡터화 기능을 사용하려면, 제대로이 일을합니다. 다행히도 이것은 R에서 매우 쉽습니다. 우리는 다각형의 꼭지점에 대해 'x'와 'y'열이있는 데이터 프레임을 허용하며 점의 위치에 'x'와 'y'값이있는 벡터를 허용합니다.

get_Point_Dist_from_Polygon <- function(.polygon, .point){ 

    # Calculate all vertex distances from the target point. 
    vertex_Distance <- sqrt((.point[1] - .polygon$x)^2 + (.point[2] - .polygon$y)^2) 

    # Select two closest vertices. 
    min_1_Index <- which.min(vertex_Distance) 
    min_2_Index <- which.min(vertex_Distance[-min_1_Index]) 

    # Calculate lengths of triangle sides made of 
    # the target point and two closest points. 
    a <- vertex_Distance[min_1_Index] 
    b <- vertex_Distance[min_2_Index] 
    c <- sqrt(diff(.polygon$x[c(min_1_Index, min_2_Index)])^2 + diff(.polygon$y[c(min_1_Index, min_2_Index)])^2) 

    if(abs(min_1_Index - min_2_Index) != 1 | 
     acos((b^2 + c^2 - a^2)/(2*b*c)) >= pi/2 | 
     acos((a^2 + c^2 - b^2)/(2*a*c)) >= pi/2 
     ){ 
     # Step 3 of algorithm. 
     return(vertex_Distance[min_1_Index]) 
    } else { 
     # Step 4 of algorithm. 
     # Here we are using the law of cosines. 
     return(sqrt((a+b-c) * (a-b+c) * (-a+b+c) * (a+b+c))/(2 * c)) 
    } 
} 

데모

polygon <- read.table(text=" 
x, y 
0, 1 
1, 0.8 
2, 1.3 
3, 1.4 
2.5,0.3 
1.5,0.5 
0.5,0.1", header=TRUE, sep=",") 

point <- c(3.2, 4.1) 

get_Point_Dist_from_Polygon(polygon, point) 
# 2.707397 

Answer 4

나는 점을 정점의 좌표 시스템을 제공 할 때를 계산하는데는 distence geosphere 패키지 distm() 기능을 사용했다. 또한 보조 계전기 dis <- function(x0,x1,y0,y1){sqrt((x0-x1)^2 +(y0-y1)^2)} (distm())을 통해 쉽게 교대로 전환 할 수 있습니다.

algo.p2poly <- function(pt, poly){ 
    if(!identical(poly[1,],poly[nrow(poly),])){poly<-rbind(poly,poly[1,])} 
    library(geosphere) 
    n <- nrow(poly) - 1 
    pa <- distm(pt, poly[1:n, ]) 
    pb <- distm(pt, poly[2:(n+1), ]) 
    ab <- diag(distm(poly[1:n, ], poly[2:(n+1), ])) 
    p <- (pa + pb + ab)/2 
    d <- 2 * sqrt(p * (p - pa) * (p - pb) * (p - ab))/ab 
    cosa <- (pa^2 + ab^2 - pb^2)/(2 * pa * ab) 
    cosb <- (pb^2 + ab^2 - pa^2)/(2 * pb * ab) 
    d[which(cosa <= 0)] <- pa[which(cosa <= 0)] 
    d[which(cosb <= 0)] <- pb[which(cosb <= 0)] 
    return(min(d)) 
} 

예 :

poly <- matrix(c(114.33508, 114.33616, 
       114.33551, 114.33824, 
       114.34629, 114.35053, 
       114.35592, 114.35951, 
       114.36275, 114.35340, 
       114.35391, 114.34715, 
       114.34385, 114.34349, 
       114.33896, 114.33917, 
       30.48271, 30.47791, 
       30.47567, 30.47356, 
       30.46876, 30.46851, 
       30.46882, 30.46770, 
       30.47219, 30.47356, 
       30.47499, 30.47673, 
       30.47405, 30.47723, 
       30.47872, 30.48320), 
       byrow = F, nrow = 16) 
pt1 <- c(114.33508, 30.48271) 
pt2 <- c(114.6351, 30.98271) 
algo.p2poly(pt1, poly) 
algo.p2poly(pt2, poly) 

결과 :

> algo.p2poly(pt1, poly) 
[1] 0 
> algo.p2poly(pt2, poly) 
[1] 62399.81