ド・カステリョのアルゴリズム

ナーミー · #1

C言語の課題で、ある3次ベジエ曲線をド・カステリョのアルゴリズムで書き直せという課題が出て、調べているのですが、分かりません。
どなたか分かる方がいらしたら教えて下さい。
よろしくお願いします。
期限は3週間以内です。
C言語初心者です。

#2

課題の丸投げは禁止です。

自分でどこまでやったのか、今どこが解らないのかを明確にして下さい。
さっぱり解らず、手も足も出ない時は、その事を明記の上、
勉強方法からアドバイスを受けましょう。

(フォーラムルールより)

ナーミー · #3

すみません。
焦っていたもので。
3週間以内に仕上げないといけないので。
何か参考になるサイトがあればいいのですが・・・。

sleep · #4

ナーミーさんが書きました: ある3次ベジエ曲線をド・カステリョのアルゴリズムで書き直せという課題が出て、調べているのですが、分かりません。

ナーミーさんが書きました: 何か参考になるサイトがあればいいのですが・・・。

何が分からないのか分かりませんが、移動する点（x, y）を１つ求めるだけですよね。

参考サイト
ベジエ曲線について
中学生でもわかるベジェ曲線

ナーミーさんの課題を私がやっても仕方のないことなので、代わりにC言語以外の言語で書いたサンプルプログラムを載せておきます。
上記参考サイト「中学生でもわかるベジェ曲線」に掲載されている３次ベジェ曲線のGIFアニメの動作をスライダーバーを動かすことで確認できるものです。
移動する点 B の座標は MainWindow.xaml.cs の 67～68行目のみで計算しています。
この計算式は、上記参考サイト「ベジエ曲線について」で書かれているものと同一です。

Visual Studio 2015 Community
.NET Framework 4.6.1
C# 6.0

MainWindow.xaml

コード:

<Window x:Class="WpfApplication1.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        xmlns:d="http://schemas.microsoft.com/expression/blend/2008"
        xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"
        xmlns:local="clr-namespace:WpfApplication1"
        mc:Ignorable="d"
        Title="MainWindow" Height="350" Width="525">
    <Canvas x:Name="canvas" Visibility="Hidden">
        <Path x:Name="bezierCurve" Stroke="LightGray"/>
        <Path x:Name="path_P0P1" Stroke="LightGray"/>
        <Path x:Name="path_P1P2" Stroke="LightGray"/>
        <Path x:Name="path_P2P3" Stroke="LightGray"/>
        <Path x:Name="path_M0M1" Stroke="Blue"/>
        <Path x:Name="path_M1M2" Stroke="Blue"/>
        <Path x:Name="path_B0B1" Stroke="Red"/>
        <Path Fill="Gray">
            <Path.Data>
                <EllipseGeometry Center="{Binding P0}" RadiusX="4" RadiusY="4"/>
            </Path.Data>
        </Path>
        <Path Fill="Gray">
            <Path.Data>
                <EllipseGeometry Center="{Binding P1}" RadiusX="4" RadiusY="4"/>
            </Path.Data>
        </Path>
        <Path Fill="Gray">
            <Path.Data>
                <EllipseGeometry Center="{Binding P2}" RadiusX="4" RadiusY="4"/>
            </Path.Data>
        </Path>
        <Path Fill="Gray">
            <Path.Data>
                <EllipseGeometry Center="{Binding P3}" RadiusX="4" RadiusY="4"/>
            </Path.Data>
        </Path>
        <Path Fill="Pink">
            <Path.Data>
                <EllipseGeometry Center="{Binding M0}" RadiusX="4" RadiusY="4"/>
            </Path.Data>
        </Path>
        <Path Fill="Pink">
            <Path.Data>
                <EllipseGeometry Center="{Binding M1}" RadiusX="4" RadiusY="4"/>
            </Path.Data>
        </Path>
        <Path Fill="Pink">
            <Path.Data>
                <EllipseGeometry Center="{Binding M2}" RadiusX="4" RadiusY="4"/>
            </Path.Data>
        </Path>
        <Path Fill="Green">
            <Path.Data>
                <EllipseGeometry Center="{Binding B0}" RadiusX="4" RadiusY="4"/>
            </Path.Data>
        </Path>
        <Path Fill="Green">
            <Path.Data>
                <EllipseGeometry Center="{Binding B1}" RadiusX="4" RadiusY="4"/>
            </Path.Data>
        </Path>
        <Path Fill="Red">
            <Path.Data>
                <EllipseGeometry Center="{Binding B}" RadiusX="4" RadiusY="4"/>
            </Path.Data>
        </Path>
        <TextBlock Canvas.Left="230" Canvas.Top="270" Text="t = "/>
        <TextBlock Canvas.Left="252" Canvas.Top="270" Text="{Binding Ratio}"/>
        <Slider x:Name="slider" Canvas.Left="55" Canvas.Top="240" Minimum="0" Maximum="1" Width="400" Orientation="Horizontal" ValueChanged="slider_ValueChanged"/>
    </Canvas>
