Bài tập về đồ họa pascal ! Giúp em với!

[bete]

Trước hết xin cám ơn bạn Mach2 đã chỉ ra 1 tài liệu rất lý thú.
Đọc xong thì thấy cách của tui là của Chrystal-Peirce nhưng tài liệu trình bày gọn gàng hơn nhiều lắm

Tui xin thử nói hướng làm của tui:

S: tập hợp các điểm đã cho

1) Bắt đầu: vẽ 1 đường tròn T đủ lớn để chứa tất cả các điểm thuộc S. Xét xmax, xmin, ymax, ymin => hình chữ nhựt ABCD chứa mọi điểm thuộc S: vẽ đường tròn ngoại tiếp hình chữ nhựt này

2) Thu nhỏ đường tròn T để chứa 3 điểm thuộc S:

Xét hình chữ nhựt ABCD:

a) Nếu không có đỉnh nào thuộc S: thu nhỏ T theo dây cung AB (AB là cạnh ngắn của hình chữ nhựt). Quay lại 2.

b) Nếu chỉ có đúng 1 đỉnh A thuộc S: thu nhỏ T theo dây cung AB (AB là cạnh ngắn của hình chữ nhựt). Quay lại 2.

c) Nếu chỉ có 2 đỉnh kề nhau A và B thuộc S (AB không là đường kính của T): thu nhỏ T theo dây cung AB. Quay lại 2.

d) Nếu có 2 đỉnh đối nhau A và C thuộc S (=> AB là đường kính): T chính là đường tròn cần tìm => ngưng tại đây.

3) Nếu có ít nhứt 3 điểm thuộc S nằm trên đường tròn T thì:

a) Nếu T chứa 2 điểm (thuộc S) nào đó thỏa: 2 điểm này là đường kính của T => T chính là đường tròn cần tìm => ngưng tại đây.

b) Nếu T chứa 3 điểm (thuộc S) nào đó thỏa: 3 điểm này tạo thành 1 tam giác không chứa góc tù (chỉ chứa góc vuông hoặc góc nhọn) => T chính là đường tròn cần tìm => ngưng tại đây.

c) Nếu T chứa 3 điểm (thuộc S) nào đó thỏa: 3 điểm này tạo thành 1 tam giác chứa 1 góc tù => thu nhỏ T lại (theo cạnh đối của góc tù) và lặp lại bước 3

*** thủ tục con: thu nhỏ đường tròn T theo dây cung AB (=> đường tròn mới là đường tròn nhỏ nhứt trong mọi đường tròn thỏa: đi qua A, B và chứa mọi điểm thuộc S).

Giả sử T đi qua 2 điểm A và B (không bắt buộc phải thuộc S). Đặt S2 là là tập hợp các điểm thuộc S và nhìn AB dưới 1 góc nhọn hoặc vuông.

Nếu tập hợp S2 là rỗng (mọi điểm thuộc S đều nhìn AB dưới 1 góc tù) => đường tròn mới T' sẽ lấy AB làm đường kính.

Nếu S2 không là rỗng: chọn P thuộc S2 thỏa: góc APB là nhỏ nhứt (trong tất cả các điểm thuộc S2) => đường tròn mới T' sẽ đi qua 3 điểm A, B và P.

***** Một vài điểm cần chứng minh trong thuật giải:

I) thủ tục thu nhỏ đường tròn T (chứa mọi điểm thuộc S) theo dây cung AB sẽ cho đường tròn mới T' thỏa: T' đi qua A và B và T' chứa mọi điểm thuộc S. Hơn nữa, gọi S3 là tập hợp các đường tròn đi qua A, B và chứa mọi điểm thuộc S. T' sẽ là phần tử nhỏ nhứt (và duy nhứt) trong S3. Và nếu điểm được chọn P nằm trên T thì T = T'; còn nếu điểm được chọn P nằm trong T thì T > T'

a) T' đi qua AB và T' chứa mọi điểm thuộc S.

