›

Thiết kế hệ thống kiểm tra các quan hệ hình học trong không gian 2D và 3D - Lê Quốc Thái

pdf 72 trang huongle 4610
Download
Bạn đang xem 20 trang mẫu của tài liệu "Thiết kế hệ thống kiểm tra các quan hệ hình học trong không gian 2D và 3D - Lê Quốc Thái", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfthiet_ke_he_thong_kiem_tra_cac_quan_he_hinh_hoc_trong_khong.pdf

Nội dung text: Thiết kế hệ thống kiểm tra các quan hệ hình học trong không gian 2D và 3D - Lê Quốc Thái

  1. Luận văn tốt nghiệp LUẬN VĂN TỐT NGHIỆP KHOA CƠNG NGHỆ THƠNG TIN Đề tài: “THIẾT KẾ HỆ THỐNG KIỂM TRA CÁC QUAN HỆ HÌNH HỌC TRONG KHƠNG GIAN 2D VÀ 3D“ Thiết kế hệ thống kiểm tra các quan hệ hình học trang 1
  2. Luận văn tốt nghiệp Trong lĩnh vực cơng nghệ máy tính cũng như cơng nghệ thơng tin cĩ những bước phát triển nhảy vọt, nĩ đã hỗ trợ vào mọi lĩnh vực trong cuộc sống xã hội, sản phẩm của cơng nghệ thơng tin biến đổi hàng ngày, hàng giờ. Trong lĩnh vực tốn học, các sản phẩm của cơng nghệ thơng tin cũng hỗ trợ đắc lực cho việc học tập và nghiên cứu. Đề tài tơi thực hiện là: “THIẾT KẾ HỆ THỐNG KIỂM TRA CÁC QUAN HỆ HÌNH HỌC TRONG KHƠNG GIAN 2D VÀ 3D“. Đề tài sử dụng ngơn ngữ lập trình Visual C++ để thể hiện. Về gĩc độ học tập, nghiên cứu tơi thấy đề tài cĩ thể giúp hiểu rõ thêm về kiến thức cơ bản của phần đồ họa máy tính và cho vấn đề kiểm tra thực hiện một số bài tốn hình học thêm phong phú hơn, tạo thêm phần hấp dẫn trong mơn học này. Trong thời gian thực hiện đề tài tơi đã thực hiện được những yêu cầu của đề tài. Việc thực hiện đề tài cịn mang ý nghĩa đánh giá lại quá trình học tập, nghiên cứu của tơi. Nên về mặt tinh thần tơi đã cố gắng tìm hiểu, nghiên cứu, và chuẩn bị khá chu đáo cho việc thực hiện. Nhưng sự tiếp thu cũng cĩ những giới hạn nhất định, bởi trong lĩnh vực máy tính cũng như cơ sở tốn học rộng lớn, khơng gian diễn dịch cĩ thể vơ hạn, sự thực hiện một ý tưởng nào đĩ cĩ thể trong tốn học thực hiện được, nhưng việc thể hiện thuật tốn bằng máy tính thì cĩ những vấn đề khĩ thể thực hiện, vì vậy đề tài chắc chắn cịn nhiều thiếu sĩt nhất định. Mong quý Thầy cơ, Anh chị và các bạn thơng cảm, đĩng gĩp ý kiến giúp đỡ. Tơi thành thật cảm ơn ! SINH VIÊN THỰC HIỆN LÊ QUỐC THÁI PHẦN I: GIỚI THIỆU Thiết kế hệ thống kiểm tra các quan hệ hình học trang 2
  3. Luận văn tốt nghiệp I. SƠ LƯỢC VỀ HỆ THỐNG KIỂM TRA CÁC QUAN HỆ HÌNH HỌC Để cho người đọc tham khảo đề tài “THIẾT KẾ HỆ THỐNG KIỂM TRA CÁC QUAN HỆ HÌNH HỌC“ dễ dàng hình dung được, tơi xin giới thiệu sơ lược về đề tài. Nhiệm vụ thực hiện của đề tài: Thiết kế hệ thống kiểm tra các quan hệ hình học trong:  Khơng gian hai chiều (2D)  Khơng gian ba chiều (3D) Với ngơn ngữ thể hiện trên mơi trường Visual C++. Đề tài áp dụng các kiến thức về cơ sở tốn học và khơng gian vector trong đồ họa máy tính, để xây dựng những thuật tốn kiểm tra các quan hệ hình học. Để dễ dàng hơn tơi xin trình bày một ví dụ điển hình như sau: Ví du: cho đường thẳng a qua hai điểm A và B và đường thẳng b qua hai điểm C và D trong khơng gian 2D hay 3D thì hai đường thẳng này cũng cĩ những sự tương quan với nhau, như trùng nhau, cắt nhau với một gĩc nào đĩ, chéo nhau (trong khơng gian 3D), hay song song Sau khi đưa vào những điều kiện giả thiết ban đầu (Input), thì chương trình thực hiện và đưa ra kết quả kiểm tra (output) của giả thiết trên là hai đường thẳng a và b đã tương quan như thế nào với nhau? Cắt nhau một gĩc bao nhiêu độ, song song, hay trùng nhau Đĩ là về mặt thuật tốn chương trình kiểm tra, đây chỉ mới là một tác vụ thực hiện của vấn đề này. Với bài tốn như trên nếu chỉ đưa ra được những kết luận với những dịng thơng điệp thì chúng ta thấy rằng đề tài trở nên quá đơn giản khơng phong phú và hấp dẫn qua ý kiến của người đọc hoặc tham khảo. Một tác vụ cùng đồng thời với bài tốn trên mà nhiệm vụ của đề tài yêu cầu thực hiện là khi đưa vào giả thiết bài tốn chẳng hạn hai điểm A và B với những tọa độ xác định nào đĩ, qua hai điểm này sẽ thực hiện vẽ lên một đoạn thẳng qua hai điểm A và B. Từ đĩ thấy vấn đề một cách trực quan hơn, hay vẽ ra gĩc giữa hai đường thẳng, chính với những thể hiện này đề tài trở nên hấp dẫn phong phú hơn, tất nhiên vấn đề này khơng ít những khĩ khăn cho người thực hiện đề tài. Trong phần nội dung tơi sẽ trình bày chi tiết hơn về đề tài “THIẾT KẾ HỆ THỐNG KIỂM TRA CÁC QUAN HỆ HÌNH HỌC TRONG 2D VÀ 3D“. II. GIỚI THIỆU SƠ LƯỢC NGƠN NGỮ THỂ HIỆN ĐỀ TÀI II.1. SƠ LƯỢC NGƠN NGỮ Ở phần I giới thiệu sơ lược về “THIẾT KẾ HỆ THỐNG KIỂM TRA CÁC QUAN HỆ HÌNH HỌC“, tơi đã trình bày một ví dụ về yêu cầu nhiệm vụ để thực hiện một tác vụ kiểm tra vấn đề nào đĩ của đề tài này. Để thực hiện những vấn đề đĩ tơi nghiên cứu và thực hiện trên mơi trường ngơn ngữ Visual C++. Thiết kế hệ thống kiểm tra các quan hệ hình học trang 3
  4. Luận văn tốt nghiệp Visual C++ là một phần mềm lập trình hướng đối tượng được phát triển trên cơ sở là ngơn ngữ lập trình C và C++. Ở đây tơi thể hiện đề tài trên ngơn ngữ Visual C++ bởi lẽ hiện nay ngơn ngữ này được xem là một trong các ngơn ngữ hỗ trợ (support user) mạnh và phổ biến nhất. Cùng mục đích sâu xa hơn nữa là để cho những đề tài sau này cĩ thể trên cùng ngơn ngữ xây dựng ý tưởng của đề tài “THIẾT KẾ HỆ THỐNG KIỂM TRA CÁC QUAN HỆ HÌNH HỌC“ ngày thêm một đầy đủ, phong phú, hấp dẫn và ứng dụng mang tính thiết thực hơn. Tơi đầu tiên nghiên cứu tìm hiểu tổng quát về ngơn ngữ như Visual C++, thực hiện những chương trình điển hình trên ngơn ngữ lập trình hướng đối tượng. Và phần tìm hiểu chính là phần thực hiện yêu cầu của đề tài, cụ thể là về phương diện tính tốn trong những thuật tốn và thể hiện trực quan bằng đồ hoạ máy tính trên ngơn ngữ Visual C++. Trong Visual C++ phần đồ họa được thể hiện trong lớp CDC (Class Device Context) với nhiều hàm thành viên hỗ trợ cho việc vẽ điểm, đường, đa giác, tơ màu . Đặc biệt hơn trong ngơn ngữ Visual C++ cĩ sự hỗ trợ cho việc vẽ các đối tượng hình học bằng chuột. Nhưng ngơn ngữ chỉ thực hiện được với các đối tượng hình học 2D, đối tượng hình học 3D thì chưa cĩ, cần phải tự thiết kế. Trong quá trình nghiên cứu, tơi nhận thấy trong ngơn ngữ Visual C++ cĩ bộ thư viện OPENGL là một thư viện API hỗ trợ cho việc thực hiện các chương trình đồ họa, trên cả 2D và 3D rất mạnh, chính vì thế ở phần kiểm tra các quan hệ hình học phần 3D tơi thực hiện trên OPENGL. Từ đây tơi chuyển hướng sang nghiên cứu OPENGL để thực hiện cho phần 3D. Để hiểu và thực hiện được trên nĩ cũng khĩ khăn khơng kém như ta bắt đầu nghiên cứu và làm quen với ngơn ngữ mới như Visual C++. Sau khi nghiên cứu và hiểu được những yếu tố cơ bản của OPENGL tơi cĩ nhận xét rằng OPENGL là một ứng dụng để thực hiện các chương trình đồ họa máy tính hấp dẫn và đẹp mắt. Khi đã cài được thì cách sử dụng cĩ phần dễ dàng hơn, chỉ cần tìm hiểu một số các hàm trong thư viện các hàm thành viên của OPENGL là đáp ứng được yêu cầu. Cịn mọi việc thực hiện cài đặt theo lý thuyết đồ họa máy tính như các phép biến hình, thiết lập chế độ màn hình, khởi tạo đồ họa, setviewport, tạo các Pallette màu, thiết lập độ sâu hình ảnh, độ phản chiếu hình ảnh, độ tương phản tất cả do OPENGL hỗ trợ hầu hết. OpenGL được định nghĩa là “giao diện phần mềm cho phần cứng đồ họa ”. Thực chất, OpenGL là một thư viện các hàm đồ họa, được xem là tiêu chuẩn thiết kế cơng nghiệp cho đồ họa ba chiều. Với giao diện lập trình mạnh mẽ, OpenGL cho phép tạo các ứng dụng 3-D phức tạp với độ tinh vi, chính xác cao, mà người thiết kế khơng phải đánh vật với các núi cơng thức tốn học và các mã nguồn phức tạp. Và do OpenGL là tiêu chuẩn cơng nghiệp, các ứng dụng tạo từ nĩ dùng được trên các phần cứng và hệ điều hành khác nhau. Thiết kế hệ thống kiểm tra các quan hệ hình học trang 4
  5. Luận văn tốt nghiệp Nhận xét về OPENGL tơi thấy rằng OPENGL là thư viện đồ họa trên WINDOWS bởi vì ta cĩ thể thấy rằng OPENGL khơng những thực hiện trên ngơn ngữ Visual C++ mà cịn cĩ thể cho phép thực hiện trên cả Visual Basis , Borland C++ II. 2. GIỚI THIỆU CÁC HÀM CỦA NGƠN NGỮ ĐƯỢC SỬ DỤNG a. Các hàm của lớp CDC (Class Device Context) Trong CDC cĩ rất nhiều hàm thành viên phục vụ cho quá trình kết xuất các hình ảnh ra các thiết bị. Trong phần thực hiện đề tài, tơi xin đưa ra các hàm được sử dụng trong đề tài  Vẽ điểm: SetPixel ( int x , int y , int color ); Hàm này thuộc lớp CClientDC trong phần màu sử dụng macro RGB(red,green,blue) Ví du: Để vẽ một điểm , ta thực hiện như sau: CClientDC dc( this ); dc.SetPixel (100,100,GRB(0,0,0); Để thể hiện tọa độ một điểm trong hệ trục tọa độ hai chiều, Visual C++ dùng lớp CPoint, đối tượng thuộc lớp này được thể hiện bởi hai thành phần x và y. Ví dụ ta khai báo điểm point như sau: CPoint point point.x=100; point.y=100;  Vẽ đường thẳng: Line (int x1, int y1, int x2, int y2); Hàm này thuộc lớp CClientDC Ví dụ: Để vẽ đường thẳng ta thực hiện các bước sau đây CClientDC dc(this); dc.Line(x1,y1,x2,y2); Ngồi ra trong việc vẽ đường thẳng cịn cĩ thể sử dụng hai hàm sau: MoveTo(int x, int y); Hàm này dùng để di chuyển con trỏ đến tọa độ x,y trong màn hình. LineTo(int x, int y); Thiết kế hệ thống kiểm tra các quan hệ hình học trang 5
  6. Luận văn tốt nghiệp Hàm này dùng để vẽ đường thẳng từ điểm hiện hành đến điểm x, y. Cả hai hàm này đều thuộc lớp CClientDC, việc sử dụng như sau: CClientDC dc(this); dc.MoveTo(x,y); dc.LineTo(newx, newy);  Vẽ hình chữ nhật: Rectangle(int x1,int y1,int x2,int y2); Hàm này thuộc lớp CclientDC. Dùng để vẽ hình chữ nhật cĩ tọa độ trên gĩc trên trái là (x1,y1) và tọa độ gĩc dưới phải là (x2,y2). Cú pháp vẽ hình chữ nhật như sau: CClientDC dc(this); dc.Rectangle(x1, y1, x2, y2);  Vẽ hình Ellipse: Ellipse(int x1,int y1,intx2,int y2); Hàm này cĩ các tham tương tự các tham số hình chữ nhật, hàm này cũng thuộc lớp CClientDC. Cú pháp vẽ hình Ellipse như sau: CClientDC dc(this); dc.ellipse(int x1, int y1, intx2, int y2);  Hàm loan vùng kín: FloodFill(int x,int y, int color); Hàm này dùng để tơ màu vùng được giới hạn bởi một đường biên khép kín. Hàm này thuộc lớp CClientDC cĩ tác dụng tơ màu với màu color tơ hết vùng cĩ tọa độ (x,y) và một vùng kín bao quanh điểm đĩ. Cú pháp hàm như sau: CClientDC dc(this); dc.FloodFill(x, y, color);  Tạo các đường vẽ: CreatePen(typeline, width, color); Để tạo đường vẽ trong các ứng dụng vẽ ta xét hàm CreatePen của lớp Cpen, hàm này cĩ dạng như sau: Cpen *pPen=new Cpen; pPen->CreatePen(typeline, width, color); Trong đĩ : Thiết kế hệ thống kiểm tra các quan hệ hình học trang 6
  7. Luận văn tốt nghiệp Tham số typeline là kiểu đường vẽ, nĩ cĩ giá trị được định nghĩa như sau: PS-SOLID Đường thẳng đồng nhất. PS-DASH Đường thẳng gồm các gạch ngang đứt nét. PS-DOT Đường thẳng gồm các nét chấm đứt. PS-DASDOT Đường thẳng gồm các gạch ngang chấm đứt. PS-DASHDOTDOT Đường thẳng gồm các gạch ngang chấm đứt. PS-NULL Đường thẳng vơ hiệu lực khơng vẽ ra. PS-INSIDEFRAME Đường thẳng nằm bên trong đường viền. Tham số width cho độ rộng của nét vẽ tính bằng pixel. Tham số color cho màu vẽ b. Các hàm trong bộ thư viện OpenGL OpenGL gồm 5 bộ hàm, bộ hạt nhân cĩ 115 hàm cơ bản. Tên các hàm này bắt đầu bằng GL. Windows NT hỗ trợ 4 chủng loại hàm khác, bao gồm thư viện OpenGL utility(tên hàm bắt đầu bằng GLU), thư viện OpenGL auxiliary(tên hàm bắt đầu bằng AUX), bộ hàm”WGL” (tên hàm bắt đầu bằng WGL), và các hàm WIN32 API (tên hàm khơng cĩ tiền tố đặc biệt). Bộ hàm hạt nhân cho phép thiết kế các hình dạng khác nhau, tạo các hiệu quả chiếu sáng, kết hợp antialiasing và gán cấu trúc, thực hiện biến đổi ma trận Do các hàm cơ bản được thể hiện ở nhiều dạng khác nhau tùy thuộc vào loại dữ liệu mà chúng tiếp nhận, nên trên thực tế cĩ hơn 300 nguyên mẫu (prototype) các hàm cơ bản.  Thư viện OpenGL utility gồm các hàm cao cấp. Các hàm này đơn giản hố việc sử dụng hình ảnh cấu trúc, thực hiện việc biến đổi tọa độ mức cao, hỗ trợ tesselation đa giác, và biểu diễn các đối tượng cĩ cơ sở đa giác như hình cầu, hình trụ hình dĩa.  Thư viện OpenGl auxiliary gồm các hàm đặc biệt dùng đơn giản hĩa các ví dụ lập trình trong sách chỉ dẫn lập trình OpenGL. Các hàm phụ thuộc platform này thực hiện các nhiệm vụ như quản ký cửa sổ, điều khiển xuất/nhập, vẽ các đối tượng 3D nhất định. Do các hàm này cĩ mực đích thiết minh nên khơng được dùng trong các mã sản xuất.  Các hàm “WGL”kết nối OpenGL với WINdows NT, cho phép người lập trình xây dựng và chọn lựa các ngữ cảnh biểu diễn, tạo các bitmap font, các hàm này chỉ dùng trên Windows NT.  Cuối cùng, các hàm Win32 API được dùng giải quyết các định dạng điểm ảnh và tạo bộ đệm đơi. Trong phần này, tơi trình bày một số hàm được sử dụng trong đề tài.  Hàm vẽ điểm, đường, đa giác: Thiết kế hệ thống kiểm tra các quan hệ hình học trang 7
  8. Luận văn tốt nghiệp Được bắt đầu bởi hàm: glBegin (Glenum mode) Để chỉ sự bắt đầu những đỉnh của một primitive, tham số mode chỉ kiểu các primitive. Tham số mode cĩ các giá trị sau:  GL_POINTS : chỉ đỉnh được sử dụng là điểm.  GL_LINES : chỉ những đỉnh được dùng để tạo đoạn thẳng.  GL_LINE_STRIP : chỉ những đỉnh được sử dụng tạo đoạn thẳng nhẵn.  GL_TRIANGLES : những đỉnh được sử dụng tạo ra những tam giác.  GL_TRIANGLE_STRIP : những đỉnh được sử dụng tạo ra tam giác cĩ cạnh nhẵn.  GL_POLYGON : những đỉnh được sử dụng tạo ra đa giác lồi. glEnd ( ) Hàm trên dùng để chấm dứt danh sách các đỉnh mà nĩ chỉ rõ primitive được khởi tạo bởi hàm glBegin. Ví du: Vẽ đường thẳng từ 2 điểm glBegin(GL_LINES) glVertex3f(0.0f, 0.0f, 0.0f); glVertex3f(50.0f, 50.0f, 50.0f); glEnd( );  Hàm chỉ ra tọa độ của điểm, đường, đa giác: glVertex2f (Glfloat x,Glfloat y) glVertex3f (Glfloat x,Glfloat y,Glfloat z)  Hàm biến đổi tọa độ: glLoadIdentity(); thay thế ma trận hiện hành bởi ma trận đơn vị. glMultMatrix(); nhân ma trận hiện hành với ma trận được chỉ định. gl PopMatrix(void); lấy ma trận hiện hành từ stack. glPushMatrix(void); đẩy ma trận hiện hành vào stack. glTranslatef (Glfloat x, Glfloat y, Glfloat z); nhân ma trận hiện hành bởi ma trận tịnh tiến. gl Rotatef(Glfloat Angle, Glfloat x, Glfloat y, Glfloat z); nhân ma trận hiện hành bởi ma trận quay.  Các hàm liên quan đến màu: glColor3f (Glfloat red, Glfloat green, Glfloat blue); đặt màu hiện hành bởi các thành phần red, green, blue với giá trị từ 0,0 đến 1,0. Thiết kế hệ thống kiểm tra các quan hệ hình học trang 8
  9. Luận văn tốt nghiệp glClearColor(GLclampf red, GLclamp green, Glclamp blue, Glclamp alpha); đặt màu cho việc xĩa buffer màu. glClear(GL_COLOR_BUFFER_BIT); xĩa buffer màu, xĩa cửa sổ bởi màu xĩa hiện hành .  Các hàm liên quan đến ánh sáng: glLightf(Glenum light, Glenum pname, GLfloat param); glLighti(Glenum light, Glenum pname, GLint param); Trong đĩ:  Tham số light chỉ ra nguồn sáng cĩ giá trị từ GL_LIGHT0 đến GL_LIGHT7.  Tham số pname chỉ ra tham số light nào được lập như GL_AMBIENT, GL_DIFFUSE  Tham số param chỉ cĩ ý nghĩa đối với nguồn sáng điểm. Tham số này cĩ các giá trị như: GL_SPOT_EXPONENT, GL_SPOT_CUTOFF  Các hàm liên quan đến thuộc tính ánh sáng của vật liệu: glColorMaterialf(Glenum face,Glenum pname, GL float param); glMateriali(Glenum face,Glenum pname, GL int param); glMaterialfi(Glenum face,Glenum pname, const Glint* params); glMaterialfi(Glenum face,Glenum pname, const Glint* params); Trong đĩ:  face: là thuộc tính bề mặt trước ,sau của đa giác.  pname: là thuộc tính của vật liệu: GL_AMBIENT,GL_DIFFUSE,  param : chỉ định giá trị mà tham số pname được lập.  params: chỉ định dãy số nguyên hay thực chứa các thành phần thuộc tính được lập. glFrontFace(Glenum mode); xác định bề mặt đa giác là mặt trước hay sau. PHẦN II: NỘI DUNG Trong phần giới thiệu tơi đã trình bày những nội dung sơ lược mang tính tổng quát của đề tài. Phần nội dung tơi trình bày chi tiết hơn theo thứ tự logic các vấn đề từ lý thuyết tốn học đến các thuật tốn chương trình. Thiết kế hệ thống kiểm tra các quan hệ hình học trang 9
  10. Luận văn tốt nghiệp I. LÝ THUYẾT CƠ SỞ TỐN HỌC Các lý thuyết cơ sở tốn học được sử dụng cho các thuật tốn trong đề tài “THIẾT KẾ HỆ THỐNG KIỂM TRA CÁC QUAN HỆ HÌNH HỌC“ bao gồm: Hình học giải tích trong mặt phẳng Hình học giải tích trong khơng gian. Phần lý thuyết cơ sở tốn học này rất cần thiết cho việc thiết kế chương trình thực hiện việc kiểm tra các quan hệ hình học, khơng gian vector là cơ sở lý thuyết tốn học tất yếu để xây dựng các cấu trúc đồ họa máy tính. I.1. Giới thiệu về vector: Điểm (point): Mơ tả các vị trí của đồ hình và cĩ nhiều cách để diễn đạt. Trong hai chiều biểu diễn bằng cách dùng bộ-2 để cho các tọa độ theo hai trục. Hai dạng thường được áp dụng nhiều đĩ là dạng Cartesian như (x,y) =(3,4) hay dạng tọa độ cực (R, )=(2.4,450). Trong khi chúng được định nghĩa một cách đại số theo các thao tác nhất định trên đĩ, chúng cũng cho phép một diễn dịch hình học theo các điểm, đường, chiều. Vector: Nhìn một cách hình học, vector là một đoạn thẳng mà các điểm đầu và điểm cuối đã được xác định . Vector là một đối tượng cĩ độ dài và chiều tương ứng với một số thực thể vật lý như lực, khoảng cách, và vận tốc. Vector thường được vẽ như một mũi tên cĩ chiều dài chỉ về một hướng. Khi vector được chọn để chỉ định hệ tọa độ, các vector cĩ một hàm số để đưa ra hai hằng số, ba hằng số, Vì thế, một trong các thể hiện của một vector hai chiều a là một cặp cĩ thứ tự a=(a x , a y ). Trong chương trình, vector được biểu diễn bằng kiểu dữ liệu: Typedef struct { dx,dy: float; } vector; struct { dx,dy,dz : float; } vector3D P x 2 P v 4 v P 1 P5 Thiết kế hệ thống kiểm tra các quan hệ hình học trang 10 P3 y
  11. Luận văn tốt nghiệp Với hai điểm P1(x1,y1) và P2(x2,y2) ta định nghĩa vector v với các thành phần là vector v =(x2-x1, y2-y1). Đơi khi vector này được ghi là P1P2 và gọi là vector từ P1 đến P2. Bản thân vector khơng bị buộc vào một vị trí, mặc dù để dễ hình dung thường vẽ chúng xuất phát từ một điểm. Với điểm bất kỳ P = (Px, Py) trong một hệ tọa độ, vector đi từ gốc tọa độ với các tọa độ v=(Px, Py) được gọi là vector vị trí cho P. Vector 3D cũng rất quan trọng trong đồ họa. I.2. Các phép tính vector: Một vector n chiều, với n là số nguyên dương bất kỳ: W=(W1,W2,. . .,Wn) với mỗi thành phần Wi là số vơ hướng. Các vector 2 chiều và 3 chiều với n=2, n=3 thì thường gặp nhất trong đồ hoạ Chúng ta khơng thể thấy được các vector lớn hơn 3 nhưng chúng là những thành phần cĩ giá rị rât lớn. Hai phép tính số học cơ bản trên vector là cộng hai vector và định tỷ lệ một vector.  Cộng hai vector Tổng hai vector a,b là vector c được định nghĩa như sau: C = (c1, c 2 , , c n ) = (a1 + b1, a 2 + b 2 , , a n + b n ) a+b b a+b a b a Hình a Hình b Hình a: Các thành phần của tổng là tổng các thành phần của các vector tham gia. Hình b: Tổng các vector là đường chéo hình bình hành. Thiết kế hệ thống kiểm tra các quan hệ hình học trang 11
  12. Luận văn tốt nghiệp Procedure AddVectors( vector a, vector b; vector &c ); { c.dx := a.dx + b.dx; c.dy := a.dy + b.dy; }  Định tỷ lệ một vector Việc định tỷ lệ một vector nhằm thay đổi độ dài của hay đảo chiều của nĩ. sa = (sa1, sa 2 , , sa n ) Với s là hệ số tỷ lệ và a là vector. Khi s âm, chiều của sa ngược lại với a. Procedure Scalar(real s; vector a; vector &b) { b.d x = s a.d x ; b.d y = s y a.d y ; }  Phép trừ hai vector: Trên cơ sở cộng và định tỷ lệ, phép trừ dễ dàng định nghĩa: a-c = a +(-c) với thành phần thứ i là ai-ci. a-c a c -c  Trị tuyệt đối (độ dài) của vector Nếu một vector W được thể hiện trong khơng gian nhiều chiều (W 2 , W 2 , , W n ), dựa theo định lý Pithagore ta cĩ cơng thức sau: W (W 2 W 2 W 2 ) 1 2 n Thiết kế hệ thống kiểm tra các quan hệ hình học trang 12
  13. Luận văn tốt nghiệp Vector cĩ độ dài bằng zero thường được gọi là vector 0. Chương trình con minh họa như sau: Function Length(vector v): Real; Chuẩn hĩa vector -Vector đơn vị Việc định tỷ lệ một vector để kết qủa cĩ độ dài bằng 1 gọi là chuẩn hố một vector, và kết qủa gọi là vector đơn vị. Ví dụ dạng chuẩn hố ua của a như sau: ua = a / | a| và cĩ cùng chiều với a. Biểu thức cho hệ số của vector cĩ thể khai báo trực tiếp như sau: Normalize(vector v, vector &u); Nĩ cĩ dạng vector đơn vị u do các hệ số mỗi thành phần của v: u.d x := v.d x /Length(v); u.d y:= v.d y/Length(v);  Tổ hợp tuyến tính của vector: Để hình thành tổ hợp tuyến tính của hai vector V và W, định tỷ lệ mỗi vector theo các tỷ số a và b rồi cộng kết qủa để thành vector mới av+bw. Tổng quát, tổ hợp tuyến tính của m vector V 1, V 2 , , V m như sau: W = a1V 1 + a 2 V 2 + + a mV m Procedure Combo2D(float a,b vector u,v ,vector &W ); { w.dx:=a*u.dx+b*v.dx; w.dy:=a*u.dy+b*v.dy; } Tổ hợp lồi của vector Một lớp đặc biệt của tổ hợp tuyến tính cĩ vị trí quan trọng trong tốn học và ứng dụng số học trong đồ họa, đĩ là:Tổ hợp lồi (convex combination), hay tổ hợp tuyến tính mà các hệ số khơng âm và tổng bằng 1. Vậy tổ hợp tuyến tính: W = a 1 V 1 + a 2 V 2 + +a mV m là tổ hợp lồi nếu tổng  a i =1và a i 0, và cung “spline” thực ra là tổ hợp lồi của một tập các vector. Thiết kế hệ thống kiểm tra các quan hệ hình học trang 13
  14. Luận văn tốt nghiệp  Tích vơ hướng của hai vector: Tích vơ hướng của hai vector cho ta thơng tin đáng giá về một cặp vector như gĩc giữa chúng (cụ thể là khi nào chúng vuơng gĩc) và chiếu vector lên vector khác. Nĩ cũng cho ta phương trình của một mặt phẳng mơ tả bằng một điểm và hai vector. Cho hai vector, ví dụ hai chiều (a1,a2) và (b1,b2). Tích vơ hướng hai vector định nghĩa là: a.b = a1b1+ a2b2 Một cách tổng quát cho vector n chiều như sau: Cho Vector V= (v 1, v 2 , , v n ) và W=( w1, w 2 , , w n ), tích vơ hướng củahai vector trên là: V W V. W =  i i với i = 1, ,n Tích vơ hướng của hai vector được thể hiện trong thủ tục sau: Procedure Float Dot (vector a,b) { return Dot = a.d x * b.d x + a.d y* b.d y; } Các tính chất của tích vơ hướng 1. Đối xứng : a.b = b.a 2. Tuyến tính: (a+c).b = a.b + c.b 3. Đồng nhất : (sa).b = s(a.b) 4. | b2 | = b.b Độ dài của hiệu và tổng hai vector được cho như sau: | a-b|2 = |a|2 - 2ab + |b|2 | a+b|2 = |a|2 + 2ab + |b|2  Các ứng dụng của tích vơ hướng: a. Gĩc giữa hai vector (hay hai đường) Đây là ứng dụng quan trọng của tích vơ hướng. Hình a dưới cho thấy gĩc  giữa hai vector a và b. Các vector này cĩ thể cĩ hai, ba, hay nhiều chiều. Chúng tạo thành hai cạnh của tam giác, và cạnh thứ ba là a-b. Theo hệ thức lượng trong tam giác, ta cĩ : Thiết kế hệ thống kiểm tra các quan hệ hình học trang 14
  15. Luận văn tốt nghiệp | a-b|2 = |a|2 + |b|2 - 2 |a||b|cos() Từ phương trình này và phương trình | a-b|2 = |a|2 - 2ab + |b|2 ta suy ra được: a.b = |a||b| cos() Nghĩa là cos() = ua.ub a b Hình a Vậy cosin của gĩc giữa hai vector a và b là tích vơ hướng của dạng chuẩn hĩa hai vector. Dấu cuả vector a.b và sự trực giao Ta biết rằng cos( ) >0 nếu 90 0 cos( ) =0 nếu = 0 Do vậy từ phương trình: cos( ) = u a .u b ta cĩ gĩc giữa hai vector như sau:  Nhỏ hơn 90o nếu a.b >0  Bằng 900 nếu a.b = 0  Lớn hơn 90o nếu a.b 0 a.b=0 a.b<0 Thiết kế hệ thống kiểm tra các quan hệ hình học trang 15
  16. Luận văn tốt nghiệp b. Chiếu và phân tích vector: Hình trên ta phân tích a thành c theo chiều vector b và e. Theo cách này vector c gọi là chiếu trực giao của a lên b. Rõ ràng c cĩ cùng chiều với b, ta cịn phải tính độ lớn | c|. Theo phương trình a.b = |a||b|cos( ) và hệ thức lượng tam giác ta cĩ phương trình: a.b |c| = |a| = a.u b (*) a b Như thế độ dài của c chỉ phụ thuộc vào độ dài của a. Bây giờ ta hình thành vector c, bằng cách thêm chiều của b. c = |c|.ub Sau đĩ, kết hợp với phương trình (*) trên ta cĩ: c = ( a.ub)ub c = a.b b |b|2 Ví du: trong hai chiều, chiếu của a = (6,4) lên b = (1,2) như hình dưới y c e b a x Hình chiếu của c nằm dài hơn b kể từ gốc, từ phương trình trên ta cĩ độ dài của c là (2.8, 5.6), vector e = a-c = (3.2, -1.6 ). Thiết kế hệ thống kiểm tra các quan hệ hình học trang 16
  17. Luận văn tốt nghiệp c. Dạng điểm chuẩn cho đường và mặt phẳng Dạng điểm chuẩn cho đường và cho mặt phẳng dùng nhiều trong đồ họa như việc cắt loại bỏ đường bị che và tơ đa giác. n y L c A n c x Xét đường L đi qua điểm A = (Ax ,Ay) theo chiều vector c = (cx ,cy), ta cĩ vector n vuơng gĩc với vector c nghĩa là c.n = 0, cũng cĩ nghĩa là c x .n x+ c y.n y=0, hay: cy / cx = -nx / ny Điều kiện n trực giao với c cho ta suy ra n cĩ thể là bội số bất kỳ của (cx , cy), cĩ hai chiều đối nhau. Để cĩ phương trình cho đường L, xét điểm bất kỳ R = (x,y) trên L. Vector R phải vuơng gĩc với n, nên n.(R-A) = 0. Ta cĩ thể viết lại như sau: nR=nA, nhưng khơng thể nhân điểm với vector được. Ta thay vector R bằng r đi từ gốc và thay A bằng a. Như vậy, các tính tốn đều phụ thuộc vào việc chọn gốc tọa độ, cịn phương trình đường thẳng vẫn phụ thuộc vào gốc khơng cĩ gì thay đổi. Như vậy ta cĩ: n.r = D Với D = n.a = nx Ax + ny Ay Đây là phương trình điểm chuẩn cho đường. Phương trình này cĩ thể viết dạng quen thuộc như sau: nxx + nyy = D Mở rộng dạng điểm cho mặt phẳng Các mặt phẳng cũng cĩ thể biểu diễn ở dạng chuẩn điểm. Một mặt phẳng hồn tồn được xác định với một điểm S = (sx, sy, sz) nằm trong đĩ và hướng chuẩn của mặt phẳng. Chuẩn cho mặt phẳng được hiểu là vuơng gĩc với mọi đường trong mặt phẳng. Gọi hướng chuẩn là n= (nx, ny, nz). Với điểm R= (x, y, z) bất kỳ trong mặt phẳng, xây dựng vector từ R đến S, vuơng gĩc với n. n.(R-S) = 0 Thay R-S bằng r -s và dùng tính tuyến tính, ta được: n.r = D với D = n.s Thiết kế hệ thống kiểm tra các quan hệ hình học trang 17
  18. Luận văn tốt nghiệp Đây là phương trình điểm chuẩn của mặt phẳng. Mọi điểm trên mặt phẳng cĩ cùng tích vơ hướng với chuẩn. Nghĩa là mọi điểm cĩ cùng hình chiếu lên n. Phương trình mặt phẳng P thường viết là:Ax + By + Cz = D Tư tích vơ hướng của phương trình ta thấy rằng dạng điểm chuẩn thực ra là: nxX + nyY + nz Z = D Với A = nx, B = ny , và C = nz. Điều này cho thấy (A, B, C) là chiều chuẩn của mặt phẳng. Điểm trên mặt gần gốc nhất là điểm chiếu vuơng gĩc của gốc lên mặt. Như vậy nĩ tỉ lệ với n, gọi là Kn, nên khoảng cách là| Kn |. Vì Kn nằm trên mặt nên n. (Kn)=D. n S d. Kiểm tra nửa khơng gian trong và ngồi của một điểm Xét điểm Q, giả sử đường E đi qua điểm A và cĩ chuẩn hướng ra n như hình vẽ: E n E A inside Gĩc giữa n và Q -A 0. Tương tự, gĩc sẽ lớn hơn 90 0 nếu Q nằm phía trong, vì vậy n.(Q -A) D. 2. Trên E nếu p.n = D. 3. Ở nửa khơng gian phía trong của E nếu q.n < D. Thiết kế hệ thống kiểm tra các quan hệ hình học trang 18
  19. Luận văn tốt nghiệp Mở rộng cho mặt phẳng Giả sử mặt P qua điểm A và cĩ vector chuẩn hướng ra n thì điểm Q sẽ: 1. Ở nửa khơng gian phía ngồi của P nếu T=(q-a).n > 0 2. Trên P nếu (q-a).n=0 3. Ở nửa khơng gian phía trong của P nếu (q-a).n<0. e. Cắt đường thẳng với cửa sổ lồi Ta dùng kiểm tra trong-ngồi để xây dựng cơng cụ cắt hữu hiệu với cửa sổ là đa giác lồi bất kỳ. Cửa sổ W chứa một đa giác lồi cùng với đường thẳng L từ P1 tới P2. Ta muốn xác định phần thấy của L nằm trong W. Đa giác lồi nên phần trong cửa sổ được định nghĩa là vùng nằm ở nửa khơng gian phía trong của mỗi cạnh của W. Đoạn L được kiểm tra đối với mỗi cạnh của W, và phần nằm ở nửa khơng gian phía ngồi được loại ra. Sau khi mọi cạnh đã được kiểm tra, phần cịn lại của L sẽ nằm trong W.Ta biểu diễn L ở dạng tham số: P(t) = P1 + ct với c = P2 - P1. w P 1 L P Với mỗi cạnh cửa sổ, dùng hai giá trị t in và t out để giữ lại vùng của t mà đoạn cĩ thể nằm trong cửa sổ. Nghĩa là khơng thể thấy đoạn ở ngồi khoảng (t in , t out). Giá trị bắt đầu cho t in và t out là 0 và 1. Khoảng này liên tục được cắt xén khi xử lý xong mỗi cạnh. Nếu lúc nào khoảng này thành rỗng, thốt ra khỏi thuật giải cắt, và đoạn L hồn tồn bị cắt. Cịn khơng thì khoảng (t in, t out ) xác định phần của L nằm trong cửa sổ. Vì W lồi, mỗi cạnh E của nĩ cĩ thể cho là đường cho ở dạng điểm chuẩn: n.p = D Thiết kế hệ thống kiểm tra các quan hệ hình học trang 19
  20. Luận văn tốt nghiệp Với n là chuẩn hướng ra của cạnh. Bây giờ E cĩ thể cĩ một số tình huống so với đường L. P 1 P 1 n n c c E P E P E song song L: nếu n trực giao với c (nghĩa là: n .c= 0). Như vậy L sẽ nằm hồn tồn ở trong hoặc ở ngồi cửa sổ. Để xét tiếp, chọn điểm bất kỳ trên L, là P1 và kiểm tra trong-ngồi. Đặt p 1= P 1 - 0 là vector từ gốc tọa độ đến P 1. L sẽ hồn tồn nằm trong nếu: p1.n 0) thì đường sẽ đi ra. Ngược lại sẽ đi vào. Nếu đi vào, thì phần với t ti sẽ khơng thấy được, và t out được giảm về ti(nếu ti < t out). Khi kết thúc, giá trị của t in và t out sẽ được thay vào P1+ ct, để cĩ được các điểm đầu của đường bị cắt.  Tích hai vector Tích vector của hai vector là một vector. Một trong nhiều tính chất hữu dụng của nĩ là nĩ trực giao với hai vector ban đầu. Tích vector chỉ được định nghĩa cho vector ba chiều, nhưng nĩ cũng áp dụng trong một số vấn đề trong đồ họa liên quan đến đa giác hai chiều. Thiết kế hệ thống kiểm tra các quan hệ hình học trang 20
  21. Luận văn tốt nghiệp Cho vector a=(ax, ay, az) và b=(bx, by, bz) tích vector của chúng viết là a x b. Nĩ được định nghĩa theo các vector đơn vị chuẩn i, j, k như sau: a x b = (ay.bz - az.by).i + (az.bx - ax.bz).j + (ax.by - aybx).k Từ định nghĩa suy ra các tính chất đại số sau: 1. i x j = k j x k = i i x k = j 2. a x b = -b x b 3. a x (b + c) = a x b +a x c 4. (sa) x b = s(a xb) Ý nghĩa hình học của tích vector: 1. ax b trực giao với cả a và b. 2. Độ dài a x b bằng diện tích hình bình hành xác định bởi a và b. Diện tích này là: |a x b| = |a||b|sin( ) với là gĩc giữa a và b, đo từ a đến b hay ngược lại miễn sao gĩc nhỏ hơn 180 0 . 3. Chiều của a x b xác định từ quy tắc bàn tay phải khi làm việc trong hệ tay phải.  Tích bộ ba vơ hướng Cho ba vector a, b, c kết hợp chúng cho ra số vơ hướng như sau: S = a.(b x c) = ax (bycz -bzcy) + ay(bz cx - bxcz ) + az (bxcy - bycx). Ta co: S = a.(b x c) = b.(c x a) = c.(a x b) Tích bộ ba vơ hướng cĩ ý nghĩa hình học đơn giản. Giá trị của nĩ là thể tích của khối lăng trụ tạo bởi các vector a,b, c. Dấu của tích bộ ba vơ hướng tùy theo cos ( ) dương nếu 90 0 . a x b c Thể tích a x b x c b Thiết kế hệ thống kiểm tra các quan hệ hình học trang 21 a
  22. Luận văn tốt nghiệp  Phương trình mặt phẳng Trong khơng gian, qua 3 điểm A (xa, ya, za), B(xb, yb, zb), và C(xc, Yc, zc) khơng thẳng hàng xác định được phương trình mặt phẳng như sau: Ta cĩ vector AB = (x b-x a , y b-y a , z b-z a ) và AC = (x c -x a , y c -y a , z c -z a ) Tích hữu hướng của hai vector AB và AC là pháp vector n của mặt phẳng mp(ABC). Vector n cĩ tọa độ như sau: n = ((y b-y a)*(z c-z a) - (y c-y a)*(z b-z a), (z b-z a )*(x c-x a ) - (z c-z a )*(x b-x a ), (x b-x a )*(y c-y a) - (x c -x a )*(y b-y a )) Nếu chúng ta đặt: a 1 = (y b-y a )*(z c -z a ) - (y c -y a )*(z b -z a ) b1 = (z b-z a )*(x c-x a ) - (z c -z a)*(x b-x a ) c 1 = (x b -x a)*(y c-y a ) - (x c-x a )*(y b-y a ) d1 = - x a a1- y a b1- z a c1 thì vector n cĩ thể viết lại như sau: n = (a 1 , b 1 , c 1 ) Phương trình mặt phẳng được xác định theo định thức cấp 3 như sau: x-x x -x x -x a b a a a y-y y -y y -y = 0 a b a c a z-z z -z z -z a b a b a Thiết kế hệ thống kiểm tra các quan hệ hình học trang 22
  23. Luận văn tốt nghiệp Phương trình mặt phẳng mp(ABC) ở dạng tổng quát: a 1X + b 1 Y+ c 1Z + d 1= 0  Phương trình đường thẳng Trong khơng gian cho hai điểm A (xa , ya , za), B(xb , yb , zb) sẽ xác định được phương trình đường thẳng đi qua hai điểm A ,B như sau: Vector AB = (xb - xa , yb - ya , zb -za ) là vector chỉ phương của đường thẳng qua hai điểm A, B (để gọn hơn ta viết vector chỉ phương AB=(a1, a2, a3), phương trình của đường thẳng cĩ ba dạng như sau: Phương trình tham số: X = a t + x 1 a Y = a 2 t + y a Z = a 3 t + y a Phương trình dạng chính tắc: X xa Y y a Z z a = = (với điều kiện a1, a 2 , a 3 <> 0 ) a1 a 2 a 3 Phương trình dạng tổng quát: a2(x - xa ) = a1( y - ya ) a1(z - za ) = a3( x - xa ) Hệ phương trình trên tương đương với hệ phương trình sau: a 2 x - a1y + 0 + a 1y a- a 2 x a = 0 a 3x + 0 - a1z + a 1 z a - a 3x a = 0 Phương trình tổng quát của đường thẳng qua 2 điểm trong khơng gian là hệ phương trình bậc nhất 3 biến x, y, z như trên. II. CÁC ĐỐI TƯỢNG HÌNH HỌC VÀ SỰ TƯƠNG QUAN Trong phạm vi của mơn hình học thì khơng gian diễn dịch của nĩ rất lớn, chính vì vậy tơi thiết kế thuật tốn trên các đối tượng hình học cơ bản. Và từ những thuật tốn này chúng ta cĩ thể mở rộng ra cho một diễn dịch rộng lớn hơn. Thiết kế hệ thống kiểm tra các quan hệ hình học trang 23
  24. Luận văn tốt nghiệp II.1. CÁC QUAN HỆ HÌNH HỌC TRONG 2D 1. Các đối tượng hình học cơ bản: Điểm Đường thẳng Đa giác 2. Sự tương quan giữa các đối tượng hình học: Điểm - Đường thẳng. Điểm - Đa giác. Đường thẳng - Đường thẳng. Đường thẳng - Đa giác. Đa giác - Đa giác. 3. Kiểm tra sự tương quan giữa các đối tượng hình học: a. Điểm - Đường thẳng  Kiểm tra điểm cĩ thuộc đường thẳng?  Tính khoảng cách từ điểm đến đường thẳng nếu điểm khơng thuộc đường thẳng. b. Điểm - Đa giác  Kiểm tra điểm bên trong hay bên ngồi đa giác?. c. Đường thẳng - Đường thẳng  Kiểm tra hai đường thẳng trùng nhau, cắt nhau hay song song.  Tính gĩc giữa hai đường thẳng.  Tính hình chiếu của đoạn thẳng trên đường thẳng. d. Đường thẳng - Đa giác  Kiểm tra đường thẳng nằm bên trong hay bên ngồi đa giác.  Clip một đoạn thẳng vào đa giác. e. Đa giác - Đa giác  Kiểm tra sự tương quan giữa hai đa giác. Cắt nhau? Lồng nhau hay rời nhau? Tính diện tích giao nhau của hai đa giác.  Kiểm tra đa giác lồi, lõm.  Tính diện tích của đa giác. Thiết kế hệ thống kiểm tra các quan hệ hình học trang 24
  25. Luận văn tốt nghiệp II.2. CÁC QUAN HỆ HÌNH HỌC TRONG 3D 1. Các đối tượng hình học cơ bản: Điểm Đường thẳng Mặt phẳng 2. Sự tương quan giữa các đối tượng hình học: Điểm - Đường thẳng. Điểm - Mặt phẳng. Đường thẳng - Đường thẳng. Đường thẳng - Mặt phẳng. Mặt phẳng - Mặt phẳng. 3. Kiểm tra sự tương quan giữa các đối tượng hình học: a. Điểm - Đường thẳng  Kiểm tra điểm cĩ thuộc đường thẳng?  Tính khoảng cách từ điểm đến đường thẳng nếu điểm khơng thuộc đường thẳng. b. Điểm - Mặt phẳng  Kiểm tra điểm cĩ thuộc mặt phẳng?  Tính khoảng cách từ điểm đến mặt phẳng nếu điểm khơng thuộc mặt phẳng. c. Đường thẳng - Đường thẳng  Kiểm tra hai đường thẳng đồng phẳng, cắt, song song, chéo nhau, vuơng gĩc?  Tính gĩc giữa hai đường thẳng.  Tính khoảng cách giữa hai đường thẳng chéo nhau.  Tính hình chiếu của đoạn thẳng trên đường thẳng. d. Đường thẳng - Mặt phẳng  Kiểm tra đường thẳng thuộc mặt phẳng?  Kiểm tra đường thẳng và mặt phẳng cắt nhau?  Kiểm tra đường thẳng và mặt phẳng song song?  Kiểm tra đường thẳng và mặt phẳng vuơng gĩc?  Tính gĩc giữa đường thẳng và mặt phẳng nếu đường thẳng và mặt phẳng cắt nhau. Thiết kế hệ thống kiểm tra các quan hệ hình học trang 25
  26. Luận văn tốt nghiệp  Tính khoảng cách giữa đường thẳng và mặt phẳng nếu đường thẳng và mặt phẳng song song nhau. e. Mặt phẳng - Mặt phẳng  Kiểm tra hai mặt phẳng trùng nhau?  Kiểm tra hai mặt phẳng cắt nhau?  Kiểm tra hai mặt phẳng song song?  Kiểm tra hai mặt phẳng vuơng gĩc?  Tính gĩc giữa hai mặt phẳng nếu hai mặt phẳng cắt nhau.  Tính khoảng cách giữa hai mặt phẳng nếu hai mặt phẳng song song nhau.  Tìm giao điểm của hai mặt phẳng. III. CÁC THUẬT TỐN KIỂM TRA SỰ TƯƠNG QUAN GIỮA CÁC ĐỐI TƯỢNG HÌNH HỌC Trong phần này tơi trình bày cách thực hiện một vấn đề, được xây dựng theo logic nhằm mục đích để người đọc hoặc tham khảo cĩ thể dễ dàng kiểm tra so sánh đối chiếu giữa thuật tốn với cơ sở tốn học. III.1. CÁC QUAN HỆ HÌNH HỌC TRONG MẶT PHẲNG (2D) 1. Tính gĩc giữa hai đường thẳng Cơ sở tốn học: Đây là ứng dụng quan trọng của tích vơ hướng. Hình a dưới cho thấy gĩc  giữa hai vector a và b. Chúng tạo thành hai cạnh của tam giác, và cạnh thứ ba là a-b. a a-b b Từ định nghĩa tích vơ hướng của vector và là a.b= |a||b| cos( ) a a1,a2 b (b1,b2 ) với  :gĩc giữa vector a và vector b Và từ biểu thức giải tích của tích vơ hướng: a.b = a1 b1+ a 2 b 2 Thiết kế hệ thống kiểm tra các quan hệ hình học trang 26
  27. Luận văn tốt nghiệp 2 2 2 2 Ta cĩ cos( ) = a.b / |a||b|= a1b1 a2b2 / (a1 a2 )(b1 b2 ) Cos( ) dương nếu | | nhỏ hơn 90o, và âm nếu | | lớn hơn 90o. Giải thuật: - Tính vector chỉ phương a và b của 2 đoạn thẳng - Tính vector vơ hướng a.b - Cos ( )= a.b / |a| |b| - Gĩc 2 đoạn thẳng Alpha= arcos(cos( )) 2. Tìm hình chiếu của đoạn thẳng AB lên đường thẳng b Cơ sở tốn học: Để tính hình chiếu đoạn AB lên đường thẳng b đi qua C và D, ta tìm hình chiếu của điểm A là A’ và B là B’ trên đường thẳng b. Đoạn A’B’ chính là hình chiếu của AB trên đường b. B A (b) A’ B C D Xác định PT đi qua 2 điểm C, D: ax + by + c = 0 cĩ vector chỉ phương VCF = (x -x , y -y ) = (-b, a) và c = - a * x - b * y . D C D C C C Xác định PT đường thẳng đi qua điểm A và vuơng gĩc với CD: bx -ay + c’ = 0 cĩ vector chỉ phương của =(a, b) và c’= b*x + a*y A A Tính giao điểm A’(x , y ) của hệ PT (1) và (2) A’ A’ ax + by + c = 0 (1) bx - ay + c’= 0 (2) Thiết kế hệ thống kiểm tra các quan hệ hình học trang 27
  28. Luận văn tốt nghiệp x = (-c’*b + c*a) / ( a*a + b*b) A’ y = ( -c*b + c’*a) / ( a*a + b*b) A’ Tương tự tính B’ là giao điểm của: . Phương trình đường thẳng đi qua CD . Và Phương trình đường thẳng ’ đi qua B và vuơng gĩc với CD Giải thuật: - Tìm vector chỉ phương VCF (-b, a) của phương trình đường thẳng qua hai diểm C, D: ax + by + c =0 - Tính hệ số c. - Tính c1 của phương trình 1 đi qua điểm A và vuơng gĩc với CD: bx - ay + c1 = 0 - Tìm giao điểm A’của đường 1 và đường qua C, D . - Tìm giao điểm B’ của đường 2 đi qua điểm B và vuơng gĩc với đường thẳng CD. - Khi đĩ A’B’ chính là hình chiếu của AB. 3. Xác định giao điểm giữa hai đoạn thẳng Cơ sở tốn học: Cho hai đoạn thẳng, xác định chúng cĩ cắt nhau khơng, nếu cĩ tìm giao điểm.Giả sử đường 1 từ a đến b và đường 2 từ c đến d như trong hình vẽ, hai đoạn thẳng cĩ thể bố trí theo nhiều cách khác nhau. b d b d b d 1 b 2 c d a a a c a c c Phương trình tham số cho mỗi đường như sau: x1 (t) = ax + (bx - ax) * t (1) y1 (t) = ay + (by - ay) * t và (2) Thiết kế hệ thống kiểm tra các quan hệ hình học trang 28
  29. Luận văn tốt nghiệp x2 (u) = cx + (dx - cx) * u y2 (u) = cy + (dy - cy) * u Ta gọi các đường thẳng chứa các đoạn thẳng ab và cd là các đường cha, đây là các đường vơ hạn. Trước hết, ta xét hai đường “cha” cĩ giao nhau khơng, sau đĩ xem giao điểm cĩ thuộc cả hai đoạn thẳng khơng? Nếu các đường “cha’ giao nhau, ta cĩ giá trị to và uo sao cho: x1 (to) = x2(uo) và y1(to) =y2(uo) Từ đây, ta cĩ các phương trình sau: ax + (bx - ax) * to = cx + (dx - cx ) * uo (3) ay + (by - ay) * to = cy + (dy - cy ) * uo Khử uo, ta được: D* t = (c - a ) * (d - c ) - (c - a ) * (d - c ) o x x y y y y x x (4) với D = (b - a ) * (d - c ) - ( b - a ) * (d - c ) x x y y y y x x (5) Cĩ hai trường hợp cơ bản, D bằng hay khác 0. D khác zero Nếu D khác 0, ta tính to từ phương trình (4). Nếu to nằm ngồi đoạn [0, 1] thì khơng cĩ giao điểm giữa hai đoạn. Ngược lại, thì cĩ thể cĩ giao điểm, thay to vào (3) để tính uo. Nếu uo nằm trong đoạn [0, 1] thì chắc chắn cĩ giao điểm, và dùng phương trình (1) và (2) để tính. D bằng zero Nếu D bằng 0, từ phương trình (5) suy ra: (dy - cy) / (dx - cx) = (by - ay) / (bx - ax) (6) Nghĩa là các hệ số gĩc bằng nhau, nên các đường cha song song. Nếu các đường cha trùng nhau thì các đoạn cũng cĩ thể trùng nhau. Để kiểm điều này, ta xem c cĩ nằm trên đường cha đi qua a và b khơng. Dựa vào phương trình của đường cha là: (bx - ax) * (y - ay) - (by - ay) * (x - ax) = 0 (7) thay cx cho x và cy cho y và xem vế trái cĩ đủ gần 0 khơng (nghĩa là: nhỏ hơn lượng nào đĩ, như 10 - 5). Nếu khơng, các đường cha khơng trùng nhau, và khơng cĩ Thiết kế hệ thống kiểm tra các quan hệ hình học trang 29
  30. Luận văn tốt nghiệp giao điểm. Nếu thỏa mãn thì phải thực hiện bước kiểm cuối cùng để xem các đoạn cĩ trùng nhau khơng. Từ phương trình (1) tìm hai giá trị tc và td mà đường đạt tới vị trí c và d. Vì các đường cha trùng nhau, ta chỉ cần dùng thành phần x (nếu đường 1 thẳng đứng, thì dùng thành phần y), và thay cx và dx, ta cĩ : t = (c - a ) / (b - a ) c x x x x (8) td = (dx - ax) / (bx - ax) Đường 1 bắt đầu tại 0 và kết thúc tại 1, và xét thứ tự của bốn giá trị 0, 1, tc và td, ta xác định được vị trí tương đối của hai đường. Sẽ chồng nhau trừ khi cả hai tc và td nhỏ hơn 0 hay lớn hơn 1. Nếu cĩ trùng nhau, ta dễ dàng xác định các điểm đầu trùng nhau từ tc và td. Giải thuật được xây dựng trong thủ tục Intersect (), gồm các tham số là bốn điểm đầu của các đường, giá trị trả về cĩ thể cĩ thể cĩ các giá trị sau: 1: cĩ một giao điểm. 2: khơng giao nhau. 3: các đoạn thẳng song song nhau. 4: hai đoạn thẳng chồng nhau. 5: hai đoạn thẳng cùng nằm trên 1 đường thẳng, khơng cắt nhau. Giải thuật: -Tính Mẫu số D; -Nếu D 0 . Tính to,uo; . Nếu to thuộc [0,1] và uo thuộc [0,1] + Tính giao điểm M + Return 1; ( 2 đoạn thẳng cắt nhau tại M) Ngược lại Return 2; (2 doạn thẳng khơng cắt nhau) - Ngược lại, Thiết kế hệ thống kiểm tra các quan hệ hình học trang 30
  31. Luận văn tốt nghiệp . Nếu c nằm trên đoạn ab + Tính tc, td; + Nếu khơng phải cả tc và td 1 Return 4; (2 doạn thẳng chồng nhau) + Ngược lại, Return 5; (2đoạn thẳng nằm trên 1 đường thẳng và khơng cắt nhau) . Ngược lại, Return 3; (2 đoạn thẳng song song ) 4. Vẽ đa giác (Polygon) Cơ sở tốn học: Đa giác là tập hợp các đoạn thẳng liên tiếp cùng nằm trong mặt phẳng khép kín. Một đa giác cĩ ít nhất 3 cạnh. Như vậy, đa giác đơn giản nhất là tam giác. Giải thuật: - Xuất phát từ đỉnh đầu tiên - Vẽ nối đến đỉnh kế tiếp theo thứ tự cùng chiều kim đồng hồ. - Vẽ nối từ đỉnh cuối cùng đến đỉnh đầu tiên. 5. Vẽ n-giác Cơ sở tốn học: Một n-giác là đa giác quy tắc cĩ N cạnh (đa giác quy tắc: đa giác mà mọi cạnh cĩ độ dài bằng nhau, và các cạnh kề nhau tạo nên những gĩc trong bằng nhau). Nếu cho đỉnh đầu tiên trên trục x tại (R, x). Cho gĩc A bất kỳ, vị trí (x,y) của một điểm trên đường trịn cĩ gĩc A sẽ được tính (x,y) = (R cos(A), R sin(A)). Và đỉnh thứ i, V i , của n -giác nằm ở gĩc 2 (i -1) / N và cĩ vị trí: V i = ( R cos(2 (i -1) / N ), R sin(2 (i -1) / N) ). Giải thuật: - Số đỉnh = N - Định gĩc A = 2 Pi / N - Vịng lặp xác định đỉnh thứ i Thiết kế hệ thống kiểm tra các quan hệ hình học trang 31
  32. Luận văn tốt nghiệp . Gĩc = i *A; . Tìm tọa độ đỉnh V i . 6. Tơ màu đa giác Cơ sở tốn học: Phương pháp hiển thị các vùng được tơ màu trong đồ họa máy tính là quá trình xác định các pixel tương ứng thuộc vùng tơ màu cho nĩ. Cĩ nhiều thuật tốn đã được nghiên cứu và phát triển cho việc hiển thị các vùng được tơ màu trên màn hình, một trong những thuật tốn đĩ là tơ màu theo vết dầu loang, một thuật tốn khác là tơ màu theo dịng quét. Ở đây ta dùng phương pháp tơ màu theo dịng quét (scan-line algorithm) hay cịn gọi là giải thuật tơ màu chẵn lẻ (odd - even algorithm). Thuật giải này sử dụng các giao điểm giữa các đường biên của vùng cần tơ với các đường thẳng gọi là dịng quét và xác định các pixel nào nằm trong vùng tơ màu giữa hai giao điểm liên tiếp, đĩ chính là các pixel dọc theo đường quét nằm giữa hai giao điểm và nằm bên trong đa giác. Ở mỗi điểm giao dịng quét chuyển đổi hoặc đi vào hoặc đi ra khỏi đa giác, đĩ là sự thay đổi parity của điểm đĩ. Nếu dịng quét đi vào trong đa giác những pixels tiếp theo sẽ được tơ, nếu đi ra ngồi những pixels tiếp theo sẽ khơng được tơ. Khi dịng quét đi qua một đỉnh P của đa giác (chính là giao điểm của 2 cạnh của đa giác) nĩ tạo ra 2 giao điểm, mỗi điểm với 1 cạnh của đa giác đi qua đỉnh đĩ, nếu đỉnh ở giá trị cực (local extremum) Pixels ở bên trái và bên phải của đỉnh đĩ sẽ cĩ cùng parity, nhưng nếu đỉnh khơng ở giá trị cực các Pixels ở bên trái và bên phải của đỉnh đĩ sẽ cĩ parity ngược nhau, do đĩ ta cần cĩ một xử lý đặc biệt hơn. 4 1 Scan line 1 2, 3 2 Scan Line  Nếu P là giao điểm của hai cạnh cĩ hướng y ngược nhau (một cạnh cĩ giá trị y tăng,một cạnh cĩ giá trị y giảm - Scan Line 1) thì dịng quét cĩ 2 điểm giao.  Nếu P là giao điểm của hai cạnh cĩ hướng y trùng nhau (hai cạnh đều cĩ giá trị y cùng tăng hay giảm - Scan Line 2) thì dịng quét cĩ 1 điểm giao. Thiết kế hệ thống kiểm tra các quan hệ hình học trang 32
  33. Luận văn tốt nghiệp Trước khi tơ màu, ta cần kiểm tra mỗi đỉnh đa giác. Nếu y của nĩ khơng là giá trị cực trị(local extremum), như trong scan line 2. Vì những Pixels đối với bên trái và phải của đỉnh đĩ khác parity, khác giá trị kiểm tra inside-outside; ta phải làm ngắn một trong hai cạnh đi một chút (giảm y của đầu cạnh đĩ một pixel). Đối với cạnh nằm ngang trong đa giác khơng cần đưa vào tập các cạnh của đa giác để xử lý. Giải thuật: Bước 1: Xác định Frame “bao” đa giác. Frame bao đa giác là hình chữ nhật nhỏ nhất chứa tồn bộ đa giác. Để xác định hình chữ nhật này ta lấy min hoặc max các tọa độ đỉnh của đa giác trong hệ tọa độ Descartes rồi tăng, hoặc giảm 1 để đảm bảo hình chữ nhật là hình bao và đa giác hồn tồn nằm trong nĩ. Bước 2: Xác định danh sách các cạnh đa giác để xử lý. Lần lượt duyệt tất cả cạnh của đa giác: Khơng đưa cạnh nằm ngang của đa giác vào danh sách. Kiểm tra 2 cạnh đa giác liên tiếp, nếu đỉnh chung khơng là điểm cực trị (local extremum), làm ngắn đầu cạnh của một cạnh đi qua đỉnh chung một pixel. Bước 3: Tiến hành tơ màu. Tiến hành các đường quét ngang tư Ymin + 1 đến Ymax - 1. Ứng với một đường quét ngang yi nào đĩ, ta xác định các điểm cắt (bằng giải thuật tìm giao điểm giữa hai đoạn thẳng đã cĩ), giữa các đường quét ngang với tất cả các cạnh của đa giác. Vì tung độ y của điểm cắt bằng yi nên ta chỉ cần đưa các hồnh độ xi của điểm cắt vào một danh sách. Sắp xếp lại danh sách sao cho các giá trị xi tăng dần. Duyệt qua các điểm cắt và đếm số điểm cắt đã duyệt. Nếu điểm cắt trùng với đỉnh của đa giác: Nếu cĩ một cạnh song song với đường quét thì đỉnh trước đếm tăng và đỉnh sau khơng đếm tăng. Tơ màu giữa các cặp giao điểm . Bước 4: Lập lại bước hai cho đến khi yi = ymax. Bước 5: Vẽ lại đa giác bằng màu đã tơ. Thiết kế hệ thống kiểm tra các quan hệ hình học trang 33
  34. Luận văn tốt nghiệp Lưu ý: Nếu đa giác khơng phải là đa giác đơn thì giải thuật này khơng vận dụng được. 7. Điểm bên trong / bên ngồi đa giác Cơ sở tốn học: Giải thuật này nhằm xác định một điểm cho trước cĩ nằm bên trong một đa giác đơn phẳng hay khơng. Giải thuật xây dựng dựa trên định lý mang tên JORDAN sau đây: “Mỗi đường cong, kín, đơn, phẳng, một chiều, phân hoạch mặt phẳng thành hai miền, một trong hai miền đĩ hồn tồn chứa những đường thẳng nào đĩ, miền cịn lại thì khơng cĩ tính chất đĩ”. Trong định lý trên đây một trong hai miền sẽ được gọi là miền trong (gồm bản thân đường cong và phần mặt phẳng giới nội bởi đường cong). Khơng thuộc miền trong gọi là miền ngồi. Định lý này vẫn đúng cho trường hợp đa giác đơn phẳng một chiều như là một trường hợp riêng. Từ định lý này dẫn đến hệ quả sau: “Từ một điểm P bất kỳ, vẽ một tia chỉ cắt đa giác ở những điểm trong của các cạnh (nghĩa là : khơng đi qua đỉnh nào của đa giác); nếu số giao điểm là lẻ thì P là điểm trong, nếu số giao điểm là chẵn thì P là điểm ngồi”. Về mặt kỹ thuật mọi đường cong đơn, phẳng, kín, liên thơng, khơng tự cắt đều cĩ thể tiếp cận tuyến tính bằng một đa giác bao gồm một số hữu hạn các cạnh liên tiếp. Vì vậy cho phép xây dựng một giải thuật test quan hệ trong/ ngồi chỉ bằng cách xét số giao điểm của tia cĩ gốc là điểm cần xét. Giải thuật: - Chọn Px là nửa đường thẳng xuất phát từ P song song với trục Ox, hướng về phía x>0. Lấy P=(x,y). - P là điểm cần xét. - Nếu (P là một đỉnh) hoặc (P thuộc trong một cạnh) thì Return (P điểm trong) - Ngược lại, xác định giao điểm Px với các cạnh đa giác { Thiết kế hệ thống kiểm tra các quan hệ hình học trang 34
  35. Luận văn tốt nghiệp . Ci là cạnh Pi Pi+1 của đa giác . Nếu y = yi thì xét hai cạnh cĩ một đầu là Pi (1) Nếu cả hai đầu kia ở một phía của Pi thì tính Px cắt cả hai cạnh . Ngược lại (1) Nếu y > Max(yi,yi+1) hay y = xo thì Px khơng cắt Ci } - Nếu số giao điểm lẻ . Return P thuộc đa giác. 8. Kiểm tra quan hệ giữa đoạn thẳng và đa giác Các chương trình ứng dụng mơ tả các hình ảnh bằng hệ tọa độ thế giới thực, cĩ thể là bất kỳ hệ tọa độ Descartes nào mà người dùng cảm thấy thuận tiện nhất. Các hình ảnh được mơ tả trong hệ tọa độ thực sau đĩ sẽ được các hệ độ họa ánh xạ vào các hệ tọa độ thiết bị. Thơng thường, các hệ đồ họa cho phép người dùng xác định một vùng nào đĩ của hình ảnh được hiển thị và nĩ sẽ hiển thị ở đâu trên màn hình (viewport). Ta cĩ thể chọn một vùng hay nhiều vùng để hiển thị, các vùng này cĩ thể đặt ở các nơi khác nhau hay lồng vào nhau trên màn hình. Quá trình này địi hỏi nhiều thao tác như dịch chuyển, biến đổi tỷ lệ để đưa vào bên trong viewport hoặc đơn giản là loại bỏ các phần hình ảnh nằm ngồi vùng đang được xét. Thao tác cuối cùng và cũng được sử dụng nhiều nhất cịn được gọi là clipping. Trong thuật ngữ thơng thường Viewport được hiểu như một window (hình chữ nhật) theo đĩ hình ảnh được clipping. Tuy nhiên Viewport cũng cĩ thể là một đa giác bất kỳ. Bài tốn clipping sau đây được xét cho trường hợp tổng quát hơn: clipping với đa giác đơn bất kì (cho cả hai trường hợp đa giác lồi hoặc lõm). Thiết kế hệ thống kiểm tra các quan hệ hình học trang 35
  36. Luận văn tốt nghiệp Cơ sở tốn học và giải thuật: Các bước tiến hành clipping đoạn thẳng AB bằng một đa giác đơn, phẳng bất kì như sau: Bước 1: Hốn đổi A, B để xA < xB. Nếu xA = xB . Hốn đổi A,B để yA < yB Bước 2: Kiểm tra tính trong ngồi của A và B đối với đa giác (Dùng giải thuật kiểm tra điểm bên trong/ngồi đa giác ) Bước 3: Tìm giao điểm của AB với đa giác (Dùng giải thuật xác định giao điểm của 2 đoạn đã cĩ ) Nếu cĩ giao điểm thì { - Đưa các tọa độ của các điểm cắt vào một danh sách - Sắp xếp cho hồnh độ các giao điểm tăng dần (Nếu xA = xB sắp xếp theo tung độ) } Bước 4: Thực hiện clipping. - Nếu A và B đều nằm trong đa giác thì (1) Nếu số điểm cắt = 0, Return (AB nằm hồn tồn trong đa giác) - Ngược lại { . Đoạn thẳng từ A đến điểm cắt thứ 1 thuộc đa giác. . i = 1 . Lặp lại . Tìm trung điểm của đoạn thẳng nối hai điểm cắt kế tiếp nhau. . Kiểm tra trong /ngồi đối với trung điểm. Thiết kế hệ thống kiểm tra các quan hệ hình học trang 36
  37. Luận văn tốt nghiệp . Nếu trung điểm nằm trong đa giác thì Return (Đoạn thẳng thuộc đa giác) . Ngược lại, Return (Đoạn thẳng khơng thuộc đa giác). . Inc (i,1) Cho đến khi i = số điểm cắt } - Ngược lại, cĩ điểm A hay B nằm ngồi đa giác (1) - Nếu số điểm cắt = 0, Return (Đoạn AB nằm ngồi đa giác). - Nếu số điểm cắt <> 0 thì { . Thêm tọa độ điểm A vào đầu danh sách . Thêm tọa độ điểm B vào cuối danh sách . i = 1 . Lặp lại . Tìm trung điểm của đoạn thẳng nối hai điểm cắt kế tiếp nhau . Kiểm tra trong/ ngồi đối với trung điểm. . Nếu trung điểm nằm trong đa giác thì Return (Đoạn thẳng thuộc đa giác) . Ngược lại, Return (Đoạn thẳng khơng thuộc đa giác) . inc (i,1) Cho đến khi hết danh sách } - Ngược lại, Return (Đoạn thẳng khơng thuộc đa giác). Bước 5: Vẽ lại các đoạn thẳng thuộc đa giác Mở rộng: Giải thuật cĩ thể được mở rộng cho việc clipping một đa giác bằng cách thực hiện clipping tất cả các cạnh của đa giác. 9. Kiểm tra quan hệ hai đa giác Thiết kế hệ thống kiểm tra các quan hệ hình học trang 37
  38. Luận văn tốt nghiệp Cơ sở tốn học: Giải thuật này cho phép clip bất kỳ một đa giác vào 1 đa giác. Nĩ cũng cho phép hình thành sự giao, hội của 2 đa giác.Chúng ta bắt đầu bằng ví dụ minh họa trong hình sau. Ta liệt kê những đỉnh theo thứ tự từ trái sang phải, theo chiều kim đồng hồ. Hai đa giác SUBJ và CLIP được thể hiện bằng 2 danh sách (a,b,c,d) và (A,B,C,D) tương ứng. Tất cả điểm giao của 2 danh sách sẽ được xác định và lưu vào danh sách (theo thứ tự sang phải của mỗi cạnh). a C A c 6 B 5 3 1 2 4 d b Dựa vào hình vẽ trên, ta cĩ: D SUBJ_LIST: a, 1, b, 2, c, 3, 4, d, 5, 6 CLIP_LIST: A, 6 ,3 , 2, B, C, D, 4, 5 Duyệt SUBJ theo hướng đi tới cho tới khi tìm được 1 điểm giao đi vào (entering intersection), là điểm giao mà SUBJ di chuyển từ ngồi vào trong đa giác CLIP.Và đưa điểm này vào danh sách xuất đa giác được clip. Duyệt SUBJ tới khi gặp 1điểm giao khác. Nhảy ra khỏi SUBJ và di chuyển theo CLIP thay vì SUBJ. Duyệt CLIP theo hướng đi tới. Tới khi gặp một điểm giao, nhảy ra khỏi CLIP và duyệt theo SUBJ theo hướng đi tới, và cứ tiếp tục như vậy. Mỗi đỉnh hoặc mỗi điểm giao gặp phải khi duyệt sẽ được đưa vào danh sách xuất đa giác được clip. Lặp lại tiến trình trên giữa 2 đa giác, duyệt mỗi đa giác theo hướng đi tới cho tới khi đỉnh đầu tiên được gặp lại. Danh sách xuất ra ở thời điểm này (1,b,2,B) start restar SUBJ_LIST: a 1 b 2 a 3 4 d 5 6 Thiết kế hệ thống kiểm tra các quan hệ hình học trang 38
  39. Luận văn tốt nghiệp Bây giờ, ta kiểm tra một điểm giao“entering” khác của SUBJ. Và sẽ tạo ra danh sách xuất (3,4,5,6). Việc kiểm tra những điểm giao “entering” khác sẽ chỉ ra là tất cả chúng đã được duyệt, quá trình chấm dứt. Cách thức để hiện thực quá trình xử lý này là xây dựng hai danh sách SUBJ_LIST: a, 1, b, 2, c, 3, 4, d, 5, 6 CLIP_LIST : A, 6, 3, 2, B,1, C, D, 4 , 5 Mà trong đo, việc duyệt mỗi đa giác và liệt kê những đỉnh và điểm giao phải theo thứ tự được gặp. Giải thuật: -Bước 1: Tạo danh sách SUBJ_LIST Duyệt lần lượt mỗi cạnh đa giác SUBJ theo thứ tự cùng chiều kim đồng hồ { - Tìm các điểm cắt của cạnh Pi-Pi+1 với đa giác CLIP. - Sắp xếp danh sách điểm cắt theo hồnh độ tăng dần . Nếu hồnh độ Pi.x=Pi+1.x thì sắp xếp theo tung độ. - Đưa đỉnh Pi vào danh sách SUBJ_LIST - Đưa các điểm cắt từ danh sách điểm cắt vào SUBJ_LIST theo hướng đi từ Pi tới Pi+1 } -Bước 2: Tạo danh sách CLIP_LIST Duyệt lần lượt mỗi cạnh đa giác CLIP theo thứ tự cùng chiều kim đồng hồ { - Tìm các điểm cắt của cạnh Pi- Pi+1 với đa giác SUBJ. - Sắp xếp danh sách điểm cắt theo hồnh độ tăng dần. Nếu hồnh độ Pi.x=Pi+1.x sắp xếp theo tung độ. - Đưa đỉnh Pi vào danh sách CLIP_LIST. - Đưa các điểm cắt từ danh sách điểm cắt vào CLIP_LIST theo hướng đi từ Pi tới Pi+1. Thiết kế hệ thống kiểm tra các quan hệ hình học trang 39
  40. Luận văn tốt nghiệp } -Bước 3: Duyệt danh sách SUBJ_LIST và CLIP_LIST. Vịng lặp (1) Vịng lặp (2) - Tìm điểm giao “entering” chưa duyệt của SUBJ_LIST. - Duyệt trên SUBJ_LIST tới khi thấy điểm giao tiếp theo . - Chuyển sang duyệt trên CLIP_LIST tới khi thấy điểm giao tiếp theo. Cho tới khi điểm đầu tiên(điểm ‘entering’) được gặp lại. (vịng lặp 2 ) - Xuất Danh sách đa giác tìm được ở trên. Cho tới khi tất cả các điểm giao ‘entering’ đã được duyệt (vịng lặp 1) 10. Kiểm tra tính lồi của đa giác Cơ sơ tốn học: -Nhận biết quay trái với quay phải: Cĩ những thuật giải ta phải duyệt một đa giác, lần lượt thăm mỗi đỉnh hay cạnh. Ta xem như di chuyển theo một cạnh từ đỉnh này đến đỉnh kia và sau đĩ ra cạnh kế. Như vậy cần phải biết đi theo chiều phải hay trái. Ví dụ, nếu P1, P2, P3 là ba cạnh kề nhau của đa giác, ta tạo vector cạnh a=P2-P1 và b=P3- P2. Hình (1) cho thấy trường hợp a và b nằm trong mặt xy và quay trái khi đi từ a đến b. Cịn hình (2) là quay phải. b b a a Hình 1 Hình 2 Giả sử dùng hệ tay phải ở hình 1 và hình 2 nên trục z (hay chiều k) hướng ra ngồi từ trang sách tới chúng ta. Dùng quy tắc tay phải, tích a x b chỉ ra ngồi với thành phần k dương. Nếu lập tích vơ hướng vector này với chính k, sẽ được một đại lượng mà dấu của nĩ cho biết chiều quay, dương nếu quay trái và âm nếu quay phải. Cho vector a và b trong mặt xy, quay từ a đến b sẽ là dương nếu T= k.(a x b) >= 0 và âm nếu ngược lại (Kết quả khơng đổi đối với hệ tay trái). Với đa giác lồi, mọi phép quay cĩ cùng chiều, như đa giác A. Nếu đa giác khơng lồi, như trường hợp B, gồm cả hai phép quay. Như vậy, đa giác đơn là lồi nếu và chỉ nếu mọi phép quay cĩ cĩ cùng dấu khi được duyệt. Thiết kế hệ thống kiểm tra các quan hệ hình học trang 40
  41. Luận văn tốt nghiệp A B Giải thuật: - Duyệt đa giác theo thứ tự các đỉnh để xét việc quay từ cạnh a đến cạnh b tại mỗi đỉnh là quay phải hay quay trái. .Tính tọa độ theo hướng oz của tích vector a x b T= k(a x b) = ax*by - ay*bx - Nếu mọi phép quay đều như phép quay tại đỉnh thứ nhất, đa giác lồi. - Nếu cĩ một phép quay khác phép quay tại đỉnh thứ nhất,đa giác lõm. 11. Tính diện tích đa giác Cơ sở tốn học: Việc tính một đa giác đơn phẳng bất kỳ xuất phát từ việc tính diện tích tam giác. Diện tích tam giác được tính dựa vào tích hai vector như sau: S =(1/2) |a x b| Trong đĩ các vector a, b là các vector cạnh của tam giác. Với một đa giác n đỉnh, ta cĩ thể phân thành n - 2 tam giác bằng cách từ một đỉnh nào đĩ của tam giác ta vẽ các cạnh nối đến tất cả các cạnh cịn lại của đa giác. Khi đĩ diện tích đa giác bằng tổng diện tích của các tam giác con này. Lấy đỉnh P1 làm chốt, lập (n- 1) vector chốt vector a1=P2 - P1, a2 = P3 - P1, an-1=Pn - P1. Các vector này dùng để tính diện tích mỗi tam giác. Hai cạnh của tam giác i được xác định bởi hai vector ai và ai+1. P 3 P 2 P 4 P 1 P 5 Nhưng nếu đa giác là lõm, thì khơng phải mọi đa giác đều cĩ diện tích dương. Do đĩ để P hình thành cơng thức tổng quát tính diện6 tích một đa giác bất kỳ ta phải biến đổi cơng thức tính diện tích tam giác một chút. Thiết kế hệ thống kiểm tra các quan hệ hình học trang 41
  42. Luận văn tốt nghiệp Trong cơng thức tính diện tích tam giác trên, thay vì dùng trị tuyệt đối của tích hai vector, ta nhân nĩ với un, chuẩn hướng (độ dài đơn vị) ra của mặt chứa đa giác (nếu đa giác nằm trong mặt xy, un là k). Vector chuẩn hướng ra của mặt chứa đa giác được xác định bằng cách tính tích hữu hướng hai vector cạnh của tam giác. Nhân với chuẩn hướng ra un là để lọc ra diện tích âm và diện tích dương, nĩ khơng ảnh hưởng đến bản thân từng diện tích tam giác. Lúc này diện tích tam giác được tính theo cơng thức: S = (ax.by-ay.bx)/ 2 trong đĩ a, b là hai vector cạnh của tam giác. Khi đĩ diện tích của đa giác là: N 2 S =  S i i 1 trong đĩ Si là diện tích (cĩ dấu) của tam giác thứ I Giải thuật: - i bắt đầu = 2 - Diện tích đa giác = 0 - Lặp lại { . Tính diện tích tam giác cĩ 3 đỉnh là : đỉnh 1,đỉnh i, đỉnh i+1 . Diện tích đa giác = Diện tích đa giác + Diện tích tam giác . Inc (i,1) } Cho đến khi i=N-1 - Diện tích đa giác = Abs (diện tích đa giác) III.2. CÁC QUAN HỆ HÌNH HỌC TRONG KHƠNG GIAN (3D) 1- Các phép biến hình 3 chiều Cơ sở tốn học: Một trong những ưu điểm quan trọng của đồ họa là cho phép dễ dàng tác động lên các đối tượng đồ họa. Tất cả các biến đổi trên đồ họa máy tính đều cĩ thể thỏa mãn một cách tương đối dễ dàng vì các hình ảnh khi đưa vào xử lý đã được số hố, do đĩ nĩ cĩ thể thay đổi dễ dàng bằng các phép biến đổi tốn học. Phép biến đổi hình học thường được dùng là phép biến đổi Affine. Thiết kế hệ thống kiểm tra các quan hệ hình học trang 42
  43. Luận văn tốt nghiệp Cĩ hai quan điểm về phép biến đổi, đĩ là: Biến đổi đối tượng. Biến đổi hệ tọa độ. Biến đổi đối tượng: là thay đổi tọa độ các điểm mơ tả nĩ theo một quy luật nào đĩ. Biến đổi hệ tọa độ: sẽ tạo ra một hệ tọa độ mới và tất cả các điểm mơ tả đối tượng sẽ được chuyển về hệ tọa độ mới này. Phần này ta sẽ mơ tả một số phép biến đổi đối tượng. Phép biến đổi affine 3D biến đổi điểm P(Px,Py,Pz) thành điểm Q: Q = PM Với P = (Px, Py, Pz), Q = (Qx, Qy, Qz) và M là ma trận biến hình 4x4 m m m m 11 12 13 14 m m m m M = 21 22 23 24 m m m m 31 32 33 34 m m m m 41 42 43 44 Một số phép biến đổi Affine cơ sở, đĩ là: phép tịnh tiến, phép co dãn, phép quay. a/ Phép tịnh tiến: Dịch chuyển đối tượng từ vị trí này sang vị trí khác. Tịnh tiến với các độ dời tx, ty, tz. 1 0 0 0 0 1 0 0 M = 0 0 1 0 tx ty tz 1 b/Phép co dãn: Với hệ số co Sx , Sy, Sz. Ma trận M là Sx 0 0 0 M = 0 Sy 0 0 Thiết kế hệ thống kiểm tra các0 quan 0hệ hìnhSz học 0 trang 43 0 0 0 1
  44. Luận văn tốt nghiệp c/Phép quay quanh trục x gĩcA: Tọa độ x của vật thể khơng đổi. Ma trận M là 1 0 0 0 0 cos(A) sin(A) 0 M = 0 -sin(A) cos(A) 0 0 0 0 1 d/Phép quay quanh trục y gĩc A: Tọa độ y của vật thể khơng đổi. Ma trận M là: cos(A) 0 -sin(A) 0 0 1 0 0 M = sin(A) 0 cos(A) 0 0 0 0 1 e/Phép quay trục z gĩcA: Tọa độ z của vật thể khơng đổi. Ma trận M là cos(A) sin(A) 0 0 -sin(A) cos(A) 0 0 M = 0 0 1 0 0 0 0 1 * Tổng hợp các phép biến hình Phép biến hình T1: P Q’ cĩ ma trận M1. Phép biến hình T2 : Q’ Q cĩ ma trận M2. Tổng hợp 2 phép biến hình T1, T2 là phép biến hình T: P Q Phép biến hình T cĩ ma trận M = M1 x M2 Thiết kế hệ thống kiểm tra các quan hệ hình học trang 44
  45. Luận văn tốt nghiệp Giải thuật: - Tính các phần tử của ma trận M. - Xác định các điểm mới của đối tượng qua phép biến hình. -Vẽ lại đối tượng. 2- Biểu diễn đối tượng 3D Cơ sở tốn học: Các đối tượng trong thế giới thực hầu hết là các đối tượng 3D. Việc biểu diễn các đối tượng 3D trên mặt phẳng 2D, bằng máy tính phải tuân thủ các quy luật về phối cảnh nhằm giúp người xem cĩ ấn tượng hình ảnh gần đúng trong thực tế. Mơ hình khung dây(Wireframe) dùng biễu diễn các đối tượng 3D đơn giản như các khối đa diện, các mặt mà cĩ thể đơn giản hĩa cách thể hiện nĩ như gồm tập hợp gồm các đỉnh và các cạnh nối liền các đỉnh đĩ. Để lưu trữ mơ hình khung dây cần phải cĩ 2 danh sách: + Danh sách đỉnh chứa tọa độ các đỉnh. + Danh sách cạnh chứa các cặp đỉnh nối cạnh đĩ. Cấu trúc dữ liệu mơ tả Wireframe Typedef struct { int NumVerts; int NumEdges; Point3D vert [ ]; Point3D edge[ ][2]; } wireframe; Thiết kế hệ thống kiểm tra các quan hệ hình học trang 45
  46. Luận văn tốt nghiệp Để vẽ các đối tượng biểu diễn bằng mơ hình khung dây chúng ta chỉ cần vẽ các cạnh trong danh sách cạnh. Tuy nhiên do các đỉnh và cạnh được định nghĩa trong 3D nên để vẽ ta phải chiếu lên mặt phẳng 2D bằng các phép chiếu thích hợp : +Chiếu mỗi điểm lên 2D. +Vẽ đoạn thẳng giữa hai điểm chiếu này. Giải thuật: +Khởi tạo danh sách đỉnh. Đưa các đỉnh đa giác vào danh sách đỉnh. +Khởi tạo danh sách các cạnh. Đưa các cặp đỉnh nối cạnh vào danh sách cạnh. +Khởi tạo phép chiếu. Tìm các điểm chiếu của các đỉnh wireframe. +Vẽ các cạnh của đối tượng. Trong chương trình minh họa, chúng ta sẽ dùng mơ hình wireframe để biểu diễn một số đối tượng ba chiều đặc biệt như hình lăng trụ, hình chĩp.  Hình lăng trụ: Cơ sở của hình lăng trụ là một đa giác P nằm trên mặt xy và được quét dọc theo trục z đến một chiều cao H nào đĩ. Nếu đa giác P cĩ n đỉnh, hình lăng trụ cĩ 2*n đỉnh và 3*n cạnh. Danh sách đỉnh: n đỉnh đầu tiên dành cho đa giác P cĩ tọa độ z bằng 0, n đỉnh kế tiếp cĩ tọa độ z là h. Danh sách cạnh: n cạnh được chọn đầu tiên thuộc đa giác P sao cho prism.edge[i,1] là i và prism.edge[i,2] là i+1 (ngoại trừ khi i =n thì sẽ là 1 để thành đa giác), tương tự n cạnh kế ở mặt trên của hình trụ. Cuối cùng là n cạnh đứng của hình trụ cĩ prism.edge[i+2n,1] là i và prism.edge[i+2n] là i+n.  Hình chĩp: Đáy của hình chĩp là đa giác P cĩ n đỉnh nằm trên mặt xy. Và đỉnh hình chĩp khơng thuộc mặt xy. Hình chĩp cĩ 2*n đỉnh và 2*n cạnh. Danh sách đỉnh: n đỉnh đầu tiên dành cho đa giác P cĩ tọa độ z bằng 0, đỉnh kế tiếp (n+1) cĩ tọa độ z là h. Danh sách cạnh: n cạnh được chọn đầu tiên thuộc đa giác P sao cho pyramide.edge[i,1] là i và pyramide.edge[i,2] là i+1 (ngoại trừ khi i =n thì sẽ là 1 để thành đa giác). n cạnh kế cĩ pyramide.edge[i+n,1] là i và pyramide.edge[i+n,2] là n+1. Thiết kế hệ thống kiểm tra các quan hệ hình học trang 46
  47. Luận văn tốt nghiệp 3- Quan sát vật thể 3D qua hệ tọa độ quan sát Cơ sở tốn học: Một đối tượng 3-D được xác định bởi các tọa độ x,y,z,nhưng màn hình thì đối tượng được biểu diễn chỉ với các tọa độ x và y. Để cĩ thể biểu diễn được một đối tượng 3-D lên màn hình, cĩ hai phương pháp để thực hiện vấn đề trên là phép chiếu song song và phép chiếu phối cảnh. a. Phép chiếu song song: Loại hình đơn giản nhất của phép chiếu song song là phép chiếu trực giao nhưng lại cĩ rất nhiều ứng dụng trong các bản vẽ kỹ thuật. Với phép chiếu song song, một đối tượng 3-D được thể hiện lên màn hình bằng cách bỏ qua các tọa độ z. Kết quả là một hình 2-D đơn giãn. Như vậy, với trường hợp khối vuơng, hình ảnh thể hiện trên màn hình chỉ là một hình vuơng. b. Phép chiếu phối cảnh: Khác với phép chiếu song song, phép chiếu phối cảnh được hình thành từ các tia chiếu khơng song song với nhau mà hội tụ tại một điểm gọi là tâm chiếu. Kích thước của vật qua phép chiếu sẽ được phĩng to hay thu nhỏ phụ thuộc vào khoảng cách giữa tâm chiếu và mặt phẳng chiếu (mặt quan sát). Khoảng cách giữa mắt và mặt quan sát gọi là tầm nhìn. y’ z x, ’ P P ’ z R D 0 y  Trong đĩ: x Ox’y’z’: Hệ trục tọa độ quan sát. D: Khoảng cách giữa mặt phẳng chiếu và hệ trục quan sát. R: Khoảng cách giữa 2 gốc tọa độ. Thiết kế hệ thống kiểm tra các quan hệ hình học trang 47
  48. Luận văn tốt nghiệp : gĩc giữa hình chiếu OO’trên mặt phẳng xoy và trục ox. : gĩc giữa OO’và mặt phẳng xoy. Mắt đặt tại gốc hệ tọa độ quan sát đặt dọc với trục O’z’hướng vào gốc O. Mặt phẳng quan sát vuơng gĩc với OO’. Khi thay đổi gĩc  và gĩc sẽ dẫn đến việc thay đổi gĩc quan sát vật thể từ đĩ việc thể hiện đối tượng được quan sát sẽ linh động hơn. Để chuyển đổi điểm P(x,y,z) trong hệ tọa độ Oxyz ra tọa độ (xo,yo,zo) trong hệ tọa độ thứ hai dựa trên x,y,z chúng ta sử dụng cơng thức sau: (xo,yo,zo,1) = (x,y,z,1) * T với là ma trận biến hình T -sin -cos sin -cos cos 0    cos -sin sin -sincos 0 T = 0 cos -sin 0 0 0 R 1 và xo = -x sin + y cos yo = -x cossin - y sinsin + z cos zo = -x coscos - y sincos - zsin + R Hình chiếu P’(xc, yc) của điểm P(xo, yo, zo): Do mặt phẳng màn hình vuơng gĩc với trục Oz’ và tâm chiếu là O’. x’ màn hình màn hình ’ P z x0 ’ y P xc c P’ P z’ D z 0 y’ Ap dụng tính chất tam giác đồng dạng, ta cĩ: xc = D*xo / zo yc = D*yo / zo Thiết kế hệ thống kiểm tra các quan hệ hình học trang 48
  49. Luận văn tốt nghiệp Với phép chiếu phối cảnh, tọa độ của điểm chiếu là: P’.xc =D*xo/ zo P’.yc = D*yo/ zo Với phép chiếu song song, mắt đặt ở vơ cực, vì vậy: xc = xo và yc = yo Vậy từ điểm P(x,y,z) trên đối tượng 3D qua phép chiếu phối cảnh hay song song đã cho ta điểm P’(xc,yc) trong mặt phẳng 2D. + Tăng gĩc  sẽ làm hệ quan sát xê dịch trong mặt phẳng xy theo chiều ngược chiều kim đồng hồ làm quay vật thể theo chiều kim đồng hồ. + Giảm gĩc  làm quay vật thể ngược chiều kim đồng hồ. + Tăng gĩc sẽ đẩy hệ quan sát lên trên làm quay vật xuống dưới. + Giảm gĩc làm quay vật lên trên. Giải thuật ứng dụng trong vẽ mơ hình khung dây. + Trường hợp nhấn phím mũi tên Up : gĩc  =  - 5; (tính theo độ) Down : gĩc  =  + 5; Left : gĩc = - 5; Right : gĩc = + 5; + Khởi tạo lại phép chiếu Tìm các điểm chiếu của các đỉnh wireframe. + Vẽ lại các cạnh của đối tượng. 4 -Kiểm tra quan hệ Điểm - Đường thẳng Cơ sở tốn học và giải thuật: Begin - Nhập tọa độ 2 điểm A(xa, ya , za), B(xb, yb, zb ) mà đường thẳng d đi qua. - Nhập tọa độ điểm C (xc , yc , zc). - Tính tọa độ vector chỉ phương của đường thẳng d . Vector AB = (xb - xa ; yb - ya ; zb -za ) ( hay AB=( a1,a2,a3 ) ) Thiết kế hệ thống kiểm tra các quan hệ hình học trang 49
  50. Luận văn tốt nghiệp . Phương trình tổng quát đường thẳng d qua hai điểm A, B là hệ phương trình tương đương với hệ sau: a2x - a1y + 0 + a1ya - a2xa = 0 a3x + 0 - a1z + a1za - a3xa = 0 - Thay tọa độ của điểm C (xc , yc , zc) vào hệ phương trình tổng quát của đường thẳng, ta được: a2xc - a1yc + 0 + a1ya - a2xa = 0 a3xc + 0 - a1zc + a1za - a3xa = 0 . Nếu hệ trên thỏa thì điểm thuộc đường thẳng, xuất thơng điệp “ĐIỂM THUỘC ĐƯỜNG THẲNG“; . Nếu khơng thỏa tính khoảng cách từ điểm đến đường thẳng: Viết phương trình của mặt phẳng qua C(xc , yc , zc) vuơng gĩc với đường thẳng d qua 2 điểm A , B và cĩ vector chỉ phương AB = (a1 , a2 , a3). Phương trình mặt phẳng cĩ dạng: a1x + a2y + a3z - a1xc - a2yc - a3zc = 0 (* ) Viết phương trình tham số của đường thẳng qua A, B X = a1t + xa Y = a2t + ya Z = a3t + za Thay X , Y, Z vào phương trình mặt phẳng (*), ta được:  a1( a1t + xa)+ a2( a2t + ya) + a3( a3t + za) - a1xc - a2yc - a3zc = 0  t = a1xa - a2ya - a3za + a1xc + a2yc + a3zc / 2 2 2 ( a1 + a2 + a3 ) Thay t vào phương trình tham số của đường thẳng d qua A, B tìm được điểm H - Tọa độ cuả điểm cắt H(Xh , Yh ,Zh): 2 2 2 Xh = a1(a1xa - a2ya - a3za + a1xc + a2yc + a3zc)/ ( a1 + a2 + a3 ) + xa 2 2 2 Yh = a2(a1xa - a2ya - a3za + a1xc + a2yc + a3zc)/ ( a1 + a2 + a3 ) + ya 2 2 2 Zh = a3(a1xa - a2ya - a3za + a1xc + a2yc + a3zc)/ ( a1 + a2 + a3 ) + za - Tính khoảng cách từ điểm C đến đường d qua 2 điểm A, B: 2 2 2 dch = | CH | = sqrt(( xc - xh ) + ( yc - yh ) + ( zc - za ) ) - Xuất tọa độ điểm H(Xh , Yh ,Zh) và khoảng cách dch End. 5 - Kiểm tra quan hệ Điểm - Mặt phẳng Cơ sở tốn học và giải thuật: Begin Thiết kế hệ thống kiểm tra các quan hệ hình học trang 50
  51. Luận văn tốt nghiệp - Nhập tọa độ 3 điểm A(xa , ya , za), B(xb , yb , zb ), C ( xc , yc , zc) xác định mặt phẳng mp(ABC) (3 điểm A, B, C khơng thẳng hàng). - Nhập tọa độ điểm D(xd , yd , zd). - Tính các vector : vector AB = ( xb - xa , yb - ya , zb - za ) vector AC = ( xc - xa , yc - ya , zc - za ) vector AD = ( xd - xa , yd - ya , zd - za ) - Xét điểm D(xd , yd, zd) cĩ thuộc mp(ABC) khơng? . Tính tích hữu hướng của 2 vector AB, AC là n = AB x AC cĩ dạng định thức như sau: y - y z -z z -z x - x x - x y - y n = b a b a b a b a b a b a yc - ya zc-za , zc -za xc - xa , xc - xa yc - ya Hoặc cĩ thể theo cách viết dưới đây: AB x AC = ((yb - ya )*(zc - za) - (yc - ya)*(zb - za), (zb - za )*(xc - xa) - (zc - za)*(xb - xa), (xb - xa )*(yc - ya) - (xc - xa)*(yb - ya)) . Tính tích vơ hướng của 2 véc tơ n=(AB x AC) và vector AD là (ABxAC).AD bằng dùng định thức cấp 3 với ba véc tơ AB, AC, AD như sau: xb - xa yb - ya zb - za Dt = xc - xa yc - ya zc - za x - x y - y z - z d a d a d a Dt = (AB x AC).AD = ( xd - xa )(( yb - ya )*( zc -za ) - (yc - ya )*( zb -za ) ) + (yd - ya )(( zb -za )* (xc - xa ) - ( zc -za ) *(xb - xa ) ) + (zd - za )((xb - xa )*( yc - ya ) - (xc - xa )*( yb - ya )) . Ta xét định thức cấp 3 này Nếu Dt = 0 xuất “Điểm D thuộc mp(ABC)“ Nếu Dt 0 tìm khoảng cách từ điểm D đến mp(ABC) Viết phương trình tổng quát của mp(ABC), cĩ 2 vector AB = (xb - xa ,yb - ya , zb -za ) AC = (zb - za , yc - ya , zc - za ) N = (AB x AC) = (( yb - ya )*( zc - za ) - (yc - ya )*(zb - za ), Thiết kế hệ thống kiểm tra các quan hệ hình học trang 51
  52. Luận văn tốt nghiệp ( zb - za )* (xc - xa ) - (zc - za )*(xb - xa ), ( xb - xa )*(yc - ya ) - (xc - xa )*(yb - ya )) Nếu chúng ta đặt: A = (yb - ya )*( zc -za ) - (yc - ya )*( zb -za ) B = ( zb -za )* (xc - xa ) - ( zc -za )*(xb - xa ) C = (xb - xa )*(ya - yb ) - (xc - xa )*( xb - xa) D = -xaA - yaB - zaC . vector n cĩ thể viết lại n =(A, B, C ) là pháp vector của mp(ABC). Và phương trình tổng quát của mặt phẳng mp(ABC) la: Ax + By + Cz + D = 0 . Khoảng cách từ D(xd , yd , zd) đến mp(ABC) 2 2 2 ddmp(ABC) = abs( Axd + Byd + Czd + D ) / sqrt (A + B + C ) . . Xuất ra “ ddmp(ABC) “ - Tìm giao điểm của đường thẳng d qua D(xd, yd, zd) và vuơng gĩc với mp(ABC), cĩ vector chỉ phương là pháp vector n = (A, B, C). Phương trình tham số của đường thẳng d: X = At + xd Y = Bt + yd Z = Ct + zd . Thay X , Y , Z vào phương trình mặt phẳng mp(ABC): A( At + xa) + B( Bt + ya) + C(Ct + za) + D = 0 2 2 2  t = -(Axd + Byd + Czd + D ) / ( A + B + C ) . Thay t vào phương trình tham số của đường thẳng d. Ta cĩ tọa độ điểm cắt H(Xh , Yh ,Zh) 2 2 2 Xh = A(-(Axd + Byd + Czd + D ) / ( A + B + C ))+ xd 2 2 2 Yh = B(-(Axd + Byd + Czd + D ) / ( A + B + C )) + yd 2 2 2 Zh = C(-(Axd + Byd + Czd + D ) / ( A + B + C )) + za . Xuất tọa độ điểm H(Xh , Yh ,Zh) End. 6 - Kiểm tra quan hệ Đường thẳng - Đường thẳng Cơ sở tốn học và thuật giải: Begin - Nhập tọa độ 2 điểm A(xa , ya , za) và B(xb , yb , zb) mà đường thẳng d đi qua. - Nhập tọa độ 2 điểm C(xc , yc , zc) và D(xd , yd , zd) mà đường thẳng d’ đi qua. Thiết kế hệ thống kiểm tra các quan hệ hình học trang 52
  53. Luận văn tốt nghiệp - Tính véc tơ chỉ phương AB của đường thẳng d: AB =( xb - xa , yb - ya , zb - za ) ( hay cĩ thể viết gọn hơn AB = ( a1 , a2 , a3 ) ) - Tính véc tơ chỉ phương CD của đường thẳng d’ CD = ( xd - xc , yd - yc , zd - zc ) (hay cĩ thể viết gọn hơn CD = ( b1 , b2 , b3 ) ) - Viết phương trình của đường thẳng d: Phương trình chính tắc: ( x - xa )/ a1 = ( y - ya )/ a2 = ( z - za )/ a3 Hệ phương trình tổng quát của đường thẳng d : a2x - a1y + 0 + a1ya - a2xa = 0 a3x + 0 - a1z + a1za - a3xa = 0 - Viết phương trình của đường thẳng d’: Phương trình chính tắc: ( x - xc )/ b1 = ( y - yc )/ b2 = ( z - zc )/ b3 Hệ phương trình tổng quát của đường thẳng d’: b2x - b1y + 0 + b1yc - b2xc = 0 b3x + 0 - b1z + b1zc - b3xc = 0 - Xét sự tương quan của đường thẳng d qua A, B và d’qua C, D: Ta cĩ 3 vector AB, CD, AC: Vector AB = ( xb - xa , yb - ya , zb - za ) Vector CD = ( xd - xc , yd - yc , zd - zc ) Vector AC = ( xc - xa , yc - ya , zc - za ) Lập định thức cấp 3 của 3 vector AB, CD, AC xb - xa yb - ya zb - za Dt = xd - xc yd - yc zd - zc xc - xa yc - ya zc - za Dt = (Ab x CD).AC = ( xc - xa )(( yb - ya )*( zd - zc ) - ( yd - yc )*( zb -za )) + ( yc - ya )(( zd - zc )*( xc - xa ) - ( zc - za )*( xb - xa )) + ( zc - za )(( xb - xa )*( yd - yc ) - ( xd - xc )*( yb - ya )) - Nếu (Dt<>0), xuất ra kết quả “Hai đường thẳng d và d’ chéo nhau“. Thiết kế hệ thống kiểm tra các quan hệ hình học trang 53
  54. Luận văn tốt nghiệp - Nếu ((Dt = 0) AND (a1 / b1 = a2 / b2 = a3 / b3)), xuất ra kết quả “ Hai đường thẳng d và d’ song song“. - Nếu ((Dt = 0) AND (a1 / b1 = a2 / b2 = a3 / b3) AND (d, d’cĩ 2 điểm chung)), xuất ra kết quả “ Hai đường thẳng d và d’ trùng nhau“. - Nếu ((Dt = 0) AND (a1 / b1 a3 / b3)), xuất ra kết quả “Hai đừơng thẳng d và d’cắt nhau“. - Tìm tọa độ của điểm cắt nhau giữa hai đường thẳng d và d’: Hệ phương trình tổng quát của đường thẳng d: a2x - a1y + 0 + a1ya - a2xa = 0 a3x + 0 - a1z + a1za - a3xa = 0 Hệ phương trình tổng quát của đường thẳng d’: b2x - b1y + 0 + b1yc - b2xc = 0 b3x + 0 - b1z + b1zc - b3xc = 0 Giải các hệ phương trình tổng quát của đường thẳng d, d’: a2x - a1y + 0 + a1ya - a2xa = 0 a3x + 0 - a1z + a1za - a3xa = 0 (*) b2x - b1y + 0 + b1yc - b2xc = 0 Đặt: d1 = a1ya - a2xa d2 = a1za - a3xa d3 = b1yc - b2xc Hệ phương trình (*) viết lại như sau: a2x - a1y + 0 + d1 = 0 a3x + 0 - a1z + d2 = 0 b2x - b1y + 0 + d3 = 0 Lập định thức cấp 3 cho hệ ba phương trình trên để tìm tọa độ giao điểm của đường thẳng d và d’: a2 -a1 0 Dt = a 0 -a gd 3 1 b -b 0 2 1 -d1 -a1 0 Dt = xgd -d2 0 -a1 -d3 -b1 0 Thiết kế hệ thống kiểm tra các quan hệ hình học trang 54 a2 -d1 0 Dt = a3 -d2 -a1 ygd b2 -d3 0
  55. Luận văn tốt nghiệp Tọa độ giao điểm của đường thẳng d, d’ là E(xgd , ygd , zgd): xgd = Dtxgd / Dtgd ygd = Dtygd / Dtgd zgd = Dtzgd / Dtgd - Xuất ra kết quả tọa độ giao điểm E(xgd , ygd , zgd). - Nếu (Dt <> 0) thì hai đường thẳng d và d’ chéo nhau Tính khoảng cách giữa đường thẳng d và d’(đoạn vuơng gĩc chung). End. 7 - Kiểm tra quan hệ Đường thẳng - Mặt phẳng Cơ sở tốn học và giải thuật: Begin - Nhập tọa độ 3 điểm A(xa , ya , za), B(xb , yb , zb ), C(xc , yc , zc) xác định mặt phẳng mp(ABC) (3 điểm A, B, C khơng thẳng hàng với nhau). - Nhập tọa độ 2 điểm E(xe , ye , ze) và F(xf , yf , zf) mà đường thẳng d đi qua. - Tính tọa độ các vector : AB = ( xb - xa , yb - ya , zb - za ) AC = ( xc - xa , yc - ya , zc - za ) - Tính tích hữu hướng của 2 vector AB, AC cĩ dạng định thức cấp 2 như sau (n = AB x AC chính là pháp vector của mp(ABC)) y -y z -z z -z x -x x -x y -y Ab x AC = b a b a b a b a b a b a y -y z -z , z -z x -x , x -x y -y c a c a c a c a c a c a Hoặc cĩ thể viết dưới dạng như sau: Thiết kế hệ thống kiểm tra các quan hệ hình học trang 55
  56. Luận văn tốt nghiệp n = AB x AC = (( yb - ya )*( zc - za ) - ( yc - ya )*( zb -za ), ( zb - za )*( xc - xa ) - ( zc - za )*( xb - xa ), ( xb - xa )*( yc - ya ) - ( xc - xa)*( yb - ya )) Nếu chúng ta đặt: A = ( yb - ya )*( zc - za ) - ( yc - ya )*( zb - za ) B = ( zb - za )*( xc - xa ) - ( zc - za )*( xb - xa ) C = ( xb - xa )*( ya - yb ) - ( xc - xa)*( xb - xa ) D = -xaA - yaB - zaC Phương trình tổng quát của mặt phẳng mp(ABC) cĩ dạng: Ax + By + Cz + D = 0 - Tính vector chỉ phương EF của đường thẳng d đi qua hai điểm E và F: vector EF = ( xf - xe , yf - ye , zf - ze ) ( cĩ thể viết gọn lại EF = ( a1 , a2 , a3 ) ) -Viết phương trình tham số của đường thẳng d: X = a1t + xe Y = a2t + ye Z = a3t + ze - Xét sự tương quan giữa đường thẳng d qua 2 điểm E, F và mp(ABC) qua 3 điểm A, B, C : Tính tích vơ hướng của 2 vector (AB x AC) và vector EF bằng việc sử dụng định thức cấp 3 với ba vector AB, AC, EF như sau: vector AB = ( xb - xa , yb - ya , zb - za ) vector AC = ( xc - xa , yc - ya , zc - za ) vector EF = ( xf - xe , yf - ye , zf - ze ) Định thức cấp 3: xb - xa yb - ya zb - za Dt = xc - xa yc - ya zc - za x - x y - y z - z f e f e f e Dt = (AB x AC).EF = ( xf - xe )(( yb - ya)*( zc - za ) - ( yc - ya )*( zb - za )) + ( yf - ye )(( zb - za )*( xc - xa ) - ( zc -za )*( xb - xa )) + ( zf - ze )(( xb - xa )*( yc - ya ) - ( xc - xa)*( yb - ya )) Xét định thức cấp 3 này: + Nếu Dt = 0, xuất ra kết quả “Đường thẳng d song song hoặc chứa trong mp(ABC)“ + Nếu Dt<>0, xuất ra kết quả “Đường thẳng d cắt mp(ABC)“ Thiết kế hệ thống kiểm tra các quan hệ hình học trang 56
  57. Luận văn tốt nghiệp - Nếu Dt<>0, tìm tọa độ giao điểm giữa đường thẳng d và mp(ABC): + Phương trình tổng quát của mặt phẳng mp(ABC) cĩ dạng: Ax + By + Cz + D = 0 + Phương trình tham số cuả đường thẳng d: X = a1t + xe Y = a2t + ye Z = a3t + ze + Thay X, Y, Z vào phương trình mặt phẳng (ABC), ta được: A( a1t + xe) + B( a2t + ye) + C(a3t + ze) + D = 0  t = -(Axe + Bye + Cze + D ) / ( Aa1 + Ba2 + Ca3 ) + Thay t vào phương trình tham số cuả đường thẳng d, ta cĩ tọa độ giao điểm của d và mp(ABC): Xgd = a1(-(Axe + Bye + Cze + D ) / ( Aa1 + Ba2 + Ca3 ) ) + xe Ygd = a2(-(Axe + Bye + Cze + D ) / ( Aa1 + Ba2 + Ca3 ) ) + ye Zgd = a3(-(Axe + Bye + Cze + D ) / ( Aa1 + Ba2 + Ca3 ) ) + ze + Xuất ra tọa độ giao điểm H(xgd , ygd , zgd). - Tính gĩc giữa đường thẳng d qua E, F và mp(ABC) qua A, B, C 2 2 2 2 2 2 Cos(AB^n) = abs(Aa1 + Ba2 + Ca3 ) / sqrt(A + B + C ) * sqrt(a1 + a2 + a3 ) - Đường thẳng d song song với mp(ABC). Tính khoảng cách từ đường thẳng d đến mp(ABC): + Viết phương trình đường thẳng d’qua điểm E và vuơng gĩc với mặt phẳng (ABC) cĩ pháp vector n=(A , B, C ) X = At + xe Y = Bt + ye Z = Ct + ze + Thay X , Y , Z vào phương trình mặt phẳng (ABC), ta được: A( At + xe) + B( Bt + ye) + C(Ct + ze) + D = 0 2 2 2  t = -(Axe + Bye + Cze + D ) / ( A + B + C ) + Thay t vào phương trình tham số của đường d’, ta cĩ tọa độ giao điểm giữa đường thẳng d’và mp(ABC): 2 2 2 Xh = A(-(Axe + Bye + Cze + D ) / ( A + B + C )) + xe 2 2 2 Yh = B(-(Axe + Bye + Cze + D ) / ( A + B + C )) + ye 2 2 2 Zh = C(-(Axe + Bye + Cze + D ) / ( A + B + C ) ) + ze + Xuất ra tọa độ giao điểm H( xh , yh , zh ) . + Tính khoảng cách từ đường thẳng d đến mp(ABC), chính là đoạn AH: 2 2 2 dah = sqrt ( ( xh - xa ) + ( yh - ya ) + ( zh - za ) ) Thiết kế hệ thống kiểm tra các quan hệ hình học trang 57
  58. Luận văn tốt nghiệp + Xuất ra khoảng cách dah End. 8 . Kiểm tra quan hệ Mặt phẳng - Mặt phẳng Cơ sở tốn học và thuật giải: Begin - Nhập tọa độ 3 điểm A(xa, ya, za), B(xb, yb, zb ), C(xc, yc, zc) để xác định tọa độ mp(ABC) - Nhập tọa độ 3 điểm M(xm , ym , zm), P(xp , yp , zp ), Q( xq , yq , zq) để xác định tọa độ mặt phẳng mp(MPQ). - Tính tọa độ các véc tơ của mp( ABC) vector AB = ( xb - xa , yb - ya , zb - za ) vector AC = ( xc - xa , yc - ya , zc - za ) (3 điểm A,B,C tạo thành mp(ABC) nên vector AB khơng cùng phương với vectơ AC) -Tính tích hữu hướng của 2 vector AB, AC là n = (AB x AC),n chính là pháp vector của mp(ABC) cĩ tọa độ : n = AB x AC = (( yb - ya )*( zc - za ) - ( yc - ya )*( zb - za ), ( zb - za )*( xc - xa ) - ( zc - za )*( xb - xa ), ( xb - xa )*( yc - ya ) - ( xc - xa )*( yb - ya )) Nếu chúng ta đặt: A = ( yb - ya )*( zc - za ) - ( yc - ya )*( zb - za ) B = ( zb - za )*( xc - xa ) - ( zc - za )*( xb - xa ) C = ( xb - xa )*( ya - yb ) - ( xc - xa )*( xb - xa) D = -xaA - yaB - zaC . Phương trình tổng quát của mặt phẳng mp(ABC) cĩ dạng: Ax + By + Cz + D = 0 - Tính tọa độ các vector của mặt phẳng mp(MPQ) : vector MP = ( xp - xm , yp - ym , zp - zm ) vector MQ = (xq - xm , yq - ym , zq - zm ) (3 điểm M, P, Q tạo thành mp(MPQ) nên vector MP khơng cùng phương với vector MQ) - Tính tích hữu hướng của 2 vector MP, MQ là m = MP x MQ, m chính là pháp vector của mp(MPQ), cĩ tọa độ : m = MP x MQ y -y z -z z -z x -x x - x y - y m = p m p m p m p m p m p m yq -ym zq -zm , zq -zm xq -xm , xq - xm yq - ym Thiết kế hệ thống kiểm tra các quan hệ hình học trang 58
  59. Luận văn tốt nghiệp hay cĩ thể viết như sau: m = MP x MQ = (( yp - ym )*( zq -zm ) - (yq - ym )*( zp -zm ), ( zp -zm )* (xq - xm ) - ( zq -zm ) *(xp - xm ), (xp - xm )*( yq - ym ) - (xq - xm )*( yp - ym )) Nếu chúng ta đặt: A1 = (yp - ym )*( zq -zm ) - (yq - ym )*( zp -zm ) B1 = ( zp -zm )* (xq - xm ) - ( zq -zm ) *(xp - xm ) C1 = (xp - xm )*(yp - ym ) - (xq - xm )*( xp - xm) D1 = -xmA1 - ymB1 - zmC1 . Phương trình tổng quát của mặt phẳng mp(MPQ): mp(MPQ) = A1x + B1y + C1z + D1 = 0 - Xét sự tương quan của 2 mặt phẳng trên: Nếu (A/A1 = B/B1 = C/C1) xuất ra kết quả “Hai mặt phẳng trùng nhau“. Nếu (A/A1 = B/B1 = C/C1 B/B1) hoặc (B/B1 C/C1) xuất ra kết quả “Hai mặt phẳng cắt nhau“. - Hai mặt phẳng mp(ABC) và mp(MPQ) cắt nhau theo một giao tuyến là đường thẳng cĩ phương trình là hệ phương trình của hai mặt phẳng mp(ABC) và mp(MPQ): Ax + By + Cz + D = 0 A1x + B1y + C1z + D1 = 0 - Tính tọa độ giao điểm thuộc giao tuyến: Nếu (A/A1 <> B/B1) thì tọa độ z cĩ thể được chọn tuỳ ý cho đơn giản, dùng định thức cấp 2 tìm tọa độ giao tuyến : Ax + By + Cz + D = 0 A1x + B1y + C1z + D1 = 0 Ta tính được: Dx1 = AB2 - A1B Dx1 = B1(-D - Ck1 ) + B( D1 + C1k1 ) Dy1 = A(-D1 – C1k1 ) + A1( D + C1k1 ) Suy ra: X1 = Dx1/ D Y1 = Dy1/ D Z1= k1 Tọa độ I(X1 , Y1 , Z1) Tìm tọa độ điểm thứ 2: Thiết kế hệ thống kiểm tra các quan hệ hình học trang 59
  60. Luận văn tốt nghiệp Dx2 = AB2 - A1B Dx2 = B1(-D - Ck2 ) + B( D1 + C1k2 ) Dy2 = A(-D1 - C1k2 ) + A1( D + C1k2 ) X2 = Dx2 / D Y2 = Dy2 / D Z2 = k2 Tọa độ J(X2 , Y2 , Z2) Xuất tọa độ 2 điểm thuộc giao tuyến J(X2, Y2 , Z2 ) và I(X1, Y1, Z1) - Nếu hai mặt phẳng song song, tính khoảng cách của 2 mặt phẳng: Tìm giao điểm của đường thẳng d qua điểm M( xm, ym, zm) và vuơng gĩc với mp(ABC), cĩ vector chỉ phương là pháp vector của mp(ABC) là vector n=(A,B,C). Viết phương trình tham số của đường thẳng d: X = At + xm Y = Bt + ym Z = Ct + zm Thay X, Y, Z vào phương trình mặt phẳng mp(ABC): A( At + xm)+B( Bt + ym) + C(Ct + zm) + D = 0 2 2 2  t = -(Axm + Bym + Czm + D ) / ( A + B + C ) Thay t vào phương trình tham số của đườngthẳng d: + Ta cĩ tọa độ điểm cắt H(Xh , Yh, Zh): 2 2 2 Xh = A(-(Axd + Byd + Czd + D ) / ( A + B + C ))+ xd 2 2 2 Yh = B(-(Axd + Byd + Czd + D ) / ( A + B + C )) + yd 2 2 2 Zh = C(-(Axd + Byd + Czd + D ) / ( A + B + C )) + zd Khoảng cách hai mp(ABC) và mp(MPQ) là đoạn MH: 2 2 2 dmh =|MH | = sqrt ( ( xh - xm) + ( yh - ym ) + ( zh - zm ) ) Xuất khoảng cách dmh End. 9-Kiểm tra tính đồng phẳng của đa giác Cơ sở tốn học: Đa giác gọi là phẳng nếu mọi đỉnh của nĩ nằm trong một mặt phẳng. Trong trường hợp này ba đỉnh bất kỳ (khơng thẳng hàng), cĩ thể dùng để xác định mặt phẳng Thiết kế hệ thống kiểm tra các quan hệ hình học trang 60
  61. Luận văn tốt nghiệp chứa nĩ. Khi cĩ hơn ba đỉnh, cĩ thể các điểm khơng cùng nằm trên 1 mặt phẳng. Vì vậy các ứng dụng phải kiểm tra dữ liệu để bảo đảm tính đồng phẳng. Chọn một trong m điểm, gọi là P1, làm điểm chốt (pivot) và hình thành (m-1) vector chốt Vi=Pi-P1, với i = 2, , m. Các vector này nằm trong cùng 1 mặt phẳng nếu và chỉ nếu các đỉnh Pi nằm trong cùng một mặt phẳng. Ta biết ba vector đồng phẳng nếu và chỉ nếu tích bộ ba vơ hướng của chúng triệt tiêu.Vì vậy, tạo (m-3) tích bộ ba vơ hướng Vi.(V3.V2) với i=4, ., m. Nếu một trong các tích này khác zero đa giác sẽ khơng đồng phẳng. Giải thuật: - Tạo danh sách (n-1) vector từ đa giác P cĩ n cạnh - Vịng lặp từ i =3 đến i =n-1 +Tính tích bộ ba vơ hướng S= Vi .(V1 x V2) + Nếu (S khác 0) Return Đa giác khơng đồng phẳng. - Return Đa giác đồng phẳng 10 -Tính thể tích hình lăng trụ: Giải thuật: - Tính S là diện tích của đa giác đáy. - Nhập h, chiều cao của hình lăng trụ. - Tính thể tích đa giác V = S*h. 11- Tính thể tích hình chĩp: Giải thuật: - Tính S là diện tích của đa giác đáy. - Nhập h, chiều cao của hình chĩp. - Tính thể tích V= S*h /3. 12- Tính thể tích hình nĩn: Giải thuật: - Nhập R, bán kính đáy hình nĩn. - Nhập h, chiều cao hình nĩn. - Tính thể tích V = S*h / 3 = Pi*R2*h / 3. PHẦN III: THIẾT KẾ CHƯƠNG TRÌNH Thiết kế hệ thống kiểm tra các quan hệ hình học trang 61
  62. Luận văn tốt nghiệp I. THIẾT KẾ GIAO DIỆN THỰC HIỆN KIỂM TRA CÁC QUAN HỆ HÌNH HỌC Thiết kế giao diện cho quá trình thực hiện những ứng dụng trong việc kiểm tra các quan hệ hình học, cập nhật các thơng số về kích thước vùng của vùng Client:  Lớp CMainFrame : Cĩ chức năng tạo màn hình vùng Client.  Lớp CApp : Cĩ chức năng thực hiện ứng dụng kiểu đơn tài liệu (SDI).  Lớp CView : Cĩ chức năng hiển thị những hiện thực cuả chương trình kiểm tra các quan hệ hình học.  Lớp CDoc : Cĩ chức năng xử lý việc lưu trữ dữ liệu.  Lớp CDialog : Cĩ chức năng nhập, xuất dữ kiện. II. MỘT SỐ KIỂU DỮ LIỆU ĐƯỢC SỬ DỤNG TRONG CHƯƠNG TRÌNH a. Các đỉnh của đa giác P phẳng được lưu trữ lần lượt trong danh sách kiểu CPoint như P[0].x, P[0].y; P[1].x,P[1].y; . Với đỉnh cuối được nhận biết bởi chỉ số đa giác kèm theo. b. Kiểu dữ liệu điểm trong khơng gian ba chiều (3D), được khai báo như sau: typedef struct { long x; long y; long z; } point3d ; c. Cấu trúc dữ liệu mơ tả Wireframe bao gồm: +Danh sách đỉnh chứa tọa độ các đỉnh +Danh sách cạnh chứa các cặp đỉnh nối cạnh đĩ. typedef struct { int NumV; int NumE; point3d vert[20]; int edge[30][2]; } Wireframe; Thiết kế hệ thống kiểm tra các quan hệ hình học trang 62
  63. Luận văn tốt nghiệp Kiểu dữ liệu dùng để tạo danh sách cạnh từ các đỉnh liên tiếp nhau: typedef struct { CPoint A; CPoint B; } TypeListEdge; Kiểu dữ liệu lưu trữ các điểm, cĩ kèm theo cờ để phân biệt các loại điểm khác nhau (điểm giao nhau giữa 2 đa giác, điểm này đã được duyệt hay chưa duyệt; hay đỉnh của đa giác) được dùng trong thủ tục kiểm tra quan hệ hai đa giác, được khai báo như sau: typedef struct { CPoint P; int CFlag; } ListPoint; III. CÁCH TỔ CHỨC CÁC HÀM TRONG 2D Các hàm được giới thiệu dưới đây được nhĩm lại thành từng nhĩm giúp cho việc theo dõi được dễ dàng hơn 1- Những hàm được sử dụng trong lớp CkiemTra2DView.cpp  Construction/destruction lớp CView CKiemTra2DView:: CKiemTra2DView() CKiemTra2DView:: ~CKiemTra2DView()  Các hàm tạo cửa sổ, vẽ của lớp CView BOOL CKiemTra2DView::PreCreateWindow(CREATESTRUCT& cs) void CKiemTra2DView:: OnDraw(CDC* pDC)// Debug void CKiemTra2DView::AssertValid() const void CKiemTra2DView::Dump(CDumpContext& dc) const CTestHHDoc* CKiemTra2DView::GetDocument()  Các hàm phục vụ vẽ trong 2D void CKiemTra2DView::OnVediem() void CKiemTra2DView::OnUpdateVediem(CCmdUI* pCmdUI) void CKiemTra2DView::OnVeduongthang1() void CKiemTra2DView::OnUpdateVeduongthang1(CCmdUI* pCmdUI) void CKiemTra2DView::OnVeduongthang2() void CKiemTra2DView::OnUpdateVeduongthang1(CCmdUI* pCmdUI) Thiết kế hệ thống kiểm tra các quan hệ hình học trang 63
  64. Luận văn tốt nghiệp void CKiemTra2DView:: OnVedagiac1() void CKiemTra2DView::OnUpdateVedagiac1(CCmdUI* pCmdUI) void CKiemTra2DView::OnVedagiac2() void CKiemTra2DView::OnUpdateVedagiac2(CCmdUI* pCmdUI)  Các hàm liên quan đến mouse void CKiemTra2DView::OnLButtonDown(UINT nFlags, CPoint point) void CKiemTra2DView::OnLButtonUp(UINT nFlags, CPoint point) void CKiemTra2DView::OnRButtonDown(UINT nFlags, CPoint point) void CKiemTra2DView::OnMouseMove(UINT nFlags, CPoint point)  Tính Max ,Min của 2 giá trị(thủ tục tìm giá trị lớn nhất giữa hai giá trị) int Max(int x, int y) int Min(int x, int y) { { int tam; int tam; tam=(x>=y)? x:y; tam=(x>=y)? y:x; return tam; return tam; } }  Các hàm kiểm tra điểm P ở bên trong / bên ngồi đa giác BOOL TestPoint_Boundary (CPoint P,UINT n,CPoint dayP[]) BOOL Giaodiem(CPoint P,UINT n,CPoint dayP[]) void CKiemTra2DView::OnTestDiem()  Các hàm kiểm tra quan hệ giữa 2 đường thẳng double LengthOfSegment(CPoint A,CPoint B) void CKiemTra2DView::OnTinhgoc() void CKiemTra2DView::OnHinhchieu() UINT Intersect(CPoint A,CPoint B,CPoint C,CPoint D,CPoint &M)  Các hàm kiểm tra quan hệ giữa đoạn thẳng và đa giác void Trungdiem(CPoint A,CPoint B,CPoint &TDiem) void ClippingLine(CPoint A,CPoint B,UINT nDinh,CPoint DGiac[], CPoint DsachDcat[],UINT &SoDcat) void CKiemTra2DView::OnDoanthang_Dagiac()  Hàm kiểm tra Đa giác lồi hay lõm? long Toado(CPoint A, CPoint B) Thiết kế hệ thống kiểm tra các quan hệ hình học trang 64
  65. Luận văn tốt nghiệp void CKiemTra2DView:: OnTest2Dagiac()  Hàm tính diện tích của đa giác void CKiemTra2DView::OnTinhdientich()  Nhĩm các hàm cĩ liên quan tới phép chiếu song song và phối cảnh void InitProjection(double &t1,double &t2,double &t3,double &t4,double &t5,double &t6,double &t7,double &t8,float xRot,float yRot) void Projection(BOOL PhepChieu ,float xRot,float yRot, Wireframe &WF) void CKiemTra2DView:: OnChieuPhoiCanh() void CKiemTra2DView::OnUpdateChieuPhoiCanh(CCmdUI* pCmdUI) void CKiemTra2DView:: OnChieuSongSong() void CKiemTra2DView::OnUpdateChieuSongSong(CCmdUI* pCmdUI)  Nhĩm hàm liên quan đến các thao tác của hình lăng trụ void CKiemTra2DView:: OnLangTru() void CKiemTra2DView::OnChieuLangTru() void CKiemTra2DView::OnKeyDown(UINT nChar, UINT nRepCnt, UINT nFlags)  Nhĩm hàm liên quan đến các thao tác của hình chĩp void CKiemTra2DView::OnNhapDinhChop() void CKiemTra2DView:: OnChieu_Chop()  Nhĩm hàm liên quan đến các thao tác của hình nĩn void CKiemTra2DView::OnHinhnon() void CKiemTra2DView::OnChieu_Non()  Các hàm kiểm tra tính đồng phẳng của đa giác void CKiemTra2DView::OnNhapDagiac() void CKiemTra2DView::PlanarPolygon()  Tơ màu đa giác void CKiemTra2DView::OnTomaudagiac()  Kiểm tra quan hệ giữa 2 đa giác void CKiemTra2DView::OnTest2Dagiac() 2- Những hàm được sử dụng trong lớp CKiemTra2DDoc.cpp CkiemTra2DDoc::CkiemTra2DDoc() CkiemTra2DDoc::~ CkiemTra2DDoc() BOOL CkiemTra2DDoc::OnNewDocument() void CkiemTra2DDoc::Serialize(CArchive& ar) Thiết kế hệ thống kiểm tra các quan hệ hình học trang 65
  66. Luận văn tốt nghiệp IV. CÁCH TỔ CHỨC CÁC HÀM TRONG OPENGL 3D Trong phần kiểm tra trong 3D, cĩ các phương thúc xử lý các thao tác như sau: 1- Những hàm được sử dụng trong lớp CkiemTra3Dview  Construction/destruction lớp CView CKiemTra3DView::CKiemTra3DView() CKiemTra3DView::~CKiemTra3DView()  Các hàm tạo cửa sổ, vẽ của lớp CView BOOLCKiemTra3DView::PreCreateWindow(CREATESTRUCT& cs) void CKiemTra3DView::OnDraw(CDC* pDC) void CKiemTra3DView::AssertValid() const void CKiemTra3DView::Dump(CDumpContext& dc) const  Hàm tạo ngữ cảnh để phù hợp với việc vẽ các vật thể 3D int CKiemTra3DView::OnCreate(LPCREATESTRUCT pCreateStruct)  Các hàm điều chỉnh kích thước, tạo màu nền void CKiemTra3DView::OnDestroy() void CKiemTra3DView::OnSize(UINT nType, int cx, int cy) BOOL CKiemTra3DView::OnEraseBkgnd(CDC* pDC) void CKiemTra3DView::GLResize(GLsizei w, GLsizei h) void CKiemTra3DView::GLSetupRC() void CKiemTra3DView::Khoitaopalette() BOOL CKiemTra3DView::OnQueryNewPalette() void CKiemTra3DView::OnPaletteChanged(CWnd* pFocusWnd)  Hàm nhấn các phím mũi tên để quan sát vật thể void CkiemTra3Dview::OnKeyDown(UINT nChar, UINT nRepCnt, INT Flags)  Các hàm thực hiện các thao tác nhập tọa độ cho mặt phẳng, điểm, đường thẳng void CKiemTra3DView:: OnNhapMPhang1() void CKiemTra3DView:: OnNhapMPhang2() void CKiemTra3DView:: OnNhapTDDiem() void CKiemTra3DView:: OnNhapTDDuong1() Thiết kế hệ thống kiểm tra các quan hệ hình học trang 66
  67. Luận văn tốt nghiệp void CKiemTra3DView:: OnNhapTDDuong2()  Các hàm thực hiện các thao tác kiểm tra, tính tốn giữa các đối tượng điểm, đường thẳng, mặt phẳng. void CKiemTra3DView:: OnKtraDiemMP() void CKiemTra3DView:: OnVeGiao2MP() void CKiemTra3DView:: OnKtraDiem_Duong() void CKiemTra3DView:: OnKtra2DThang() void CKiemTra3DView:: OnKtraDuong_MP() void CKiemTra3DView:: OnTinhGoc2MP() void CKiemTra3DView:: OnTinhGocDuong_MP() void CKiemTra3DView:: OnTinhGoc2DT() void CKiemTra3DView:: OnTinhKCDiem_Duong() void CKiemTra3DView:: OnTinhKC2Duong() void CKiemTra3DView:: OnTinhKC2MP() void CKiemTra3DView:: OnDiemDongPhang() void CKiemTra3DView:: Ve_Hai_MP() void CKiemTra3DView:: On2MPhang() void CKiemTra3DView:: GT_hai_mp1() void CKiemTra3DView:: GT_hai_mp3() void CKiemTra3DView:: OnVe_KC_Diem_MP() void CKiemTra3DView:: OnTinh_KC_Diem_MP() void CKiemTra3DView:: Ve_Diem_MP()  Các hàm thực hiện việc vẽ, demo các vật thể void CKiemTra3DView:: GLRenderScene() void CKiemTra3DView:: Cube() void CKiemTra3DView:: HinhChop() void CKiemTra3DView:: Wireframchop() void CKiemTra3DView:: OnCube() void CKiemTra3DView:: Onscence() void CKiemTra3DView:: OnHinhchop() void CkiemTra3Dview:: OnWireframWireframchop()  Hàm thực hiện thao tác xố màn hình void CKiemTra3DView:: OnClearScreen() 2- Những hàm được sử dụng trong lớp CkiemTra3Ddoc CkiemTra3DDoc:: CkiemTra3DDoc() CkiemTra3DDoc:: ~ CkiemTra3DDoc() BOOL CkiemTra3DDoc:: OnNewDocument() Thiết kế hệ thống kiểm tra các quan hệ hình học trang 67
  68. Luận văn tốt nghiệp void CkiemTra3DDoc:: Serialize(CArchive& ar) PHẦN IV: HƯỚNG DẪN SỬ DỤNG CHƯƠNG TRÌNH Trong phần này, tơi sẽ đề cập cách sử dụng các thao tác của việc kiểm tra các quan hệ hình học trong phần 2D và 3D. I. Giao diện phần 2D  Màn hình giao diện chính của chương trình, người sử dụng cĩ thể xem các thơng tin về chương trình và chọn thao tác kiểm tra trong 2D và 3D. Giao diện bao gồm 4 thao tác:  Kiểm tra 2D.  Kiểm tra 3D.  Đề tài.  Thốt chương trình.  Màn hình làm việc trong phần 2D, bao gồm các đề mục như thao tác trong 2D, thao tác trong 3D và các thao tác xử lý tương ứng. Người sử dụng cĩ thể dùng phím Enter hay tổ hợp các phím để chọn các thao tác phù hợp. Trong phần kiểm tra 2D bao gồm các đối tượng điểm, đường thẳng, đa giác và các thao tác kiểm tra tương ứng với các đối tượng hình học này. Thiết kế hệ thống kiểm tra các quan hệ hình học trang 68
  69. Luận văn tốt nghiệp  Màn hình làm việc khi người dùng chọn một trong các thao tác kiểm tra giữa các đối tượng hình học II. Giao diện phần 3D Trong phần 3D, tơi xin giới thiệu một số hình ảnh demo chương trình Thiết kế hệ thống kiểm tra các quan hệ hình học trang 69
  70. Luận văn tốt nghiệp Kiểm tra điểm cĩ đồng phẳng với mặt phẳng hay khơng? Thiết kế hệ thống kiểm tra các quan hệ hình học trang 70
  71. Luận văn tốt nghiệp Vẽ vật thể phụ thuộc vào yêu cầu người dùng III. Đề nghị hướng phát triển Tạo thêm những chức năng kích hoạt lại những đối tượng hình học khi đã được thể hiện trên vùng Client như: Kéo giản kích thước Dịch chuyển những đối tượng tuỳ ý Cập nhật lại dữ liệu cho các vị trí mới Từ những tương quan cơ bản đã đựơc thiết kế của đề tài này, xây dựng lên nhiều bài tốn hình học khác. Thiết kế hệ thống kiểm tra các quan hệ hình học trang 71
  72. Luận văn tốt nghiệp TÀI LIỆU THAM KHẢO  [1] Lê Tấn Hùng, Huỳnh Quyết Thắng, Kỹ thuật đồ họa, Nhà xuất bản Khoa Học và Kỹ Thuật 2000. [2] Lê Minh Trí, Kỹ năng lập trình Windows bằng Visual C++ 6.0 (Tập 1 và 2), Nhà xuất bản Thanh Niên 2001. [3] Dương Quang Thiện, Lập trình Windows dùng Visual C++ 5.0 và MFC (Tập 1, 2 và 3), Nhà xuất bản Thống Kê 1998. [4] Dương Quang Thiện, Nhập mơn lập trình Windows dùng Visual C++, Nhà xuất bản Thống Kê 1998. [5] Trần Quốc Bình, Học Visual C++ 6 trong 21 ngày, Nhà xuất bản Mũi Cà Mau. [6] FrancisS.Hill,Jr, Computer Graphics, Nhà xuất bản MacMillan 1990. [7] Richard S. Wright, Jr , Michael Sweet, OpenGL SuperBible, Waite Group Press 1996. [8] David J. Kruglinski, Inside Visual C++ (Fourth Edition), Microsoft Press 1997. Thiết kế hệ thống kiểm tra các quan hệ hình học trang 72