Классификация линий

Есть совокупность графиков нескольких гладких функций одного действительного аргумента, которые имеют разную область определения и значения. Все эти функции в совокупности удовлетворяют следующему свойству: в любой точке x определены ровно n функций. Иными словами, все эти функции в совокупности можно мыслить как кусочно-гладкую функцию , которая достаточно гладкая всюду, кроме нескольких точек, в которых обрывается одна функция и начинается другая, а остальные функции продолжаются непрерывно. Ещё одно свойство: все непрерывные функции лежат между обрывающимися функциями.

Дано: сетка на оси абсцисс и совокупность точек, взятых по этой сетке, т.е. дана таблица , где xi обозначает точку на сетке, а все y, которых по условию всегда ровно n штук, являются значениями функций в точке xi и отсортированы по величине.

Проблема: допустим, есть три функции. Одна из них — константный нуль, определенный на (-1,1), вторая — x+1 на (-1,0), третья — x-1 на (0,1). В точке x=0 вторая обрывается и начинается третья. Если делать таблицу с шагом 2/5, то будет следующее:
Здесь видно, что одна из функция поменяла свой порядковый номер. Также изменение порядкового номера может происходить при пересечении двух кривых.

Задача: восстановить кривые так, чтоб пересекающиеся кривые пересекались и на графике восстановленных функций, а обрывающиеся кривые обравылись и на графике. Хочется определить, сколько всего имеется пересечений линий, сколько всего кривых, в каком диапазоне лежит каждаяю

Помогите, пожалуйста. Кроме брутфорса в голову ничего не лезет, а ограничения достаточно жестки: n ~ 500, количество строк в таблице m >> n, m ~ 5 000, их достаточно много, чтобы распознать (визуально) любое пересечение, т.е. сетка не крупная, а мелкая.
Можно принимать любые предположения о гладкости и ограниченности функций.

0

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

Имеется ли специальное число показывающее что значении функций в данной точке нет ? Т.е. если функция не определенна для заданного x_i ?

А этот пример. Разве там не происходит разрыв шириной в 0,8 и 0,4 ? (вроде в математике определен термин для ширины разрыва кусочной функции, но забыл/не могу найти).
Я так понял что склеивать эти три функции вообще нельзя, так как у=0 имеет общую область определения с остальными двумя, а у=х+1 и у=х-1 образуют разрыв.
Неудачный пример?

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

Если мы имеем число "тут функция не определена", то мы можем составить график/функцию из любых функций, таких что полученная кусочно-гладкая функция будет включать:
1) графики функций с совпадающими концами по (х;у)
2) графики функций, область определения которых отстоит от всех соседей более чем на один отсчет, если только сосед не удовлетворяет пункту (1)
3) "пустые" места заполнены "символами" "функция не определена"

Добавлено через 9 минут
Брутфорс? А мне почему-то припомнился алгоритм коммивояжёра.

0

Дана таблица и только.

Сообщение от wingblack Имеется ли специальное число показывающее что значении функций в данной точке нет ?

Нет. Даны только точки.

На выходе хочется получить число непрерывных кривых и точки, которые им принадлежат.

Я такой алгоритм придумал:
взять некоторое количество точек (я брал ~10) слева и предположить, что кривые не успевают пересечься. Затем по этим точкам экстраполировать на следующую точку слева и сравнить предсказание с реальностью. Классифицировать: отклонение в пределах погрешности экстраполяции / две кривые пересекаются / одна кривая обрывается, а другая начинается.
Работает, но медленно очень.

n неизменно.

0

Сообщение от Mysterious Light На выходе хочется получить число непрерывных кривых и точки, которые им принадлежат

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

0

Можно считать все функции достаточно гладкими и ограниченными. Например, можно предполагать, что производная (первая, вторая) на расстоянии одного отсчёта меняются слабо.

Ещё раз повторю, что есть два типа неприятностей в такой таблице:
1. пересечение кривых ведёт к перепутыванию частей двух соседних столбцов, как хромосомы при кроссинговере.
2. одна кривая заканчивается, а другая с другой стороны от массива кривых начинается. В определённом смысле этот случай похож на первому, потому что здесь все столбцы сдвигаются циклично.
По первому случаю хочется проследить движение каждой кривой и определить пересечения между собой. По второму — определить число кривых и их области определения.

0

Использование кроссинговера было обнаружено только при анализе данных или это заранее было известно?

Сомневаюсь что я сейчас выражу особо уникальную идею, но все же:
- на основе хотя бы первой производной разбить графики на непрерывные куски.
- для концов каждого непрерывного куска сформировать тройки (x,y,dy) (плюс флаг к левому или правому краю эта тройка относится)
- склеивать графики по признаку 1) склеиваемые краи отстоят на один отсчет 2) разница в первых производных не превышает погрешность 3) разница в высоте краев не противоречит первой производной + погрешность

1

Задача стала актуальной снова, поскольку наконец-то появились данные, на которых можно наглядно показать, что есть и что хочется.
В приложении находится файлик с данными в немного отличающемся от описанного выше формате: это список из m наборов, каждый набор есть список из n точек, каждая точка есть пара {x,y}. В одном наборе все абсциссы совпадают, т.е. данные выглядят так:
{
{ {x1,y11}, {x1,y12}, {x1,y13} },
{ {x2,y21}, {x2,y22}, {x2,y23} },
...
}
В приложении также можете увидеть картинку, которая получается, если каждый каждый столбец этой двумерной матрицы из точек изображать, как отдельную ломаную линию, которая проходит через точки:
линия 1: {x1,y11}-{x2,y21}-{x3,y31}-...
линия 2: {x1,y12}-{x2,y22}-{x3,y32}-...

На второй картинке увидеть расположение всех точек, цвет отмечает столбец, которому она принадлежит.

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

Миниатюры

   

Вложения

eJxTTMoPSuNgYGAoZgESPpnFJZlAmiGTEU4wwIiiWTNBYKd9JhNI6AtQFgBkMgyf.zip (13.3 Кб, 6 просмотров)

0

А подскажите как называется такая структура данных и какие готовые инструменты/шаблоны кода существуют для их ввода в программу, чтобы не изобретать велосипед на костылях?

Т.е. мы имеем набор для графиков слева , а нужно - чтобы данные создавали рисунок справа?

Добавлено через 35 минут
Хотелось хотя бы в экселе просмотреть на графики повнимательней, чтобы увидеть как именно ведет себя каждый столбик данных.
Внешне напоминает запись переменного тока, как кардиограмма. Тут точки задают вершины "пилы" или в том числе могут быть на линии между вершинами?

0

Сообщение от Mysterious Light Есть совокупность графиков нескольких гладких функций одного действительного аргумента, которые имеют разную область определения и значения. Все эти функции в совокупности удовлетворяют следующему свойству: в любой точке x определены ровно n функций. Иными словами, все эти функции в совокупности можно мыслить как кусочно-гладкую функцию https://www.cyberforum.ru/cgi-bin/latex.cgi?\mathbb{R} \to \mathbb{R}^n, которая достаточно гладкая всюду, кроме нескольких точек, в которых обрывается одна функция и начинается другая, а остальные функции продолжаются непрерывно. Ещё одно свойство: все непрерывные функции лежат между обрывающимися функциями.

Прочитав это - жить не хочется (не говоря уже об отвечать). Но когда предъявлена картинка (пост #7) оказывается задача-то вполне земная - восстановить ф-ции по точкам?

0