Instantly share code, notes, and snippets.

# /TBezierInterpolation.cpp

Created August 4, 2015 14:18
Show Gist options
• Save anonymous/06f4104d93f6cef6f341 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 #include #include #include 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 &values, vector &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 testValues; vector 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; }

### absltn commented Oct 3, 2016 • edited

Привет, Анна,

спасибо за ваш код, однако, в моей MSVS 2010 он частично некорректен (версия ниже C11)... Убрал директиву using namespace std, определил векторы явно как std::vector. Далее, auto в '<C11 не является универсальным типом. Все вроде поправил, но остается:

`s.calc((double)i / (double)RESOLUTION, p); cout << p.x << " " << p.y << endl;`

здесь, по совету со Stackoverflow, я добавил `s.template`, однако, ошибка сохраняется. Прошу Вас подсказать, какую корректировку я не учел? =)

### Deshrezine commented Apr 4, 2017

Здравствуйте.
На точках:
20.97 8668.515
20.98 8695.611
20.99 8655.389
Выводит какую-то дичь. Можете подсказать, в чем может быть проблема, пожалуйста?

### eitijupaenoithoowohd commented May 29, 2017

В коде используется функция abs(), которая работает с целочисленными аргументами. Компилятор проглатывает, но лучше исправить на fabs()

### eitijupaenoithoowohd commented May 29, 2017

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