Xét trường hợp AB là đường kính của T' (S2 là rỗng; mọi điểm thuộc S đều nhìn dây cung AB dưới 1 góc tù)
Phản chứng: giả sử có 1 điểm Q thuộc S và Q nằm ngoài T'
=> góc AQB là nhọn (những điểm nằm trên T' sẽ nhìn đường kính AB dưới 1 góc vuông; nằm trong T' => góc tù; nằm ngoài T' => góc nhọn)
=> mâu thuẫn với việc mọi điểm thuộc S đều nhìn dây cung AB dưới 1 góc tù

Xét trường hợp AB không là đường kính của T' (S2 không rỗng).
Phản chứng: giả sử có 1 điểm Q thuộc S và Q nằm ngoài T'
Nếu góc AQB là góc nhọn:
=> góc AQB < góc APB
=> mâu thuẫn với sự chọn lựa: góc APB là nhỏ nhứt trong các điểm thuộc S2
Nếu góc AQB là góc tù:
=> góc AQB > góc ARB
=> góc APB < góc ANB
= mâu thuẫn với việc P nằm trong T

b) T' là phần tử nhỏ nhứt trong S3 (tập hợp các đường tròn qua A, B và chứa mọi điểm thuộc S).

Phản chứng: giả sử có 1 đường tròn T" qua A, B, T" chứa mọi điểm thuộc S và T" < T'

Xét trường hợp AB là đường kính của T': T" chứa A và B
=> đường kính của T" phải lớn hơn AB
=> mâu thuẫn với T" < T

Xét trường hợp AB không là đường kính của T': T" chứa điểm được chọn P
=> E nằm ngoài HD
=> O' nằm ngoài HO (HO' > HO)
=> O'A (bán kính của T") > OA (bán kính của T')
=> mâu thuẫn với việc T" < T'

Vậy T' là phần tử nhỏ nhứt trong S3. Và vì T' lấy AB làm đường kính hoặc T' đi qua 3 điểm phân biệt A, B và P => T' là duy nhứt

c) T >= T':

Xét trường hợp AB là đường kính của T' (S2 là rỗng): đường kính của T >= dây cung AB của T. Mà AB là đưỡng kính của T' => T >= T

Xét trường hợp AB không là đường kính của T' (S2 không rỗng)

Nếu điểm được chọn P nằm trên T thì T = T': vì T và T' cùng đi qua 3 điểm phân biệt A, B và P

Còn nếu điểm được chọn P nằm trong T thì T > T': chứng minh tương tự như phần (Ib)

II) Thuật toán sẽ ngưng sau 1 số hữu hạn bước

* Bắt đầu ở bước 1 => sẽ rơi vô 1 trong 4 trường hợp:

2a) không có đỉnh nào thuộc S: AB là cạnh ngắn => mọi điểm trên cạnh đối CD nhìn AB dưới 1 góc nhọn. Có ít nhứt 1 điểm (thuộc S) nằm trên cạnh đối CD => thủ tục thu nhỏ đường tròn T sẽ chọn ra được ít nhứt 1 điểm P thuộc S và đường tròn mới T' đi qua điểm này => chuyển qua 2b

2b) chỉ có đúng 1 đỉnh A thuộc S: tương tự như ở 2a, vì AB là cạnh ngắn => thủ tục thu nhỏ đường tròn T sẽ chọn ra được ít nhứt 1 điểm P thuộc S và đường tròn mới T' đi qua P (và A) => chuyển qua 2c hoặc 2d

2c) chỉ có 2 đỉnh kề nhau A và B thuộc S, AB không là đường kính của T: sau khi gọi thủ tục thu nhỏ đường tròn mình sẽ rơi vào 1 trong 2 trường hợp:

mọi điểm thuộc S đều nhìn AB dưới 1 góc tù (AB sẽ là đường kính của T') => chuyển qua 2d;

hoặc chọn được điểm P thuộc S sao cho đường tròn mới đi qua P (và A, B) => chuyển qua 3

2d) A,B thuộc S và AB là đường kính của T: mình sẽ ngưng thuật toán (lời giải sẽ là T).

* Nếu mình qua được bước 3 (không ngưng ở bước 2d): đường tròn T đã chứa 3 điểm thuộc S

