【文章內(nèi)容簡介】 線 凸極值點是函數(shù)圖象的某段子區(qū)間內(nèi)極大值的橫坐標，極值點出現(xiàn)在函數(shù) 的駐點或不可導處；極值點上函數(shù)的導數(shù)為零或不存在，且函數(shù)的單調(diào)性必然變化。若一個 函數(shù) 的某一點存在某一鄰域，在該鄰域內(nèi)函數(shù)處處都有定義，而該點的函數(shù)值為最大（?。?，則該函數(shù)在該點處的值就是一個極大（小）值。如果它比鄰域內(nèi)其他各點處的 函數(shù)值 都大（小），它就是一個嚴格極大（小）值。該點就相應地稱為一 個極值點 或嚴格極值點。在極值點的左右，函數(shù)的增減性不一樣，比如說在極值點的左方鄰域內(nèi)函數(shù)單調(diào)增加，則在極值點的右方鄰域內(nèi)函數(shù)單調(diào)減小。極值是對函數(shù)某一區(qū)間的取值；極值不一定是整個函數(shù)定義域內(nèi)的最值。 幾何上，切線指的是 一條剛好觸碰 到曲線 上某一點的直線。更準確的說，當切線經(jīng)過曲線上的某點（即切點）時，切線的方向與曲線上該點的方向是相同的，此時， “ 切線在切點附近的部分 ” 最接近 “ 曲線在切點附近的部分 ” （無限逼近思想）。 2． 3． 3 區(qū)域的劃分與存儲 根據(jù)擬合的曲線和過凸極值點做的水平切線，將整個地圖劃分為小塊的區(qū)域，存儲每個區(qū)域的邊界值。通過計算每個區(qū)域的邊界值，將每個區(qū)域抽象為一個點。 2． 3． 4 構造連通無向圖 在 圖論 中，連通圖基于連通的概念。在一個 無向圖 G 中，若從 頂點 vi 到頂點 vj 有路徑相連 (當然從 vj 到 vi 也一 定有路徑 )，則稱 vi 和 vj 是連通的。如果 G 是 有向圖 ，那么連接 vi 和 vj 的路徑中所有的邊都必須同向。如果圖中任意兩點都是連通的，那么圖被稱作連通圖。圖的連通性是圖的基本性質。 將區(qū)域抽象為一個點后，根據(jù)原來區(qū)域的關聯(lián)性，將相應的點連接起來，構造連通無向圖，使用鄰接表或其他數(shù)據(jù)結構存儲無向圖。 2． 3． 5 設定權值，確定最優(yōu)路徑 最優(yōu)路徑就是路徑中最符合某種需求的一條路徑，比如最短路徑，就是從起點到終點的權值和最小的 邊 。對圖求最優(yōu)路徑的方法即稱為最優(yōu)路徑算法，通常用計算機編程實現(xiàn)。 中北大學 2020 屆畢業(yè)設計說明書 第 6 頁 共 31 頁 在公路運輸中，為了使運 輸?shù)臅r間和花費最少（花費可以是油耗和費用），需要找到起點和終點的最優(yōu)路徑。這條最優(yōu)路徑可以是路程最短的路徑，也可以是油耗最省的路徑，依 據(jù) 實際需求而定。在實際應用中，知道起點和終點，便可用最優(yōu)路徑算法計算出路徑，這對車輛的行駛有很好的指導作用。使用計算機編程實現(xiàn)，更能提高效率。 2． 4 系統(tǒng)規(guī)劃 該系統(tǒng)主要分為三部分，分別是基本的障礙物擬合及水平切線的求取、區(qū)域存儲并構造無向圖、設定權值然后尋找最優(yōu)路徑。 2． 4． 1 基本的障礙物擬合及水平切線的求取 本部分主要包括多個障礙物的曲線擬合、求取每個障礙物 的凸極值點和過凸極值點做水平切線。 2． 4． 2 區(qū)域存儲并構造無向圖 本部分主要包括對整個地圖的區(qū)域進行遍歷與編號和無向圖的構造 2． 4． 3 設定權值及尋找最優(yōu)路徑 本部分主要包括起點與終點的設定，計算出一個或多個通路，然后根據(jù)權值尋找出最優(yōu)的路徑 2． 5 系統(tǒng)流程分析 通過調(diào)查和分析，本系統(tǒng)的業(yè)務流程主要是：用戶通過在畫板上點擊相應的點來構造障礙物，當障礙物完成之后，點擊‘畫切線’按鈕開始對地圖中所有的障礙物進行凸極值點的計算，然后在凸極值點處畫水平切線，將整個地圖劃分為多個區(qū)域；之后用戶選擇 出起點和終點，然后輸入起點和終點所在的區(qū)域；最后點擊‘完成’按鈕，程序開始計算所有可行的路徑，并標記出最優(yōu)的路徑。 在用戶的操作過程中和系統(tǒng)運行的過程中，程序都要時刻地記下重要的數(shù)據(jù)，方便之后的計算。程序存儲的數(shù)據(jù)主要有：用戶點擊的點的坐標、每個障礙物的邊界經(jīng)過的點的坐標、每個障礙物的凸極值點的坐標、過凸極值點做的水平切線的兩個端點的坐標和用來存儲無向圖的鄰接表等等。 中北大學 2020 屆畢業(yè)設計說明書 第 7 頁 共 31 頁 圖 21 系統(tǒng)流程圖 中北大學 2020 屆畢業(yè)設計說明書 第 8 頁 共 31 頁 3 系統(tǒng)設計 3． 1 系統(tǒng)配置 硬件平臺： CPU： 內(nèi)存： 1GB 以上 軟件平臺： 操作系統(tǒng)： windows、 linux 等 開發(fā)工具：支持 HTML5 的瀏覽器、 notepad++ 3． 2 系統(tǒng)結構模型設計 基于 jQuery 的 JavaScript 框架的圖形化實現(xiàn)，數(shù)據(jù)由用戶進行輸入，數(shù)據(jù)處理分布在格子的類中，通過與界面類進行交互。根據(jù)系統(tǒng)的總體目標，本系統(tǒng)開發(fā)采用了面向消息機制的實時消息處理機制。不斷的監(jiān)聽用戶的動作，以做出相應的處理。在點擊面板 后，程序會做出相應的處理。同時采用了面向對象的思路和方法，對比較相似的操作寫進一個類中，方便操作，提高了系統(tǒng)的安全性能，便于以后的擴展和維護。 Jquery 是一個 非常 優(yōu)秀的 Javascript 框架。它是輕量級的 js 庫 ，它兼容 CSS3，還兼容各種瀏覽器（ IE +, FF +, Safari +, Opera +）。 jQuery 使用戶能更方便地處理 HTML documents、 events、實現(xiàn)動畫效果，并且方便地為網(wǎng)站提供AJAX 交互。 jQuery 還有一個比較大的優(yōu)勢是，它的文檔說明 很全，而且各種應用也說得很詳細，同時還有許多成熟的插件可供選擇。 jQuery 能夠使用戶的 html頁面保持代碼和 html 內(nèi)容分離，也就是說，不用再在 html 里面插入一堆 js 來調(diào)用命令了，只需定義 id 即可。 jCanvaScript 是一個面向 HTML5 畫布（ canvas）的 Javascript 類庫，它提供了許多方法用于簡化處理 HTML5 畫布（ canvas）元素的內(nèi)容，只要支持 canvas 和Javascript 的瀏覽器都可以使用它，包括 iPhone、 iPad 和 Android 等平臺。 中北大學 2020 屆畢業(yè)設計說明書 第 9 頁 共 31 頁 圖 31 功能結構圖 3． 3 系統(tǒng)數(shù)據(jù)結構設計 3． 3． 1 邏輯結構設計要點 本系統(tǒng)內(nèi)所使用的每個數(shù)據(jù)結構的名稱、標識符以及它們之中每個數(shù)據(jù)項、記錄、問卷和系的標識、定義、長度及它們之間的層次的或表格的相互關系。 3． 3． 2 基本物理結構設計要點 本系統(tǒng)內(nèi)所使用的每個數(shù)據(jù)結構中的每個數(shù)據(jù)項的存儲要求，訪問方法、存取單位、存取的物理關系（索引、設備、存儲區(qū)域）、設計考慮和保密條件。 3． 3． 3 數(shù)據(jù)結構 定義如下數(shù)據(jù)結構： 表 31 圓的數(shù)據(jù)結構 字段 類型 長度 描述 x float 11 橫坐標 y float 11 縱坐標 b int 11 半徑 c color 8 顏色 bool boolean 1 是否填充 circleId string 15 編號 中北大學 2020 屆畢業(yè)設計說明書 第 10 頁 共 31 頁 表 32 線段的數(shù)據(jù)結構 字段 類型 長度 描述 points array 端點的坐標集合 color color 8 顏色 lw float 11 線段的寬度 lineId string 8 編號 表 33 三次貝賽爾曲線的數(shù)據(jù)結構 字段 類型 長度 描述 points array 11 端點的坐標集合 extrapoints array 11 額外點的坐標集合 color color 8 顏色 lw float 11 寬度 fill boolean 1 是否填充 表 34 文本的數(shù)據(jù)結構 字段 類型 長度 描述 string array 11 文本內(nèi)容 x array 11 文本左下方的橫坐標 y color 8 文本左下方的縱坐標 maxWidth float 11 文本的最大寬度 color color 8 字體顏色 fill boolean 1 是否填充 中北大學 2020 屆畢業(yè)設計說明書 第 11 頁 共 31 頁 4 功能模塊劃分 根據(jù)要實現(xiàn)的目標和思路，主 要劃分了以下的模塊：障礙物擬合模塊、凸極值點計算模塊、水平切線劃分區(qū)域模塊、區(qū)域存儲模塊、無向圖構造模塊和路徑尋找模塊。每個模塊都有著承上啟下的作用，缺少了任何一個模塊，都將無法進行。 4． 1 障礙物擬合模塊 該模塊需要實現(xiàn)的功能主要有：獲取用戶點擊的點的坐標，計算出所需要畫三次貝賽爾曲線所需要的數(shù)據(jù)，調(diào)用畫圖函數(shù)擬合出障礙物，計算邊界經(jīng)過的點的坐標。 圖 41 障礙物擬合模塊 當用戶的鼠標處于畫圖區(qū)域中時，時刻檢測鼠標的位置，當用戶點擊下左鍵時馬上獲取當前的坐標值并存儲。用戶點擊一個障礙物完成之后， 就開始計算三次貝賽爾曲線需要的其他的點的坐標；計算完成之后調(diào)用畫圖函數(shù)完成一個障礙物的擬合。 同時在這個模塊中還要計算該障礙物經(jīng)過的所有點的坐標，方便之后的區(qū)域存儲模塊的執(zhí)行。 障礙物的繪制與障礙物經(jīng)過的點坐標使用的是不同的方法：障礙物的繪制調(diào)用的是 jCanvaScript 類庫中的方法，畫出來的三次貝賽爾曲線是平滑的；而障礙物經(jīng)過的點的坐標是使用三次貝賽爾曲線方程計算出來的，因此這些點是不連續(xù)的，相鄰兩點之間的距離也是不確定的。 4． 2 凸極值點計算模塊 在本系統(tǒng)中，凸極值點的含義是：邊界上的點相對于障礙 物的內(nèi)部來說更偏中北大學 2020 屆畢業(yè)設計說明書 第 12 頁 共 31 頁 向于外界。而且本系統(tǒng)僅僅使用水平方向上的凸極值點。 對于某個障礙物的邊界點，我們可以根據(jù)該點與相鄰兩點的 y 值進行比較，能夠確認該點是不是極值點，但是目前還不能確認該點是否是凸極值點，因為某些極值點是向障礙物內(nèi)部凹陷的 。 在計算極值點時要確認該極值點是向上凸的還是向下凸的，若該極值點是向上凸的則向下做射線，否則向上做射線；然后計算該射線與障礙物邊界交點的個數(shù)，若交點個數(shù)是奇數(shù)則該極值點是凸極值點，否則不是。 圖 42 凸極值點計算模塊 4． 3 水平切線劃分區(qū)域模塊 該模塊的主要功能是將 整個地圖劃分出幾個區(qū)域，對每個區(qū)域和區(qū)域之間進行權值的計算，然后可以尋找出最優(yōu)的路徑。 在凸極值點計算模塊已經(jīng)計算出所有障礙物的凸極值點，便可以過凸極值點做水平切線劃分區(qū)域了。這個模塊的難點是如何計