Уроки, алгоритмы, программы, примеры

Вход на сайт

Материалы по разделам

Построения
на плоскости (2D)
Графика
в пространстве (3D)
Вычислительная
геометрия
Физическое
моделирование
Фрактальная
графика

Новые комментарии

dobryj den, popytalas otkryt prikreplionnyj fail ctoby posmotret kak rabotaet, no mne ego ne pokazyvaet vydajet osibku. Pochemu?
Очень интересно! ии сайт крутой жалко что умирает(
У Вас число превысит максимальное число int. Можно использовать в Вашем случае uint, но лучше все переписать на double.
Добавление к программе строки glutReshapeFunc(changeSize); приводит к тому, что треугольник перестаёт совсем отрисовываться.
Выдаёт ошибку glut32.dll не найден! При том, что он лежит в System32! Всё решил) Нужно отправить не в System32, а в System.

Счетчики и рейтинг

Рейтинг@Mail.ru Яндекс.Метрика
Скриншот к примеру
Среда программирования: 
Visual Studio 2010 Express

По заданному набору точек построить график полинома Лангранжа.

Более формально:
Пусть задана функция y = f(x)
Пусть заданы точки X = {xi| i = 1...n} из некоторой области D.
Пусть значения функции f известны только в этих точках.
Точки X называют узлами интерполяции.
δxi = xi - xi-1 - шаг интерполяционной сетки.
Задача интерполяции состоит в поиске такой функции F из заданного класса функций, что F(xi) = yi

Теперь немного об интерфейсе программы:
Для того, чтобы произвести интерполяцию, вводим координаты точек в поле ввода слева от кнопки Add Point. Вводим координаты очередной точки (через пробел) и нажимаем на кнопку Add Point (Enter нажимать не нужно). Программа умеет работать с отрицательными вещественным числами, с точностью до 4-х знаков после запятой. Кол-во точек должно быть больше одной. Все добавленные точки записываются в список (справа от кнопки Clear).
Если вы хотите удалить какую-то точку, то введите номер этой точки в поле ввода под кнопкой Delete Point и нажмите саму кнопку Delete Point.

Как только вы ввели координаты всех точек, нажимаем Spline и получаем график полинома Лангранжа. Ура!

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

Код программы: 

Функция вычисляющая по определению точки полинома Лангранжа

Как мы видим из определения многочлена Лангранжа, сложность вычисления координаты y для каждого x составляет O(N^2), где N - это кол-во ключевых точек (по которым мы строим интерполяцию)

