thuật toán Midpoint

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down

thuật toán Midpoint

Bài gửi by nth on 19/10/09, 07:20 pm

Nội dung thuật toán là:
-Đầu tiên bạn cần có 1 cái tâm và tọa độ của nó.
-Thứ hai bạn chỉ cần vẽ 1/8 cung tròn thôi rồi bạn lấy đối xứng qua các trục tọa độ để được hình tròn hoàn thiện.
-Về thuật toán vẽ 1 cung tròn, bạn giả sử đã vẽ được điểm (x,y), cần vẽ tiếp điểm (x+dx,y+dy) kế tiếp đó.Có 4 TH xảy ra với điểm tiếp theo này, ta chỉ xét 1 TH là điểm này có dx,dy>0
thế thì chúng ta dựa vào phương trình đương tròn x2+y2=R2
thiết lập ra các điều kiện ràng buộc của dx,dy và tọa độ của điểm tiếp theo.
Theo thuật toán ta nên lấy 1 điêm có tọa độ nguyên thỏa mãn các tính chất gần với điểm cần vẽ.
-Cứ như thế cho đến khi vẽ hết cung tròn thì dừng lại.
Đây là code của thuật toán Midpoint:

// Ve 8 diem doi xung
void Put8Pixel(int x, int y)
{
putpixel(x, y, Color);
putpixel(y, x, Color);
putpixel(y, -x, Color);
putpixel(x, -y, Color);
putpixel(-x, -y, Color);
putpixel(-y, -x, Color);
putpixel(-y, x, Color);
putpixel(-x, y, Color);
} // Put8Pixel
void CircleMidPoint (int R)
{
int x, y;
x = 0;
y = R;
Put8Pixel(x, y);
p = 1 - R; // 5/4-R
while (x < y)
{
if (p < 0)
p += 2*x + 3;
else
{
p += 2*(x -y) + 5;
y--;
}
x++;
Put8Pixel(x, y);
}
} // CircleMidPoint

