Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#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;
}
@absltn

This comment has been minimized.

Copy link

commented Oct 3, 2016

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

спасибо за ваш код, однако, в моей 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

This comment has been minimized.

Copy link

commented Apr 4, 2017

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

@eitijupaenoithoowohd

This comment has been minimized.

Copy link

commented May 29, 2017

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

@eitijupaenoithoowohd

This comment has been minimized.

Copy link

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

This comment has been minimized.

Copy link

commented May 29, 2017

https://github.com/eitijupaenoithoowohd/TBezierInterpolation

  • Bugfixes for C++
  • Pure C language code
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.