``````g++ -pipe -std=c++11 -g -ggdb -ggdb3 -O0 -DDEBUG -finline-functions -Wall -Wextra -Wpedantic -Wshadow -Wconversion -Wsign-conversion -Winit-self -Wunreachable-code -Wformat-y2k -Wformat-nonliteral -Wformat-security -Wmissing-include-dirs -Wswitch-default -Wtrigraphs -Wstrict-overflow=5 -Wfloat-equal -Wundef -Wshadow -Wcast-qual -Wcast-align -Wwrite-strings -Winline -Wsuggest-attribute=const -Wsuggest-attribute=pure -Wsuggest-attribute=noreturn -Wsuggest-attribute=format -Wmissing-format-attribute -Wlogical-op -o TBezierInterpolation TBezierInterpolation.cpp -lm
TBezierInterpolation.cpp: In function ‘bool calculateSpline(const std::vector<Point2D>&, std::vector<Segment>&)’:
TBezierInterpolation.cpp:51:27: warning: conversion to ‘int’ from ‘std::vector<Point2D>::size_type {aka long unsigned int}’ may alter its value [-Wconversion]
int n = values.size() - 1;
^
TBezierInterpolation.cpp:56:20: warning: conversion to ‘std::vector<Segment>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
bezier.resize(n);
^
TBezierInterpolation.cpp:70:17: warning: conversion to ‘std::vector<Segment>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
bezier[i].points[0] = bezier[i].points[1] = values[i];
^
TBezierInterpolation.cpp:70:39: warning: conversion to ‘std::vector<Segment>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
bezier[i].points[0] = bezier[i].points[1] = values[i];
^
TBezierInterpolation.cpp:70:61: warning: conversion to ‘std::vector<Point2D>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
bezier[i].points[0] = bezier[i].points[1] = values[i];
^
TBezierInterpolation.cpp:71:17: warning: conversion to ‘std::vector<Segment>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
bezier[i].points[2] = bezier[i].points[3] = values[i + 1];
^
TBezierInterpolation.cpp:71:39: warning: conversion to ‘std::vector<Segment>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
bezier[i].points[2] = bezier[i].points[3] = values[i + 1];
^
TBezierInterpolation.cpp:71:62: warning: conversion to ‘std::vector<Point2D>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
bezier[i].points[2] = bezier[i].points[3] = values[i + 1];
^
TBezierInterpolation.cpp:74:25: warning: conversion to ‘std::vector<Point2D>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
next = values[i + 2] - values[i + 1];
^
TBezierInterpolation.cpp:74:41: warning: conversion to ‘std::vector<Point2D>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
next = values[i + 2] - values[i + 1];
^
TBezierInterpolation.cpp:82:27: warning: conversion to ‘std::vector<Point2D>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
if (fabs(values[i + 1].y - values[i].y) < EPSILON)
^
TBezierInterpolation.cpp:82:44: warning: conversion to ‘std::vector<Point2D>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
if (fabs(values[i + 1].y - values[i].y) < EPSILON)
^
TBezierInterpolation.cpp:88:28: warning: conversion to ‘std::vector<Point2D>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
tmp = values[i + 1].x - values[i].x;
^
TBezierInterpolation.cpp:88:45: warning: conversion to ‘std::vector<Point2D>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
tmp = values[i + 1].x - values[i].x;
^
TBezierInterpolation.cpp:98:31: warning: conversion to ‘std::vector<Point2D>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
x = (values[i + 1].y - tgR.y / tgR.x * values[i + 1].x - values[i].y + tgL.y / tgL.x * values[i].x) / tmp;
^
TBezierInterpolation.cpp:98:65: warning: conversion to ‘std::vector<Point2D>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
x = (values[i + 1].y - tgR.y / tgR.x * values[i + 1].x - values[i].y + tgL.y / tgL.x * values[i].x) / tmp;
^
TBezierInterpolation.cpp:98:82: warning: conversion to ‘std::vector<Point2D>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
x = (values[i + 1].y - tgR.y / tgR.x * values[i + 1].x - values[i].y + tgL.y / tgL.x * values[i].x) / tmp;
^
TBezierInterpolation.cpp:98:112: warning: conversion to ‘std::vector<Point2D>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
x = (values[i + 1].y - tgR.y / tgR.x * values[i + 1].x - values[i].y + tgL.y / tgL.x * values[i].x) / tmp;
^
TBezierInterpolation.cpp:99:33: warning: conversion to ‘std::vector<Point2D>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
if (x > values[i].x && x < values[i + 1].x)
^
TBezierInterpolation.cpp:99:53: warning: conversion to ‘std::vector<Point2D>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
if (x > values[i].x && x < values[i + 1].x)
^
TBezierInterpolation.cpp:119:17: warning: conversion to ‘std::vector<Segment>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
bezier[i].points[1] += tgL * l1;
^
TBezierInterpolation.cpp:120:17: warning: conversion to ‘std::vector<Segment>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
bezier[i].points[2] -= tgR * l2;
^
TBezierInterpolation.cpp:123:44: warning: conversion to ‘std::vector<Point2D>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
l1 = fabs(tgL.x) > EPSILON ? (values[n + 1].x - values[n].x) / (2.0 * tgL.x) : 1.0;
^
TBezierInterpolation.cpp:123:61: warning: conversion to ‘std::vector<Point2D>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
l1 = fabs(tgL.x) > EPSILON ? (values[n + 1].x - values[n].x) / (2.0 * tgL.x) : 1.0;
^
TBezierInterpolation.cpp:125:13: warning: conversion to ‘std::vector<Segment>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
bezier[n].points[0] = bezier[n].points[1] = values[n];
^
TBezierInterpolation.cpp:125:35: warning: conversion to ‘std::vector<Segment>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
bezier[n].points[0] = bezier[n].points[1] = values[n];
^
TBezierInterpolation.cpp:125:57: warning: conversion to ‘std::vector<Point2D>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
bezier[n].points[0] = bezier[n].points[1] = values[n];
^
TBezierInterpolation.cpp:126:13: warning: conversion to ‘std::vector<Segment>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
bezier[n].points[2] = bezier[n].points[3] = values[n + 1];
^
TBezierInterpolation.cpp:126:35: warning: conversion to ‘std::vector<Segment>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
bezier[n].points[2] = bezier[n].points[3] = values[n + 1];
^
TBezierInterpolation.cpp:126:58: warning: conversion to ‘std::vector<Point2D>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
bezier[n].points[2] = bezier[n].points[3] = values[n + 1];
^
TBezierInterpolation.cpp:127:13: warning: conversion to ‘std::vector<Segment>::size_type {aka long unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
bezier[n].points[1] += tgR * l1;
^

``````

### eitijupaenoithoowohd commented May 29, 2017 • edited

https://github.com/eitijupaenoithoowohd/TBezierInterpolation

• Bugfixes for C++
• Pure C language code