</Window>

MainWindow.xaml.cs

コード:

using System;
using System.Collections.Concurrent;    // ConcurrentDictionary
using System.ComponentModel;            // INotifyPropertyChanged, PropertyChangedEventHandler
using System.Runtime.CompilerServices;  // [CallerMemberName]

using System.Windows;
using System.Windows.Media;

namespace WpfApplication1
{
    /// <summary>
    /// MainWindow.xaml の相互作用ロジック
    /// </summary>
    public partial class MainWindow : Window, INotifyPropertyChanged
    {
        public MainWindow()
        {
            InitializeComponent();
            DataContext = this;

            Bezier_Drawing();
            Support_Drawing();

            canvas.Visibility = Visibility.Visible;
        }

        private void slider_ValueChanged(object sender, RoutedPropertyChangedEventArgs<double> e)
        {
            Ratio = e.NewValue;
            Support_Drawing();
        }

        private void Bezier_Drawing()
        {
            BezierSegment bezier = new BezierSegment();
            bezier.Point1 = P1;
            bezier.Point2 = P2;
            bezier.Point3 = P3;

            PathFigure figure = new PathFigure();
            figure.StartPoint = P0;
            figure.Segments.Add(bezier);

            PathGeometry geometry = new PathGeometry();
            geometry.Figures.Add(figure);

            bezierCurve.Data = geometry;
        }

        private void Support_Drawing()
        {
            path_P0P1.Data = new LineGeometry(P0, P1);  //P0～P1間の直線（LightGray）（描画）
            path_P1P2.Data = new LineGeometry(P1, P2);  //P1～P2間の直線（LightGray）（描画）
            path_P2P3.Data = new LineGeometry(P2, P3);  //P2～P3間の直線（LightGray）（描画）

            M0 = Distance(P0, P1);                      //移動する点 M0 の座標（Pink）（描画）
            M1 = Distance(P1, P2);                      //移動する点 M1 の座標（Pink）（描画）
            M2 = Distance(P2, P3);                      //移動する点 M2 の座標（Pink）（描画）
            path_M0M1.Data = new LineGeometry(M0, M1);  //M0～M1間の直線（Blue）（描画）
            path_M1M2.Data = new LineGeometry(M1, M2);  //M1～M2間の直線（Blue）（描画）

            B0 = Distance(M0, M1);                      //移動する点 B0 の座標（Green）（描画）
            B1 = Distance(M1, M2);                      //移動する点 B1 の座標（Green）（描画）
            path_B0B1.Data = new LineGeometry(B0, B1);  //B0～B1間の直線（Red）（描画）

            //３次ベジェ曲線の計算式
            var p_x = Math.Pow((1 - t), 3) * P0.X + 3 * Math.Pow((1 - t), 2) * t * P1.X + 3 * (1 - t) * Math.Pow(t, 2) * P2.X + Math.Pow(t, 3) * P3.X;
            var p_y = Math.Pow((1 - t), 3) * P0.Y + 3 * Math.Pow((1 - t), 2) * t * P1.Y + 3 * (1 - t) * Math.Pow(t, 2) * P2.Y + Math.Pow(t, 3) * P3.Y;
            B = new Point(p_x, p_y);                    //移動する点 B1 の座標（Red）（描画）
        }

        private Point Distance(Point P1, Point P2)
        {
            double dx = P1.X + (P2.X - P1.X) * t;
            double dy = P1.Y + (P2.Y - P1.Y) * t;
            return new Point(dx, dy);
        }

        public Point P0 { get; } = new Point(130, 210);
        public Point P1 { get; } = new Point(156, 95);
        public Point P2 { get; } = new Point(255, 44);
        public Point P3 { get; } = new Point(350, 166);

        private Point m0;
        public Point M0
        {
            get { return m0; }
            set { m0 = value; OnPropertyChanged(); }
        }
        private Point m1;
        public Point M1
        {
            get { return m1; }
            set { m1 = value; OnPropertyChanged(); }
        }
        private Point m2;
        public Point M2
        {
            get { return m2; }
            set { m2 = value; OnPropertyChanged(); }
        }
        private Point b0;
        public Point B0
        {
            get { return b0; }
            set { b0 = value; OnPropertyChanged(); }
        }
        private Point b1;
        public Point B1
        {
            get { return b1; }
            set { b1 = value; OnPropertyChanged(); }
        }
        private Point b;
        public Point B
        {
            get { return b; }
            set { b = value; OnPropertyChanged(); }
        }

        private double t = 0.0;
        public double Ratio
        {
            get { return t; }
            set { t = value; OnPropertyChanged(); }
        }

