How to resolve the algorithm Bernstein basis polynomials step by step in the ObjectIcon programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Bernstein basis polynomials step by step in the ObjectIcon programming language
Table of Contents
Problem Statement
The
n + 1
{\displaystyle n+1}
Bernstein basis polynomials of degree
n
{\displaystyle n}
are defined as Any real polynomial can written as a linear combination of such Bernstein basis polynomials. Let us call the coefficients in such linear combinations Bernstein coefficients. The goal of this task is to write subprograms for working with degree-2 and degree-3 Bernstein coefficients. A programmer is likely to have to deal with such representations. For example, OpenType fonts store glyph outline data as as either degree-2 or degree-3 Bernstein coefficients. The task is as follows: ALGOL 60 and Python implementations are provided as initial examples. The latter does the optional monomial-basis evaluations. You can use the following algorithms. They are written in unambiguous Algol 60 reference language instead of a made up pseudo-language. The ALGOL 60 example was necessary to check my work, but these reference versions are in the actual standard language designed for the printing of algorithms.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Bernstein basis polynomials step by step in the ObjectIcon programming language
Source code in the objecticon programming language
#!/bin/env oiscript
import
io(),
ipl.lists(list2str)
final abstract class Bernstein ()
public static from_monomial_degree2 (a0_a1_a2)
# Subprogram (1): transform monomial coefficients [a0, a1, a2] to
# Bernstein coefficients [b0, b1, b2].
local a0, a1, a2
a0 := a0_a1_a2[1]; a1 := a0_a1_a2[2]; a2 := a0_a1_a2[3]
return [a0, a0 + (0.5 * a1), a0 + a1 + a2]
end
public static evaluate_degree2 (b0_b1_b2, t)
# Subprogram (2): evaluate, at t, the polynomial with Bernstein
# coefficients [b0, b1, b2]. Use de Casteljau's
# algorithm.
local b0, b1, b2
local s, b01, b12, b012
b0 := b0_b1_b2[1]; b1 := b0_b1_b2[2]; b2 := b0_b1_b2[3]
s := 1 - t
b01 := (s * b0) + (t * b1)
b12 := (s * b1) + (t * b2)
b012 := (s * b01) + (t * b12)
return b012
end
public static from_monomial_degree3 (a0_a1_a2_a3)
# Subprogram (3): transform monomial coefficients [a0, a1, a2, a3]
# to Bernstein coefficients [b0, b1, b2, b3].
local a0, a1, a2, a3
a0 := a0_a1_a2_a3[1]; a1 := a0_a1_a2_a3[2]
a2 := a0_a1_a2_a3[3]; a3 := a0_a1_a2_a3[4]
#
# In Object Icon, the same symbol / is used for both floating
# point and integer division. Thus you will get the WRONG result
# if you write 1/3 instead of 1.0/3.0, etc. (This is
# error-encouraging language design but true of many languages. I
# fell victim while writing this code.)
#
return [a0, a0 + ((1.0 / 3.0) * a1),
a0 + ((2.0 / 3.0) * a1) + ((1.0 / 3.0) * a2),
a0 + a1 + a2 + a3]
end
public static evaluate_degree3 (b0_b1_b2_b3, t)
# Subprogram (4): evaluate, at t, the polynomial with Bernstein
# coefficients [b0, b1, b2, b3]. Use de Casteljau's
# algorithm.
local b0, b1, b2, b3
local s, b01, b12, b23, b012, b123, b0123
b0 := b0_b1_b2_b3[1]; b1 := b0_b1_b2_b3[2]
b2 := b0_b1_b2_b3[3]; b3 := b0_b1_b2_b3[4]
s := 1 - t
b01 := (s * b0) + (t * b1)
b12 := (s * b1) + (t * b2)
b23 := (s * b2) + (t * b3)
b012 := (s * b01) + (t * b12)
b123 := (s * b12) + (t * b23)
b0123 := (s * b012) + (t * b123)
return b0123
end
public static degree2_to_degree3 (q0_q1_q2)
# Subprogram (5): transform the quadratic Bernstein coefficients
# [q0, q1, q2] to the cubic Bernstein coefficients
# [c0, c1, c2, c3].
local q0, q1, q2
q0 := q0_q1_q2[1]; q1 := q0_q1_q2[2]; q2 := q0_q1_q2[3]
return [q0, ((1.0 / 3.0) * q0) + ((2.0 / 3.0) * q1),
((2.0 / 3.0) * q1) + ((1.0 / 3.0) * q2), q2]
end
end # final abstract class Bernstein
final abstract class Monomial ()
public static evaluate_degree2 (a0_a1_a2, t)
# Evaluate, at t, the polynomial with monomial coefficients [a0,
# a1, a2].
local a0, a1, a2
a0 := a0_a1_a2[1]; a1 := a0_a1_a2[2]; a2 := a0_a1_a2[3]
return a0 + (t * (a1 + (t * a2))) # Horner form.
end
public static evaluate_degree3 (a0_a1_a2_a3, t)
# Evaluate, at t, the polynomial with monomial coefficients [a0,
# a1, a2, a3].
local a0, a1, a2, a3
a0 := a0_a1_a2_a3[1]; a1 := a0_a1_a2_a3[2]
a2 := a0_a1_a2_a3[3]; a3 := a0_a1_a2_a3[4]
return a0 + (t * (a1 + (t * (a2 + (t * a3))))) # Horner form.
end
end # final abstract class Monomial
procedure lstr (lst)
return "[" || list2str (lst, ", ") || "]"
end
procedure main ()
local x
local pmono2, qmono2, pbern2, qbern2
local pmono3, qmono3, rmono3, pbern3, qbern3, rbern3
local pbern3a, qbern3a
#
# For the following polynomials, use Subprogram (1) to find
# coefficients in the degree-2 Bernstein basis:
#
# p(x) = 1
# q(x) = 1 + 2x + 3x²
#
# Display the results.
#
pmono2 := [1, 0, 0]
qmono2 := [1, 2, 3]
pbern2 := Bernstein.from_monomial_degree2 (pmono2)
qbern2 := Bernstein.from_monomial_degree2 (qmono2)
io.write ("Subprogram (1) examples:")
io.write (" mono ", lstr (pmono2), " --> bern ", lstr (pbern2))
io.write (" mono ", lstr (qmono2), " --> bern ", lstr (qbern2))
#
# Use Subprogram (2) to evaluate p(x) and q(x) at x = 0.25, 7.50.
# Display the results. Optionally also display results from
# evaluating in the original monomial basis.
#
io.write ("Subprogram (2) examples:")
every x := 0.25 | 7.50 do
io.write (" p(", x, ") = ",
Bernstein.evaluate_degree2 (pbern2, x),
" (mono: ",
Monomial.evaluate_degree2 (pmono2, x), ")")
every x := 0.25 | 7.50 do
io.write (" q(", x, ") = ",
Bernstein.evaluate_degree2 (qbern2, x),
" (mono: ",
Monomial.evaluate_degree2 (qmono2, x), ")")
#
# For the following polynomials, use Subprogram (3) to find
# coefficients in the degree-3 Bernstein basis:
#
# p(x) = 1
# q(x) = 1 + 2x + 3x²
# r(x) = 1 + 2x + 3x² + 4x³
#
# Display the results.
#
pmono3 := [1, 0, 0, 0]
qmono3 := [1, 2, 3, 0]
rmono3 := [1, 2, 3, 4]
pbern3 := Bernstein.from_monomial_degree3 (pmono3)
qbern3 := Bernstein.from_monomial_degree3 (qmono3)
rbern3 := Bernstein.from_monomial_degree3 (rmono3)
io.write ("Subprogram (3) examples:")
io.write (" mono ", lstr (pmono3), " --> bern ", lstr (pbern3))
io.write (" mono ", lstr (qmono3), " --> bern ", lstr (qbern3))
io.write (" mono ", lstr (rmono3), " --> bern ", lstr (rbern3))
#
# Use Subprogram (4) to evaluate p(x), q(x), and r(x) at x = 0.25,
# 7.50. Display the results. Optionally also display results from
# evaluating in the original monomial basis.
#
io.write ("Subprogram (4) examples:")
every x := 0.25 | 7.50 do
io.write (" p(", x, ") = ",
Bernstein.evaluate_degree3 (pbern3, x),
" (mono: ",
Monomial.evaluate_degree3 (pmono3, x), ")")
every x := 0.25 | 7.50 do
io.write (" q(", x, ") = ",
Bernstein.evaluate_degree3 (qbern3, x),
" (mono: ",
Monomial.evaluate_degree3 (qmono3, x), ")")
every x := 0.25 | 7.50 do
io.write (" r(", x, ") = ",
Bernstein.evaluate_degree3 (rbern3, x),
" (mono: ",
Monomial.evaluate_degree3 (rmono3, x), ")")
#
# For the following polynomials, using the result of Subprogram (1)
# applied to the polynomial, use Subprogram (5) to get coefficients
# for the degree-3 Bernstein basis:
#
# p(x) = 1
# q(x) = 1 + 2x + 3x²
#
# Display the results.
#
io.write ("Subprogram (5) examples:")
pbern3a := Bernstein.degree2_to_degree3 (pbern2)
qbern3a := Bernstein.degree2_to_degree3 (qbern2)
io.write (" bern ", lstr (pbern2), " --> bern ", lstr (pbern3a))
io.write (" bern ", lstr (qbern2), " --> bern ", lstr (qbern3a))
end
You may also check:How to resolve the algorithm Vector products step by step in the Crystal programming language
You may also check:How to resolve the algorithm Map range step by step in the ALGOL 68 programming language
You may also check:How to resolve the algorithm Jump anywhere step by step in the Wren programming language
You may also check:How to resolve the algorithm A+B step by step in the Robotic programming language
You may also check:How to resolve the algorithm Handle a signal step by step in the Jsish programming language