Gọi A, B là điểm bất kỳ thuộc S và mình sẽ thu nhỏ đường tròn theo dây cung AB. Sau thủ tục thu nhỏ đường tròn: nếu mình không ngưng (vì tam giác ABC không chứa góc tù -- tìm ra lời giải) thì mình sẽ tiếp tục thu nhỏ theo dây cung PA (hoặc PB) vì góc PBA (hoặc góc PAB) là góc tù. Khi đó PA (hoặc PB) (dây cung tiếp theo) là dài hơn AB (dây cung ban đầu). Như vậy độ dài của dây cung (mà mình sẽ dựa vào đó để thu nhỏ đường tròn) sẽ ng`y càng tăng => mình chỉ thu nhỏ đường tròn theo một dây cung AB không quá 1 lần.

Vì số điểm thuộc S là N (hữu hạn) => mình sẽ gọi thủ tục (để thu nhỏ đường tròn) tối đa là N^2 (hữu hạn) lần (một khi mình tới được bước 3)

IV) thuật toán ngưng => T chính là lời giải: theo phần chứng minh ở (I), thủ tục thu nhỏ đường tròn T (chứa mọi điểm thuộc S) theo dây cung AB sẽ cho đường tròn mới T' thỏa: T' đi qua A và B và T' chứa mọi điểm thuộc S; và T' là đường tròn nhỏ nhứt thỏa tính chất này. Thuật toán ngưng ở các bước 1d, 3a và 3b; ở các bước này A và B đều thuộc S => T' là đường tròn nhỏ nhứt chứa mọi điểm thuộc S

(viết dài, dai, dở, lộn xộn; có gì sai sót mong được góp ý, xin cám ơn)

-thân

[Master_Baby]

Ặc, anh viết dài wé, trùi ui. Cho em ít thời gian nghiền ngẫm nhá.

[bete]

Thân gửi MasterBaby: tui sẽ thử đưa mấy cái hình vẽ lên coi có đỡ rối hơn không nghen.

Trong tài liệu mà bạn Mach2 giới thiệu họ trình bày thuật toán của Crystal-Peirce chỉ cần có mấy dòng thôi:

0) Dựng 1 đường tròn chứa mọi điểm P[i] và đi qua 2 điểm Ps và Pt. Gọi Xk là tâm của đường tròn này và Sk = {Ps, Pt}.

1) Chọn góc PsPrPt = min{góc PsPjPt: Pj không thuộc Sk}. Nếu góc PsPrPt là góc tù thì dừng; đường tròn nhỏ nhứt có đường kính là PsPt. Ngược lại, xét bước tiếp theo.

2) Nếu tam giác PsPrPt không có góc tù thì ngưng; đường tròn cần tìm sẽ đi qua Ps, Pr và Pt. Ngược lại, loại bỏ đỉnh của góc tù và đặt 2 đỉnh còn lại là Ps và Pt. Đặt Sk = {Ps, Pt} và lặp lại bước 1

-thân

[Master_Baby]

- Thân gửi anh bete:
Cái này có lẽ phải chứng minh Toán học nữa anh ạ. Nếu chỉ nêu ra không thì chưa đủ thuyết phục, mà em lại mù đặc tiếng Anh, thế nên không đọc nổi tài liệu của anh Mach2 => chứng minh giùm em với! :help:

[Mach2]

http://web.mit.edu/huynh/Public/Paper/Elzinga-Hearn.pdf

Tôi tìm được thuật toán Elzinga-Hearn và chứng minh cũng khá dễ hiểu bằng hình học. Idea là chứng minh lời giải sau từng bước lặp là hội tụ dần mà thôi. Phần CM có nhiều hình nên ko đem lên đây được, bạn cứ chịu khó đọc là hiểu thôi

[bete]

Thân gửi MasterBaby

Trong tài liệu của Mach2 đưa ra hình như không có phần chứng minh cho thuật toán của Crystal-Peirce. Hình như phải coi phần danh sách các tài liệu tham khảo ở cuối để tìm tài liệu chính của thuật toán này, may ra có phần chứng minh ở đó. Tuy nhiên sau khi đọc thuật toán Crystal-Peirce => tui nghĩ cách tui đưa ra chính là nó (nhưng tui trình bày rất luộm thuộm). MasterBaby chịu khó ngân kíu coi phần chứng minh của tui có sai hay dở chỗ nào hay không. Tui sẽ thử tìm đọc tài liệu gốc coi phần chứng minh ra sao và sẽ post lên (tiếng Việt) nếu được

Thân gửi Mach2: tui đoán Mach2 là dân toán hay thích toán lắm ?
Sẽ cố gắng đọc thuật toán Elzinga-Hearn coi sao (xin cám ơn)
Tui nghĩ khi chứng minh thuật toán, ngoài chuyện chứng minh nó hội tụ, còn phải chứng minh là nó hội tụ sau 1 số bước hữu hạn (ít nhứt là trong bài này), có đúng không ? Còn nếu thuật toán hội tụ sau vô hạn bước tức là không bao giờ tìm được đáp số đúng hết (chạy càng nhiều bước thì đáp số càng gần với lời giải), có đúng không Mach2. Tuy chưa đọc phần chứng minh của Elzinga-Hearn nhưng tui đoán họ chứng minh thuật toán hội tụ sau hữu hạn bước ? (tui vừa đọc lướt qua Elzinga-Hearn: đây là hướng nới rộng đường tròn từ từ, mỗi lần chọn 1 điểm nằm ngoài thì phải => sẽ dừng sau hữu hạn bước. Nhưng nếu thu nhỏ đường tròn từ từ thì tui nghĩ phải chứng minh nó sẽ dừng sau 1 số hữu hạn bước)

-thân

[Mach2]

@bete: tôi ko phải dân toán nhưng phải làm toán

Thuật toán Chrystal-Peirce được cite từ 2 papers thuộc... thế kỷ trước nên ko cách nào tìm được. Tuy nhiên tôi tìm được một đoạn nằm trong 1 LV tiếng Pháp có nói sơ về cách CM (hình học), cũng dựa trên cơ sở chứng minh lời giải sau tốt hơn lời giải trước (đường tròn là nhỏ dần)...

Đúng như bạn nói thì dù lời giải ở bước sau tốt hơn lời giải ở bước trước không đủ để kết luận tính hội tụ của một bài toán trong trường hợp tổng quát, nhưng trong trường hợp này nó đủ, vì tập hợp lời giải là hữu hạn (số đường tròn đi qua 2 hay 3 điểm trong tập hợp điểm cho trước là hữu hạn). Chỉ cần tập hợp lời giải hữu hạn và lời giải được improved hơn (monotone) thì chắc chắn sẽ tìm được lời giải tối ưu dù có đi theo cách nào (improved "tăng dần" hay improved "giảm dần")...

[haphuong]

Trước hết, cám ơn bạn Mach2 đã gởi lên đây hai bài báo hay, đặc biệt là bài báo của Elzinga – Hearn.

Tui muốn nêu một số ý kiến về bài toán này. Ký hiệu 2 bài báo đó là : [1] là bài báo đầu tiên , [2] là bài báo của Elzinga – Hearn.
1)Về bài báo [2]
-Ta đã biết 2 kết quả đơn giản sau:
a)Nếu tam giác IKL nhọn thì đường tròn nhỏ nhứt chứa ba điểm I, K, L là đường tròn ngoại tiếp tam giác IKL (tạm gọi là đường tròn loại 1).
b)Nếu tam giác IKL tù (giả sử góc I tù) thì đường tròn nhỏ nhứt chứa ba điểm I, K, L là đường tròn đường kính KL (đường tròn loại 2).
(Nếu I, K, L thẳng hàng và I ở trên đoạn thẳng KL thì lấy đường tròn đường kính KL)
Nội dung chính của thuật toán Elzinga – Hearn (viết tắt là E-H alg) có thể tóm tắt như sau: đầu tiên, chọn 2 điểm tùy ý rồi vẽ đường tròn nhận chúng làm đường kính: nếu đường tròn đó chứa hết các điểm thì xong, nếu nó chưa chứa hết các điểm thì lấy 1 điểm nằm ngoài đường tròn đó. Khi đó, ta có 3 điểm và vẽ tiếp đường tròn theo a) hoặc b), v.v…
Điểm đặc sắc nhứt trong E-H alg chính là bước 4 trong [2]: nếu ba điểm tạo thành tam giác nhọn mà đường tròn ngoại tiếp của nó chưa chứa hết các điểm thì:
*Chọn một điểm nằm ngoài đường tròn (và các tác giả cho rằng nên chọn điểm nằm xa đường tròn nhứt), gọi điểm đó là D.
*Gọi A là điểm (trong 3 điểm của tam giác nhọn đang xét) cách xa D nhứt. Khi đó, vẽ đường kính AA’. (Tui sửa cách ký hiệu một chút, nội dung vẫn giống!)
*Gọi C là điểm nằm khác phía với D so với đường thẳng AA’.
*Khi đó ta có ba điểm A, C và D: vẽ đường tròn theo a) hoặc b) nói trên.

Với cách chọn tam giác ACD trong bước 4 này, các tác giả chứng minh được rằng: bán kính của đường tròn sau lớn hơn hẳn bán kính của đường tròn trước, do đó mà thuật toán do họ đưa ra sẽ hội tụ. Vì chỉ có một số hữu hạn các đường tròn loại 1 hoặc loại 2 nên quá trình vẽ các đường tròn sẽ dừng sau một số hữu hạn bước.
Có thể nói rằng, thành công của 2 tác giả đó khi giải bài toán này chính là việc họ đã nghĩ ra được bước 4 này (tức là cách chọn điểm A và điểm C)!
-Trong [2], các tác giả có đề cập đến tính duy nhứt của nghiệm hình: chỉ có duy nhứt một đường tròn với bán kính nhỏ nhứt chứa n điểm cho trước trong mặt phẳng. Tuy nhiên, họ không viết chứng minh, có lẽ vì phép chứng minh đó quá dễ (một bài tập hình học đơn giản của lớp 8!). Các bạn tự chứng minh lấy hoặc có thể xem chứng minh trong bổ đề 2 (lemma 2) của bài sau (ký hiệu là [3]):
http://www.cut-the-knot.org/Generali...circles2.shtml

Việc chứng minh tính duy nhứt của lời giải là cần thiết. Thật vậy, trong E-H alg, ở bước 1, ta chọn 2 điểm tùy ý trong n điểm đã cho, nên có thể xày ra trường hợp: nếu ta chọn 2 điểm khác thì có thể sẽ nhận được đường tròn lời giải khác đi chăng? Điều này có thể xảy ra nếu bài toán có vài nghiệm hình. Vì vậy, sau khi đã chứng minh được nghiệm hình là duy nhứt, ta có thể yên tâm rằng: cho dù các điểm chọn trong buớc 1, 2, … có thế nào đi nữa thì các nghiệm hình nhận được sẽ trùng nhau.
Trong [3], các bạn cũng nên xem bổ đề 3: người ta chứng minh được rằng: nghiệm hình chỉ có thể là một trong hai loại: hoặc nó là loại 1, hoặc là loại 2. Nói nôm na dễ hiểu là không thể có nghiệm hình là đường tròn qua 2 điểm mà lại không nhận 2 điểm đó làm đường kính, v.v. . .
Điều này được kiểm chứng lại bởi các bài báo [1] và [2]: đọc các thuật toán của E-H hoặc của Chrystal-Peirce, ta thấy các đường tròn vẽ sau mỗi bước luôn luôn là loại 1 hoặc loại 2. (Ngoại trừ bước đầu tiên của thuật toán Chr-P)
2)Chương trình
Các bạn xem bài trong link dưới đây:

http://delphiforfun.com/Programs/cir...ing_points.htm

Cuối bài đó có các phần:
Browse source extract
Download source
Download executable
Các bạn click vào Download executable rồi extract file CircleCoveringPoints.zip ra, sau đó chạy chương trình đó sẽ thấy rằng sau khi các bạn click để tạo các điểm, các đường tròn nghiệm hình sẽ được vẽ ra. Các bạn cũng có thể load data bằng .txt file.
Còn Browse source extract, Download source dành cho bạn nào thích lập trình.
3)Các hướng mở rộng của bài toán:
Như thông thường, ta sẽ nhờ cậy “anh bạn Gú-Gồ ” để có thêm các tài liệu liên quan đến bài toán mà chúng ta đang quan tâm:
http://www.google.com.vn/search?hl=v...g+points&meta=

[haphuong]

Tui tìm được bài báo của Chrystal đăng trên tập san của Hội Toán học Pháp in năm 1885 nên đưa lên đây các bạn cùng xem.
Tui dốt tiếng Pháp nên không dịch bài báo đó được. Bạn nào rành tiếng Pháp làm ơn dịch dùm cho mọi người cùng đọc. Xin cảm ơn.

http://archive.numdam.org/ARCHIVE/BS..._13__198_0.pdf

[Godbloc]

Đơn giản lắm , tìm trọng tâm của các đỉnh làm tâm đường tròn , bán kính là khoảng cách từ tâm đến đỉnh xa nhất Ok .