        #region INotifyPropertyChanged: OnPropertyChanged()
        public event PropertyChangedEventHandler PropertyChanged;
        private static readonly ConcurrentDictionary<string, PropertyChangedEventArgs> PropertyChangedEventArgs_Dictionary = new ConcurrentDictionary<string, PropertyChangedEventArgs>();
        private void OnPropertyChanged([CallerMemberName] string propertyName = null)
        {
            PropertyChangedEventArgs args;
            if (!PropertyChangedEventArgs_Dictionary.TryGetValue(propertyName, out args))
            {
                args = PropertyChangedEventArgs_Dictionary.GetOrAdd(propertyName, new PropertyChangedEventArgs(propertyName));
            }
            PropertyChanged?.Invoke(this, args);
        }
        #endregion
    }
}

sleep · #5

一応、計算式を利用して曲線を描画するサンプルプログラムも載せて置くことにします。

前回は既存のライブラリを利用して描いたベジェ曲線と計算式を利用して取得した座標が同じ軌道を描くことを確認できるサンプルプログラムでしたが、今回はその計算式で取得した座標を利用して単純な方法で曲線を描きます。

もし前回のサンプルコードを見て、移動する点 B が以下でも求めることができることに気付けたのであれば、おおよそ理屈は理解できたと言えます。（むしろ、Paul de Casteljauが気付いたのはこの事な訳で・・・）

コード:

B = Distance(B0, B1);

そこまで気付けた状態であれば、Wikipediaの記載内容を読んでも理解できるのではないでしょうか。

t の変化に合わせて座標をサンプリングし、曲線を描画します。

MainWindow.xaml

コード:

<Window x:Class="WpfApplication1.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        xmlns:d="http://schemas.microsoft.com/expression/blend/2008"
        xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"
        xmlns:local="clr-namespace:WpfApplication1"
        mc:Ignorable="d"
        Title="MainWindow" Height="350" Width="525">
    <Canvas>
        <local:BezierCurve t="{Binding ElementName=slider, Path=Value}"/>
        <TextBlock Canvas.Left="230" Canvas.Top="270" Text="t = "/>
        <TextBlock Canvas.Left="252" Canvas.Top="270" Text="{Binding ElementName=slider, Path=Value}"/>
        <Slider x:Name="slider" Canvas.Left="55" Canvas.Top="240" Minimum="0" Maximum="1" LargeChange="0.01" Width="400" Orientation="Horizontal"/>
    </Canvas>
</Window>

MainWindow.xaml.cs

コード:

using System;
using System.Linq;
using System.Collections.Generic;

using System.Windows;
using System.Windows.Media;

namespace WpfApplication1
{
    /// <summary>
    /// MainWindow.xaml の相互作用ロジック
    /// </summary>
    public partial class MainWindow : Window
    {
        public MainWindow()
        {
            InitializeComponent();
        }
    }

    public class BezierCurve : FrameworkElement
    {
        public static readonly DependencyProperty tProperty = DependencyProperty.Register("t", typeof(double), typeof(BezierCurve), new FrameworkPropertyMetadata(0.0, FrameworkPropertyMetadataOptions.AffectsRender));
        public double t
        {
            get { return (double)GetValue(tProperty); }
            set { SetValue(tProperty, value); }
        }

        private readonly Point P0 = new Point(130, 210);
        private readonly Point P1 = new Point(156, 95);
        private readonly Point P2 = new Point(255, 44);
        private readonly Point P3 = new Point(350, 166);

        private List<KeyValuePair<double, Point>> samplingList = new List<KeyValuePair<double, Point>> { new KeyValuePair<double, Point>(0.0, new Point(130, 210)) };
        private readonly Pen pen = new Pen(Brushes.Red, 2);

        protected override void OnRender(DrawingContext drawingContext)
        {
            var t = this.t;

            if (t > samplingList.Last().Key)
            {
                //座標計算
                var p_x = Math.Pow((1 - t), 3) * P0.X + 3 * t * Math.Pow((1 - t), 2) * P1.X + 3 * (1 - t) * Math.Pow(t, 2) * P2.X + Math.Pow(t, 3) * P3.X;
                var p_y = Math.Pow((1 - t), 3) * P0.Y + 3 * t * Math.Pow((1 - t), 2) * P1.Y + 3 * (1 - t) * Math.Pow(t, 2) * P2.Y + Math.Pow(t, 3) * P3.Y;

                //サンプリング
                samplingList.Add(new KeyValuePair<double, Point>(t, new Point(p_x, p_y)));
            }
            else
            {
                //巻き戻し
                while (samplingList.Last().Key > t)
                {
                    samplingList.Remove(samplingList.Last());
                }
            }

            //描画
            for (int i = 1; i < samplingList.Count; i++)
            {
                drawingContext.DrawLine(pen, samplingList[i - 1].Value, samplingList[i].Value);
            }
        }
    }
}

		8月 2025
日	月	火	水	木	金	土
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31

ド・カステリョのアルゴリズム

ド・カステリョのアルゴリズム

Re: ド・カステリョのアルゴリズム

Re: ド・カステリョのアルゴリズム

Re: ド・カステリョのアルゴリズム

Re: ド・カステリョのアルゴリズム