Как найти самый длинный аккорд перпендикулярно максимальному аккорду через многоугольник

Question

У меня неправильные многоугольники, определенные набором точек.Я могу найти максимальное местоположение и длину аккорда, но я не совсем уверен, как анализировать точки, чтобы найти самое длинное местоположение и длину аккорда, перпендикулярную максимальному аккорду.

Вот что ядо сих пор, некоторые примеры данных точек для определения многоугольника:

points_ex <- structure(list(V1 = c(68L, 67L, 66L, 66L, 65L, 65L, 64L, 63L, 
                                   62L, 61L, 61L, 60L, 59L, 58L, 57L, 56L, 56L, 55L, 55L, 55L, 55L, 
                                   54L, 54L, 54L, 54L, 54L, 54L, 54L, 53L, 53L, 53L, 52L, 52L, 52L, 
                                   51L, 51L, 50L, 50L, 49L, 49L, 49L, 48L, 48L, 47L, 47L, 46L, 46L, 
                                   45L, 45L, 45L, 44L, 44L, 44L, 44L, 44L, 44L, 44L, 43L, 43L, 42L, 
                                   42L, 41L, 41L, 41L, 41L, 40L, 40L, 40L, 40L, 40L, 40L, 39L, 39L, 
                                   38L, 38L, 38L, 38L, 37L, 37L, 36L, 36L, 36L, 35L, 35L, 35L, 35L, 
                                   35L, 34L, 34L, 34L, 33L, 33L, 33L, 32L, 32L, 32L, 32L, 32L, 32L, 
                                   32L, 32L, 32L, 32L, 32L, 32L, 32L, 32L, 32L, 32L, 32L, 32L, 32L, 
                                   32L, 32L, 32L, 32L, 32L, 32L, 32L, 32L, 32L, 32L, 32L, 33L, 33L, 
                                   33L, 33L, 33L, 33L, 33L, 33L, 33L, 33L, 33L, 33L, 33L, 33L, 33L, 
                                   33L, 33L, 32L, 32L, 32L, 32L, 32L, 32L, 32L, 31L, 31L, 31L, 31L, 
                                   31L, 31L, 31L, 31L, 31L, 31L, 31L, 31L, 31L, 31L, 31L, 31L, 31L, 
                                   30L, 30L, 30L, 30L, 30L, 30L, 30L, 30L, 30L, 30L, 30L, 30L, 30L, 
                                   30L, 30L, 30L, 30L, 30L, 30L, 30L, 30L, 30L, 30L, 30L, 31L, 31L, 
                                   31L, 31L, 31L, 31L, 31L, 31L, 31L, 31L, 31L, 31L, 31L, 31L, 31L, 
                                   31L, 31L, 31L, 31L, 31L, 31L, 31L, 31L, 31L, 32L, 32L, 33L, 33L, 
                                   34L, 34L, 35L, 36L, 36L, 37L, 38L, 39L, 40L, 41L, 42L, 43L, 43L, 
                                   44L, 44L, 45L, 46L, 46L, 47L, 47L, 48L, 48L, 49L, 49L, 50L, 51L, 
                                   51L, 51L, 52L, 52L, 52L, 52L, 53L, 53L, 53L, 53L, 54L, 54L, 54L, 
                                   54L, 54L, 54L, 54L, 53L, 53L, 53L, 53L, 53L, 53L, 52L, 52L, 52L, 
                                   51L, 51L, 51L, 51L, 51L, 51L, 51L, 51L, 52L, 52L, 52L, 52L, 52L, 
                                   53L, 53L, 54L, 54L, 55L, 55L, 56L, 57L, 58L, 59L, 60L, 61L, 62L, 
                                   63L, 64L, 65L, 66L, 67L, 68L, 69L, 70L, 71L, 72L, 73L, 74L, 75L, 
                                   76L, 77L, 78L, 79L, 80L, 81L, 82L, 83L, 84L, 84L, 85L, 85L, 86L, 
                                   86L, 86L, 87L, 87L, 88L, 88L, 88L, 89L, 89L, 90L, 90L, 91L, 91L, 
                                   92L, 93L, 94L, 95L, 96L, 97L, 98L, 99L, 100L, 101L, 102L, 103L, 
                                   104L, 105L, 105L, 106L, 106L, 107L, 108L, 109L, 109L, 110L, 111L, 
                                   112L, 113L, 114L, 115L, 116L, 117L, 118L, 118L, 119L, 120L, 121L, 
                                   122L, 123L, 123L, 124L, 125L, 126L, 126L, 127L, 127L, 127L, 127L, 
                                   127L, 128L, 128L, 128L, 128L, 128L, 128L, 128L, 128L, 128L, 129L, 
                                   129L, 129L, 129L, 129L, 129L, 130L, 130L, 130L, 130L, 131L, 131L, 
                                   131L, 131L, 131L, 132L, 132L, 132L, 132L, 132L, 133L, 133L, 133L, 
                                   133L, 133L, 133L, 133L, 132L, 132L, 132L, 131L, 131L, 130L, 130L, 
                                   129L, 129L, 128L, 128L, 128L, 128L, 128L, 128L, 128L, 128L, 128L, 
                                   129L, 129L, 129L, 129L, 129L, 129L, 129L, 129L, 129L, 129L, 128L, 
                                   127L, 126L, 125L, 125L, 124L, 123L, 123L, 122L, 121L, 120L, 120L, 
                                   119L, 119L, 118L, 117L, 117L, 116L, 115L, 115L, 115L, 114L, 114L, 
                                   113L, 113L, 112L, 111L, 111L, 110L, 110L, 109L, 109L, 109L, 109L, 
                                   108L, 108L, 108L, 108L, 107L, 107L, 107L, 107L, 106L, 106L, 106L, 
                                   106L, 105L, 105L, 105L, 105L, 104L, 104L, 104L, 104L, 103L, 103L, 
                                   103L, 103L, 103L, 102L, 102L, 102L, 102L, 102L, 102L, 102L, 102L, 
                                   102L, 102L, 102L, 102L, 101L, 101L, 101L, 101L, 101L, 101L, 101L, 
                                   100L, 100L, 100L, 100L, 100L, 100L, 100L, 99L, 99L, 99L, 99L, 
                                   99L, 98L, 98L, 98L, 98L, 98L, 98L, 98L, 98L, 98L, 98L, 97L, 97L, 
                                   97L, 97L, 97L, 97L, 96L, 96L, 96L, 96L, 96L, 96L, 96L, 96L, 96L, 
                                   96L, 95L, 95L, 95L, 95L, 95L, 95L, 95L, 95L, 95L, 95L, 95L, 95L, 
                                   94L, 94L, 94L, 94L, 93L, 93L, 92L, 92L, 91L, 90L, 90L, 89L, 89L, 
                                   89L, 88L, 88L, 88L, 88L, 88L, 87L, 87L, 87L, 86L, 86L, 86L, 85L, 
                                   84L, 83L, 82L, 81L, 80L, 79L, 78L, 77L, 76L, 75L, 74L, 73L, 72L, 
                                   71L, 70L, 69L), V2 = c(20L, 21L, 22L, 23L, 24L, 25L, 26L, 27L, 
                                                          28L, 29L, 30L, 31L, 32L, 33L, 34L, 35L, 36L, 37L, 38L, 39L, 40L, 
                                                          41L, 42L, 43L, 44L, 45L, 46L, 47L, 48L, 49L, 50L, 51L, 52L, 53L, 
                                                          54L, 55L, 56L, 57L, 58L, 59L, 60L, 61L, 62L, 63L, 64L, 65L, 66L, 
                                                          67L, 68L, 69L, 70L, 71L, 72L, 73L, 74L, 75L, 76L, 77L, 78L, 79L, 
                                                          80L, 81L, 82L, 83L, 84L, 85L, 86L, 87L, 88L, 89L, 90L, 91L, 92L, 
                                                          93L, 94L, 95L, 96L, 97L, 98L, 99L, 100L, 101L, 102L, 103L, 104L, 
                                                          105L, 106L, 107L, 108L, 109L, 110L, 111L, 112L, 113L, 114L, 115L, 
                                                          116L, 117L, 118L, 119L, 120L, 121L, 122L, 123L, 124L, 125L, 126L, 
                                                          127L, 128L, 129L, 130L, 131L, 132L, 133L, 134L, 135L, 136L, 137L, 
                                                          138L, 139L, 140L, 141L, 142L, 143L, 144L, 145L, 146L, 147L, 148L, 
                                                          149L, 150L, 151L, 152L, 153L, 154L, 155L, 156L, 157L, 158L, 159L, 
                                                          160L, 161L, 162L, 163L, 164L, 165L, 166L, 167L, 168L, 169L, 170L, 
                                                          171L, 172L, 173L, 174L, 175L, 176L, 177L, 178L, 179L, 180L, 181L, 
                                                          182L, 183L, 184L, 185L, 186L, 187L, 188L, 189L, 190L, 191L, 192L, 
                                                          193L, 194L, 195L, 196L, 197L, 198L, 199L, 200L, 201L, 202L, 203L, 
                                                          204L, 205L, 206L, 207L, 208L, 209L, 210L, 211L, 212L, 213L, 214L, 
                                                          215L, 216L, 217L, 218L, 219L, 220L, 221L, 222L, 223L, 224L, 225L, 
                                                          226L, 227L, 228L, 229L, 230L, 231L, 232L, 233L, 234L, 235L, 236L, 
                                                          237L, 238L, 239L, 240L, 241L, 242L, 243L, 244L, 245L, 246L, 247L, 
                                                          248L, 249L, 250L, 251L, 252L, 253L, 254L, 255L, 256L, 257L, 258L, 
                                                          259L, 260L, 261L, 262L, 263L, 264L, 265L, 266L, 267L, 268L, 269L, 
                                                          270L, 271L, 272L, 273L, 274L, 275L, 276L, 277L, 278L, 279L, 280L, 
                                                          281L, 282L, 283L, 284L, 285L, 286L, 287L, 288L, 289L, 290L, 291L, 
                                                          292L, 293L, 294L, 295L, 296L, 297L, 298L, 299L, 300L, 301L, 302L, 
                                                          303L, 304L, 305L, 306L, 307L, 308L, 308L, 308L, 309L, 309L, 309L, 
                                                          310L, 310L, 310L, 311L, 311L, 312L, 312L, 312L, 312L, 312L, 312L, 
                                                          312L, 311L, 311L, 310L, 310L, 310L, 310L, 309L, 308L, 307L, 306L, 
                                                          305L, 304L, 303L, 302L, 301L, 300L, 299L, 298L, 297L, 296L, 295L, 
                                                          294L, 293L, 292L, 291L, 290L, 289L, 288L, 287L, 286L, 285L, 284L, 
                                                          283L, 282L, 281L, 280L, 279L, 279L, 278L, 277L, 276L, 275L, 274L, 
                                                          273L, 272L, 271L, 270L, 269L, 268L, 267L, 266L, 265L, 264L, 263L, 
                                                          262L, 261L, 260L, 259L, 258L, 257L, 256L, 255L, 254L, 253L, 252L, 
                                                          252L, 251L, 250L, 249L, 248L, 247L, 246L, 245L, 244L, 243L, 242L, 
                                                          241L, 240L, 239L, 238L, 237L, 236L, 235L, 234L, 233L, 232L, 231L, 
                                                          230L, 229L, 228L, 227L, 226L, 225L, 224L, 223L, 222L, 221L, 220L, 
                                                          219L, 218L, 217L, 216L, 215L, 214L, 213L, 212L, 211L, 210L, 209L, 
                                                          208L, 207L, 206L, 205L, 204L, 203L, 202L, 201L, 200L, 199L, 198L, 
                                                          197L, 196L, 195L, 194L, 193L, 192L, 191L, 190L, 189L, 188L, 187L, 
                                                          186L, 185L, 184L, 183L, 182L, 181L, 180L, 179L, 178L, 177L, 176L, 
                                                          175L, 174L, 173L, 172L, 171L, 170L, 169L, 168L, 167L, 166L, 165L, 
                                                          164L, 163L, 162L, 161L, 160L, 159L, 158L, 157L, 156L, 155L, 154L, 
                                                          153L, 152L, 151L, 150L, 149L, 148L, 147L, 146L, 145L, 144L, 143L, 
                                                          142L, 141L, 140L, 139L, 138L, 137L, 136L, 135L, 134L, 133L, 132L, 
                                                          131L, 130L, 129L, 128L, 127L, 126L, 125L, 124L, 123L, 122L, 121L, 
                                                          120L, 119L, 118L, 117L, 116L, 115L, 114L, 113L, 112L, 111L, 110L, 
                                                          109L, 108L, 107L, 106L, 105L, 104L, 103L, 102L, 101L, 100L, 99L, 
                                                          98L, 97L, 96L, 95L, 94L, 93L, 92L, 91L, 90L, 89L, 88L, 87L, 86L, 
                                                          85L, 84L, 83L, 82L, 81L, 80L, 79L, 78L, 77L, 76L, 75L, 74L, 73L, 
                                                          72L, 71L, 70L, 69L, 68L, 67L, 66L, 65L, 64L, 63L, 62L, 61L, 60L, 
                                                          59L, 58L, 57L, 56L, 55L, 54L, 53L, 52L, 51L, 50L, 49L, 48L, 47L, 
                                                          46L, 45L, 44L, 43L, 42L, 41L, 40L, 39L, 38L, 37L, 36L, 35L, 34L, 
                                                          33L, 32L, 31L, 30L, 29L, 28L, 27L, 26L, 26L, 26L, 25L, 25L, 24L, 
                                                          24L, 23L, 23L, 22L, 22L, 21L, 21L, 20L, 20L, 20L)), class = "data.frame", row.names = c(NA, 
                                                                                                                                                  -613L))

