資源描述：
《幾何學(xué)算法基礎(chǔ)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、西南交通大學(xué)計(jì)算機(jī)與通信工程學(xué)院程序設(shè)計(jì)基礎(chǔ)算法IntersectingLinesWeallknowthatapairofdistinctpointsonaplanedefinesalineandthatapairoflinesonaplanewillintersectinoneofthreeways:1)nointersectionbecausetheyareparallel,2)intersectinalinebecausetheyareontopofoneanother(i.e.theyarethesameline),3)intersectinapoint
2、.Inthisproblemyouwilluseyouralgebraicknowledgetocreateaprogramthatdetermineshowandwheretwolinesintersect.Yourprogramwillrepeatedlyreadinfourpointsthatdefinetwolinesinthex-yplaneanddeterminehowandwherethelinesintersect.Allnumbersrequiredbythisproblemwillbereasonable,saybetween-1000and
3、1000.InputThefirstlinecontainsanintegerNbetween1and10describinghowmanypairsoflinesarerepresented.ThenextNlineswilleachcontaineightintegers.Theseintegersrepresentthecoordinatesoffourpointsontheplaneintheorderx1y1x2y2x3y3x4y4.Thuseachoftheseinputlinesrepresentstwolinesontheplane:thelin
4、ethrough(x1,y1)and(x2,y2)andthelinethrough(x3,y3)and(x4,y4).Thepoint(x1,y1)isalwaysdistinctfrom(x2,y2).Likewisewith(x3,y3)and(x4,y4).OutputThereshouldbeN+2linesofoutput.ThefirstlineofoutputshouldreadINTERSECTINGLINESOUTPUT.Therewillthenbeonelineofoutputforeachpairofplanarlinesreprese
5、ntedbyalineofinput,describinghowthelinesintersect:none,line,orpoint.Iftheintersectionisapointthenyourprogramshouldoutputthexandycoordinatesofthepoint,correcttotwodecimalplaces.Thefinallineofoutputshouldread``ENDOFOUTPUT".SampleInput5 00440440 50761023 50763-64-3 2022715185 03401225Sa
6、mpleOutputINTERSECTINGLINESOUTPUT POINT2.002.00NONE LINE POINT2.005.00 POINT1.072.20 ENDOFOUTPUT計(jì)算幾何學(xué)算法設(shè)計(jì)1、確定任意兩條線段是否都不相交設(shè)有一組線段，要求判斷這組線段中任意兩條線段是否都不相交。問(wèn)題分析：對(duì)于一組線段，我們可以先假設(shè)這組線段中不存在與垂直軸平行的線段，同時(shí)也沒(méi)有三條線段相交于一點(diǎn)的情況?；谶@種假設(shè)，我們可以通過(guò)一根垂直掃描線來(lái)掃描這組線段，在掃描過(guò)程中我們可以發(fā)現(xiàn)，一旦兩條線段存在交點(diǎn)，則其掃描的結(jié)果會(huì)發(fā)生變化。即垂直掃描線自上而下掃描時(shí)的
7、輸出會(huì)發(fā)生變化，如下圖所示。ABCDABABACDABCADCBDCBCDC從上面的圖可以看出，如果兩條線段之間存在交點(diǎn)，則在交點(diǎn)前后兩點(diǎn)之間的順序?qū)l(fā)生變化。因此我們可以通過(guò)如下算法來(lái)判斷哪些線段之間存在交點(diǎn)：1、將所有線段的端點(diǎn)按照X坐標(biāo)從小到大的順序進(jìn)行排列，如果兩個(gè)端點(diǎn)的X坐標(biāo)相同，則將Y坐標(biāo)小的放在前面，Y坐標(biāo)大的放在后面。設(shè)該集合為S。2、取S集合中的一個(gè)端點(diǎn)p。如果p是線段s的左端點(diǎn)，則將其插入序列T中；否則將其從序列中刪除。插入的方法是：若p在T集合中某線段的上方則插入到該線段的前面，否則查找下一條線段。這兒如何判斷在p點(diǎn)在T集合某線段的上方呢？
8、我們看一下下面的圖形：P
