Перевести код из C++ в чистый Си - C (СИ)
Формулировка задачи:
Из-за наличия специфики плюсов (векторы, классы, operator) вообще не удаётся интерпретировать логику, заложенную в код. Помогите, пожалуйста, разобраться и получить хотя бы шаблонный вариант на Си, который я смогу дописать до рабочего.
Приведённая программа позволяет интерполировать графики кривыми Безье. В отличие от других сотен вариаций на данную тему не даёт ложных экстремумов. Вот статья на хабре с подробным описанием и примерами. Код программы на гитхабе.
// TBezierInterpolation.cpp
#include <vector>
#include <iostream>
#include <cmath>
using namespace std;
#define EPSILON 1.0e-5
#define RESOLUTION 32
class Point2D
{
public:
double x, y;
Point2D() { x = y = 0.0; };
Point2D(double _x, double _y) { x = _x; y = _y; };
Point2D operator +(const Point2D &point) const { return Point2D(x + point.x, y + point.y); };
Point2D operator -(const Point2D &point) const { return Point2D(x - point.x, y - point.y); };
Point2D operator *(double v) const { return Point2D(x * v, y * v); };
void operator +=(const Point2D &point) { x += point.x; y += point.y; };
void operator -=(const Point2D &point) { x -= point.x; y -= point.y; };
void normalize()
{
double l = sqrt(x * x + y * y);
x /= l;
y /= l;
}
};
class Segment
{
public:
Point2D points[4];
void calc(double t, Point2D &p)
{
double t2 = t * t;
double t3 = t2 * t;
double nt = 1.0 - t;
double nt2 = nt * nt;
double nt3 = nt2 * nt;
p.x = nt3 * points[0].x + 3.0 * t * nt2 * points[1].x + 3.0 * t2 * nt * points[2].x + t3 * points[3].x;
p.y = nt3 * points[0].y + 3.0 * t * nt2 * points[1].y + 3.0 * t2 * nt * points[2].y + t3 * points[3].y;
};
};
bool calculateSpline(const vector<Point2D> &values, vector<Segment> &bezier)
{
int n = values.size() - 1;
if (n < 2)
return false;
bezier.resize(n);
Point2D tgL;
Point2D tgR;
Point2D cur;
Point2D next = values[1] - values[0];
next.normalize();
double l1, l2, tmp, x;
--n;
for (int i = 0; i < n; ++i)
{
bezier[i].points[0] = bezier[i].points[1] = values[i];
bezier[i].points[2] = bezier[i].points[3] = values[i + 1];
cur = next;
next = values[i + 2] - values[i + 1];
next.normalize();
tgL = tgR;
tgR = cur + next;
tgR.normalize();
if (abs(values[i + 1].y - values[i].y) < EPSILON)
{
l1 = l2 = 0.0;
}
else
{
tmp = values[i + 1].x - values[i].x;
l1 = abs(tgL.x) > EPSILON ? tmp / (2.0 * tgL.x) : 1.0;
l2 = abs(tgR.x) > EPSILON ? tmp / (2.0 * tgR.x) : 1.0;
}
if (abs(tgL.x) > EPSILON && abs(tgR.x) > EPSILON)
{
tmp = tgL.y / tgL.x - tgR.y / tgR.x;
if (abs(tmp) > EPSILON)
{
x = (values[i + 1].y - tgR.y / tgR.x * values[i + 1].x - values[i].y + tgL.y / tgL.x * values[i].x) / tmp;
if (x > values[i].x && x < values[i + 1].x)
{
if (tgL.y > 0.0)
{
if (l1 > l2)
l1 = 0.0;
else
l2 = 0.0;
}
else
{
if (l1 < l2)
l1 = 0.0;
else
l2 = 0.0;
}
}
}
}
bezier[i].points[1] += tgL * l1;
bezier[i].points[2] -= tgR * l2;
}
l1 = abs(tgL.x) > EPSILON ? (values[n + 1].x - values[n].x) / (2.0 * tgL.x) : 1.0;
bezier[n].points[0] = bezier[n].points[1] = values[n];
bezier[n].points[2] = bezier[n].points[3] = values[n + 1];
bezier[n].points[1] += tgR * l1;
return true;
}
int main()
{
vector<Point2D> testValues;
vector<Segment> spline;
Point2D p;
testValues.push_back(Point2D(0, 0));
testValues.push_back(Point2D(20, 0));
testValues.push_back(Point2D(45, -47));
testValues.push_back(Point2D(53, 335));
testValues.push_back(Point2D(57, 26));
testValues.push_back(Point2D(62, 387));
testValues.push_back(Point2D(74, 104));
testValues.push_back(Point2D(89, 0));
testValues.push_back(Point2D(95, 100));
testValues.push_back(Point2D(100, 0));
calculateSpline(testValues, spline);
for (auto s : spline)
{
for (int i = 0; i < RESOLUTION; ++i)
{
s.calc((double)i / (double)RESOLUTION, p);
cout << p.x << " " << p.y << endl;
}
}
cout << testValues.back().x << " " << testValues.back().y << endl;
return 0;
}g++ -std=c++11 TBezierInterpolation.cpp
Решение задачи: «Перевести код из C++ в чистый Си»
textual
Листинг программы
// TBezierInterpolation.c
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <stdbool.h>
#include <float.h>
#define RESOLUTION 32
#define POINTS_LEN 10
typedef struct
{
double x, y;
}Point2D;
Point2D Point2DAdd( Point2D *left, Point2D *right)
{
Point2D newPoint = {left->x + right->x, left->y + right->y};
return newPoint;
}
Point2D Point2DSubtract( Point2D *left, Point2D *right)
{
Point2D newPoint = {left->x - right->x, left->y - right->y};
return newPoint;
}
Point2D Point2DMultiply( Point2D *left, double v)
{
Point2D newPoint = {left->x * v, left->y * v};
return newPoint;
}
void Point2DNormalize(Point2D *point)
{
double l = sqrt(point->x * point->x + point->y * point->y);
point->x /= l;
point->y /= l;
}
typedef struct
{
Point2D points[4];
}Segment;
void SegmentCalc(Segment *seg,double t, Point2D *p)
{
double t2 = t * t;
double t3 = t2 * t;
double nt = 1.0 - t;
double nt2 = nt * nt;
double nt3 = nt2 * nt;
p->x = nt3 * seg->points[0].x + 3.0 * t * nt2 * seg->points[1].x + 3.0 * t2 * nt * seg->points[2].x + t3 * seg->points[3].x;
p->y = nt3 * seg->points[0].y + 3.0 * t * nt2 * seg->points[1].y + 3.0 * t2 * nt * seg->points[2].y + t3 * seg->points[3].y;
}
bool CalculateSpline( Point2D values[], int valuesSize, Segment bezier[])
{
int n = valuesSize - 1;
if (valuesSize < 2)
return false;
Point2D tgL= {0.0,0.0};
Point2D tgR= {0.0,0.0};
Point2D cur= {0.0,0.0};
Point2D next = Point2DSubtract(&values[1] ,&values[0]);
Point2D tmpPoint= {0.0,0.0};
Point2DNormalize(&next);
double l1 = 0.0, l2= 0.0, tmp= 0.0, x= 0.0;
--n;
for (int i = 0; i < n; ++i)
{
bezier[i].points[0] = bezier[i].points[1] = values[i];
bezier[i].points[2] = bezier[i].points[3] = values[i + 1];
cur = next;
next = Point2DSubtract(&values[i + 2],&values[i + 1]);
Point2DNormalize(&next);
tgL = tgR;
tgR = Point2DAdd(&cur,&next);
Point2DNormalize(&tgR);
if (abs(values[i + 1].y - values[i].y) < DBL_EPSILON)
{
l1 = l2 = 0.0;
}
else
{
tmp = values[i + 1].x - values[i].x;
l1 = abs(tgL.x) > DBL_EPSILON ? tmp / (2.0 * tgL.x) : 1.0;
l2 = abs(tgR.x) > DBL_EPSILON ? tmp / (2.0 * tgR.x) : 1.0;
}
if (abs(tgL.x) > DBL_EPSILON && abs(tgR.x) > DBL_EPSILON)
{
tmp = tgL.y / tgL.x - tgR.y / tgR.x;
if (abs(tmp) > DBL_EPSILON)
{
x = (values[i + 1].y - tgR.y / tgR.x * values[i + 1].x - values[i].y + tgL.y / tgL.x * values[i].x) / tmp;
if (x > values[i].x && x < values[i + 1].x)
{
if (tgL.y > 0.0)
{
if (l1 > l2)
l1 = 0.0;
else
l2 = 0.0;
}
else
{
if (l1 < l2)
l1 = 0.0;
else
l2 = 0.0;
}
}
}
}
tmpPoint = Point2DMultiply(&tgL , l1);
bezier[i].points[1] = Point2DAdd(& bezier[i].points[1],&tmpPoint);
tmpPoint = Point2DMultiply(&tgR , l2);
bezier[i].points[2] = Point2DSubtract(& bezier[i].points[2],&tmpPoint);
}
l1 = abs(tgL.x) > DBL_EPSILON ? (values[n + 1].x - values[n].x) / (2.0 * tgL.x) : 1.0;
bezier[n].points[0] = bezier[n].points[1] = values[n];
bezier[n].points[2] = bezier[n].points[3] = values[n + 1];
tmpPoint = Point2DMultiply(&tgR , l1);
bezier[n].points[1] = Point2DAdd(& bezier[n].points[1],&tmpPoint);
return true;
}
int main()
{
Point2D testValues[POINTS_LEN] = {{0.0, 0.0},
{20.0, 0.0},
{45.0, -47.0},
{53.0, 335.0},
{57.0, 26.0},
{62.0, 387.0},
{ 74.0, 104.0},
{ 89.0, 0.0},
{95.0, 100.0},
{ 100.0, 0.0} };
Segment spline[100];
Point2D p = {0.0,0.0};
CalculateSpline(testValues,POINTS_LEN, spline);
for(int i = 0; i < POINTS_LEN - 1;i++)
{
for (int j = 0; j < RESOLUTION; j++)
{
SegmentCalc(&spline[i],(double)j / (double)RESOLUTION, &p);
printf("%lf %lf\n", p.x, p.y);
}
}
printf("%lf %lf\n", testValues[POINTS_LEN - 1].x,testValues[POINTS_LEN - 1].y);
return 0;
}
Объяснение кода листинга программы
Код выполняет вычисление сплайсинга для набора точек в двумерном пространстве. Список действий:
- Включаются необходимые заголовочные файлы:
stdio.hдля работы с стандартным вводом/выводомmath.hдля работы с математическими функциямиstdlib.hдля работы с функциями стандартной библиотеки Cstdbool.hдля работы с булевыми значениямиfloat.hдля работы с плавающей точкой
- Определяются константы:
RESOLUTION- количество точек на интервале между двумя соседними точкамиPOINTS_LEN- общее количество точек
- Создается структура
Point2D, представляющая точку в двумерном пространстве - Реализуются функции для работы с точками:
Point2DAdd- добавляет две точки и возвращает их суммуPoint2DSubtract- вычитает две точки и возвращает разностьPoint2DMultiply- умножает точку на число и возвращает результатPoint2DNormalize- нормализует точку (делает ее длину равной 1)
- Создается структура
Segment, представляющая сегмент кривой - Реализуется функция
SegmentCalc, которая вычисляет значения точки на сегменте кривой для заданного параметра - Реализуется функция
CalculateSpline, которая вычисляет сплайсинг для набора точек - В функции
mainсоздается набор точекtestValues, инициализируются начальные значения для сегментов кривой - Вызывается функция
CalculateSplineдля вычисления сплайсинга - Для каждого сегмента кривой вычисляются значения точек на интервале от 0 до 1 с шагом
RESOLUTIONи выводятся на экран - Выводятся координаты последней точки
testValues[POINTS_LEN - 1] - Функция
mainвозвращает 0, что означает успешное выполнение программы