1樓：Xi Yang
隨便想了一下，想出來這樣乙個思路。得到的應當不是最優解，但是是乙個實用的解：
將凹多邊形劃分為若干個凸多邊形的組合，記錄它們的連線方式。這一步甚至可以離線做、手工做。
給定兩點之後，尋找它們所在的凸多邊形。如果不是在同乙個上面，就尋找凸多邊形的連線路徑。
首先生成一條經過多邊形相鄰接邊的中點的折線。
想辦法優化這條折線，比如讓它「勒」到邊上，使它變短。
2樓：Yharnam
曲線從A 點出發，在曲線上每點的切線與 AB 所在直線存在夾角 ， 在該點處行進距離為 , 到達B 點，所產生的 「損失」
.....可能等於某個積分
在 處， 可以把座標系逆時針旋轉，計算此處增量為此處旋轉過後S的導數，為相應自變數增量
假設在受約束情況下 A,B 兩點之間最短曲線存在且唯一設為則：方案：
①：連AB，測試是否穿越了某凹點左右兩側線段，如果沒有，則直接相連就是最短。反之，找出所有這些凹點，直接連向最近的凹點。如果連線過程中穿越了其他凹點，則①
②：將①中找到的凹點置為A， 重複方案
3樓：Shinoi
猜想，中間拐點只可能是凹點(就是那個大於180度角的那個點，我不清楚是不是這麼叫)
那麼單獨取出凹點和所需要求的兩個端點，兩點之間有直線能夠連線距離就為直線距離，否則為∞，做個最短路。
4樓：峰頂飛龍
直接連線，出現相交、不相交，不相交沒什麼好說的
隨手在紙上畫了幾個圖（我以前寫過類似的，最好先把可能情況都列出來，然後先解決最普通的在處理特殊的），演算法寫起來估計會很複雜，需要一步步迭代解決
簡單地提一下思路，相交就至少有以下問題需要解決了
1、相交點與連線終點（這個可能又涉及到取哪個點做終點）之間全部都是凹點
2、相交點與連線終點之間有凹點和凸點
3、從第乙個相交點到終點之間的點開始找折線點（怎麼找呢，如果是凸點，基本上可以直接略過。凹點的話要比較斜率，起始點到凹點的斜率k1與起始點到終點的斜率k2，我以順時針找為例，k1 4、上面的幾點涉及到凹點的判斷、還有可能需要判斷點的下標值、多邊形是順時針還是逆時針等基本的演算法（我這兒以前封裝過部分現成的函式，如果有需要可以發出來參考） 5樓：大丶便一籮筐 有乙個思路，但不一定是最高效的： 1. 兩兩連線凹多邊形所有的頂點 2. 剔除上一步中所有不在凹多邊形內部的線段（具體演算法可以直接搜尋引擎裡找，很多。。。） 3. 問題轉化為最小路徑問題，可以上Dijkstra演算法了。。。 理由：兩點之間線段最短。。。因為是凹多邊形，有可能不能走直線，那就只能走最接近直線的路線了。。。 6樓： b) AB不在多邊形的外面 具體做法： 1. 當找折線操作比較頻繁時，可以把多邊形每對點之間滿足條件2的點對都找出來快取，這樣搜尋會快些。 2. 當多邊形邊非常多，起始點目標點又往往比較近的時候，可以邊搜邊擴充套件。以前寫過乙個簡單的尋路https:// 胖圓不多於瘦圓。瘦圓數目可以數出來。感謝 金玥蘇指正完善。對平面上任意乙個點集，都存在叫做 Delaunay Triangulation 1 的三角化，把點連成三角網格，使得每個三角形的外接圓都不包含任何其他點。如果任意四點不共圓，那麼這樣的三角化是唯一的。歸納可證，這些三角形的外接圓就是所有的瘦圓... 走點心 隊 首先由它們的頭領 樹苗複製機上場，我把5棵樹苗放進它的肚子裡，只聽 轟隆隆 幾聲，5棵樹苗變成了5000棵樹苗，我開心極了黃河，把黃河的髒水排了出去，又把清水放進了黃河，哈哈！黃河變成了 清河 了！掃地機械人 只要用30秒的時間就能打掃完乙個城市，可是，人們每乙個表，這個表雖小，五臟俱全... 邱江坤 wrf.ecse.rpi.edu Research Short Notes pnpoly.htmlRandolph Franklin的演算法 intpnpoly int npol float xp float yp floatx,floaty returnc Sam Richard 之前做過...乙個凸多邊形，任意四頂點不共圓，對於過任意三個頂點的圓，如果其他頂點都在該圓內，稱之為胖圓，如果其他頂點都在該圓外，則稱為瘦圓。胖圓和瘦圓哪個多？
給定任意長度的四條邊圍成四邊形，如何快速求出最大面積以及擺放角度？
如何判斷點在哪個多邊形內？