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

Вход на сайт

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

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

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

torrvic, возможно, Вам нужно добавить -lGLU
Извините за тупой вопрос. У меня при сборке Вашего примера выходит ошибка: "undefined reference to gluLookAt". Не могу найти в какой библиотеке находится эта функция. У меня задано: -lGL -lglut ... Искал в /usr/lib таким образом: nm lib*so* | grep...
Здравствуйте. Спасибо за проект. У меня вопрос, по какой причине определение принадлежности точки многоугольнику работает некорректно, если координаты из больших чисел состоят, например: int[] vertex = new int[] {...
Сейчас проверила нашла причину не запускания // Создание контекста воспроизведения OpenGL и привязка его к панели на форме OpenGLControl1:=TOpenGLControl.Create(Self); with OpenGLControl1 do begin Name:='OpenGLControl1'; //вот тут...
Ну..кажется что то пошло не так http://pp.usera...

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

Рейтинг@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 кб