выглядит так:

Я могу найти максимальный аккорд и ничьячто:

# draw max dimension points and line
suppressPackageStartupMessages(library(tidyverse))
df_dist = data.frame(as.matrix(dist(cbind(points_ex$V1,points_ex$V2))))
df_dist_x = df_dist %>% 
  mutate(row.1 = 1:nrow(df_dist)) %>% 
  mutate(Y = paste0("Y", row_number())) %>%
  gather(X,  distance, X1:nrow(.)) %>% 
  select(X, Y, distance) %>% 
  mutate_at(vars(X, Y), parse_number)

df_dist_x_max <- 
  df_dist_x %>% 
  dplyr::filter(distance == max(distance)) 

points(points_ex[df_dist_x_max$X[1],], col = "red", cex = 2)
points(points_ex[df_dist_x_max$X[2],], col = "red", cex = 2.5)

segments(points_ex[df_dist_x_max$X[1], 'V1'], 
         points_ex[df_dist_x_max$X[1], 'V2'],
         points_ex[df_dist_x_max$X[2], 'V1'], 
         points_ex[df_dist_x_max$X[2], 'V2'],
         col = "green")

И вот что я пытался получить самый длинный аккорд, перпендикулярный максимальной длине аккорда:

# transform the points and lines into spatial objects
library(sf)
library(sp)
library(rgeos)

