多角形領域の内外判定

crossing_number_algorithm.R

#https://www.nttpc.co.jp/technology/number_algorithm.html
cn <- function(polygon, point) {
  cn <- 0
  n <- nrow(polygon)
  for (i in 1:(n - 1)) {
    y0 <- polygon$y[i]
    y1 <- polygon$y[i + 1]
    x0 <- polygon$x[i]
    x1 <- polygon$x[i + 1]
    # ルール1（上向きの辺）
    cond1 <- (y0 <= point$y) && (y1 > point$y)
    # ルール2（下向きの辺）
    cond2 <- (y0 > point$y) && (y1 <= point$y)
    if (cond1 || cond2) {
      # 辺が点と同じ高さになる位置
      vt <- (point$y - y0) / (y1 - y0)
      x_cross <- x0 + vt * (x1 - x0)
      if (point$x < x_cross) {
        cn <- cn + 1
      }
    }
  }
  cn
}


Is_inside <- function(polygon,pos){
  cn(polygon, point) %% 2L == 1L
}


df_v <- data.frame(
  x = c(1:9, 8:1),
  y = c(1, 2*(5:3), 2, -1, 17, 9, 8, 2:9)
  )

point <- locator(1)

plot(range(polygon$x), range(polygon$y), type = "n")
polygon(polygon$x, polygon$y, col = "orange", lty = 2, lwd = 2, border = "red")
segments(x0 = point$x, y0 = point$y, x1 = max(x), y1 = point$y, lty=2)

cn(polygon, point)
Is_inside(polygon, pos)