Algorithm for connecting dots on a graph with curved lines

Asked

Viewed 221 times

3

I need to develop an algorithm that connects dots in a way nonlinear, that is, with smooth curves, as in the image below:

inserir a descrição da imagem aqui

The problem is I can’t find the best solution, whether using Bezier curves, Interpolation Polimonial, Curve adjustment, among others.

In short, I need a formula that interpolates the points as shown above, generating N intermediate points between a coordinate and another.

Ex: In the above image, the first coordinate (C1) is (x=1, y=220) and the second (C2) is (x=2, y=40).

So if I want to create for example 4 intermediate coordinates between C1 and C2 I have to get an array (x, y) of 4 elements more or less like this:

[1.2, 180], [1.4, 140], [1.6, 120], [1.8, 80] 

Would anyone have any idea?

  • 1

    https://en.wikipedia.org/wiki/Hermite_interpolation

  • @Victor Stafusa, thank you, but I think I’m a few steps behind your knowledge. I’m not a mathematician, and I’m not very familiar with advanced formulas. It is easier for me to understand a code of any working language to understand the "step by step". You could help me with that?

  • For example, as in the example I put above, between the first two known points (x = 1 and x = 2), as I would calculate y when x is = 1.2, 1.4 and so on?

  • I’m also not a mathematician and I don’t know how to solve it without having to spend at least a few hours on it. I’m just pointing you in the direction that a possible solution would be to use this Hermite interpolation. The principle is that if you have n predefined points, then there is some polynomial function of degree n-1 that passes through these points, and this Hermite interpolation is used to determine what this polynomial function is. However, at least yet, I do not have sufficient knowledge to understand in depth how this interpolation works.

1 answer

0

What you want is an interpolation of the points.

This consists of finding a function f(x) that given n points P1,P2,...,Pn, f(x) pass through all points.

How is it done?

Let’s think of the simplest case, 2 points (n=2), in this case we want to find a straight (remember, there is always a straight that goes through 2 points not coincidental), a straight is a function of the form

f(x) = Ax + b

Note that f(x) is a polynomial of degree 1, in the case of polynomial interpolation, we want f(x) to be a polynomial of lesser degree possible.

There are several interpolation algorithms, you can find their description here, but most languages already have a lib with this implemented

https://en.wikipedia.org/wiki/Newton_polynomial

https://en.wikipedia.org/wiki/Lagrange_polynomial

  • Thank you, I’ve already developed an algorithm with Bicubic Polynomial Interpolation.

Browser other questions tagged

You are not signed in. Login or sign up in order to post.