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

Trong lónh vöïc coâng ngheä maùy tính cuõng nhö coâng ngheä thoâng tin coù nhöõng böôùc phaùt trieån nhaûy voït, noù ñaõ hoã trôï vaøo moïi lónh vöïc trong cuoäc soáng xaõ hoäi, saûn phaåm cuûa coâng ngheä thoâng tin bieán ñoåi haøng ngaøy, haøng giôø. Trong lónh vöïc toaùn hoïc, caùc saûn phaåm cuûa coâng ngheä thoâng tin cuõng hoã trôï ñaéc löïc cho vieäc hoïc taäp vaø nghieân cöùu. Ñeà taøi toâi thöïc hieän laø: “THIEÁT KEÁ HEÄ THOÁNG KIEÅM TRA CAÙC QUAN HEÄ HÌNH HOÏC TRONG KHOÂNG GIAN 2D VAØ 3D“. Ñeà taøi söû duïng ngoân ngöõ laäp trình Visual C++ ñeå theå hieän. Veà goùc ñoä hoïc taäp, nghieân cöùu toâi thaáy ñeà taøi coù theå giuùp hieåu roõ theâm veà kieán thöùc cô baûn cuûa phaàn ñoà hoïa maùy tính vaø cho vaán ñeà kieåm tra thöïc hieän moät soá baøi toaùn hình hoïc theâm phong phuù hôn, taïo theâm phaàn haáp daãn trong moân hoïc naøy. Trong thôøi gian thöïc hieän ñeà taøi toâi ñaõ thöïc hieän ñöôïc nhöõng yeâu caàu cuûa ñeà taøi. Vieäc thöïc hieän ñeà taøi coøn mang yù nghóa ñaùnh giaù laïi quaù trình hoïc taäp, nghieân cöùu cuûa toâi. Neân veà maët tinh thaàn toâi ñaõ coá gaéng tìm hieåu, nghieân cöùu, vaø chuaån bò khaù chu ñaùo cho vieäc thöïc hieän. Nhöng söï tieáp thu cuõng coù nhöõng giôùi haïn nhaát ñònh, bôûi trong lónh vöïc maùy tính cuõng nhö cô sôû toaùn hoïc roäng lôùn, khoâng gian dieãn dòch coù theå voâ haïn, söï thöïc hieän moät yù töôûng naøo ñoù coù theå trong toaùn hoïc thöïc hieän ñöôïc, nhöng vieäc theå hieän thuaät toaùn baèng maùy tính thì coù nhöõng vaán ñeà khoù theå thöïc hieän, vì vaäy ñeà taøi chaéc chaén coøn nhieàu thieáu soùt nhaát ñònh. Mong quyù Thaày coâ, Anh chò vaø caùc baïn thoâng caûm, ñoùng goùp yù kieán giuùp ñôõ. Toâi thaønh thaät caûm ôn …! PHAÀN I: GIÔÙI THIEÄU SÔ LÖÔÏC VEÀ HEÄ THOÁNG KIEÅM TRA CAÙC QUAN HEÄ HÌNH HOÏC Ñeå cho ngöôøi ñoïc tham khaûo ñeà taøi “THIEÁT KEÁ HEÄ THOÁNG KIEÅM TRA CAÙC QUAN HEÄ HÌNH HOÏC“ deã daøng hình dung ñöôïc, toâi xin giôùi thieäu sô löôïc veà ñeà taøi. Nhieäm vuï thöïc hieän cuûa ñeà taøi: Thieát keá heä thoáng kieåm tra caùc quan heä hình hoïc trong: Khoâng gian hai chieàu (2D) Khoâng gian ba chieàu (3D) Vôùi ngoân ngöõ theå hieän treân moâi tröôøng Visual C++. Ñeà taøi aùp duïng caùc kieán thöùc veà cô sôû toaùn hoïc vaø khoâng gian vector trong ñoà hoïa maùy tính, ñeå xaây döïng nhöõng thuaät toaùn kieåm tra caùc quan heä hình hoïc. Ñeå deã daøng hôn toâi xin trình baøy moät ví duï ñieån hình nhö sau: Ví duï: cho ñöôøng thaúng a qua hai ñieåm A vaø B vaø ñöôøng thaúng b qua hai ñieåm C vaø D trong khoâng gian 2D hay 3D thì hai ñöôøng thaúng naøy cuõng coù nhöõng söï töông quan vôùi nhau, nhö truøng nhau, caét nhau vôùi moät goùc naøo ñoù, cheùo nhau (trong khoâng gian 3D), hay song song… Sau khi ñöa vaøo nhöõng ñieàu kieän giaû thieát ban ñaàu (Input), thì chöông trình thöïc hieän vaø ñöa ra keát quaû kieåm tra (output) cuûa giaû thieát treân laø hai ñöôøng thaúng a vaø b ñaõ töông quan nhö theá naøo vôùi nhau? Caét nhau moät goùc bao nhieâu ñoä, song song, hay truøng nhau... Ñoù laø veà maët thuaät toaùn chöông trình kieåm tra, ñaây chæ môùi laø moät taùc vuï thöïc hieän cuûa vaán ñeà naøy. Vôùi baøi toaùn nhö treân neáu chæ ñöa ra ñöôïc nhöõng keát luaän vôùi nhöõng doøng thoâng ñieäp thì chuùng ta thaáy raèng ñeà taøi trôû neân quaù ñôn giaûn khoâng phong phuù vaø haáp daãn qua yù kieán cuûa ngöôøi ñoïc hoaëc tham khaûo. Moät taùc vuï cuøng ñoàng thôøi vôùi baøi toaùn treân maø nhieäm vuï cuûa ñeà taøi yeâu caàu thöïc hieän laø khi ñöa vaøo giaû thieát baøi toaùn chaúng haïn hai ñieåm A vaø B vôùi nhöõng toïa ñoä xaùc ñònh naøo ñoù, qua hai ñieåm naøy seõ thöïc hieän veõ leân moät ñoaïn thaúng qua hai ñieåm A vaø B. Töø ñoù thaáy vaán ñeà moät caùch tröïc quan hôn, hay veõ ra goùc giöõa hai ñöôøng thaúng, chính vôùi nhöõng theå hieän naøy ñeà taøi trôû neân haáp daãn phong phuù hôn, taát nhieân vaán ñeà naøy khoâng ít nhöõng khoù khaên cho ngöôøi thöïc hieän ñeà taøi. Trong phaàn noäi dung toâi seõ trình baøy chi tieát hôn veà ñeà taøi “THIEÁT KEÁ HEÄ THOÁNG KIEÅM TRA CAÙC QUAN HEÄ HÌNH HOÏC TRONG 2D VAØ 3D“. GIÔÙI THIEÄU SÔ LÖÔÏC NGOÂN NGÖÕ THEÅ HIEÄN ÑEÀ TAØI 1. SÔ LÖÔÏC NGOÂN NGÖÕ ÔÛ phaàn I giôùi thieäu sô löôïc veà “THIEÁT KEÁ HEÄ THOÁNG KIEÅM TRA CAÙC QUAN HEÄ HÌNH HOÏC“, toâi ñaõ trình baøy moät ví duï veà yeâu caàu nhieäm vuï ñeå thöïc hieän moät taùc vuï kieåm tra vaán ñeà naøo ñoù cuûa ñeà taøi naøy. Ñeå thöïc hieän nhöõng vaán ñeà ñoù toâi nghieân cöùu vaø thöïc hieän treân moâi tröôøng ngoân ngöõ Visual C++. Visual C++ laø moät phaàn meàm laäp trình höôùng ñoái töôïng ñöôïc phaùt trieån treân cô sôû laø ngoân ngöõ laäp trình C vaø C++. ÔÛ ñaây toâi theå hieän ñeà taøi treân ngoân ngöõ Visual C++ bôûi leõ hieän nay ngoân ngöõ naøy ñöôïc xem laø moät trong caùc ngoân ngöõ hoã trôï (support user) maïnh vaø phoå bieán nhaát. Cuøng muïc ñích saâu xa hôn nöõa laø ñeå cho nhöõng ñeà taøi sau naøy coù theå treân cuøng ngoân ngöõ xaây döïng yù töôûng cuûa ñeà taøi “THIEÁT KEÁ HEÄ THOÁNG KIEÅM TRA CAÙC QUAN HEÄ HÌNH HOÏC“ ngaøy theâm moät ñaày ñuû, phong phuù, haáp daãn vaø öùng duïng mang tính thieát thöïc hôn. Toâi ñaàu tieân nghieân cöùu tìm hieåu toång quaùt veà ngoân ngöõ nhö Visual C++, thöïc hieän nhöõng chöông trình ñieån hình treân ngoân ngöõ laäp trình höôùng ñoái töôïng. Vaø phaàn tìm hieåu chính laø phaàn thöïc hieän yeâu caàu cuûa ñeà taøi, cuï theå laø veà phöông dieän tính toaùn trong nhöõng thuaät toaùn vaø theå hieän tröïc quan baèng ñoà hoaï maùy tính treân ngoân ngöõ Visual C++. Trong Visual C++ phaàn ñoà hoïa ñöôïc theå hieän trong lôùp CDC (Class Device Context) vôùi nhieàu haøm thaønh vieân hoã trôï cho vieäc veõ ñieåm, ñöôøng, ña giaùc, toâ maøu…. Ñaëc bieät hôn trong ngoân ngöõ Visual C++ coù söï hoã trôï cho vieäc veõ caùc ñoái töôïng hình hoïc baèng chuoät. Nhöng ngoân ngöõ chæ thöïc hieän ñöôïc vôùi caùc ñoái töôïng hình hoïc 2D, ñoái töôïng hình hoïc 3D thì chöa coù, caàn phaûi töï thieát keá. Trong quaù trình nghieân cöùu, toâi nhaän thaáy trong ngoân ngöõ Visual C++ coù boä thö vieän OPENGL laø moät thö vieän API hoã trôï cho vieäc thöïc hieän caùc chöông trình ñoà hoïa, treân caû 2D vaø 3D raát maïnh, chính vì theá ôû phaàn kieåm tra caùc quan heä hình hoïc phaàn 3D toâi thöïc hieän treân OPENGL. Töø ñaây toâi chuyeån höôùng sang nghieân cöùu OPENGL ñeå thöïc hieän cho phaàn 3D. Ñeå hieåu vaø thöïc hieän ñöôïc treân noù cuõng khoù khaên khoâng keùm nhö ta baét ñaàu nghieân cöùu vaø laøm quen vôùi ngoân ngöõ môùi nhö Visual C++. Sau khi nghieân cöùu vaø hieåu ñöôïc nhöõng yeáâu toá cô baûn cuûa OPENGL toâi coù nhaän xeùt raèng OPENGL laø moät öùng duïng ñeå thöïc hieän caùc chöông trình ñoà hoïa maùy tính haáp daãn vaø ñeïp maét. Khi ñaõ caøi ñöôïc thì caùch söû duïng coù phaàn deã daøng hôn, chæ caàn tìm hieåu moät soá caùc haøm trong thö vieän caùc haøm thaønh vieân cuûa OPENGL laø ñaùp öùng ñöôïc yeâu caàu. Coøn moïi vieäc thöïc hieän caøi ñaët theo lyù thuyeát ñoà hoïa maùy tính nhö caùc pheùp bieán hình, thieát laäp cheá ñoä maøn hình, khôûi taïo ñoà hoïa, setviewport, taïo caùc Pallette maøu, thieát laäp ñoä saâu hình aûnh, ñoä phaûn chieáu hình aûnh, ñoä töông phaûn … taát caû do OPENGL hoã trôï haàu heát. OpenGL ñöôïc ñònh nghóa laø “giao dieän phaàn meàm cho phaàn cöùng ñoà hoïa ”. Thöïc chaát, OpenGL laø moät thö vieän caùc haøm ñoà hoïa, ñöôïc xem laø tieâu chuaån thieát keá coâng nghieäp cho ñoà hoïa ba chieàu. Vôùi giao dieän laäp trình maïnh meõ, OpenGL cho pheùp taïo caùc öùng duïng 3-D phöùc taïp vôùi ñoää tinh vi, chính xaùc cao, maø ngöôøi thieát keá khoâng phaûi ñaùnh vaät vôùi caùc nuùi coâng thöùc toaùn hoïc vaø caùc maõ nguoàn phöùc taïp. Vaø do OpenGL laø tieâu chuaån coâng nghieäp, caùc öùng duïng taïo töø noù duøng ñöôïc treân caùc phaàn cöùng vaø heä ñieàu haønh khaùc nhau. Nhaän xeùt veà OPENGL toâi thaáy raèng OPENGL laø thö vieän ñoà hoïa treân WINDOWS bôûi vì ta coù theå thaáy raèng OPENGL khoâng nhöõng thöïc hieän treân ngoân ngöõ Visual C++ maø coøn coù theå cho pheùp thöïc hieän treân caû Visual Basis , Borland C++ 2. GIÔÙI THIEÄU CAÙC HAØM CUÛA NGOÂN NGÖÕ ÑÖÔÏC SÖÛ DUÏNG a. Caùc haøm cuûa lôùp CDC (Class Device Context) Trong CDC coù raát nhieàu haøm thaønh vieân phuïc vuï cho quaù trình keát xuaát caùc hình aûnh ra caùc thieát bò. Trong phaàn thöïc hieän ñeà taøi, toâi xin ñöa ra caùc haøm ñöôïc söû duïng trong ñeà taøi Veõ ñieåm: SetPixel ( int x , int y , int color ); Haøm naøy thuoäc lôùp CClientDC trong phaàn maøu söû duïng macro RGB(red,green,blue) Ví du:ï Ñeå veõ moät ñieåm , ta thöïc hieän nhö sau: CClientDC dc( this ); dc.SetPixel (100,100,GRB(0,0,0); Ñeå theå hieän toïa ñoä moät ñieåm trong heä truïc toïa ñoä hai chieàu, Visual C++ duøng lôùp CPoint, ñoái töôïng thuoäc lôùp naøy ñöôïc theå hieän bôûi hai thaønh phaàn x vaø y. Ví duï ta khai baùo ñieåm point nhö sau: CPoint point point.x=100; point.y=100; Veõ ñöôøng thaúng: Line (int x1, int y1, int x2, int y2); Haøm naøy thuoäc lôùp CClientDC Ví duï: Ñeå veõ ñöôøng thaúng ta thöïc hieän caùc böôùc sau ñaây CClientDC dc(this); dc.Line(x1,y1,x2,y2); Ngoaøi ra trong vieäc veõ ñöôøng thaúng coøn coù theå söû duïng hai haøm sau: MoveTo(int x, int y); Haøm naøy duøng ñeå di chuyeån con troû ñeán toïa ñoä x,y trong maøn hình. LineTo(int x, int y); Haøm naøy duøng ñeå veõ ñöôøng thaúng töø ñieåm hieän haønh ñeán ñieåm x, y. Caû hai haøm naøy ñeàu thuoäc lôùp CClientDC, vieäc söû duïng nhö sau: CClientDC dc(this); dc.MoveTo(x,y); dc.LineTo(newx, newy); Veõ hình chöõ nhaät: Rectangle(int x1,int y1,int x2,int y2); Haøm naøy thuoäc lôùp CclientDC. Duøng ñeå veõ hình chöõ nhaät coù toïa ñoä treân goùc treân traùi laø (x1,y1) vaø toïa ñoä goùc döôùi phaûi laø (x2,y2). Cuù phaùp veõ hình chöõ nhaät nhö sau: CClientDC dc(this); dc.Rectangle(x1, y1, x2, y2); Veõ hình Ellipse: Ellipse(int x1,int y1,intx2,int y2); Haøm naøy coù caùc tham töông töï caùc tham soá hình chöõ nhaät, haøm naøy cuõng thuoäc lôùp CClientDC. Cuù phaùp veõ hình Ellipse nhö sau: CClientDC dc(this); dc.ellipse(int x1, int y1, intx2, int y2); Haøm loan vuøng kín: FloodFill(int x,int y, int color); Haøm naøy duøng ñeå toâ maøu vuøng ñöôïc giôùi haïn bôûi moät ñöôøng bieân kheùp kín. Haøm naøy thuoäc lôùp CClientDC coù taùc duïng toâ maøu vôùi maøu color toâ heát vuøng coù toïa ñoä (x,y) vaø moät vuøng kín bao quanh ñieåm ñoù. Cuù phaùp haøm nhö sau: CClientDC dc(this); dc.FloodFill(x, y, color); Taïo caùc ñöôøng veõ: CreatePen(typeline, width, color); Ñeå taïo ñöôøng veõ trong caùc öùng duïng veõ ta xeùt haøm CreatePen cuûa lôùp Cpen, haøm naøy coù daïng nhö sau: Cpen *pPen=new Cpen; pPen->CreatePen(typeline, width, color); Trong ñoù : · Tham soá typeline laø kieåu ñöôøng veõ, noù coù giaù trò ñöôïc ñònh nghóa nhö sau: PS-SOLID Ñöôøng thaúng ñoàng nhaát. PS-DASH Ñöôøng thaúng goàm caùc gaïch ngang ñöùt neùt. PS-DOT Ñöôøng thaúng goàm caùc neùt chaám ñöùt. PS-DASDOT Ñöôøng thaúng goàm caùc gaïch ngang chaám ñöùt. PS-DASHDOTDOT Ñöôøng thaúng goàm caùc gaïch ngang chaám ñöùt. PS-NULL Ñöôøng thaúng voâ hieäu löïc khoâng veõ ra. PS-INSIDEFRAME Ñöôøng thaúng naèm beân trong ñöôøng vieàn. · Tham soá width cho ñoä roäng cuûa neùt veõ tính baèng pixel. · Tham soá color cho maøu veõ b. Caùc haøm trong boä thö vieän OpenGL OpenGL goàm 5 boä haøm, boä haït nhaân coù 115 haøm cô baûn. Teân caùc haøm naøy baét ñaàu baèng GL. Windows NT hoã trôï 4 chuûng loaïi haøm khaùc, bao goàm thö vieän OpenGL utility(teân haøm baét ñaàu baèng GLU), thö vieän OpenGL auxiliary(teân haøm baét ñaàu baèng AUX), boä haøm”WGL” (teân haøm baét ñaàu baèng WGL), vaø caùc haøm WIN32 API (teân haøm khoâng coù tieàn toá ñaëc bieät). Boä haøm haït nhaân cho pheùp thieát keá caùc hình daïng khaùc nhau, taïo caùc hieäu quaû chieáu saùng, keát hôïp antialiasing vaø gaùn caáu truùc, thöïc hieän bieán ñoåi ma traän… Do caùc haøm cô baûn ñöôïc theå hieän ôû nhieàu daïng khaùc nhau tuøy thuoäc vaøo loaïi döõ lieäu maø chuùng tieáp nhaän, neân treân thöïc teá coù hôn 300 nguyeân maãu (prototype) caùc haøm cô baûn. ó Thö vieän OpenGL utility goàm caùc haøm cao caáp. Caùc haøm naøy ñôn giaûn hoaù vieäc söû duïng hình aûnh caáu truùc, thöïc hieän vieäc bieán ñoåi toïa ñoä möùc cao, hoã trôï tesselation ña giaùc, vaø bieåu dieãn caùc ñoái töôïng coù cô sôû ña giaùc nhö hình caàu, hình truï hình dóa. ó Thö vieän OpenGl auxiliary goàm caùc haøm ñaëc bieät duøng ñôn giaûn hoùa caùc ví duï laäp trình trong saùch chæ daãn laäp trình OpenGL. Caùc haøm phuï thuoäc platform naøy thöïc hieän caùc nhieäm vuï nhö quaûn kyù cöûa soå, ñieàu khieån xuaát/nhaäp, veõ caùc ñoái töôïng 3D nhaát ñònh. Do caùc haøm naøy coù möïc ñích thieát minh neân khoâng ñöôïc duøng trong caùc maõ saûn xuaát. ó Caùc haøm “WGL”keát noái OpenGL vôùi WINdows NT, cho pheùp ngöôøi laäp trình xaây döïng vaø choïn löïa caùc ngöõ caûnh bieåu dieãn, taïo caùc bitmap font, caùc haøm naøy chæ duøng treân Windows NT. ó Cuoái cuøng, caùc haøm Win32 API ñöôïc duøng giaûi quyeát caùc ñònh daïng ñieåm aûnh vaø taïo boä ñeäm ñoâi. Trong phaàn naøy, toâi trình baøy moät soá haøm ñöôïc söû duïng trong ñeà taøi. Haøm veõ ñieåm, ñöôøng, ña giaùc: Ñöôïc baét ñaàu bôûi haøm: glBegin (Glenum mode) Ñeå chæ söï baét ñaàu nhöõng ñænh cuûa moät primitive, tham soá mode chæ kieåu caùc primitive. Tham soá mode coù caùc giaù trò sau: Ÿ GL_POINTS : chæ ñænh ñöôïc söû duïng laø ñieåm. Ÿ GL_LINES : chæ nhöõng ñænh ñöôïc duøng ñeå taïo ñoaïn thaúng. Ÿ GL_LINE_STRIP : chæ nhöõng ñænh ñöôïc söû duïng taïo ñoaïn thaúng nhaün. Ÿ GL_TRIANGLES : nhöõng ñænh ñöôïc söû duïng taïo ra nhöõng tam giaùc. Ÿ GL_TRIANGLE_STRIP : nhöõng ñænh ñöôïc söû duïng taïo ra tam giaùc coù caïnh nhaün. Ÿ GL_POLYGON : nhöõng ñænh ñöôïc söû duïng taïo ra ña giaùc loài. glEnd ( ) Haøm treân duøng ñeå chaám döùt danh saùch caùc ñænh maø noù chæ roõ primitive ñöôïc khôûi taïo bôûi haøm glBegin. Ví du: Veõ ñöôøng thaúng töø 2 ñieåm glBegin(GL_LINES) glVertex3f(0.0f, 0.0f, 0.0f); glVertex3f(50.0f, 50.0f, 50.0f); glEnd( ); Haøm chæ ra toïa ñoä cuûa ñieåm, ñöôøng, ña giaùc: glVertex2f (Glfloat x,Glfloat y) glVertex3f (Glfloat x,Glfloat y,Glfloat z) Haøm bieán ñoåi toïa ñoä: · glLoadIdentity(); thay theá ma traän hieän haønh bôûi ma traän ñôn vò. · glMultMatrix(); nhaân ma traän hieän haønh vôùi ma traän ñöôïc chæ ñònh. · gl PopMatrix(void); laáy ma traän hieän haønh töø stack. · glPushMatrix(void); ñaåy ma traän hieän haønh vaøo stack. · glTranslatef (Glfloat x, Glfloat y, Glfloat z); nhaân ma traän hieän haønh bôûi ma traän tònh tieán. · gl Rotatef(Glfloat Angle, Glfloat x, Glfloat y, Glfloat z); nhaân ma traän hieän haønh bôûi ma traän quay. Caùc haøm lieân quan ñeán maøu: · glColor3f (Glfloat red, Glfloat green, Glfloat blue); ñaët maøu hieän haønh bôûi caùc thaønh phaàn red, green, blue vôùi giaù trò töø 0,0 ñeán 1,0. · glClearColor(GLclampf red, GLclamp green, Glclamp blue, Glclamp alpha); ñaët maøu cho vieäc xoùa buffer maøu. · glClear(GL_COLOR_BUFFER_BIT); xoùa buffer maøu, xoùa cöûa soå bôûi maøu xoùa hieän haønh . Caùc haøm lieân quan ñeán aùnh saùng: · glLightf(Glenum light, Glenum pname, GLfloat param); · glLighti(Glenum light, Glenum pname, GLint param); Trong ñoù: E Tham soá light chæ ra nguoàn saùng coù giaù trò töø GL_LIGHT0 ñeán GL_LIGHT7. E Tham soá pname chæ ra tham soá light naøo ñöôïc laäp nhö GL_AMBIENT, GL_DIFFUSE… E Tham soá param chæ coù yù nghóa ñoái vôùi nguoàn saùng ñieåm. Tham soá naøy coù caùc giaù trò nhö: GL_SPOT_EXPONENT, GL_SPOT_CUTOFF… Caùc haøm lieân quan ñeán thuoäc tính aùnh saùng cuûa vaät lieä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 ñoù: E face: laø thuoäc tính beà maët tröôùc ,sau cuûa ña giaùc. E pname: laø thuoäc tính cuûa vaät lieäu: GL_AMBIENT,GL_DIFFUSE,… E param : chæ ñònh giaù trò maø tham soá pname ñöôïc laäp. E params: chæ ñònh daõy soá nguyeân hay thöïc chöùa caùc thaønh phaàn thuoäc tính ñöôïc laäp. · glFrontFace(Glenum mode); xaùc ñònh beà maët ña giaùc laø maët tröôùc hay sau. PHAÀN II: NOÄI DUNG Trong phaàn giôùi thieäu toâi ñaõ trình baøy nhöõng noäi dung sô löôïc mang tính toång quaùt cuûa ñeà taøi. Phaàn noäi dung toâi trình baøy chi tieát hôn theo thöù töï logic caùc vaán ñeà töø lyù thuyeát toaùn hoïc ñeán caùc thuaät toaùn chöông trình. I. LYÙ THUYEÁT CÔ SÔÛ TOAÙN HOÏC Caùc lyù thuyeát cô sôû toaùn hoïc ñöôïc söû duïng cho caùc thuaät toaùn trong ñeà taøi “THIEÁT KEÁ HEÄ THOÁNG KIEÅM TRA CAÙC QUAN HEÄ HÌNH HOÏC“ bao goàm: · Hình hoïc giaûi tích trong maët phaúng · Hình hoïc giaûi tích trong khoâng gian. Phaàn lyù thuyeát cô sôû toaùn hoïc naøy raát caàn thieát cho vieäc thieát keá chöông trình thöïc hieän vieäc kieåm tra caùc quan heä hình hoïc, khoâng gian vector laø cô sôû lyù thuyeát toaùn hoïc taát yeáu ñeå xaây döïng caùc caáu truùc ñoà hoïa maùy tính. I.1. Giôùi thieäu veà vector: Ñieåm (point): Moâ taû caùc vò trí cuûa ñoà hình vaø coù nhieàu caùch ñeå dieãn ñaït. Trong hai chieàu bieåu dieãn baèng caùch duøng boä-2 ñeå cho caùc toïa ñoä theo hai truïc. Hai daïng thöôøng ñöôïc aùp duïng nhieàu ñoù laø daïng Cartesian nhö (x,y) =(3,4) hay daïng toïa ñoä cöïc (R, q)=(2.4,450). Trong khi chuùng ñöôïc ñònh nghóa moät caùch ñaïi soá theo caùc thao taùc nhaát ñònh treân ñoù, chuùng cuõng cho pheùp moät dieãn dòch hình hoïc theo caùc ñieåm, ñöôøng, chieàu. Vector: Nhìn moät caùch hình hoïc, vector laø moät ñoaïn thaúng maø caùc ñieåm ñaàu vaø ñieåm cuoái ñaõ ñöôïc xaùc ñònh . Vector laø moät ñoái töôïng coù ñoä daøi vaø chieàu töông öùng vôùi moät soá thöïc theå vaät lyù nhö löïc, khoaûng caùch, vaø vaän toác. Vector thöôøng ñöôïc veõ nhö moät muõi teân coù chieàu daøi chæ veà moät höôùng. Khi vector ñöôïc choïn ñeå chæ ñònh heä toïa ñoä, caùc vector coù moät haøm soá ñeå ñöa ra hai haèng soá, ba haèng soá,... Vì theá, moät trong caùc theå hieän cuûa moät vector hai chieàu a laø moät caëp coù thöù töïï a=(a, a). Trong chöông trình, vector ñöôïc bieåu dieãn baèng kieåu döõ lieäu: Typedef struct { dx,dy: float; } vector; struct { dx,dy,dz : float; } vector3D x P2 v P4 P3 v P1 y P5 Vôùi hai ñieåm P1(x1,y1) vaø P2(x2,y2) ta ñònh nghóa vector v vôùi caùc thaønh phaàn laø vector v =(x2-x1, y2-y1). Ñoâi khi vector naøy ñöôïc ghi laø P1P2 vaø goïi laø vector töø P1 ñeán P2. Baûn thaân vector khoâng bò buoäc vaøo moät vò trí, maëc duø ñeå deã hình dung thöôøng veõ chuùng xuaát phaùt töø moät ñieåm. Vôùi ñieåm baát kyø P = (Px, Py) trong moät heä toïa ñoä, vector ñi töø goác toïa ñoä vôùi caùc toïa ñoä v=(Px, Py) ñöôïc goïi laø vector vò trí cho P. Vector 3D cuõng raát quan troïng trong ñoà hoïa. I.2. Caùc pheùp tính vector: Moät vector n chieàu, vôùi n laø soá nguyeân döông baát kyø: W=(W1,W2,. . .,Wn) vôùi moãi thaønh phaàn Wi laø soá voâ höôùng. Caùc vector 2 chieàu vaø 3 chieàu vôùi n=2, n=3 thì thöôøng gaëp nhaát trong ñoà hoaï Chuùng ta khoâng theå thaáy ñöôïc caùc vector lôùn hôn 3 nhöng chuùng laø nhöõng thaønh phaàn coù giaù rò raât lôùn. Hai pheùp tính soá hoïc cô baûn treân vector laø coäng hai vector vaø ñònh tyû leä moät vector. Coäng hai vector Toång hai vector a,b laø vector c ñöôïc ñònh nghóa nhö sau: C = (c, c, …, c) = (a + b, a + b, …, a + b) b a+b a a+b b a Hình b Hình a Hình a: Caùc thaønh phaàn cuûa toång laø toång caùc thaønh phaàn cuûa caùc vector tham gia. Hình b: Toång caùc vector laø ñöôøng cheùo hình bình haønh. Procedure AddVectors( vector a, vector b; vector &c ); { c.dx := a.dx + b.dx; c.dy := a.dy + b.dy; } Ñònh tyû leä moät vector Vieäc ñònh tyû leä moät vector nhaèm thay ñoåi ñoä daøi cuûa hay ñaûo chieàu cuûa noù. sa = (sa, sa, …, sa) Vôùi s laø heä soá tyû leä vaø a laø vector. Khi s aâm, chieàu cuûa sa ngöôïc laïi vôùi a. Procedure Scalar(real s; vector a; vector &b) { b.d = sa.d ; b.d= sa.d; } Pheùp tröø hai vector: Treân cô sôû coäng vaø ñònh tyû leä, pheùp tröø deã daøng ñònh nghóa: a-c = a +(-c) vôùi thaønh phaàn thöù i laø ai-ci. a a-c c -c Trò tuyeät ñoái (ñoä daøi) cuûa vector Neáu moät vector W ñöôïc theå hieän trong khoâng gian nhieàu chieàu (W, W, …, W), döïa theo ñònh lyù Pithagore ta coù coâng thöùc sau: Vector coù ñoä daøi baèng zero thöôøng ñöôïc goïi laø vector 0. Chöông trình con minh hoïa nhö sau: Function Length(vector v): Real; · Chuaån hoùa vector -Vector ñôn vò Vieäc ñònh tyû leä moät vector ñeå keát quûa coù ñoä daøi baèng 1 goïi laø chuaån hoaù moät vector, vaø keát quûa goïi laø vector ñôn vò. Ví duï daïng chuaån hoaù ua cuûa a nhö sau: ua = a / | a| vaø coù cuøng chieàu vôùi a. Bieåu thöùc cho heä soá cuûa vector coù theå khai baùo tröïc tieáp nhö sau: Normalize(vector v, vector &u); Noù coù daïng vector ñôn vò u do caùc heä soá moãi thaønh phaàn cuûa v: u.d:= v.d/Length(v); u.d:= v.d/Length(v); Toå hôïp tuyeán tính cuûa vector: Ñeå hình thaønh toå hôïp tuyeán tính cuûa hai vector V vaø W, ñònh tyû leä moãi vector theo caùc tyû soá a vaø b roài coäng keát quûa ñeå thaønh vector môùi av+bw. Toång quaùt, toå hôïp tuyeán tính cuûa m vector V, V, …, V nhö sau: W = aV + aV + …+ aV 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; } · Toå hôïp loài cuûa vector Moät lôùp ñaëc bieät cuûa toå hôïp tuyeán tính coù vò trí quan troïng trong toaùn hoïc vaø öùng duïng soá hoïc trong ñoà hoïa, ñoù laø:Toå hôïp loài (convex combination), hay toå hôïp tuyeán tính maø caùc heä soá khoâng aâm vaø toång baèng 1. Vaäy toå hôïp tuyeán tính: W = aV + aV + … +aV laø toå hôïp loài neáu toång =1vaø a0, vaø cung “spline” thöïc ra laø toå hôïp loài cuûa moät taäp caùc vector. Tích voâ höôùng cuûa hai vector: Tích voâ höôùng cuûa hai vector cho ta thoâng tin ñaùng giaù veà moät caëp vector nhö goùc giöõa chuùng (cuï theå laø khi naøo chuùng vuoâng goùc) vaø chieáu vector leân vector khaùc. Noù cuõng cho ta phöông trình cuûa moät maët phaúng moâ taû baèng moät ñieåm vaø hai vector. Cho hai vector, ví duï hai chieàu (a1,a2) vaø (b1,b2). Tích voâ höôùng hai vector ñònh nghóa laø: a.b = a1b1+ a2b2 Moät caùch toång quaùt cho vector n chieàu nhö sau: Cho Vector V= (v, v, …, v) vaø W=( w, w, …, w), tích voâ höôùng cuûahai vector treân laø: V. W = vôùi i = 1,… ,n Tích voâ höôùng cuûa hai vector ñöôïc theå hieän trong thuû tuïc sau: Procedure Float Dot (vector a,b) { return Dot = a.d* b.d+ a.d* b.d; } · Caùc tính chaát cuûa tích voâ höôùng 1. Ñoái xöùng : a.b = b.a 2. Tuyeán tính: (a+c).b = a.b + c.b 3. Ñoàng nhaát : (sa).b = s(a.b) 4. | b2 | = b.b Ñoä daøi cuûa hieäu vaø toång hai vector ñöôïc cho nhö sau: | a-b|2 = |a|2 - 2ab + |b|2 | a+b|2 = |a|2 + 2ab + |b|2 Caùc öùng duïng cuûa tích voâ höôùng: Goùc giöõa hai vector (hay hai ñöôøng) Ñaây laø öùng duïng quan troïng cuûa tích voâ höôùng. Hình a döôùi cho thaáy goùc q giöõa hai vector a vaø b. Caùc vector naøy coù theå coù hai, ba, hay nhieàu chieàu. Chuùng taïo thaønh hai caïnh cuûa tam giaùc, vaø caïnh thöù ba laø a-b. Theo heä thöùc löôïng trong tam giaùc, ta coù : | a-b|2 = |a|2 + |b|2 - 2 |a||b|cos(q) Töø phöông trình naøy vaø phöông trình | a-b|2 = |a|2 - 2ab + |b|2 ta suy ra ñöôïc: a.b = |a||b| cos(q) Nghóa laø cos(q) = ua.ub a b Hình a Vaäy cosin cuûa goùc giöõa hai vector a vaø b laø tích voâ höôùng cuûa daïng chuaån hoùa hai vector. * Daáu cuaû vector a.b vaø söï tröïc giao Ta bieát raèng cos() >0 neáu < 90 cos() 90 cos() =0 neáu = 0 Do vaäy töø phöông trình: cos() = u.u ta coù goùc giöõa hai vector nhö sau: l Nhoû hôn 90o neáu a.b >0 l Baèng 900 neáu a.b = 0 l Lôùn hôn 90o neáu a.b < 0 a.b>0 a.b=0 a.b<0 a a a b b b Chieáu vaø phaân tích vector: Hình treân ta phaân tích a thaønh c theo chieàu vector b vaø e. Theo caùch naøy vector c goïi laø chieáu tröïc giao cuûa a leân b. Roõ raøng c coù cuøng chieàu vôùi b, ta coøn phaûi tính ñoä lôùn | c|. Theo phöông trình a.b = |a||b|cos() vaø heä thöùc löôïng tam giaùc ta coù phöông trình: |c| = |a| = a.u (*) Nhö theá ñoä daøi cuûa c chæ phuï thuoäc vaøo ñoä daøi cuûa a. Baây giôø ta hình thaønh vector c, baèng caùch theâm chieàu cuûa b. c = |c|.ub Sau ñoù, keát hôïp vôùi phöông trình (*) treân ta coù: c = ( a.ub)ub c = a.b b |b|2 Ví duï: trong hai chieàu, chieáu cuûa a = (6,4) leân b = (1,2) nhö hình döôùi c a e b x y Hình chieáu cuûa c naèm daøi hôn b keå töø goác, töø phöông trình treân ta coù ñoä daøi cuûa c laø (2.8, 5.6), vector e = a-c = (3.2, -1.6 ). Daïng ñieåm chuaån cho ñöôøng vaø maët phaúng Daïng ñieåm chuaån cho ñöôøng vaø cho maët phaúng duøng nhieàu trong ñoà hoïa nhö vieäc caét loaïi boû ñöôøng bò che vaø toâ ña giaùc. A c n L c n x y Xeùt ñöôøng L ñi qua ñieåm A = (Ax ,Ay) theo chieàu vector c = (cx ,cy), ta coù vector n vuoâng goùc vôùi vector c nghóa laø c.n = 0, cuõng coù nghóa laø c.n + c.n=0, hay: cy / cx = -nx / ny Ñieàu kieän n tröïc giao vôùi c cho ta suy ra n coù theå laø boäi soá baát kyø cuûa (cx , cy), coù hai chieàu ñoái nhau. Ñeå coù phöông trình cho ñöôøng L, xeùt ñieåm baát kyø R = (x,y) treân L. Vector R phaûi vuoâng goùc vôùi n, neân n.(R-A) = 0. Ta coù theå vieát laïi nhö sau: nR=nA, nhöng khoâng theå nhaân ñieåm vôùi vector ñöôïc. Ta thay vector R baèng r ñi töø goác vaø thay A baèng a. Nhö vaäy, caùc tính toaùn ñeàu phuï thuoäc vaøo vieäc choïn goác toïa ñoä, coøn phöông trình ñöôøng thaúng vaãn phuï thuoäc vaøo goác khoâng coù gì thay ñoåi. Nhö vaäy ta coù: n.r = D Vôùi D = n.a = nx Ax + ny Ay Ñaây laø phöông trình ñieåm chuaån cho ñöôøng. Phöông trình naøy coù theå vieát daïng quen thuoäc nhö sau: nxx + nyy = D · Môû roäng daïng ñieåm cho maët phaúng Caùc maët phaúng cuõng coù theå bieåu dieãn ôû daïng chuaån ñieåm. Moät maët phaúng hoaøn toaøn ñöôïc xaùc ñònh vôùi moät ñieåm S = (sx, sy, sz) naèm trong ñoù vaø höôùng chuaån cuûa maët phaúng. Chuaån cho maët phaúng ñöôïc hieåu laø vuoâng goùc vôùi moïi ñöôøng trong maët phaúng. Goïi höôùng chuaån laø n= (nx, ny, nz). Vôùi ñieåm R= (x, y, z) baát kyø trong maët phaúng, xaây döïng vector töø R ñeán S, vuoâng goùc vôùi n. n.(R-S) = 0 Thay R-S baèng r -s vaø duøng tính tuyeán tính, ta ñöôïc: n.r = D vôùi D = n.s Ñaây laø phöông trình ñieåm chuaån cuûa maët phaúng. Moïi ñieåm treân maët phaúng coù cuøng tích voâ höôùng vôùi chuaån. Nghóa laø moïi ñieåm coù cuøng hình chieáu leân n. Phöông trình maët phaúng P thöôøng vieát laø: Ax + By + Cz = D Tö ø tích voâ höôùng cuûa phöông trình ta thaáy raèng daïng ñieåm chuaån thöïc ra laø: nxX + nyY + nz Z = D Vôùi A = nx, B = ny , vaø C = nz. Ñieàu naøy cho thaáy (A, B, C) laø chieàu chuaån cuûa maët phaúng. Ñieåm treân maët gaàn goác nhaát laø ñieåm chieáu vuoâng goùc cuûa goác leân maët. Nhö vaäy noù tæ leä vôùi n, goïi laø Kn, neân khoaûng caùch laø| Kn |. Vì Kn naèm treân maët neân n. (Kn)=D. S n Kieåm tra nöûa khoâng gian trong vaø ngoaøi cuûa moät ñieåm Xeùt ñieåm Q, giaû söû ñöôøng E ñi qua ñieåm A vaø coù chuaån höôùng ra n nhö hình veõ: n E A inside E Goùc giöõa n vaø Q -A 0. Töông töï, goùc seõ lôùn hôn 90 neáu Q naèm phía trong, vì vaäy n.(Q -A) < 0. Cuoái cuøng, = 90 neáu Q naèm treân E, vaø n .(Q - A) = 0. Neáu thay Q -A baèng vector q - a vaø goïi ñaët a.n = D, thì ñöôøng E ñöôïc cho bôûi phöông trình n.p = D, vaø ta vieát laïi thuû tuïc kieåm tra ñieåm Q vôùi vector bieåu dieãn q seõ naèm: 1. ÔÛ nöûa khoâng gian phía ngoaøi cuûa E neáu q.n > D. 2. Treân E neáu p.n = D. 3. ÔÛ nöûa khoâng gian phía trong cuûa E neáu q.n < D. · Môû roäng cho maët phaúng Giaû söû maët P qua ñieåm A vaø coù vector chuaån höôùng ra n thì ñieåm Q seõ: 1. ÔÛ nöûa khoâng gian phía ngoaøi cuûa P neáu T=(q-a).n > 0 2. Treân P neáu (q-a).n=0 3. ÔÛ nöûa khoâng gian phía trong cuûa P neáu (q-a).n<0. Caét ñöôøng thaúng vôùi cöûa soå loài Ta duøng kieåm tra trong-ngoaøi ñeå xaây döïng coâng cuï caét höõu hieäu vôùi cöûa soå laø ña giaùc loài baát kyø. Cöûa soå W chöùa moät ña giaùc loài cuøng vôùi ñöôøng thaúng L töø P1 tôùi P2. Ta muoán xaùc ñònh phaàn thaáy cuûa L naèm trong W. Ña giaùc loài neân phaàn trong cöûa soå ñöôïc ñònh nghóa laø vuøng naèm ôû nöûa khoâng gian phía trong cuûa moãi caïnh cuûa W. Ñoaïn L ñöôïc kieåm tra ñoái vôùi moãi caïnh cuûa W, vaø phaàn naèm ôû nöûa khoâng gian phía ngoaøi ñöôïc loaïi ra. Sau khi moïi caïnh ñaõ ñöôïc kieåm tra, phaàn coøn laïi cuûa L seõ naèm trong W.Ta bieåu dieãn L ôû daïng tham soá: P(t) = P1 + ct vôùi c = P2 - P1. w L P P Vôùi moãi caïnh cöûa soå, duøng hai giaù trò t vaø t ñeå giöõ laïi vuøng cuûa t maø ñoaïn coù theå naèm trong cöûa soå. Nghóa laø khoâng theå thaáy ñoaïn ôû ngoaøi khoaûng (t, t). Giaù trò baét ñaàu cho t vaø tlaø 0 vaø 1. Khoaûng naøy lieân tuïc ñöôïc caét xeùn khi xöû lyù xong moãi caïnh. Neáu luùc naøo khoaûng naøy thaønh roãng, thoaùt ra khoûi thuaät giaûi caét, vaø ñoaïn L hoaøn toaøn bò caét. Coøn khoâng thì khoaûng (t, t) xaùc ñònh phaàn cuûa L naèm trong cöûa soå. Vì W loài, moãi caïnh E cuûa noù coù theå cho laø ñöôøng cho ôû daïng ñieåm chuaån: n.p = D Vôùi n laø chuaån höôùng ra cuûa caïnh. Baây giôø E coù theå coù moät soá tình huoáng so vôùi ñöôøng L. P P P P c c n n E E · E song song L: neáu n tröïc giao vôùi c (nghóa laø: n .c= 0). Nhö vaäy L seõ naèm hoaøn toaøn ôû trong hoaëc ôû ngoaøi cöûa soå. Ñeå xeùt tieáp, choïn ñieåm baát kyø treân L, laø P1 vaø kieåm tra trong-ngoaøi. Ñaët p= P - 0 laø vector töø goác toïa ñoä ñeán P. L seõ hoaøn toaøn naèm trong neáu: p.n < D Ngöôïc laïi L hoaøn toaøn naèm ngoaøi. · E khoâng song song vôùi L: L phaûi caét caïnh E taïi ti, ñeå tính ti duøng phöông trình: ti=( D - n.p1 ) /n.c Neáu chieàu c cuûa noù nhoû hôn 900 keå töø n ( n.c > 0) thì ñöôøng seõ ñi ra. Ngöôïc laïi seõ ñi vaøo. Neáu ñi vaøo, thì phaàn vôùi t ti seõ khoâng thaáy ñöôïc, vaø t ñöôïc giaûm veà ti(neáu ti < t). Khi keát thuùc, giaù trò cuûa t vaø t seõ ñöôïc thay vaøo P1+ ct, ñeå coù ñöôïc caùc ñieåm ñaàu cuûa ñöôøng bò caét. Tích hai vector Tích vector cuûa hai vector laø moät vector. Moät trong nhieàu tính chaát höõu duïng cuûa noù laø noù tröïc giao vôùi hai vector ban ñaàu. Tích vector chæ ñöôïc ñònh nghóa cho vector ba chieàu, nhöng noù cuõng aùp duïng trong moät so._.á vaán ñeà trong ñoà hoïa lieân quan ñeán ña giaùc hai chieàu. Cho vector a=(ax, ay, az) vaø b=(bx, by, bz) tích vector cuûa chuùng vieát laø a x b. Noù ñöôïc ñònh nghóa theo caùc vector ñôn vò chuaå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 caùc tính chaát ñaïi soá 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) · YÙ nghóa hình hoïc cuûa tích vector: 1. ax b tröïc giao vôùi caû a vaø b. 2. Ñoä daøi a x b baèng dieän tích hình bình haønh xaùc ñònh bôûi a vaø b. Dieän tích naøy laø: |a x b| = |a||b|sin() vôùi laø goùc giöõa a vaø b, ño töø a ñeán b hay ngöôïc laïi mieãn sao goùc nhoû hôn 180. 3. Chieàu cuûa a x b xaùc ñònh töø quy taéc baøn tay phaûi khi laøm vieäc trong heä tay phaûi. Tích boä ba voâ höôùng Cho ba vector a, b, c keát hôïp chuùng cho ra soá voâ 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 boä ba voâ höôùng coù yù nghóa hình hoïc ñôn giaûn. Giaù trò cuûa noù laø theå tích cuûa khoái laêng truï taïo bôûi caùc vector a,b, c. Daáu cuûa tích boä ba voâ höôùng tuøy theo cos () döông neáu 90. a x b Theå tích a x b x c a b c Phöông trình maët phaúng Trong khoâng gian, qua 3 ñieåm A (xa, ya, za), B(xb, yb, zb), vaø C(xc, Yc, zc) khoâng thaúng haøng xaùc ñònh ñöôïc phöông trình maët phaúng nhö sau: Ta coù vector AB = (x-x, y-y, z-z) vaø AC = (x-x, y-y, z-z) Tích höõu höôùng cuûa hai vector AB vaø AC laø phaùp vector n cuûa maët phaúng mp(ABC). Vector n coù toïa ñoä nhö sau: n = ((y-y)*(z-z) - (y-y)*(z-z), (z-z)*(x-x) - (z-z)*(x-x), (x-x)*(y-y) - (x-x)*(y-y)) Neáu chuùng ta ñaët: a = (y-y)*(z-z) - (y-y)*(z-z) b = (z-z)*(x-x) - (z-z)*(x-x) c= (x-x)*(y-y) - (x-x)*(y-y) d = - xa- y b- z c thì vector n coù theå vieát laïi nhö sau: n = (a, b, c) Phöông trình maët phaúng ñöôïc xaùc ñònh theo ñònh thöùc caáp 3 nhö sau: x-x x-x x-x y-y y-y y-y z-z z-z z-z = 0 Phöông trình maët phaúng mp(ABC) ôû daïng toång quaùt: aX + bY+ cZ + d= 0 Phöông trình ñöôøng thaúng Trong khoâng gian cho hai ñieåm A (xa , ya , za), B(xb , yb , zb) seõ xaùc ñònh ñöôïc phöông trình ñöôøng thaúng ñi qua hai ñieåm A ,B nhö sau: Vector AB = (xb - xa , yb - ya , zb -za ) laø vector chæ phöông cuûa ñöôøng thaúng qua hai ñieåm A, B (ñeå goïn hôn ta vieát vector chæ phöông AB=(a1, a2, a3), phöông trình cuûa ñöôøng thaúng coù ba daïng nhö sau: · Phöông trình tham soá: X = at + x Y = at + y Z = at + y · Phöông trình daïng chính taéc: = = (vôùi ñieàu kieän a, a, a 0 ) · Phöông trình daïng toång quaùt: a2(x - xa ) = a1( y - ya ) a1(z - za ) = a3( x - xa ) Heä phöông trình treân töông ñöông vôùi heä phöông trình sau: ax - ay + 0 + ay- ax = 0 ax + 0 - az + az - ax = 0 Phöông trình toång quaùt cuûa ñöôøng thaúng qua 2 ñieåm trong khoâng gian laø heä phöông trình baäc nhaát 3 bieán x, y, z nhö treân. II. CAÙC ÑOÁI TÖÔÏNG HÌNH HOÏC VAØ SÖÏ TÖÔNG QUAN Trong phaïm vi cuûa moân hình hoïc thì khoâng gian dieãn dòch cuûa noù raát lôùn, chính vì vaäy toâi thieát keá thuaät toaùn treân caùc ñoái töôïng hình hoïc cô baûn. Vaø töø nhöõng thuaät toaùn naøy chuùng ta coù theå môû roäng ra cho moät dieãn dòch roäng lôùn hôn. II.1. CAÙC QUAN HEÄ HÌNH HOÏC TRONG 2D Caùc ñoái töôïng hình hoïc cô baûn: · Ñieåm · Ñöôøng thaúng · Ña giaùc Söï töông quan giöõa caùc ñoái töôïng hình hoïc: · Ñieåm - Ñöôøng thaúng. · Ñieåm - Ña giaùc. · Ñöôøng thaúng - Ñöôøng thaúng. · Ñöôøng thaúng - Ña giaùc. · Ña giaùc - Ña giaùc. Kieåm tra söï töông quan giöõa caùc ñoái töôïng hình hoïc: Ñieåm - Ñöôøng thaúng Kieåm tra ñieåm coù thuoäc ñöôøng thaúng? Tính khoaûng caùch töø ñieåm ñeán ñöôøng thaúng neáu ñieåm khoâng thuoäc ñöôøng thaúng. Ñieåm - Ña giaùc Kieåm tra ñieåm beân trong hay beân ngoaøi ña giaùc?. Ñöôøng thaúng - Ñöôøng thaúng Kieåm tra hai ñöôøng thaúng truøng nhau, caét nhau hay song song. Tính goùc giöõa hai ñöôøng thaúng. Tính hình chieáu cuûa ñoaïn thaúng treân ñöôøng thaúng. Ñöôøng thaúng - Ña giaùc Kieåm tra ñöôøng thaúng naèm beân trong hay beân ngoaøi ña giaùc. Clip moät ñoaïn thaúng vaøo ña giaùc. Ña giaùc - Ña giaùc Kieåm tra söï töông quan giöõa hai ña giaùc. Caét nhau? Loàng nhau hay rôøi nhau? Tính dieän tích giao nhau cuûa hai ña giaùc. Kieåm tra ña giaùc loài, loõm. Tính dieän tích cuûa ña giaùc. II.2. CAÙC QUAN HEÄ HÌNH HOÏC TRONG 3D Caùc ñoái töôïng hình hoïc cô baûn: · Ñieåm · Ñöôøng thaúng · Maët phaúng Söï töông quan giöõa caùc ñoái töôïng hình hoïc: · Ñieåm - Ñöôøng thaúng. · Ñieåm - Maët phaúng. · Ñöôøng thaúng - Ñöôøng thaúng. · Ñöôøng thaúng - Maët phaúng. · Maët phaúng - Maët phaúng. Kieåm tra söï töông quan giöõa caùc ñoái töôïng hình hoïc: Ñieåm - Ñöôøng thaúng Kieåm tra ñieåm coù thuoäc ñöôøng thaúng? Tính khoaûng caùch töø ñieåm ñeán ñöôøng thaúng neáu ñieåm khoâng thuoäc ñöôøng thaúng. Ñieåm - Maët phaúng Kieåm tra ñieåm coù thuoäc maët phaúng? Tính khoaûng caùch töø ñieåm ñeán maët phaúng neáu ñieåm khoâng thuoäc maët phaúng. Ñöôøng thaúng - Ñöôøng thaúng Kieåm tra hai ñöôøng thaúng ñoàng phaúng, caét, song song, cheùo nhau, vuoâng goùc? Tính goùc giöõa hai ñöôøng thaúng. Tính khoaûng caùch giöõa hai ñöôøng thaúng cheùo nhau. Tính hình chieáu cuûa ñoaïn thaúng treân ñöôøng thaúng. Ñöôøng thaúng - Maët phaúng Kieåm tra ñöôøng thaúng thuoäc maët phaúng? Kieåm tra ñöôøng thaúng vaøø maët phaúng caét nhau? Kieåm tra ñöôøng thaúng vaø maët phaúng song song? Kieåm tra ñöôøng thaúng vaø maët phaúng vuoâng goùc? Tính goùc giöõa ñöôøng thaúng vaø maët phaúng neáu ñöôøng thaúng vaø maët phaúng caét nhau. Tính khoaûng caùch giöõa ñöôøng thaúng vaø maët phaúng neáu ñöôøng thaúng vaø maët phaúng song song nhau. Maët phaúng - Maët phaúng Kieåm tra hai maët phaúng truøng nhau? Kieåm tra hai maët phaúng caét nhau? Kieåm tra hai maët phaúng song song? Kieåm tra hai maët phaúng vuoâng goùc? Tính goùc giöõa hai maët phaúng neáu hai maët phaúng caét nhau. Tính khoaûng caùch giöõa hai maët phaúng neáu hai maët phaúng song song nhau. Tìm giao ñieåm cuûa hai maët phaúng. III. CAÙC THUAÄT TOAÙN KIEÅM TRA SÖÏ TÖÔNG QUAN GIÖÕA CAÙC ÑOÁI TÖÔÏNG HÌNH HOÏC Trong phaàn naøy toâi trình baøy caùch thöïc hieän moät vaán ñeà, ñöôïc xaây döïng theo logic nhaèm muïc ñích ñeå ngöôøi ñoïc hoaëc tham khaûo coù theå deã daøng kieåm tra so saùnh ñoái chieáu giöõa thuaät toaùn vôùi cô sôû toaùn hoïc. III.1. CAÙC QUAN HEÄ HÌNH HOÏC TRONG MAËT PHAÚNG (2D) Tính goùc giöõa hai ñöôøng thaúng Cô sôû toaùn hoïc: Ñaây laø öùng duïng quan troïng cuûa tích voâ höôùng. Hình a döôùi cho thaáy goùc q giöõa hai vector a vaø b. Chuùng taïo thaønh hai caïnh cuûa tam giaùc, vaø caïnh thöù ba laø a-b. b a a-b Töø ñònh nghóa tích voâ höôùng cuûa vector ø vaø laø a.b= |a||b| cos( ) vôùi q :goùc giöõa vector a vaø vector b Vaø töø bieåu thöùc giaûi tích cuûa tích voâ höôùng: a.b = a b+ a b Ta coù cos() = a.b / |a||b|=/ Cos() döông neáu || nhoû hôn 90o, vaø aâm neáu || lôùn hôn 90o. Giaûi thuaät: - Tính vector chæ phöông a vaø b cuûa 2 ñoaïn thaúng - Tính vector voâ höôùng a.b - Cos ()= a.b / |a| |b| - Goùc 2 ñoaïn thaúng Alpha= arcos(cos()) Tìm hình chieáu cuûa ñoaïn thaúng AB leân ñöôøng thaúng b Cô sôû toaùn hoïc: Ñeå tính hình chieáu ñoaïn AB leân ñöôøng thaúng b ñi qua C vaø D, ta tìm hình chieáu cuûa ñieåm A laø A’ vaø B laø B’ treân ñöôøng thaúng b. Ñoaïn A’B’ chính laø hình chieáu cuûa AB treân ñöôøng b. A B B’ A’ C D (b) · Xaùc ñònh PT ñi qua 2 ñieåm C, D: ax + by + c = 0 coù vector chæ phöông VCF = (xD-xC , yD-yC ) = (-b, a) vaø c = - a * xC - b * yC. · Xaùc ñònh PT ñöôøng thaúng D ñi qua ñieåm A vaø vuoâng goùc vôùi CD: bx -ay + c’ = 0 coù vector chæ phöông cuûa D =(a, b) vaø c’= b*xA + a*yA · Tính giao ñieåm A’(xA’, yA’) cuûa heä PT (1) vaø (2) ax + by + c = 0 (1) bx - ay + c’= 0 (2) xA’= (-c’*b + c*a) / ( a*a + b*b) yA’= ( -c*b + c’*a) / ( a*a + b*b) · Töông töï tính B’ laø giao ñieåm cuûa: . Phöông trình ñöôøng thaúng ñi qua CD . Vaø Phöông trình ñöôøng thaúng D’ ñi qua B vaø vuoâng goùc vôùi CD Giaûi thuaät: - Tìm vector chæ phöông VCF (-b, a) cuûa phöông trình ñöôøng thaúng qua hai dieåm C, D: ax + by + c =0 - Tính heä soá c. - Tính c1 cuûa phöông trình D1 ñi qua ñieåm A vaø vuoâng goùc vôùi CD: bx - ay + c1 = 0 - Tìm giao ñieåm A’cuûa ñöôøng D1 vaø ñöôøng qua C, D . - Tìm giao ñieåm B’ cuûa ñöôøng D2 ñi qua ñieåm B vaø vuoâng goùc vôùi ñöôøng thaúng CD. - Khi ñoù A’B’ chính laø hình chieáu cuûa AB. Xaùc ñònh giao ñieåm giöõa hai ñoaïn thaúng Cô sôû toaùn hoïc: Cho hai ñoaïn thaúng, xaùc ñònh chuùng coù caét nhau khoâng, neáu coù tìm giao ñieåm.Giaû söû ñöôøng 1 töø a ñeán b vaø ñöôøng 2 töø c ñeán d nhö trong hình veõ, hai ñoaïn thaúng coù theå boá trí theo nhieàu caùch khaùc nhau. a b c d d c b a b a d c a b c d 1 2 Phöông trình tham soá cho moãi ñöôøng nhö sau: (1) (2) x1 (t) = ax + (bx - ax) * t y1 (t) = ay + (by - ay) * t vaø x2 (u) = cx + (dx - cx) * u y2 (u) = cy + (dy - cy) * u Ta goïi caùc ñöôøng thaúng chöùa caùc ñoaïn thaúng ab vaø cd laø caùc ñöôøng cha, ñaây laø caùc ñöôøng voâ haïn. Tröôùc heát, ta xeùt hai ñöôøng “cha” coù giao nhau khoâng, sau ñoù xem giao ñieåm coù thuoäc caû hai ñoaïn thaúng khoâng? Neáu caùc ñöôøng “cha’ giao nhau, ta coù giaù trò to vaø uo sao cho: x1 (to) = x2(uo) vaø y1(to) =y2(uo) Töø ñaây, ta coù caùc phöông trình sau: (3) (4) (5) ax + (bx - ax) * to = cx + (dx - cx ) * uo ay + (by - ay) * to = cy + (dy - cy ) * uo Khöû uo, ta ñöôïc: D* to = (cx - ax) * (dy - cy ) - (cy - ay) * (dx - cx) vôùi D = (bx - ax) * (dy - cy) - ( by - ay) * (dx - cx) Coù hai tröôøng hôïp cô baûn, D baèng hay khaùc 0. D khaùc zero Neáu D khaùc 0, ta tính to töø phöông trình (4). Neáu to naèm ngoaøi ñoaïn [0, 1] thì khoâng coù giao ñieåm giöõa hai ñoaïn. Ngöôïc laïi, thì coù theå coù giao ñieåm, thay to vaøo (3) ñeå tính uo. Neáu uo naèm trong ñoaïn [0, 1] thì chaéc chaén coù giao ñieåm, vaø duøng phöông trình (1) vaø (2) ñeå tính. D baèng zero (6) Neáu D baèng 0, töø phöông trình (5) suy ra: (dy - cy) / (dx - cx) = (by - ay) / (bx - ax) (7) Nghóa laø caùc heä soá goùc baèng nhau, neân caùc ñöôøng cha song song. Neáu caùc ñöôøng cha truøng nhau thì caùc ñoaïn cuõng coù theå truøng nhau. Ñeå kieåm ñieàu naøy, ta xem c coù naèm treân ñöôøng cha ñi qua a vaø b khoâng. Döïa vaøo phöông trình cuûa ñöôøng cha laø: (bx - ax) * (y - ay) - (by - ay) * (x - ax) = 0 thay cx cho x vaø cy cho y vaø xem veá traùi coù ñuû gaàn 0 khoâng (nghóa laø: nhoû hôn löôïng naøo ñoù, nhö 10 - 5). Neáu khoâng, caùc ñöôøng cha khoâng truøng nhau, vaø khoâng coù giao ñieåm. Neáu thoûa maõn thì phaûi thöïc hieän böôùc kieåm cuoái cuøng ñeå xem caùc ñoaïn coù truøng nhau khoâng. Töø phöông trình (1) tìm hai giaù trò tc vaø td maø ñöôøng ñaït tôùi vò trí c vaø d. Vì caùc ñöôøng cha truøng nhau, ta chæ caàn duøng thaønh phaàn x (neáu ñöôøng 1 thaúng ñöùng, thì duøng thaønh phaàn y), vaø thay cx vaø dx, ta coù : (8) tc = (cx - ax) / (bx - ax) td = (dx - ax) / (bx - ax) Ñöôøng 1 baét ñaàu taïi 0 vaø keát thuùc taïi 1, vaø xeùt thöù töï cuûa boán giaù trò 0, 1, tc vaø td, ta xaùc ñònh ñöôïc vò trí töông ñoái cuûa hai ñöôøng. Seõ choàng nhau tröø khi caû hai tc vaø td nhoû hôn 0 hay lôùn hôn 1. Neáu coù truøng nhau, ta deã daøng xaùc ñònh caùc ñieåm ñaàu truøng nhau töø tc vaø td. Giaûi thuaät ñöôïc xaây döïng trong thuû tuïc Intersect (), goàm caùc tham soá laø boán ñieåm ñaàu cuûa caùc ñöôøng, giaù trò traû veà coù theå coù theå coù caùc giaù trò sau: 1: coù moät giao ñieåm. 2: khoâng giao nhau. 3: caùc ñoaïn thaúng song song nhau. 4: hai ñoaïn thaúng choàng nhau. 5: hai ñoaïn thaúng cuøng naèm treân 1 ñöôøng thaúng, khoâng caét nhau. Giaûi thuaät: -Tính Maãu soá D; -Neáu D 0 . Tính to,uo; . Neáu to thuoäc [0,1] vaø uo thuoäc [0,1] + Tính giao ñieåm M + Return 1; ( 2 ñoaïn thaúng caét nhau taïi M) Ngöôïc laïi Return 2; (2 doaïn thaúng khoâng caét nhau) - Ngöôïc laïi, . Neáu c naèm treân ñoaïn ab + Tính tc, td; + Neáu khoâng phaûi caû tc vaø td 1 Return 4; (2 doaïn thaúng choàng nhau) + Ngöôïc laïi, Return 5; (2ñoaïn thaúng naèm treân 1 ñöôøng thaúng vaø khoâng caét nhau) . Ngöôïc laïi, Return 3; (2 ñoaïn thaúng song song ) Veõ ña giaùc (Polygon) Cô sôû toaùn hoïc: Ña giaùc laø taäp hôïp caùc ñoaïn thaúng lieân tieáp cuøng naèm trong maët phaúng kheùp kín. Moät ña giaùc coù ít nhaát 3 caïnh. Nhö vaäy, ña giaùc ñôn giaûn nhaát laø tam giaùc. Giaûi thuaät: - Xuaát phaùt töø ñænh ñaàu tieân - Veõ noái ñeán ñænh keá tieáp theo thöù töï cuøng chieàu kim ñoàng hoà. - Veõ noái töø ñænh cuoái cuøng ñeán ñænh ñaàu tieân. Veõ n-giaùc Cô sôû toaùn hoïc: Moät n-giaùc laø ña giaùc quy taéc coù N caïnh (ña giaùc quy taéc: ña giaùc maø moïi caïnh coù ñoä daøi baèng nhau, vaø caùc caïnh keà nhau taïo neân nhöõng goùc trong baèng nhau). Neáu cho ñænh ñaàu tieân treân truïc x taïi (R, x). Cho goùc A baát kyø, vò trí (x,y) cuûa moät ñieåm treân ñöôøng troøn coù goùc A seõ ñöôïc tính (x,y) = (R cos(A), R sin(A)). Vaø ñænh thöù i, V, cuûa n -giaùc naèm ôû goùc 2p (i -1) / N vaø coù vò trí: V = ( R cos(2p (i -1) / N ), R sin(2p (i -1) / N) ). Giaûi thuaät: - Soá ñænh = N - Ñònh goùc A = 2 Pi / N - Voøng laëp xaùc ñònh ñænh thöù i . Goùc = i *A; . Tìm toïa ñoä ñænh V. Toâ maøu ña giaùc Cô sôû toaùn hoïc: Phöông phaùp hieån thò caùc vuøng ñöôïc toâ maøu trong ñoà hoïa maùy tính laø quaù trình xaùc ñònh caùc pixel töông öùng thuoäc vuøng toâ maøu cho noù. Coù nhieàu thuaät toaùn ñaõ ñöôïc nghieân cöùu vaø phaùt trieån cho vieäc hieån thò caùc vuøng ñöôïc toâ maøu treân maøn hình, moät trong nhöõng thuaät toaùn ñoù laø toâ maøu theo veát daàu loang, moät thuaät toaùn khaùc laø toâ maøu theo doøng queùt. ÔÛ ñaây ta duøng phöông phaùp toâ maøu theo doøng queùt (scan-line algorithm) hay coøn goïi laø giaûi thuaät toâ maøu chaün leû (odd - even algorithm). Thuaät giaûi naøy söû duïng caùc giao ñieåm giöõa caùc ñöôøng bieân cuûa vuøng caàn toâ vôùi caùc ñöôøng thaúng goïi laø doøng queùt vaø xaùc ñònh caùc pixel naøo naèm trong vuøng toâ maøu giöõa hai giao ñieåm lieân tieáp, ñoù chính laø caùc pixel doïc theo ñöôøng queùt naèm giöõa hai giao ñieåm vaø naèm beân trong ña giaùc. ÔÛ moãi ñieåm giao doøng queùt chuyeån ñoåi hoaëc ñi vaøo hoaëc ñi ra khoûi ña giaùc, ñoù laø söï thay ñoåi parity cuûa ñieåm ñoù. Neáu doøng queùt ñi vaøo trong ña giaùc nhöõng pixels tieáp theo seõ ñöôïc toâ, neáu ñi ra ngoaøi nhöõng pixels tieáp theo seõ khoâng ñöôïc toâ. Khi doøng queùt ñi qua moät ñænh P cuûa ña giaùc (chính laø giao ñieåm cuûa 2 caïnh cuûa ña giaùc) noù taïo ra 2 giao ñieåm, moãi ñieåm vôùi 1 caïnh cuûa ña giaùc ñi qua ñænh ñoù, neáu ñænh ôû giaù trò cöïc (local extremum) Pixels ôû beân traùi vaø beân phaûi cuûa ñænh ñoù seõ coù cuøng parity, nhöng neáu ñænh khoâng ôû giaù trò cöïc caùc Pixels ôû beân traùi vaø beân phaûi cuûa ñænh ñoù seõ coù parity ngöôïc nhau, do ñoù ta caàn coù moät xöû lyù ñaëc bieät hôn. 1 2, 3 1 4 2 Scan line 1 Scan Line 2 Ÿ Neáu P laø giao ñieåm cuûa hai caïnh coù höôùng y ngöôïc nhau (moät caïnh coù giaù trò y taêng,moät caïnh coù giaù trò y giaûm - Scan Line 1) thì doøng queùt coù 2 ñieåm giao. Ÿ Neáu P laø giao ñieåm cuûa hai caïnh coù höôùng y truøng nhau (hai caïnh ñeàu coù giaù trò y cuøng taêng hay giaûm - Scan Line 2) thì doøng queùt coù 1 ñieåm giao. Tröôùc khi toâ maøu, ta caàn kieåm tra moãi ñænh ña giaùc. Neáu y cuûa noù khoâng laø giaù trò cöïc trò(local extremum), nhö trong scan line 2. Vì nhöõng Pixels ñoái vôùi beân traùi vaø phaûi cuûa ñænh ñoù khaùc parity, khaùc giaù trò kieåm tra inside-outside; ta phaûi laøm ngaén moät trong hai caïnh ñi moät chuùt (giaûm y cuûa ñaàu caïnh ñoù moät pixel). Ñoái vôùi caïnh naèm ngang trong ña giaùc khoâng caàn ñöa vaøo taäp caùc caïnh cuûa ña giaùc ñeå xöû lyù. Giaûi thuaät: Böôùc 1: Xaùc ñònh Frame “bao” ña giaùc. Frame bao ña giaùc laø hình chöõ nhaät nhoû nhaát chöùa toaøn boä ña giaùc. Ñeå xaùc ñònh hình chöõ nhaät naøy ta laáy min hoaëc max caùc toïa ñoä ñænh cuûa ña giaùc trong heä toïa ñoä Descartes roài taêng, hoaëc giaûm 1 ñeå ñaûm baûo hình chöõ nhaät laø hình bao vaø ña giaùc hoaøn toaøn naèm trong noù. Böôùc 2: Xaùc ñònh danh saùch caùc caïnh ña giaùc ñeå xöû lyù. Laàn löôït duyeät taát caû caïnh cuûa ña giaùc: · Khoâng ñöa caïnh naèm ngang cuûa ña giaùc vaøo danh saùch. · Kieåm tra 2 caïnh ña giaùc lieân tieáp, neáu ñænh chung khoâng laø ñieåm cöïc trò (local extremum), laøm ngaén ñaàu caïnh cuûa moät caïnh ñi qua ñænh chung moät pixel. Böôùc 3: Tieán haønh toâ maøu. Tieán haønh caùc ñöôøng queùt ngang tö ø Ymin + 1 ñeán Ymax - 1. · ÖÙng vôùi moät ñöôøng queùt ngang yi naøo ñoù, ta xaùc ñònh caùc ñieåm caét (baèng giaûi thuaät tìm giao ñieåm giöõa hai ñoaïn thaúng ñaõ coù), giöõa caùc ñöôøng queùt ngang vôùi taát caû caùc caïnh cuûa ña giaùc. Vì tung ñoä y cuûa ñieåm caét baèng yi neân ta chæ caàn ñöa caùc hoaønh ñoä xi cuûa ñieåm caét vaøo moät danh saùch. · Saép xeáp laïi danh saùch sao cho caùc giaù trò xi taêng daàn. · Duyeät qua caùc ñieåm caét vaø ñeám soá ñieåm caét ñaõ duyeät. · Neáu ñieåm caét truøng vôùi ñænh cuûa ña giaùc: Neáu coù moät caïnh song song vôùi ñöôøng queùt thì ñænh tröôùc ñeám taêng vaø ñænh sau khoâng ñeám taêng. · Toâ maøu giöõa caùc caëp giao ñieåm . Böôùc 4: Laäp laïi böôùc hai cho ñeán khi yi = ymax. Böôùc 5: Veõ laïi ña giaùc baèng maøu ñaõ toâ. Löu yù: Neáu ña giaùc khoâng phaûi laø ña giaùc ñôn thì giaûi thuaät naøy khoâng vaän duïng ñöôïc. Ñieåm beân trong / beân ngoaøi ña giaùc Cô sôû toaùn hoïc: Giaûi thuaät naøy nhaèm xaùc ñònh moät ñieåm cho tröôùc coù naèm beân trong moät ña giaùc ñôn phaúng hay khoâng. Giaûi thuaät xaây döïng döïa treân ñònh lyù mang teân JORDAN sau ñaây: “Moãi ñöôøng cong, kín, ñôn, phaúng, moät chieàu, phaân hoaïch maët phaúng thaønh hai mieàn, moät trong hai mieàn ñoù hoaøn toaøn chöùa nhöõng ñöôøng thaúng naøo ñoù, mieàn coøn laïi thì khoâng coù tính chaát ñoù”. Trong ñònh lyù treân ñaây moät trong hai mieàn seõ ñöôïc goïi laø mieàn trong (goàm baûn thaân ñöôøng cong vaø phaàn maët phaúng giôùi noäi bôûi ñöôøng cong). Khoâng thuoäc mieàn trong goïi laø mieàn ngoaøi. Ñònh lyù naøy vaãn ñuùng cho tröôøng hôïp ña giaùc ñôn phaúng moät chieàu nhö laø moät tröôøng hôïp rieâng. Töø ñònh lyù naøy daãn ñeán heä quaû sau: “Töø moät ñieåm P baát kyø, veõ moät tia chæ caét ña giaùc ôû nhöõng ñieåm trong cuûa caùc caïnh (nghóa laø : khoâng ñi qua ñænh naøo cuûa ña giaùc); neáu soá giao ñieåm laø leû thì P laø ñieåm trong, neáu soá giao ñieåm laø chaün thì P laø ñieåm ngoaøi”. Veà maët kyõ thuaät moïi ñöôøng cong ñôn, phaúng, kín, lieân thoâng, khoâng töï caét ñeàu coù theå tieáp caän tuyeán tính baèng moät ña giaùc bao goàm moät soá höõu haïn caùc caïnh lieân tieáp. Vì vaäy cho pheùp xaây döïng moät giaûi thuaät test quan heä trong/ ngoaøi chæ baèng caùch xeùt soá giao ñieåm cuûa tia coù goác laø ñieåm caàn xeùt. Giaûi thuaät: - Choïn Px laø nöûa ñöôøng thaúng xuaát phaùt töø P song song vôùi truïc Ox, höôùng veà phía x>0. Laáy P=(x,y). - P laø ñieåm caàn xeùt. - Neáu (P laø moät ñænh) hoaëc (P thuoäc trong moät caïnh) thì Return (P ñieåm trong) - Ngöôïc laïi, xaùc ñònh giao ñieåm Px vôùi caùc caïnh ña giaùc { . Ci laø caïnh Pi Pi+1 cuûa ña giaùc . Neáu y = yi thì xeùt hai caïnh coù moät ñaàu laø Pi (1) .. Neáu caû hai ñaàu kia ôû moät phía cuûa Pi thì tính Px caét caû hai caïnh . Ngöôïc laïi (1) Neáu y > Max(yi,yi+1) hay y<Min(yi,yi+1) (2) Thì Px khoâng caét caïnh Ci . Ngöôïc laïi (2) .. Neáu x <= Min (xi,xi+1) (3) Thì Py caét caïnh Ci . Ngöôïc laïi (3) .. Xeùt toïa ñoä giao ñieåm (yo,xo) cuûa Px vôùi caïnh Ci Neáu x >= xo thì Px khoâng caét Ci } - Neáu soá giao ñieåm leû . Return P thuoäc ña giaùc. Kieåm tra quan heä giöõa ñoaïn thaúng vaø ña giaùc Caùc chöông trình öùng duïng moâ taû caùc hình aûnh baèng heä toïa ñoä theá giôùi thöïc, coù theå laø baát kyø heä toïa ñoä Descartes naøo maø ngöôøi duøng caûm thaáy thuaän tieän nhaát. Caùc hình aûnh ñöôïc moâ taû trong heä toïa ñoä thöïc sau ñoù seõ ñöôïc caùc heä ñoä hoïa aùnh xaï vaøo caùc heä toïa ñoä thieát bò. Thoâng thöôøng, caùc heä ñoà hoïa cho pheùp ngöôøi duøng xaùc ñònh moät vuøng naøo ñoù cuûa hình aûnh ñöôïc hieån thò vaø noù seõ hieån thò ôû ñaâu treân maøn hình (viewport). Ta coù theå choïn moät vuøng hay nhieàu vuøng ñeå hieån thò, caùc vuøng naøy coù theå ñaët ôû caùc nôi khaùc nhau hay loàng vaøo nhau treân maøn hình. Quaù trình naøy ñoøi hoûi nhieàu thao taùc nhö dòch chuyeån, bieán ñoåi tyû leä ñeå ñöa vaøo beân trong viewport hoaëc ñôn giaûn laø loaïi boû caùc phaàn hình aûnh naèm ngoaøi vuøng ñang ñöôïc xeùt. Thao taùc cuoái cuøng vaø cuõng ñöôïc söû duïng nhieàu nhaát coøn ñöôïc goïi laø clipping. Trong thuaät ngöõ thoâng thöôøng Viewport ñöôïc hieåu nhö moät window (hình chöõ nhaät) theo ñoù hình aûnh ñöôïc clipping. Tuy nhieân Viewport cuõng coù theå laø moät ña giaùc baát kyø. Baøi toaùn clipping sau ñaây ñöôïc xeùt cho tröôøng hôïp toång quaùt hôn: clipping vôùi ña giaùc ñôn baát kì (cho caû hai tröôøng hôïp ña giaùc loài hoaëc loõm). Cô sôû toaùn hoïc vaø giaûi thuaät: Caùc böôùc tieán haønh clipping ñoaïn thaúng AB baèng moät ña giaùc ñôn, phaúng baát kì nhö sau: Böôùc 1: Hoaùn ñoåi A, B ñeå xA < xB. Neáu xA = xB . Hoaùn ñoåi A,B ñeå yA < yB Böôùc 2: Kieåm tra tính trong ngoaøi cuûa A vaø B ñoái vôùi ña giaùc (Duøng giaûi thuaät kieåm tra ñieåm beân trong/ngoaøi ña giaùc ) Böôùc 3: Tìm giao ñieåm cuûa AB vôùi ña giaùc (Duøng giaûi thuaät xaùc ñònh giao ñieåm cuûa 2 ñoaïn ñaõ coù ) Neáu coù giao ñieåm thì { - Ñöa caùc toïa ñoä cuûa caùc ñieåm caét vaøo moät danh saùch - Saép xeáp cho hoaønh ñoä caùc giao ñieåm taêng daàn (Neáu xA = xB saép xeáp theo tung ñoä) } Böôùc 4: Thöïc hieän clipping. - Neáu A vaø B ñeàu naèm trong ña giaùc thì (1) Neáu soá ñieåm caét = 0, Return (AB naèm hoaøn toaøn trong ña giaùc) - Ngöôïc laïi { . Ñoaïn thaúng töø A ñeán ñieåm caét thöù 1 thuoäc ña giaùc. . i = 1 . Laëp laïi . Tìm trung ñieåm cuûa ñoaïn thaúng noái hai ñieåm caét keá tieáp nhau. . Kieåm tra trong /ngoaøi ñoái vôùi trung ñieåm. . Neáu trung ñieåm naèm trong ña giaùc thì Return (Ñoaïn thaúng thuoäc ña giaùc) . Ngöôïc laïi, Return (Ñoaïn thaúng khoâng thuoäc ña giaùc). . Inc (i,1) Cho ñeán khi i = soá ñieåm caét } - Ngöôïc laïi, coù ñieåm A hay B naèm ngoaøi ña giaùc (1) - Neáu soá ñieåm caét = 0, Return (Ñoaïn AB naèm ngoaøi ña giaùc). - Neáu soá ñieåm caét 0 thì { . Theâm toïa ñoä ñieåm A vaøo ñaàu danh saùch . Theâm toïa ñoä ñieåm B vaøo cuoái danh saùch . i = 1 . Laëp laïi . Tìm trung ñieåm cuûa ñoaïn thaúng noái hai ñieåm caét keá tieáp nhau . Kieåm tra trong/ ngoaøi ñoái vôùi trung ñieåm. . Neáu trung ñieåm naèm trong ña giaùc thì Return (Ñoaïn thaúng thuoäc ña giaùc) . Ngöôïc laïi, Return (Ñoaïn thaúng khoâng thuoäc ña giaùc) . inc (i,1) Cho ñeán khi heát danh saùch } Ngöôïc laïi, Return (Ñoaïn thaúng khoâng thuoäc ña giaùc). Böôùc 5: Veõ laïi caùc ñoaïn thaúng thuoäc ña giaùc * Môû roäng: Giaûi thuaät coù theå ñöôïc môû roäng cho vieäc clipping moät ña giaùc baèng caùch thöïc hieän clipping taát caû caùc caïnh cuûa ña giaùc. Kieåm tra quan heä hai ña giaùc Cô sôû toaùn hoïc: Giaûi thuaät naøy cho pheùp clip baát kyø moät ña giaùc vaøo 1 ña giaùc. Noù cuõng cho pheùp hình thaønh söï giao, hoäi cuûa 2 ña giaùc.Chuùng ta baét ñaàu baèng ví duï minh hoïa trong hình sau. Ta lieät keâ nhöõng ñænh theo thöù töï töø traùi sang phaûi, theo chieàu kim ñoàng hoà. D 6 5 4 3 2 1 d c b a C B A Hai ña giaùc SUBJ vaø CLIP ñöôïc theå hieän baèng 2 danh saùch (a,b,c,d) vaø (A,B,C,D) töông öùng. Taát caû ñieåm giao cuûa 2 danh saùch seõ ñöôïc xaùc ñònh vaø löu vaøo danh saùch (theo thöù töï sang phaûi cuûa moãi caïnh). Döïa vaøo hình veõ treân, ta coù: SUBJ_LIST: a, 1, b, 2, c, 3, 4, d, 5, 6 CLIP_LIST: A, 6 ,3 , 2, B, C, D, 4, 5 Duyeät SUBJ theo höôùng ñi tôùi cho tôùi khi tìm ñöôïc 1 ñieåm giao ñi vaøo (entering intersection), laø ñieåm giao maø SUBJ di chuyeån töø ngoaøi vaøo trong ña giaùc CLIP.Vaø ñöa ñieåm naøy vaøo danh saùch xuaát ña giaùc ñöôïc clip. Duyeät SUBJ tôùi khi gaëp 1ñieåm giao khaùc. Nhaûy ra khoûi SUBJ vaø di chuyeån theo CLIP thay vì SUBJ. Duyeät CLIP theo höôùng ñi tôùi. Tôùi khi gaëp moät ñieåm giao, nhaûy ra khoûi CLIP vaø duyeät theo SUBJ theo höôùng ñi tôùi, vaø cöù tieáp tuïc nhö vaäy. Moãi ñænh hoaëc moãi ñieåm giao gaëp phaûi khi duyeät seõ ñöôïc ñöa vaøo danh saùch xuaát ña giaùc ñöôïc clip. Laëp laïi tieán trình treân giöõa 2 ña giaùc, duyeät moãi ña giaùc theo höôùng ñi tôùi cho tôùi khi ñænh ñaàu tieân ñöôïc gaëp laïi. Danh saùch xuaát ra ôû thôøi ñieåm naøy (1,b,2,B) 1 b 2 3 4 d 5 6 a a restart start SUBJ_LIST: SUBJ_LIST: A 6 3 2 B 1 C D 4 5 Baây giôø, ta kieåm tra moät ñieåm giao“entering” khaùc cuûa SUBJ. Vaø seõ taïo ra danh saùch xuaát (3,4,5,6). Vieäc kieåm tra nhöõng ñieåm giao “entering” khaùc seõ chæ ra laø taát caû chuùng ñaõ ñöôïc duyeät, quaù trình chaám döùt. Caùch thöùc ñeå hieän thöïc quaù trình xöû lyù naøy laø xaây döïng hai danh saù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 Maø trong ño,ù vieäc duyeät moãi ña giaùc vaø lieät keâ nhöõng ñænh vaø ñieåm giao phaûi theo thöù töï ñöôïc gaëp. Giaûi thuaät: -Böôùc 1: Taïo danh saùch SUBJ_LIST Duyeät laàn löôït moãi caïnh ña giaùc SUBJ theo thöù töï cuøng chieàu kim ñoàng hoà { - Tìm caùc ñieåm caét cuûa caïnh Pi-Pi+1 vôùi ña giaùc CLIP. - Saép xeáp danh saùch ñieåm caét theo hoaønh ñoä taêng daàn . Neáu hoaønh ñoä Pi.x=Pi+1.x thì saép xeáp theo tung ñoä. - Ñöa ñænh Pi vaøo danh saùch SUBJ_LIST - Ñöa caùc ñieåm caét töø danh saùch ñieåm caét vaøo SUBJ_LIST theo höôùng ñi töø Pi tôùi Pi+1 } -Böôùc 2: Taïo danh saùch CLIP_LIST Duyeät laàn löôït moãi caïnh ña giaùc CLIP theo thöù töï cuøng chieàu kim ñoàng hoà { - Tìm caùc ñieåm caét cuûa caïnh Pi- Pi+1 vôùi ña giaùc SUBJ. - Saép xeáp danh saùch ñieåm caét theo hoaønh ñoä taêng daàn. Neáu hoaønh ñoä Pi.x=Pi+1.x saép xeáp theo tung ñoä. - Ñöa ñænh Pi vaøo danh saùch CLIP_LIST. - Ñöa caùc ñieåm caét töø danh saùch ñieåm caét vaøo CLIP_LIST theo höôùng ñi töø Pi tôùi Pi+1. } -Böôùc 3: Duyeät danh saùch SUBJ_LIST vaø CLIP_LIST. Voøng laëp (1) Voøng laëp (2) - Tìm ñieåm giao “entering” chöa duyeät cuûa SUBJ_LIST. - Duyeät treân SUBJ_LIST tôùi khi thaáy ñieåm giao tieáp theo . - Chuyeån sang duyeät treân CLIP_LIST tôùi khi thaáy ñieåm giao tieáp theo. Cho tôùi khi ñieåm ñaàu tieân(ñieåm ‘entering’) ñöôïc gaëp laïi. (voøng laëp 2 ) - Xuaát Danh saùch ña giaùc tìm ñöôïc ôû treân. Cho tôùi khi taát caû caùc ñieåm giao ‘entering’ ñaõ ñöôïc duyeät (voøng laëp 1) Kieåm tra tính loài cuûa ña giaùc Cô sô ûtoaùn hoïc: -Nhaän bieát quay traùi vôùi quay phaûi: Coù nhöõng thuaät giaûi ta phaûi duyeät moät ña giaùc, laàn löôït thaêm moãi ñænh hay caïnh. Ta xem nhö di chuyeån theo moät caïnh töø ñænh naøy ñeán ñænh kia vaø sau ñoù ra caïnh keá. Nhö vaäy caàn phaûi bieát ñi theo chieàu phaûi hay traùi. Ví duï, neáu P1, P2, P3 laø ba caïnh keà nhau cuûa ña giaùc, ta taïo vector caïnh a=P2-P1 vaø b=P3- P2. Hình (1) cho thaáy tröôøng hôïp a vaø b naèm trong maët xy vaø quay traùi khi ñi töø a ñeán b. Coøn hình (2) laø quay phaûi. b a b a Hình 1 Hình 2 Giaû söû duøng heä tay phaûi ôû hình 1 vaø hình 2 neân truïc z (hay chieàu k) höôùng ra ngoaøi töø trang saùch tôùi chuùng ta. Duøng quy taéc tay phaûi, tích a x b chæ ra ngoaøi vôùi thaønh phaàn k döông. Neáu laäp tích voâ höôùng vector naøy vôùi chính k, seõ ñöôïc moät ñaïi löôïng maø daáu cuûa noù cho bieát chieàu quay, döông neáu quay traùi vaø aâm neáu quay phaûi. Cho vector a vaø b trong maët xy, quay töø a ñeán b seõ laø döông neáu T= k.(a x b) >= 0 vaø aâm neáu ngöôïc laïi (Keát quaû khoâng ñoåi ñoái vôùi heä tay traùi). Vôùi ña giaùc loài, moïi pheùp quay coù cuøng chieàu, nhö ña giaùc A. Neáu ña giaùc khoâng loài, nhö tröôøng hôïp B, goàm caû hai pheùp quay. Nhö vaäy, ña giaùc ñôn laø loài neáu vaø chæ neáu moïi pheùp quay coù coù cuøng daáu khi ñöôïc duyeät. A B Giaûi thuaät: - Duyeät ña giaùc theo thöù töï caùc ñænh ñeå xeùt vieäc quay töø caïnh a ñeán caïnh b taïi moãi ñænh laø quay phaûi hay quay traùi. .Tính toïa ñoä theo höôùng oz cuûa tích vector a x b T= k(a x b) = ax*by - ay*bx - Neáu moïi pheùp quay ñeàu nhö pheùp quay taïi ñænh thöù nhaát, ña giaùc loài. - Neáu coù moät pheùp quay khaùc pheùp quay taïi ñænh thöù nhaát,ña giaùc loõm. Tính dieän tích ña giaùc Cô sôû toaùn hoïc: Vieäc tính moät ña giaùc ñôn phaúng baát kyø xuaát phaùt töø vieäc tính dieän tích tam giaùc. Dieän tích tam giaùc ñöôïc tính döïa vaøo tích hai vector nhö sau: S =(1/2) |a x b| Trong ñoù caùc vector a, b laø caùc vector caïnh cuûa tam giaùc. P P P P P P Vôùi moät ña giaùc n ñænh, ta coù theå phaân thaønh n - 2 tam giaùc baèng caùch töø moät ñænh naøo ñoù cuûa tam giaùc ta veõ caùc caïnh noái ñeán taát caû caùc caïnh coøn laïi cuûa ña giaùc. Khi ñoù dieän tích ña giaùc baèng toång dieän tích cuûa caùc tam giaùc con naøy. Laáy ñænh P1 laøm choát, laäp (n-1) vector choát vector a1=P2 - P1, a2 = P3 - P1, an-1=Pn - P1. Caùc vector naøy duøng ñeå tính dieän tích moãi tam giaùc. Hai caïnh cuûa tam giaùc i ñöôïc xaùc ñònh bôûi hai vector ai vaø ai+1. Nhöng neáu ña giaùc laø loõm, thì khoâng phaûi moïi ña giaùc ñeàu coù dieän tích döông. Do ñoù ñeå hình thaønh coâng thöùc toång quaùt tính dieän tích moät ña giaùc baát kyø ta phaûi bieán ñoåi coâng thöùc tính dieän tích tam giaùc moät chuùt. Trong coâng thöùc tính ._.