points_sf <- st_as_sf(points_ex, coords = c("V1", "V2"))

newline = matrix(c(points_ex[df_dist_x_max$X[1], 'V1'], 
                   points_ex[df_dist_x_max$X[1], 'V2'],
                   points_ex[df_dist_x_max$X[2], 'V1'], 
                   points_ex[df_dist_x_max$X[2], 'V2']), byrow = T, nrow = 2)

spline <- as(st_as_sfc(st_as_text(st_linestring(newline))), "Spatial") # there is probably a more straighforward solution...
position <- gProject(spline, as(points_sf, "Spatial"))
position <-  coordinates(gInterpolate(spline, position))
colnames(position) <- c("X2", "Y2")

segments <- 
  data.frame(st_coordinates(points_sf), position)  

segments$dist <- NULL
for(i in 1:nrow(segments)){
  segments$dist[i] <- 
    proxy::dist(data.frame(segments$X[i], segments$Y[i]),  
                data.frame(segments$X2[i], segments$Y2[i]))
}

# max width perpendicular to length axis
max_segment <- segments[which.max(segments$dist), ]
max_segment <- segments[segments$Y == max_segment$Y, ]

segments(max_segment$X[1], max_segment$Y[1],
         max_segment$X2[1], max_segment$Y2[1],
         col = "purple")

