поиск замкнутых контуров в списке координат

[artterrm]

здравствуйте.
есть длинный непрерывный список пар координат замкнутых контуров (примерно как на вложении)
нужно выделить каждый замкнутый контур по одинаковым координатам начальной и конечной точки.
У этой задачи есть какое то специальное название ( по типу задача о трех ферзях или там задача Монти-Пайтона -Разумовского или что то типа того)

[gamm]

если незамкнутых контуров и "хвостов" нет, то это тривиальная задача, мы из на 1 курсе решали
вспомнил молодость Она нетривиальная, только если есть "хвосты" вне циклов

Код: Выделить всё

# generate rings
sink("foo")
n.ring = 10
max.rad=10
set.seed(123)
n.pnt = sample(3:20,n.ring)
rad=runif(n.ring,3,max.rad-1)
m=matrix(0,nrow=sum(n.pnt)+n.ring,ncol=2)
ncol=round(sqrt(n.ring))
pos=0
for(i in 1:n.ring) {
  x.shift = i %% ncol
  y.shift = i %/% ncol
  x0 = i*x.shift*max.rad
  y0 = i*y.shift*max.rad
  for(j in 0:n.pnt[i]) {
    pos=pos+1
    delta = (2*pi)/n.pnt[i]
    m[pos,]=c(round(x0+rad[i]*cos(delta*j)),round(y0+rad[i]*sin(delta*j)))
    cat(m[pos,1]," ",m[pos,2],"\n")
  }
}
sink()

# plot points
plot(m)

# find rings
p=read.table("foo",header=FALSE)
state="new"
ring.list=list()
for(i in 1:nrow(p)) {
  if(state == "new") {
    cur.ring=as.double(p[i,])
    state="old"
  } else {
    cur.pnt=as.double(p[i,])
    cur.ring=rbind(cur.ring,cur.pnt)
    if(cur.pnt[1] == cur.ring[1,1] && cur.pnt[2] == cur.ring[1,2]) {
      state="new"; ring.list=append(ring.list,list(cur.ring)) 
    }
  }
}

# plot rings
for(i in 1:length(ring.list)) {
  points(ring.list[[i]],col="red",type="l")
}

[artterrm]

в гугл или яндекс в запросе если писать "тривиальная задача" много что вылетает.
как называется она? есть же название? в комментариях что то про кольца?

[gamm]

есть же название

никак не называется, это элементарное упражнение для 1 курса ВМК. В теории кодирования есть похожая задача пои ска цикла в случайной последовательности с начальным "хвостом".

[artterrm]

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

[gamm]

какой то областью знаний

какая еще "область знаний"? Это элементарное упражнениен на 10 минут, на занятии. Возьмите например учебник Шеина (если фамилию не попутал) по информатике для средней школы, там таких упражнений сотни

[artterrm]

понятно, спасибо

[trir]

Вычислительная геометрия

[artterrm]

Вычислительная геометрия

спасибо.

[artterrm]

Но если нужно преобразовать таблицу координат ( многостраничную таблицу) из 4х колонок сделать одну либо не таблицу экселя ,а файл такой же но csv

[trir]

любой язык программирования

[artterrm]

Но может есть какой-то специальный подход.
Или что-ли двигаться по строкам до конца страницы потом перескакивать опять в начало таблицы но во вторую колонку с парой координат и опять до конца страницы.
Если так то это тоже самое что пальцем по таблице водить но только со скоростью компьютера?

[gamm]

1) Ёксель - зло, создающее проблемы при обработке данных. Причем всегда, в самых неожиданных местах, и в самое неподходящее время.

2) Данные нужно готовить в нормальном виде. Если кто-то умудрился написать таблицу кусками в несколько частей, то его нужно заставить скопипастить ее на новую страницу в нормальном виде. И сделать строгий выговор, чтобы не чудил. Наверняка эти данные в таблицу не руками вбивали, а брали из файла, где все было нормально, а не кусками. Вот с этим нормальным файлом и нужно работать, а не бороться с искуственно созданными трудностями

[artterrm]

Необязательно эксель. Например питон. Но не не так что взять первую строку выбрать данные затем вторую третью и т д. Так то сделать можно но может быть есть другой подход. Какой то тривиальный алгоритм для таких случаев.
А первоначальный файл вообще в pdf и им по лицу его создателям не по возишь ибо ведомство какое-то

[gamm]

4 куска проще скопировать руками на новую страницу, чем парсер городить.