Нужен алгоритм для масштабирования графиков

Question

[Михаил Бурилов]

Задача: есть очень большое число точек, при их отрисовке на графике все дико тормозит. Если взять DevExpress-овый XtraChart и включить интерактивные возможности — это полный кошмар. Саморисованный контрол субъективно раза в два быстрее, но все равно неидеально.
По идее, надо отсечь часть точек на полном масштабе, и показывать детальней при увеличении.
Смотрю на финансовые графики на том же mt.gox — и все шустро, а там объем данных на месячном графике и побольше будет.
Подскажите, какие есть алгоритмы для этого?

Answer 1

[Алексей Акулович]

Теми же методами кластеризации группировать точки в зависимости от масштаба. Если на масштабе Z расстояние между двумя точками не превышает X, то сливать их в одну.

Comments

[Eddy_Em]

Лучше медиану (ну или хотя бы среднее арифметическое) из набора точек брать, а то кривоватое прореживание может получиться.

[Алексей Акулович]

Ну нахождение «центра масс» точек в одном кластере — это уже вопрос конкретной реализации.

[Eddy_Em]

Ну, называть такое прореживание «методами кластеризации» у меня язык не поворачивается!
Обычная передискретизация.
P.S. А можно делать передискретизацию и по неравномерной сетке: в зависимости от поведения функции на заданном участке. Получится меньше данных на графике, но больше расчетов.

[Михаил Бурилов]

Пожалуй, ваш ответ мне подходит больше всего.
Вот такой код получился

		private void Simplify2(FastChartSerie serie, double tolerance) {
			serie.Points.Clear();

			double prevX = 0;
			double maxY = 0;

			foreach (DataRowView rowView in _source) {
				var dt = Convert.ToDateTime(rowView[ArgumentFieldName]);
				double val = 0;
				if (!(rowView[serie.ColumnName] is DBNull)) {
					val = Convert.ToDouble(rowView[serie.ColumnName]);
				}

				double x = calcX(dt);

				if (serie.Points.Count==0) {
					prevX = x;
					maxY = val;

					serie.Points.Add(new FastChartPoint() { X = dt, Y = maxY });
				} else {
					double dist = x - prevX;

					if(dist<tolerance) {
						if(Math.Abs(val)>Math.Abs(maxY)) {
							maxY = val;
						}
					} else {
						prevX = x;
						serie.Points.Add(new FastChartPoint() { X = dt, Y = maxY});
						maxY = 0;
					}
				}

			}
		}

Answer 2

[Илья Попов]

Возможно вам поможет алгоритм Рамера-Дугласа-Пекера. На Хабре публиковалась его реализация на JavaScript, но его несложно реализовать на любом языке.

Comments

[Михаил Бурилов]

спасибо, но быстро получить работающий порт на C# мне не удалось. Возможно, вернусь к этому решению позже

[Илья Попов]

Может это поможет: www.codeproject.com/Articles/18936/A-C-Implementation-of-Douglas-Peucker-Line-Approxi