segments(max_segment$X[2], max_segment$Y[2],
         max_segment$X2[2], max_segment$Y2[2],
         col = "purple")

Выглядит примерно нормально, но моя проблема в том, что этот метод поиска самого длинного аккорда, перпендикулярного максимальному аккорду, смотрит только на одну сторону максимального аккорда для наибольшего расстояния до края многоугольника.

Я не знаю, как измерить каждое расстояние от края до края многоугольника, которое перпендикулярно максимальному аккорду.

Это означает, что мой метод вообще плохо обобщается, здесь он применяется к другому многоугольнику (данные здесь: https://pastebin.com/XpiB6UnX, потому что вывод dput сделал этот пост слишком длинным)

Очевидно, что это плохо, потому что два фиолетовых сегмента не должны быть на одной стороне зеленого сегмента, и это совсем не похоже на правильное расположение для самого длинного перпендикулярного аккордадо максимального аккорда.

Как надежно найти самый длинный аккорд, перпендикулярный максимальному аккорду?

Answer 1

Вот полное решение.Сначала некоторые функции:

## this returns the i,j of the largest elements in matrix `m`
findmax <- function(m){
    v = which.max(m) - 1
    c(v %% nrow(m)+1, v %/% nrow(m)+1)
}

## Return an sf line through a point at an angle of a given length
pline <- function(pt, angle, length){
    st_linestring(
        cbind(
            pt[1] + c(length,-length) * sin(angle),
            pt[2] + c(length,-length) * cos(angle)
        )
    )
}

## return the line that is the chord at angle perp.angle of length through any of the polygon vertices
max_perp_chord <- function(polygon, perp.angle, length){
    ## get polygon vertices
    pts = st_coordinates(polygon)[,c(1,2)]
    ## return the perpendicular lines
    perplines = lapply(1:nrow(pts), function(i){
        ## through the i-th vertex
        xy = pts[i,,drop=FALSE]
        perpline = pline(xy, perp.angle, length)
        ## intersect it with the polygon
        inters = st_intersection(polygon, perpline)
        inters
    }
    )

    ## get the vector of intersection lengths, find the largest
    perplengths = unlist(lapply(perplines, st_length))
    longest = which.max(perplengths)
    ## return the longest line
    perplines[[longest]]

}

### find the max length chord across all pairs of vertex points
max_chord <- function(polygon){
    ## get polygon coordinates
    xy = st_coordinates(polygon)[,1:2]

    ## compute the distance matrix and find largest element
    df_dist = as.matrix(dist(xy))
    maxij = findmax(df_dist)

    ## those elements define the largest chord
    chord = rbind(
        xy[maxij[1],],
        xy[maxij[2],]
    )
    chord
}


find_max_chord <- function(spolygon, chord=max_chord(spolygon)){

    ## Now compute the length and angle of the longest chord
    chord.length = sqrt(diff(chord[,1])^2 + diff(chord[,2])^2)
    chord.theta = atan2(diff(chord[,1]), diff(chord[,2]))

    ## The perpendicular is at this angle plus pi/2 radians
    perp = chord.theta + pi/2
    max_perp_chord(spolygon, perp, chord.length)
}

Вот как это происходит вместе.Единственная зависимость - sf - используется только база R:

library(sf)

Затем массируйте ваши данные в sf объект полигона:

## construct an sf polygon from points:
polygon = st_polygon(list(as.matrix(rbind(points_ex, points_ex[1,]))))

Получите максимальную длинуАккорд между вершинами:

chord = max_chord(polygon)

Построить полигон, аккорд и точки аккорда:

plot(polygon)
points(chord, col="red",cex=2)
lines(chord,col="green",lwd=2)

Теперь мясо.Получите аккорд перпендикулярно максимальному аккорду через одну из вершин многоугольника:

## get the max perpendicular chord
pchord = find_max_chord(polygon, chord)

Постройте его.

plot(pchord,add=TRUE)

Я проверил это на другом примере, но не на втором, который вы опубликовали ... Должен работать, но ...

Работает ...

Answer 2

Если ваш многоугольник является монотонным, вы можете применить следующий подход:

Я предполагаю, что многоугольник вращается, чтобы сделать аккорд максимальной длины вертикальным (как показывают ваши два изображения).

Началос верхней точки.Пройдите через левую часть в направлении против часовой стрелки, правую часть по часовой стрелке.

Ключевой момент: самый длинный аккорд должен касаться вершины многоугольника (поскольку не может быть достигнуто максимальное значение на отрезке линии между двумя внутренними точками по краям).

Итак, получим вершину с самой высокой Y-координатой (либо в левой части, либо в правой части).Рассчитайте точку на ребре с противоположной стороны.Получи длину.

Получить вершину со следующей Y-координатой.Рассчитайте точку на ребре с противоположной стороны.Получи длину.Продолжить.