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?

algorithm mathematics graphic
  • 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 algorithm mathematics graphic

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