for (int cur_x = Convert.ToInt32(min_x); cur_x <= Convert.ToInt32(max_x); cur_x++) // Проходим по всем области определения и вычисляем y для каждого x.
{
    double Y = 0.0;
    for (int i = 0; i < a.Count; i++)
    {
        // Вычисляем координату y базисного полинома
        double Basis = 1.0;
        for (int j = 0; j < a.Count; j++)
        {
             if (j != i)
             {
                 Basis *= (cur_x - a[j].x)/(a[i].x - a[j].x);
              }       
         }
          // Вычислям y
          Y += Basis * a[i].y;
}

Код программы:

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Collections;
using System.Threading;
 
namespace Interpolation
{    
    public partial class Form1 : Form
    {
        // Объявляем структуру для хранения точек с вещественными координатами
        struct point
        {
            public
            double x, y;
        };  
 
        const double INF = 2000000000; // Инициализируем бесконечность
        const double EPS = 1E-5; // Инициализируем достаточно малую величину (для сравнения вещественных чисел)
 
        List<point> a = new List<point>(); // Инициализируем массив точек, по которым будем строить интерполяцию
        List<point> b = new List<point>(); // Инициализируем массив точек, получаемых после интерполяции (точки полинома Лангранжа)
        List<point> inscription = new List<point>(); // Инициализируем массив ключевых точек (эти координаты будут отображены на графике, координаты совпадают с темы, которые в введем в крограмму), массив старых координат (без масштабирования)
 
        bool spline_switch = false; // флаг, показываюший была ли нажата кнопка Spline (предотвращает двойное нажатие на кнопку Spline)
 
        SolidBrush myBrush = new SolidBrush(Color.Black); // Инициализируем кисть для рисования
 
        public Form1()
        {
            InitializeComponent();
        }
 
        // Функция предназначена для добавления ключевой точки (срабатывает при нажатии кнопки Add Point)
        private void button1_Click(object sender, EventArgs e)
        {
            string s = textBox1.Text; // Записываем содержаение поля ввода в переменную типа "Строка"
            int len = s.Length; // Определяем длину строки
 
            if (len == 0) // Если строка пустая
            {
                DialogResult result = MessageBox.Show("You have not entered the coordinates!", "Error", MessageBoxButtons.OK, MessageBoxIcon.Warning); // То выводим сообщение об ошибке ввода
                return;
            }
 
            point num; // Объявляем временную переменную
 
            var parts = s.Split(' '); // Делим строку на части через пробел и записываем в массив parts каждую часть
            num.x = Convert.ToDouble(parts[0]); // Преобразуем строку в число и записываем координаты точки, которую мы ходим добавить в переменную num
            num.y = Convert.ToDouble(parts[1]);
 
            a.Add(num); // Добавляем точку в массив ключевых точек
 
            label4.Text = a.Count.ToString(); // Отображаем текущее кол-во точек
            textBox1.Text = ""; // Очищаем поле ввода
 
            comboBox1.Items.Add("[" + Convert.ToString(num.x) + " " + Convert.ToString(num.y) + "]"); // Записываем координаты ключевых точек в список
        }
 
        private void label1_Click(object sender, EventArgs e)
        {
        }
 
        private void Form1_Load(object sender, EventArgs e)
        {
        }
 
        private void textBox1_TextChanged(object sender, EventArgs e)
        {
        }
 
        // Функция рисования ключевых точек
        void Draw_Points(double k)
        {
            Graphics g = Graphics.FromHwnd(pictureBox1.Handle); // Инициализируем графику
            for (int i = 0; i < a.Count; i++) // Проходим по массиву ключевых точек
            {
                point tmp; // Объявляем временную переменную
                // Масштабируем координаты ключевых точек
                tmp.x = a[i].x * k; 
                tmp.y = a[i].y * k;
                a[i] = tmp; 
                g.FillEllipse(Brushes.YellowGreen, Convert.ToInt32(a[i].x), Convert.ToInt32(a[i].y), 5, 5); // Рисуем точку желтым цветом (для хорошей видимости используем функцию отрисовки эллипса)
 
                String drawString = "[" + Convert.ToString(inscription[i].y) + " " + Convert.ToString(inscription[i].x) + "]"; // Составляем строку для отображения координат ключевой точки рядом с ней на плоскости
 
                int size = 8; // Инициализируем размер текста
                Font drawFont = new Font("Arial", size); // Определяем шрифт
                SolidBrush drawBrush = new SolidBrush(Color.BurlyWood); // Инициализируем кисть для рисования
 
                PointF drawPoint = new PointF(Convert.ToInt32(a[i].x + drawString.Length*size/2), Convert.ToInt32(a[i].y+8)); // Определяем координаты левой верхней точки, откуда будем отображать надпись
 
                // Set format of string.
                StringFormat drawFormat = new StringFormat();
                drawFormat.FormatFlags = StringFormatFlags.DirectionRightToLeft;
 
                g.DrawString(drawString, drawFont, drawBrush, drawPoint, drawFormat); // Отображаем координаты
            }
        }
 
        // Функция вычисления точек полинома
        void Calc_Poly()
        {
            // Инициализируем минимальную и максимальную координату x
            double min_x = INF;
            double max_x = -INF;
 
            // Находим среди координат ключевых точек минимальную и максимальную координату x (вычисляем область определения)
            for (int i = 0; i < a.Count; i++)
            {
                if (a[i].x > max_x) max_x = a[i].x;
                if (a[i].x < min_x) min_x = a[i].x;
            }
 
            // Вычисляем полином Лангранжа
            for (int cur_x = Convert.ToInt32(min_x); cur_x <= Convert.ToInt32(max_x); cur_x++) // Проходим по всем области определения и вычисляем y для каждого x.
            {
                double Y = 0.0;
                for (int i = 0; i < a.Count; i++)
                {
                    // Вычисляем координату y базисного полинома
                    double Basis = 1.0;
                    for (int j = 0; j < a.Count; j++)
                    {
                        if (j != i)
                        {
                            Basis *= (cur_x - a[j].x)/(a[i].x - a[j].x);
                        }       
                    }
                // Вычислям y
                Y += Basis * a[i].y;
            }
            // Записываем координаты полученной точки в массив
            point cur;
            cur.x = cur_x;
            cur.y = Y;
            b.Add(cur); 
        }
 
        // Вычисляем область определения и область значений полинома Лангранжа
        min_x = INF;
        max_x = -INF;
        double min_y = INF;
        double max_y = -INF;
 
        for (int i = 0; i < b.Count; i++)
        {
            if (b[i].x + EPS < min_x) min_x = b[i].x;
            if (b[i].y + EPS < min_y) min_y = b[i].y;
            if (b[i].x > max_x + EPS) max_x = b[i].x;
            if (b[i].y > max_y + EPS) max_y = b[i].y;
        }
        // Смещаем начало системы координат к самой левой верхней точке полинома Лангранжа
        for (int i = 0; i < b.Count; i++)
        {
            point tmp;
            tmp.x = b[i].x - min_x;
            tmp.y = b[i].y - min_y;
            b[i] = tmp;
        }
        // Определяем длину и ширину холста
        double w = panel1.Size.Width, h = panel1.Size.Height;
        if (max_x - min_x == 0) max_x += max_y - min_y;
        if (max_y - min_y == 0) max_y += max_x - min_x;
 
        // Вычисляем коэфиициент масштабирования
        double Sx = w / (max_x - min_x), Sy = h / (max_y - min_y);
        double S = Sx;
        if (Sy < S) S = Sy;
 
        S *= 0.9;
 
        // Пересчиитываем координаты точек полинома Лангранжа в новую систему координат (экранные координаты)
        for (int i = 0; i < b.Count; i++)
        {
            point tmp;
            tmp.x = b[i].x * S;
            tmp.y = b[i].y * S;
            b[i] = tmp;
        }
        Draw_Poly(); // Вызываем функцию отрисовки точек полинома Лангранжа
        Draw_Points(S); // Отмечаем поверх графика ключевые точки
 }
        // Функция отрисовки точек полинома
        void Draw_Poly()
        {
            Pen myPen = new Pen(Color.Black, 1); // Инициализируем капрандаш
            Graphics g = Graphics.FromHwnd(pictureBox1.Handle); // Инициализируем графику
            g.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.AntiAlias; // Cглаживание для графики
            Point from = new Point(0, 0), to = new Point(0, 0); // Инициализируем начальную и конечную точку для отрисовки отрезка
            for (int i = 1; i < b.Count; i++)
            {
                // Преобразуем типы данных
                from.X = Convert.ToInt32(b[i - 1].x);
                from.Y = Convert.ToInt32(b[i - 1].y);
                to.X = Convert.ToInt32(b[i].x);
                to.Y = Convert.ToInt32(b[i].y);
                // Рисуем отрезок
                g.DrawLine(myPen, from, to);
 
            }         
        }
 
        // Функция предназначена для вычисления координат сплайна и его изобржения на холсте (вызывается при нажатии кнопки Spline)
        private void button2_Click(object sender, EventArgs e)
        {
            if (spline_switch == true) // Если эта кнопка уже была нажата, то выводим сообщение об ошибке
            {
                DialogResult result = MessageBox.Show("You clicked twice on the spline! For the next spline first press CLEAR and enter the new coordinates.", "Error", MessageBoxButtons.OK, MessageBoxIcon.Warning);
                return;
            }
            spline_switch = true; // Иначе срабатывает переключатель (2 раза подряд эта кнопка не сработает)
 
            if (a.Count == 0) // Если кол-во точек 0, то выводим сообщение об ошибке (сплайн построить нельзя)
            {
                DialogResult result = MessageBox.Show("You have not entered the coordinates of any point!", "Error", MessageBoxButtons.OK, MessageBoxIcon.Warning);
                return;
            }
            if (a.Count == 1) // Если кол-во точек 1, то выводим сообщение об ошибке (сплайн построить нельзя)
            {
                DialogResult result = MessageBox.Show("You have entered the coordinates of only one point!", "Error", MessageBoxButtons.OK, MessageBoxIcon.Warning);
                return;
            }
 
            // Иначе записываем координаты ключевых точек в массив описания
            for (int i = 0; i < a.Count; i++)
            {
                inscription.Add(a[i]);
            }
 
            // Вычисляем область определения и область значений
            double min_x = INF;
            double max_x = -INF;
            double min_y = INF;
            double max_y = -INF;
 
            for (int i = 0; i < a.Count; i++)
            {
                if (a[i].x + EPS < min_x) min_x = a[i].x;
                if (a[i].y + EPS < min_y) min_y = a[i].y;
                if (a[i].x > max_x + EPS) max_x = a[i].x;
                if (a[i].y > max_y + EPS) max_y = a[i].y;
            }
 
            // Смещаем начало системы координат к самой левой верхней точке
            for (int i = 0; i < a.Count; i++)
            {
                point tmp;
                tmp.x = a[i].x - min_x;
                tmp.y = a[i].y - min_y;
                a[i] = tmp;
            }
            // Определяем длину и ширину холста
            double w = panel1.Size.Width, h = panel1.Size.Height;
            // Вычисляем коэфиициент масштабирования
            if (max_x - min_x == 0) max_x += max_y - min_y;
            if (max_y - min_y == 0) max_y += max_x - min_x;
 
            double Sx = w / (max_x - min_x), Sy = h / (max_y - min_y);
            double S = Sx;
            if (Sy < S) S = Sy;
 
            S *= 0.9;
            // Пересчиитываем координаты ключевых точек(экранные координаты)
            for (int i = 0; i < a.Count; i++)
            {
                point tmp;
                tmp.x = a[i].x * S;
                tmp.y = a[i].y * S;
                a[i] = tmp;
            }
            Calc_Poly(); // Вызов функции вычисления точек полинома
        }
 
        // Функция, выполняемая при нажатии кнопки Clear (очищает холст и все необходимые массивы для работы с новым набором ключевых точек)
        private void button3_Click(object sender, EventArgs e)
        {
            spline_switch = false; // Переключаем флаг "нажатия кнопки Spline" (После нажатия кнопки Clear мы снова можем нажимать кнопку Spline)
            a.Clear(); // Очищаем массив ключевых точек 
            b.Clear(); // Очищаем массив точек полинома Лангранжа
            inscription.Clear(); // Очищаем массив описания ключевых точек
            label4.Text = a.Count.ToString(); // Отображаем текущее количество ключевых точек
            Graphics g = Graphics.FromHwnd(pictureBox1.Handle); // О графику
            g.Clear(pictureBox1.BackColor); // Очищаем графику
            comboBox1.Items.Clear(); // Очищаем список точек в контейнере combobox
        }
 
        private void pictureBox1_LoadCompleted(object sender, AsyncCompletedEventArgs e)
        {
        }
 
        // Функция, выполняемая при нажатии кнопки Delete, удаляет ключевую точку с необходимым номером
        private void button5_Click(object sender, EventArgs e)
        {
            int num = Convert.ToInt32(textBox2.Text); // Записываем введенный номер ключевой точки, которую необходимо удалить, в переменную
            if (num >= a.Count)
            {
                DialogResult result = MessageBox.Show("Point which has entered number does not exist!", "Error", MessageBoxButtons.OK, MessageBoxIcon.Warning); // Если точки с таким номером нет, то выводим сообщение об ошибке ввода
            }
            else // Иначе
            {
                a.RemoveAt(num); // Удаляем точку из массива ключевых точек
                inscription.RemoveAt(num); // Удаляем точку из массива описания ключевых точек
                label4.Text = a.Count.ToString(); // Отображаем новое кол-во точек
                comboBox1.Items.RemoveAt(num); // Удаляем точку из списка
                comboBox1.Text = ""; // Очищаем строку вывода в списке
            }
        }
    }
}

Проект прикреплен ниже

Прикрепленный файлРазмер
Interpolation.rar163.71 кб