Thuật toán vẽ đường cong
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (602.43 KB, 80 trang )
ĐỒ HỌA 2DĐỒ HỌA 2D
ĐƯỜNG CONGĐƯỜNG CONG
Giảng viên : Bùi Tiến Lên
Phân loạiPhân loại
Quan điểm toán học
- Đường cong được biểu diễn bằng hàm số
- Đường cong được biểu diễn bằng phương trình tham số
Quan điểm thiết kế
-
Đường cong CAD (Computer Aided Design)
Trang
Trang Trang
Trang Trang
Trang Trang
Trang 2
22
22
22
2
-
Đường cong CAD (Computer Aided Design)
Đường cong được biểu diễn bằng Đường cong được biểu diễn bằng
hàm sốhàm số
Baứi toaựnBaứi toaựn
Input
Haứm soỏ y = f(x)
Mien ủoỏi soỏ [x
min
, x
max
]
Output
ẹo thũ haứm soỏ
Trang
Trang Trang
Trang Trang
Trang Trang
Trang 4
44
44
44
4
x
max
x
min
y=f(x)
Thuật toánThuật toán
Bước 1 : Chia miền đối số ra N
đoạn bằng nhau
Trang
Trang Trang
Trang Trang
Trang Trang
Trang 5
55
55
55
5
x
0
x
1
x
2
x
N-1
x
N
x
min
x
max
Thuaät toaùnThuaät toaùn
Böôùc 2 : Tính y
y
y
1
y
2
y
N
-
1
y
N
Trang
Trang Trang
Trang Trang
Trang Trang
Trang 6
66
66
66
6
x
0
x
1
x
2
x
N-1
x
N
x
min
x
max
y
0
y
N
-
1
Thuật toánThuật toán
Bước 3 : Kẻ đường gấp khúc đi
qua N + 1 điểm.
y
y
1
y
2
y
N
-
1
y
N
Trang
Trang Trang
Trang Trang
Trang Trang
Trang 7
77
77
77
7
x
0
x
1
x
2
x
N-1
x
N
y
0
y
N
-
1
x
min
x
max
Caøi ñaëtCaøi ñaët
// Hàm vẽ đường cong hàm số
void DrawCurve2D(CDC *pDC, TFunc2D f, double x
min
, double x
max
)
{
double ∆x, x, y;
∆x = (x
max
– x
min
)/N;
x = x
min
;
y = f(x);
pDC->MoveTo(ConvertWorldToScreen2D(x, y));
for
(
int
i=1; i<=N; i++)
Trang
Trang Trang
Trang Trang
Trang Trang
Trang 8
88
88
88
8
for
(
int
i=1; i<=N; i++)
{
x += ∆x;
y = f(x);
pDC->LineTo(ConvertWorldToScreen2D(x, y));
}
}
Caøi ñaëtCaøi ñaët
// Lớp phương trình hàm
class TFunc2D {
virtual double operator () (double x) = 0;
};
Trang
Trang Trang
Trang Trang
Trang Trang
Trang 9
99
99
99
9
Vấn đề phân đoạnVấn đề phân đoạn
Số phân đoạn N là bao nhiêu ?
độ phân giải cột
Trang
Trang Trang
Trang Trang
Trang Trang
Trang 10
1010
1010
1010
10
Ñoà thò ña thöùc baäc baÑoà thò ña thöùc baäc ba
Cho
y = ax
3
+ bx
2
+ cx + d
x ∈ [x
min
, x
max
]
[
]
4
,
4
x
3
x
2
.
0
x
2
.
0
x
1
.
0
y
2
3
−
∈
+−−=
Trang
Trang Trang
Trang Trang
Trang Trang
Trang 11
1111
1111
1111
11
[
]
4
,
4
x
−
∈
Vấn đề tính giá trò đa thứcVấn đề tính giá trò đa thức
Cách tính thông thường
a*x*x*x + b*x*x + c*x + d;
Cần 6 phép nhân và 3 phép cộng
Cách tính Horner
((a*x + b)*x + c)*x + d
Cần 3 phép nhân và 3 phép cộng
Trang
Trang Trang
Trang Trang
Trang Trang
Trang 12
1212
1212
1212
12
Cần 3 phép nhân và 3 phép cộng
Cách tính cải tiến
?
Vấn đề tính giá trò đa thứcVấn đề tính giá trò đa thức
Đa thức bậc nhất y = ax + b
Cách tính thông thường Cách tính cải tiến
y
i
= ax
i
+ b y
0
y
i+1
=
=
ax
0
+ b
y
i
+ a∆
∆∆
∆x
Tính Tính
y
=
a
x
+
b
y
=
a
x
+
b
Trang
Trang Trang
Trang Trang
Trang Trang
Trang 13
1313
1313
1313
13
y
0
=
a
x
0
+
b
y
0
=
a
x
0
+
b
y
1
= ax
1
+ b y
1
=
y
0
+ a∆
∆∆
∆x
y
2
= ax
2
+ b y
2
=
y
1
+ a∆
∆∆
∆x
y
i
= ax
i
+ b y
i
=
y
i-1
+ a∆
∆∆
∆x
y
i+1
= ax
i+1
+ b y
i+1
=
y
i
+ a∆
∆∆
∆x
y
N
= ax
N+1
+ b y
0
=
y
i
+ a∆
∆∆
∆x
Vấn đề tính giá trò đa thứcVấn đề tính giá trò đa thức
Đa thức bậc hai y = ax
2
+ bx + c
Cách tính thông thường Cách tính cải tiến
y
i
= ax
i
2
+ bx
i
+ c y
0
∆y
0
y
i+1
∆y
i+1
=
=
=
=
ax
0
2
+ bx
0
+ c
2a∆
∆∆
∆xx
0
+ a∆
∆∆
∆x
2
+ b∆
∆∆
∆x
y
i
+ ∆y
i
∆y
i
+ 2a∆
∆∆
∆x
2
Trang
Trang Trang
Trang Trang
Trang Trang
Trang 14
1414
1414
1414
14
Vấn đề tính giá trò đa thứcVấn đề tính giá trò đa thức
Đa thức bậc ba y = ax
3
+ bx
2
+ cx + d
Cách tính cải tiến
y
0
∆y
0
∆∆y
0
y
i+1
=
=
=
=
ax
0
3
+ bx
0
2
+ cx
0
+ d
3a∆
∆∆
∆xx
0
2
+ (3a∆
∆∆
∆x
2
+ 2b∆
∆∆
∆x)x
0
+ a∆
∆∆
∆x
3
+ b∆
∆∆
∆x
2
+ c∆
∆∆
∆x
6a∆
∆∆
∆x
2
x
0
+ 6a∆
∆∆
∆x
3
+ 2b∆
∆∆
∆x
2
y
i
+
∆
y
i
Trang
Trang Trang
Trang Trang
Trang Trang
Trang 15
1515
1515
1515
15
y
i+1
∆y
i+1
∆∆y
i+1
=
=
=
y
i
+
∆
y
i
∆y
i
+ ∆∆y
i
∆∆y
i
+ 6a∆
∆∆
∆x
3
Đường cong được biểu diễn bằng Đường cong được biểu diễn bằng
Phương trình tham sốPhương trình tham số
Baøi toaùnBaøi toaùn
Input:
Phöông trình tham soá
x(t)
y(t)
Mieàn tham soá
t ∈ [t
min
, t
max
]
Output:
Trang
Trang Trang
Trang Trang
Trang Trang
Trang 17
1717
1717
1717
17
Output:
(
)
(
)
(
)
( ) ( ) ( )
[ ]
π
2,0
sin5cos
cos5cos
∈
=
=
t
ttty
tttx
(
)
(
)
( ) ( )
btz
taty
tatx
=
=
=
sin
cos
Thuật toánThuật toán
Bước 1 : Chia miền tham số ra
N đoạn bằng nhau
t
t
t
t
Miền tham số
Trang
Trang Trang
Trang Trang
Trang Trang
Trang 18
1818
1818
1818
18
t
o
t
1
t
2
t
N
t
min
t
max
Thuaät toaùnThuaät toaùn
Böôùc 2 : Tính (x, y)
t
t
i
t
N
Trang
Trang Trang
Trang Trang
Trang Trang
Trang 19
1919
1919
1919
19
t
o
t
1
t
2
Thuật toánThuật toán
Bước 3 : Vẽ đường gấp khúc đi
qua N + 1 điểm
(x
2
, y
2
)
(x
N
, y
N
)
Trang
Trang Trang
Trang Trang
Trang Trang
Trang 20
2020
2020
2020
20
(x
0
, y
0
)
(x
1
, y
1
)
(x
2
, y
2
)
Caøi ñaëtCaøi ñaët
// Hàm vẽ đường cong tham số
void DrawCurve2D(CDC *pDC, TPara2D f, double t
min
, double t
max
)
{
double ∆t, t;
TPoint2D p;
∆t = (t
max
– t
min
)/N;
t = t
min
;
p = f(t);
pDC
-
>MoveTo(ConvertWorldToScreen2D(p));
Trang
Trang Trang
Trang Trang
Trang Trang
Trang 21
2121
2121
2121
21
pDC
-
>MoveTo(ConvertWorldToScreen2D(p));
for(int i=1; i<=N; i++)
{
t += ∆t;
p = f(t);
pDC->LineTo(ConvertWorldToScreen2D(p));
}
}
Caøi ñaëtCaøi ñaët
// Lớp phương trình tham số
class TPara2D {
virtual TPoint2D operator () (double t) = 0;
}
Trang
Trang Trang
Trang Trang
Trang Trang
Trang 22
2222
2222
2222
22
Vaán ñeà phaân ñoaïnVaán ñeà phaân ñoaïn
(
)
( )
[ ]
π∈
=
=
2,0t
tsinty
t
cos
t
x
Trang
Trang Trang
Trang Trang
Trang Trang
Trang 23
2323
2323
2323
23
(
)
( )
[ ]
π∈
=
=
8,0t
tsintty
t
cos
t
t
x
ÑÖÔØNG CONG BEZIERÑÖÔØNG CONG BEZIER
Ñònh nghóa ñöôøng congÑònh nghóa ñöôøng cong
Input
n +1 ñieåm ñieàu khieån {p
0
, p
1
, , p
n
}
Output
p
1
Trang
Trang Trang
Trang Trang
Trang Trang
Trang 25
2525
2525
2525
25
p
0
p
n
