View Full Version : [Pascal]Giúp mình bài này với
TLV15190
09-03-2005, 20:49
Cho một điểm và một đa giác n cạnh, tìm xem điểm đó có nằm trong đa giác hay không
-Nếu M thuộc cạnh đa giác thì M thuộc miền đa giác.
-Ngược lại: Kẻ đường thẳng MN // với trục hoành.Khi cài đặt bạn có thể lấy N là điểm có hoành độ lớn hơn hoành độ tất cả các đỉnh.Xét giao các cạnh với MN. Nếu số giao điểm là lẻ thì M nằm trong đa giác. là chẵn thì nằm ngoài.
Phần cài đặt thuộc về bạn ^_^
Bạn còn chưa nói rõ là đa giác lồi hay lõm ?
Lồi lõm không thành vấn đề
Thân gửi Rikku: Nếu nửa đường thẳng đi qua 1 đỉnh thì cách đếm của bạn có thể cho kết quả sai (phải sửa 1 chút). Ví dụ có hình thoi & xét điểm nằm ngay tâm: nửa đường thẳng đi qua 1 đỉnh => cắt 2 cạnh => tuy số lần cắt là chẵn (2) nhưng điểm là nằm trong chứ không phải nằm ngoài
(có gì sai sót xin các bạn chỉ giúp, cám ơn rất nhiều)
-thân
Three pearls
10-03-2005, 20:26
Thế làm cách nào để tìm các giao điểm?
To bete: Cái đó thì phải biện luận. mình nói hết ra vậy:
Xét cạnh d[i],d[i+1]
-nếu d[i] 0 thuộc MN , d[i+1] nằm trên MN, d[i] và d[i+2] khác phía nhau so với MN.-> tăng đếm lên 1.
-d[i-1],d[i+2] nằm ngoài MN d[i] và d[i+1] thuộc MN d[i-1],d[i+2] khác phía nhau so với MN-> tăng đếm lên 1.
-d[i],d[i+1] không thuộc MN và d[i],d[i+1] cắt MN->tăng đếm lên 1.
Hix, chắc là không sai đâu lol
Thân gửi Rikku: tui xin góp ý về trường hợp thứ 3:
"d[i],d[i+1] không thuộc MN và d[i],d[i+1] cắt MN->tăng đếm lên 1."
=> d[i],d[i+1] không thuộc MN và d[i],d[i+1] cắt MN (MN đi qua đỉnh nối d[i] với d[i+1]), d[i] và d[i+1] khác phía nhau so với MN ->tăng đếm lên 1 ???(d[i] và d[i+1] cùng phía so với MN thì không tăng biến đếm)
-thân
Mình không hiểu ý bạn...
Err, bete bao nhiêu tuổi vậy, nhỡ hơn tuổi mà cứ gọi là bạn lol.
Thân gửi Rikku:
Nếu ý của bạn là:
d[i],d[i+1] không thuộc MN và d[i],d[i+1] cắt MN (MN đi qua đỉnh nối d[i] với d[i+1]) ->LUÔN LUÔN tăng đếm lên 1.
thì tui nghĩ là:
d[i],d[i+1] không thuộc MN và d[i],d[i+1] cắt MN (MN đi qua đỉnh nối d[i] với d[i+1]) -> còn tùy (có lúc tăng đếm lên 1; có lúc không tăng).
Nói rõ hơn thì có 2 trường hợp con:
a) d[i],d[i+1] không thuộc MN và d[i],d[i+1] cắt MN (MN đi qua đỉnh nối d[i] với d[i+1]), d[i] và d[i+1] khác phía nhau so với MN -> tăng đếm lên 1
(ví dụ hình thoi: điểm nằm (trong) ngay tâm và MN đi qua đỉnh ngang hông)
b) d[i],d[i+1] không thuộc MN và d[i],d[i+1] cắt MN (MN đi qua đỉnh nối d[i] với d[i+1]),d[i] và d[i+1] cùng phía so với MN thì không tăng biến đếm
(ví dụ hình thoi: điểm nằm ngoài và MN đi qua đỉnh trên cùng hay dưới cùng)
(trên diễn đàn hầu như không biết (& không phân biệt !?) tuổi tác
=> Rikku gọi tui là bạn cũng không sao :))
(có gì sai sót thì xin các bạn chỉ giúp, cám ơn rất nhiều)
-thân
tôi xin góp ý chút
Về phương diện nếu dùng "if then else" thì chắc chắn thế nào cũng xử lý được bài này. Khi trước đã có lần tôi xử lý 1 cái hình cóc ổi (hình như trái chôm chôm hay con sida) thì cái hiện tượng "cắt đỉnh" này thực sự khó chịu.
Đương nhiên là xử lý được nhưng nếu xét tất cả trường hợp e hơi mệt (ví dụ như MN đi hẳn qua 1,2... cạnh, cắt nhiều hơn 1 đỉnh)... nên tôi chơi trâu bò. Nếu "cắt đỉnh" thì dẹp, ko xét nữa, quay MN đi một góc epsilon rồi test. Làm vậy thì khỏe re ah :)
PS. Còn chuyện tuổi tác xưng hô thì mệt lắm. Tôi thì đoán bác bete chắc cũng phải ở tuổi "sồn sồn" rồi :)
real_time
11-03-2005, 15:47
ngày trước đã tìm ra một bài về đỉnh điểm trong điểm ngoài đa giác mà là vẽ trực quan rất tốt mình ko còn nhớ địa chỉ của nó nữa rồi nhưng đó năm trong planet-source-code.com. Các bạn vào đó tìm thử xem.
Ơ, MN cắt ở đây là không tính vào 2 cái đầu mút đâu, cái ở tâm hình thoi-> TH1.
Còn cái kia thì là không cắt.
Nói tuổi đi mà lol. Mình học lớp 11
Ơ, MN cắt ở đây là không tính vào 2 cái đầu mút đâu, cái ở tâm hình thoi-> TH1.
Còn cái kia thì là không cắt.
cái bài mình nói là cũng có trường hợp giống giống bạn và bete đang bàn (1 cái mê trận, có nhiều trường hợp tia qua 1 điểm nằm trong cắt tùm lum đỉnh của mê trận và bao gồm cả nhiều cạnh của mê trận nữa). Nếu xét thì "if then else" cũng xong nhưng nếu xoay xoay đường thẳng đi một tí thì né được trường hợp vớ vẫn ấy ngay.
Có bài nè trâu dã man nè:
Cho 1 hình đa giác, tìm diện tích hình đa giác X bên trong nó mà:
Tại bất kì điểm nào trong đa giác X cũng nhìn được tất cả các cạnh của đa giác ngoài.
(Tưởng tượng như cái Camera đóa. Nhìn hết được tất cả mọi chỗ trong phòng )
Số đình ...<=10000
Cho biết tuổi đi, cho biết tuổi đi lol
Thân gửi Rikku:
Cho 1 hình đa giác, tìm diện tích hình đa giác X bên trong nó mà:
Tại bất kì điểm nào trong đa giác X cũng nhìn được tất cả các cạnh của đa giác ngoài.
=> trâu bò thiệt chứ :) tui chỉ nghĩ được có cách xài thuật toán xén Sutherland-Hodgeman thôi => cũng cỡ O(n^2) hoặcO(n^3) rồi :(
-thân
Three pearls
12-03-2005, 21:14
Thuật toán xén Sutherland-Hodgeman là cái chi mô dzậy???
Hôm trước vác free pascal ra chạy mà gần 1 phút mới ra kết quả. lol, cái tên Sutherland-Hodgeman mới nghe lần đầu nha?? bete nói rõ tí được không?
P/s: Hỏi lần 3 nè. bete bao nhiêu tuổi vậy??lol
Tui đưa sai tên(Sutherland-Hodgman mới đúng thay vì Sutherland-Hodgeman)
Kiếm trên mạng sẽ thấy ngay về thuật toán trong đồ họa này:
http://www.google.com/search?hl=en&q=sutherland-hodgman+clipping+algorithm&spell=1
hoặc
http://ddth.com/showthread.htm?t=33966
Đại ý là cho 1 đa giác và 1 ô cửa sổ => tìm đa giác bị cắt bởi cửa sổ (phần nằm ngoài cửa sổ bị xén đi)
Rikku chạy khoảng 1 phút thì cách giải chắc là hay lắm => có thể trình bày cho phe ta biết !?
(gửi Rikku: tay bạn thân của tui hồi đó hay ngâm nga : "ba mươi chưa phải là già, ba mươi ta mới tà tà vào xuân" :))
-thân
Sao mà giống đề bảng A năm nay thế. Nhưng là tìm cách cắt đa giác nhỏ hơn từ đa giác ban đầu với độ dài các nhát cắt ít nhât, như cắt giấy ý. Bài này cài suýt điên luôn, chả biết có được điểm không nữa :(.Cầu trời cho con có giải. :( :(.
Bài kia Rikku... đã cài đâu lol. Hôm trước thấy ông anh 12 chạy tầm đấy, mà không nhớ có phải 1 phút không hay là ..10 phút nữa lol.
Thế rốt cục thì phải làm bài này thế nào vậy???
2 người cãi nhau mãi, mệt quá!
Thân gửi MrPaint: bạn muốn hỏi về bài "đa giác bên trong nhìn được mọi cạnh của đa giác bên ngoài" do Rikku đưa ra !? Tui xin nói thêm 1 chút về cách của tui (chắc chắn không phải là cách duy nhứt, & chắc chắn không phải là 1 cách hay. Nối dài 1 cạnh bất kỳ của đa giác => chia mặt phẳng làm 2 phần (2 nửa mặt phẳng). Loại bỏ 1 trong 2 nửa (nếu có phần nào của đa giác lọt vô trong nửa mặt phẳng này thì bỏ nó đi); bước này xài thuật toán xén Sutherland-Hodgman => 1 đa giác mới. Lần tiếp làm như trên với tất cả các cạnh còn lại của đa giác => sẽ được 1 đa giác cuối cùng hoặc không có đa giác nào cả. Biết tọa độ các đỉnh của đa giác kết quả rồi thì chỉ cần tìm diện tích của nó
(tui thấy Rikku & tui đâu có cãi nhau gì đâu; tui muốn biết cách giải của Rikku để học hỏi thêm; nếu cách giải của Rikku có chỗ nào trục trặc thì tui góp ý để cả 2 cùng biết thêm-- và tui cũng rất muốn cách giải của tui "bị chê" để biết chỗ dở của mình mà sửa đổi. Chê bai người khác hoặc lên lớp với vẻ ta đây hoặc cãi cọ để giành phần đúng vê mình là điều tui không bao giờ muốn làm. Nếu các bạn có bao giờ thấy hoặc nghĩ tui đang làm chuyện đó thì xin nhắc nhở giùm. Tui nghĩ 1 cách giải đúng có thể chỉ là tầm thường (vì ai cũng nghĩ theo hướng đó); còn 1 cách giải sai vẫn có thể hay vì nghĩ theo 1 hướng ít ai nghĩ tới. )
Gửi Rikku: tìm cách cắt đa giác nhỏ hơn từ đa giác ban đầu với độ dài các nhát cắt ít nhât => tui nhớ 1 cuốn sách về giải thuật có cho ví dụ về bài này hày tương tự gì đó (xài qui hoạch động rất đẹp)
-thân
Đúng rồi, hôm trước có thằng bạn Rikku xài QHĐ, nhưng nghe nó giải thích chả hiểu gì hết.
Lúc làm bài xén "đa giác camera" Rikku cũng nghĩ như thế, đánh dấu loại 1 trong 2 nửa, chứ không vứt bỏ nó đi vì nếu vứt đi thì bị cắt thiếu, cài muốn điên luôn, cuối cùng chả ra gì cả lol, Rikku dốt về Hình Học lắm. Để ngày mai Rikku hỏi lại xem cách làm thế nào lol? Hình như độ phức tạp là O(N^2).
Thân gửi Rikku:
"vì nếu vứt đi thì bị cắt thiếu" => ý của Rikku là nếu vứt bỏ nó đi luôn thì những cạnh bi vứt bỏ của đa giác sẽ không được xét tiếp (sẽ không được vẽ nối dài để chia mặt phẳng ra làm 2 !? Thành ra Rikku chỉ đánh dấu loại bỏ để những cạnh này vẫn còn đó(và sẽ được xét ở bước kế) !?
Nếu ý của Rikku là như vậy thì tui nghĩ mình có thể làm đại khái:
P1 = đa giác ban đầu
P2 = P1
Quét mỗi cạnh của đa giác P1: cắt P2 bằng cạnh này; và đa giác kết quả ở bước này sẽ được ghi ngược trở lại vô P2
P2 có diện tích nhỏ dần; nhưng số cạnh có thể tăng dần; còn P1 vẫn giữ nguyên không thay đổI từ đầu đến cuối
Kết quả cuối cùng là P2
Còn nếu ý của Rikku là khác thì Rikku có thể cho 1 ví dụ rõ hơn không !?
(có gì sai sót xin các bạn chỉ giúp, cám ơn rất nhiều)
-thân
Chắc là như thế đó. Cách này cài trâu lắm... không biết có cách nào giảm độ phức tạp không nữa :(
Powered by vBulletin® Version 4.2.0 Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.