Thuật toán MidPoint
Do tính đối xứng của đường tròn (C) nên ta chỉ cần vẽ cung (C1/Cool là cung 1/8 đường tròn, sau đó lấy đối xứng. Cung (C1/Cool được mô tả như sau (cung của phần tô xám trong hình vẽ) :
[You must be registered and logged in to see this image.]
[You must be registered and logged in to see this image.]
Như vậy nếu có (x, y) Î (C1/Cool thì các điểm : (y, x), (y,-x), (x,-y), (-x,-y), (-y,-x), (-y,x), (-x,y) sẽ thuộc (C).
Chọn điểm bắt đầu để vẽ là điểm (0,R). Dựa vào hình vẽ, nếu là điểm nguyên đã tìm được ở bước thứ i, thì điểm ở bước thứ (i+1) là sự lựa chọn giữa S và P.
[You must be registered and logged in to see this image.]
Tương tự như thuật toán MidPoint vẽ đoạn thẳng, việc quyết định chọn một trong hai điểm S và P sẽ được thực hiện thông qua việc xét dấu của một hàm nào đó tại điểm MidPoint là điểm nằm giữa chúng.
[You must be registered and logged in to see this image.]
[You must be registered and logged in to see this image.]
Lưu đồ thuật toán
[You must be registered and logged in to see this image.]

Code chương trình
#include "iostream"
#include "conio.h"
#include "graphics.h"
#include "math.h"
int color = RED,x,y,R;
void DDX(int x,int y)
{
putpixel(x,y,color);
putpixel(y,x,color);
putpixel(y,-x,color);
putpixel(x,-y,color);
putpixel(-x,-y,color);
putpixel(-y,-x,color);
putpixel(-y,x,color);
putpixel(-x,y,color);
}
void MidPoint(int x0,int y0, int R)
{ int x,y, p;
x=0;
y=R;
DDX(x,y);
p=5/4-R;
while (x
{
if (p<0) p=p+2*x+3 ;
else
{
p= p+2*(x-y)+5;
y=y-1;
}
x=x+1;
DDX(x+x0,y+y0);
DDX(x+x0,-y+y0);
DDX(-x+x0,y+y0);
DDX(-x+x0,-y+y0);
}
}
void KhoiTao()
{ //int n,m;
int n = DETECT;
int m;
initgraph(&n,&m,"");
}
void main()
{
KhoiTao();
printf("\nNhap tam (x,y)="); scanf("%d%d",&x,&y);
printf("\nNhap ban kinh R="); scanf("%d",&R);
MidPoint(x,y,R) ;
getch();
closegraph();
}


Được sửa bởi nth ngày 10/12/09, 04:20 am; sửa lần 4.

nth
Admin
Admin

Tổng số bài gửi : 550
Số điểm : 1113
Số lần được cám ơn : 33
Ngày đến diễn đàn: : 01/08/2009
Tuổi : 28
Đến từ : Thiên Đường

Xem lý lịch thành viên http://thuhuong.hot4um.com

Về Đầu Trang Go down

Re: thuật toán Midpoint

Bài gửi by nth on 19/10/09, 07:30 pm

Một số thứ linh tinh khác chưa kiểm soát được..:
[You must be registered and logged in to see this link.]
..
Trường mình không dạy aux, mà nehe toàn nói về 3d và aux..ác thật..

nth
Admin
Admin

Tổng số bài gửi : 550
Số điểm : 1113
Số lần được cám ơn : 33
Ngày đến diễn đàn: : 01/08/2009
Tuổi : 28
Đến từ : Thiên Đường

Xem lý lịch thành viên http://thuhuong.hot4um.com

Về Đầu Trang Go down

Re: thuật toán Midpoint

Bài gửi by nth on 19/10/09, 07:57 pm

Ngoài ra có thể làm như sau: (viết bằng C#)

public void put8pixel(int x0, int y0, int x, double y, Color color)
{
SetPixel(x0 + x, (int)(y0 - y), color);

SetPixel((int)(x0 + y), y0 - x, color);

SetPixel((int)(x0 + y), y0 + x, color);

SetPixel(x0 + x, (int)(y0 + y), color);

SetPixel((int)(x0 - y), y0 + x, color);

SetPixel(x0 - x, (int)(y0 + y), color);

SetPixel(x0 - x, (int)(y0 - y), color);

SetPixel((int)(x0 - y), y0 - x, color);
}

public void DrawCircle(int x1, int y1, int x2, int y2, Color color)
{
double r;
int Dx = Math.Abs(x2 - x1);
int Dy = Math.Abs(y2 - y1);
double R = Math.Sqrt(Dx * Dx + Dy * Dy);
r = R / Math.Sqrt(2);
put8pixel(x1, y1, 0, R, color);
for (int i = 1; i < r; i++)
{
double j;
j = Math.Sqrt(Math.Pow(R, 2) - Math.Pow(i, 2));
put8pixel(x1, y1, i, Math.Round(j), color);
}
}



Được sửa bởi nth ngày 10/12/09, 04:21 am; sửa lần 1.

nth
Admin
Admin

Tổng số bài gửi : 550
Số điểm : 1113
Số lần được cám ơn : 33
Ngày đến diễn đàn: : 01/08/2009
Tuổi : 28
Đến từ : Thiên Đường

Xem lý lịch thành viên http://thuhuong.hot4um.com

Về Đầu Trang Go down

Re: thuật toán Midpoint

Bài gửi by nth on 19/10/09, 07:59 pm

Hoặc :
void HoanVi4So(int &x1, int &y1, int &x2, int &y2)
{
int a, b;
a = x1;
b = y1;

x1 = x2;
y1 = y2;

x2 = a;
y2 = b;
}

void CGraphics::DrawLine_MidPoint(int x1, int y1, int x2, int y2)
{
int Dx, Dy, p, c1, c2;
int x, y;
int i, dx, dy;

if(x1 > x2)
HoanVi4So(x1, y1, x2, y2);

Dx = x2 - x1;
Dy = y2 - y1;

dx = (Dx >= 0) ? 1 : -1;
dy = (Dy >= 0) ? 1 : -1;

Dx = abs(Dx);
Dy = abs(Dy);

p = 2*Dy - Dx;
c1 = 2*Dy;
c2 = 2*(Dy - Dx);

x = x1;
y = y1;

SetPixel(x,y);

for(i=0; i
{
if(p < 0)
p += c1;
else
{
p += c2;
y += dy;
}
x += dx;
SetPixel(x,y);
}
}


Được sửa bởi nth ngày 10/12/09, 04:22 am; sửa lần 2.

nth
Admin
Admin

Tổng số bài gửi : 550
Số điểm : 1113
Số lần được cám ơn : 33
Ngày đến diễn đàn: : 01/08/2009
Tuổi : 28
Đến từ : Thiên Đường

Xem lý lịch thành viên http://thuhuong.hot4um.com

Về Đầu Trang Go down

Re: thuật toán Midpoint

Bài gửi by nth on 07/11/09, 04:23 pm

Vẽ đường tròn bằng thuật toán MidPoint, thầy đưa vào hàm Get8Pixel

void CGraphics::Set8Pixel(int xc, int yc, int x, int y)
{
SetPixel(xc+x,yc+y);
SetPixel(xc+x,yc-y);
SetPixel(xc-x,yc+y);
SetPixel(xc-x,yc-y);
SetPixel(xc+y,yc+x);
SetPixel(xc+y,yc-x);
SetPixel(xc-y,yc+x);
SetPixel(xc-y,yc-x);
}

Vậy sao không phải là SetPixel (x, y)..hoặc là(xc, yc) và hàm chỉ đưa vào 2 tham số thôi? Mình không nói đến cách viết, mà là hỏi về ý tưởng, sao lại phải xc + rồi xc-.. Thực tế, mình viết 1 bài không dùng 2 tham số xc+x, xc-x, mà chỉ dùng x, và -x, nó vẫn vẽ dc theo thuật toán Midpoint. Bạn nào biết giải thích cho mình nghe với.

nth
Admin
Admin

Tổng số bài gửi : 550
Số điểm : 1113
Số lần được cám ơn : 33
Ngày đến diễn đàn: : 01/08/2009
Tuổi : 28
Đến từ : Thiên Đường

Xem lý lịch thành viên http://thuhuong.hot4um.com

Về Đầu Trang Go down

Re: thuật toán Midpoint

Bài gửi by nth on 07/11/09, 04:27 pm


void CGraphics::Set8Pixel(int xc, int yc, int x, int y)
{
SetPixel(xc+x,yc+y);
SetPixel(xc+x,yc-y);
SetPixel(xc-x,yc+y);
SetPixel(xc-x,yc-y);
SetPixel(xc+y,yc+x);
SetPixel(xc+y,yc-x);
SetPixel(xc-y,yc+x);
SetPixel(xc-y,yc-x);
}
void CGraphics::DrawCicle_MidPointFull(int xc, int yc, int r)
{
int x, y, p;
x = 0; y = r;
Set8Pixel(xc, yc, x, y);
p = 5/4 - r;
while(x < y)
{
if(p < 0)
p += 2*x + 3;
else
{
p += 2*(x - y) + 5;
y--;
}
x++;
Set8Pixel(xc, yc, x+xc, y+yc);
Set8Pixel(xc, yc, x+xc, -y+yc);
Set8Pixel(xc, yc, -x+xc, y+yc);
Set8Pixel(xc, yc, -x+xc, -y+yc);
}
}



Được sửa bởi nth ngày 10/12/09, 04:23 am; sửa lần 1.

nth
Admin
Admin

Tổng số bài gửi : 550
Số điểm : 1113
Số lần được cám ơn : 33
Ngày đến diễn đàn: : 01/08/2009
Tuổi : 28
Đến từ : Thiên Đường

Xem lý lịch thành viên http://thuhuong.hot4um.com

Về Đầu Trang Go down

Re: thuật toán Midpoint

Bài gửi by nth on 08/11/09, 11:59 am

Đau đầu với Đồ Họa máy tính ghê. Mà thi 20% 20 k thấy nhà trường ghi trong lịch thi nhỉ..???

===== Thành viên Forum Thien Than CNTT ====
Nothing!

(~~/)
(~'.'~)
(_(__)~~

nth
Admin
Admin

Tổng số bài gửi : 550
Số điểm : 1113
Số lần được cám ơn : 33
Ngày đến diễn đàn: : 01/08/2009
Tuổi : 28
Đến từ : Thiên Đường

Xem lý lịch thành viên http://thuhuong.hot4um.com

Về Đầu Trang Go down

Re: thuật toán Midpoint

Bài gửi by nth on 09/11/09, 08:43 pm

// Thuật toán Line MidPiont dành cho cả 8 trường hợp
void CGraphics::DrawLine_MidPoint8th(int x1, int y1, int x2, int y2)
{ int dx, dy, x, y, c1, c2, p;
dx = abs(x2 - x1);
dy = abs(y2 - y1);
p = (dy<<1) - dx;
if(abs(dx) >= abs(dy))
{ if(x1 > x2)
{ hoanvi(x1, x2);
hoanvi(y1, y2);
}
x = x1;
y = y1;
c1 = (dy<<1);//dy*2
c2 = ((dy - dx)<<1); // (dy-dx)*2
SetPixel(x, y);
while(x < x2)
{ if(p < 0) p += c1;
else
{ p += c2;
if(y1 > y2) y--;
else y++;
}
++x;
SetPixel(x, y);
}
}
else
{ if(y1 > y2)
{ hoanvi(x1, x2);
hoanvi(y1, y2);
}
x = x1; y = y1;
c1 = (dx<<1); c2 = ((dy - dx)>>1);
SetPixel(x, y);
while(y < y2)
{ if(p < 0) p += c1;
else
{ p += c2;
if(x1 > x2) x--;
else x++;
}
++y;
SetPixel(x, y);
}
}
}

// Bài này của bạn H, dù thế, H vẫn thấy ý tưởng hog khác ji cho lắm.. Đang thắc mắc là cách nào tối ưu hơn. H sẽ post lên đây các thuật toán, còn code toàn vẹn thì H sẽ post sau cùng nha.

===== Thành viên Forum Thien Than CNTT ====
Nothing!

(~~/)
(~'.'~)
(_(__)~~

nth
Admin
Admin

Tổng số bài gửi : 550
Số điểm : 1113
Số lần được cám ơn : 33
Ngày đến diễn đàn: : 01/08/2009
Tuổi : 28
Đến từ : Thiên Đường

Xem lý lịch thành viên http://thuhuong.hot4um.com

Về Đầu Trang Go down

Re: thuật toán Midpoint

Bài gửi by Sponsored content Today at 10:34 pm


Sponsored content


Về Đầu Trang Go down

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang

- Similar topics

 
Permissions in this forum:
Bạn không có quyền trả lời bài viết