Страница 1 из 2
поиск замкнутых контуров в списке координат
Добавлено: 18 мар 2023, 03:17
artterrm
здравствуйте.
есть длинный непрерывный список пар координат замкнутых контуров (примерно как на вложении)
нужно выделить каждый замкнутый контур по одинаковым координатам начальной и конечной точки.
У этой задачи есть какое то специальное название ( по типу задача о трех ферзях или там задача Монти-Пайтона -Разумовского или что то типа того)
Re: поиск замкнутых контуров в списке координат
Добавлено: 18 мар 2023, 08:45
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")
}
Re: поиск замкнутых контуров в списке координат
Добавлено: 18 мар 2023, 09:38
artterrm
в гугл или яндекс в запросе если писать "тривиальная задача" много что вылетает.
как называется она? есть же название? в комментариях что то про кольца?
Re: поиск замкнутых контуров в списке координат
Добавлено: 18 мар 2023, 10:35
gamm
artterrm писал(а): ↑18 мар 2023, 09:38
есть же название
никак не называется, это элементарное упражнение для 1 курса ВМК. В теории кодирования есть похожая задача пои ска цикла в случайной последовательности с начальным "хвостом".
Re: поиск замкнутых контуров в списке координат
Добавлено: 18 мар 2023, 10:55
artterrm
Но если задача и тривиальная, вы когда на первом курсе код по ее решению писали в процессе работы же вдохновлялись какой то областью знаний( не одним же здравым смыслом). Какой именно? не ботанику и не уроки труда ведь в школе вспоминали и не квадратные уравнения
Теорию кодирования ?
Re: поиск замкнутых контуров в списке координат
Добавлено: 18 мар 2023, 10:58
gamm
artterrm писал(а): ↑18 мар 2023, 10:55
какой то областью знаний
какая еще "область знаний"? Это элементарное упражнениен на 10 минут, на занятии. Возьмите например учебник Шеина (если фамилию не попутал) по информатике для средней школы, там таких упражнений сотни

Re: поиск замкнутых контуров в списке координат
Добавлено: 18 мар 2023, 11:13
artterrm
понятно, спасибо
Re: поиск замкнутых контуров в списке координат
Добавлено: 18 мар 2023, 17:14
trir
Вычислительная геометрия
Re: поиск замкнутых контуров в списке координат
Добавлено: 19 мар 2023, 02:34
artterrm
trir писал(а): ↑18 мар 2023, 17:14
Вычислительная геометрия
спасибо.
Re: поиск замкнутых контуров в списке координат
Добавлено: 19 мар 2023, 02:36
artterrm
Но если нужно преобразовать таблицу координат ( многостраничную таблицу) из 4х колонок сделать одну либо не таблицу экселя ,а файл такой же но csv
Re: поиск замкнутых контуров в списке координат
Добавлено: 19 мар 2023, 08:27
trir
любой язык программирования
Re: поиск замкнутых контуров в списке координат
Добавлено: 19 мар 2023, 11:10
artterrm
Но может есть какой-то специальный подход.
Или что-ли двигаться по строкам до конца страницы потом перескакивать опять в начало таблицы но во вторую колонку с парой координат и опять до конца страницы.
Если так то это тоже самое что пальцем по таблице водить но только со скоростью компьютера?
Re: поиск замкнутых контуров в списке координат
Добавлено: 19 мар 2023, 11:41
gamm
1) Ёксель - зло, создающее проблемы при обработке данных. Причем всегда, в самых неожиданных местах, и в самое неподходящее время.
2) Данные нужно готовить в нормальном виде. Если кто-то умудрился написать таблицу кусками в несколько частей, то его нужно заставить скопипастить ее на новую страницу в нормальном виде. И сделать строгий выговор, чтобы не чудил. Наверняка эти данные в таблицу не руками вбивали, а брали из файла, где все было нормально, а не кусками. Вот с этим нормальным файлом и нужно работать, а не бороться с искуственно созданными трудностями

Re: поиск замкнутых контуров в списке координат
Добавлено: 19 мар 2023, 12:47
artterrm
Необязательно эксель. Например питон. Но не не так что взять первую строку выбрать данные затем вторую третью и т д. Так то сделать можно но может быть есть другой подход. Какой то тривиальный алгоритм для таких случаев.
А первоначальный файл вообще в pdf и им по лицу его создателям не по возишь ибо ведомство какое-то
Re: поиск замкнутых контуров в списке координат
Добавлено: 19 мар 2023, 13:22
gamm
4 куска проще скопировать руками на новую страницу, чем парсер городить.