Các Vị Trí Đối Xứng Trên Đường Tròn (C) Tương Ứng Với (X,y)

Ta có dạng tổng quát của phương trình đường thẳng:

Ax  By  C  0

với Đặt

A  y2  y1 , B x 2  x1 , C  x 2 y1  x1 y2

Fx, y Ax  By  C , ta có nhận xét :

<0 Nếu (x, y) nằm phía trên đường thẳng

Fx,y=0 Nếu x, y thuộc đường thẳng

>0 Nếu x, y nằm phía dưới đường thẳng

Lúc này việc chọn các điểm S, P ở trên được đưa về việc xét dấu của

p  2FMidPoint



2 x

Fi



 1, yi

1 .

2



Nếu pi  0 , điểm MidPoint nằm phía trên đoạn thẳng. Lúc này điểm thực Q

nằm dưới điểm MidPoint nên ta chọn S, tức là

yi1  yi .

Ngược lại, nếu pi  0 , điểm MidPoint nằm phía dưới đoạn thẳng. Lúc này điểm

thực Q nằm trên điểm MidPoint nên ta chọn P, tức là Mặt khác:

yi1  yi 1.

p  p

 2F x

 1, y

1  2F x  1, y 1 

i1 i

i1



i1 i i 



 p  p 

1

1 



1

1 

i1

i 2A x i1



Byi1



 C



2A x i



B yi



 C



 pi1

 pi

 2A  2By

i1

 yi

 2Dy  2Dxy

i1

 yi 

Vậy:

pi1  pi  2Dy , nếu

pi  0 do ta chọn yi1  yi .

pi1  pi  2Dy  2Dx , nếu

pi  0

do ta chọn yi1  yi  1.

Ta tính giá trị

p0 ứng với điểm ban đầu x 0 , y0 : vì x 0 , y0 là điểm thuộc đoạn

thẳng nên Ax0  By 0  C  0

p 

 1, y

1 

 1

1 

0 2F x 0



0  2A x 0



B y0



 C



 p0 2Ax0 By0 C 2A  B  2A  B  2Dy  Dx

Nhận xét: Thuật toán MidPoint cho kết quả tương tự như thuật toán Bresenham.

2.4. Giải thuật sinh đường tròn

2.4.1 Nguyên lý chung

Phương trình đường tròn có tâm là gốc tọa độ, bán kính R là:

x2  y2  R2 . Từ

R 2  x2

phương trình này ta có thể đưa về dạng y 

. Để vẽ các đường tròn có tâm

xC, yCbất kì, đơn giản chỉ cần tịnh tiến các điểm sau khi vẽ xong đường tròn có tâm là gốc tọa độ theo vector tịnh tiến xC, yC.

Do tính đối xứng nên để vẽ toàn bộ đường tròn, ta chỉ cần vẽ cung ¼ đường tròn sau đó lấy đối xứng để xác định các điểm còn lại.

Một trong những cách đơn giản nhất là cho x chạy từ 0 đến R, sau đó tính y từ công thức trên (chỉ lấy giá trị dương) rồi làm tròn để xác định giá trị nguyên tương ứng. Cách làm này không hiệu quả do gặp phải các phép toán nhân và lấy căn làm hạn

chế tốc độ, ngoài ra đường tròn vẽ ra theo cách này có thể không liền nét (trừ trường hợp R lớn) khi x gần R (do chỉ có một giá trị y duy nhất cho một giá trị x). Chúng ta có thể khắc phục điều này bằng cách điều chỉnh đối tượng thay đổi là x (rồi tính y theo x) hay y (rồi tính x theo y) tùy vào giá trị tuyệt đối của hệ số góc đường tròn là lớn hơn hay nhỏ hơn 1, nhưng cách làm này đòi hỏi thêm các phép tính toán và kiểm tra nên làm cho thuật toán phức tạp thêm (hình 2.12)

Một cách tiếp cận khác là vẽ các điểm

Rcosθ, Rsinθ,

với θ chạy từ 00 đến

900. Cách này sẽ khắc phục hạn chế đường không liền nét của thuật toán trên, tuy nhiên điểm hạn chế chính của thuật toán này đó là chọn bước nhảy cho θ như thế nào cho phù hợp khi bán kính thay đổi.

(0,17)

(17,0)

Hình 2.13Đường tròn vẽ ra không liền nét

2.4.2 Thuật toán MidPoint

(-x,y)

(x,y)

(-y,x)

(y,x)

(-y,-x)

2 (y,-x)

(-x,-y)

(x,-y)

Do tính đối xứng của đường tròn (C) nên ta chỉ cần vẽ cung (C1/8) là cung 1/8 đường tròn, sau đó lấy đối xứng. Cung (C1/8) được mô tả như sau (cung của phần tô xám trong hình vẽ):



0 x R

 2





R y R

 2

Hình 2.14 Các vị trí đối xứng trên đường tròn (C) tương ứng với (x,y)

Như vậy nếu có (x, y)  (C1/8) 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 x , y là điểm

nguyên đã tìm được ở bước thứ i, thì điểm xi1, yi1 ở bước thứ (i+1) là sự lựa chọn giữa S và P.

Hình 2.15 Thuật toán MidPoint vẽ đường tròn

xi1  xi  1



Như vậy: y

 yi

 1

i1 

i

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.

Đặt

Fx, y x 2  y2 R 2 , ta có :

<0 Nếu (x, y) nằm trong đường tròn Fx,y=0 Nếu x, y nằm trên đường tròn

>0 Nếu x, y nằm ngoài đường tròn

Xét pi

 FMidPoint F x



i

 1, yi

1  . Ta có:

2



Nếu

pi  0 , điểm MidPoint nằm trong đường tròn. Lúc này điểm thực Q gần S

hơn nên ta chọn S, tức là yi1  yi .

Ngược lại, nếu pi  0 , điểm MidPoint nằm ngoài đường tròn. Lúc này điểm thực Q gần P hơn nên ta chọn P, tức là yi1  yi  1.

Mặt khác:

p  p

 F x

 1, y

1  F x  1, y 1 

i1 i

i1



i1 i i 



2 1

22 1



 pi1  pi

 x i1 1  yi 1 2 

 R  x i 1  yi 2  R 



2 1





22 1

 pi 1  pi

 x i  2  yi1 2  R  x i 1  yi 2  R 

 pi1  pi



 2x i  3 y  y y

2 2

i1



 yi 



Vậy:

pi1  pi  2xi  3, nếu

pi  0 do ta chọn yi1  yi .

pi1  pi  2xi  2yi  5, nếu

pi  0

do ta chọn yi1  yi  1.

Ta tính giá trị p0ứng với điểm ban đầu x0,y0

được suy ra là (1, R – 1/2). Theo công thức:

là (0, R) và trung điểm tiếp theo



p  F x

0 0

 1, y0

1 

2



 F1, R 1 





= 1 + (R2 – R + 1/4) –R2

= 5  R 4

Lưu đồ thuật toán và chương trình cài đặt thuật toán MidPoint vẽ đường tròn

// Giải thuật vẽ 8 điểm đối xứng

procedureput8Pixel(x, y, Color: integer)

{

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);