繪製二維座標系統的曲線軌跡

我在二維座標系統中有幾個有序點（小於10）。我有一個代理在系統中移動，並且我想要找到這些點之間的最短路徑，其順序爲。爲了背景，代理人可以有一個推力的位置，我的目標是繪製最快的路線，因爲代理人具有最大的推力和最大的角速度。經過一番研究，我意識到我可能在尋找曲線擬合算法，但我不知道底層函數，因爲這些點是隨機分佈在座標系統中的。請幫我找到解決這個問題的方法。我接受任何建議，我的首選編程語言是C++。繪製二維座標系統的曲線軌跡

來源

2016-02-28 TomTomCantNot

谷歌是你的朋友：C++/Boost有你可以使用的多項式擬合庫。在擬合時，點的隨機性並不重要。您對最小時間，最大推力和角速度的約束是更困難的問題。我建議你將問題分解成幾部分並以這種方式解決問題。放鬆一些約束條件，獲得解決方案，然後添加約束條件。當我聽到「miniumum時間」時，我通過圖表思考了Dijkstra的算法。也許你需要評估所有可能的圖表並選擇最小的圖表。 – duffymo

@duffymo謝謝，你能否詳細說明Boost中的多項式擬合？在裝修時我誠實地失去了;我的程序員朋友也提到了Djikstra，但我不確定如何將此算法與我的問題聯繫起來 – TomTomCantNot

@JensHöpken問題是：我的代理必須遵循點之間的確定順序 – TomTomCantNot

我敢肯定，有一個純粹的數學解決方案，如spacecraft trajectory optimization for example，但這裏是我會考慮如何從編程/退火的角度來處理它。

即使您需要連續路徑，也可以使用謹慎的步驟開始路徑搜索，並以足夠接近每個點的寬度作爲開始。

爲每個步驟分配一定的時間並在每個步驟改變施加的角向力和推力。
計算下一步開始時產生的角動量和位置。
通過隨機搜索選擇下一步的參數，或者遍歷每個參數以找到最接近下一個目標點（量化選擇的角度和推力開始）。重複步驟直到足夠接近下一個目標點。然後重複進入下一點。

一旦你有一個粗略的路徑，你可以通過減少步驟的時間/大小和目標點的容差來開始細化它（也許使用前一次運行的粗糙點作爲新運行的目標點）。

在每一步評估參數的適應性時，您可能想要考慮一旦達到目標點，您也可能想要在下一點的方向上有動量。如果考慮多條路徑並且適應度函數考慮最短總時間，則這應該是一個緊急屬性。

如果你使用std :: priority_queue和std :: map來跟蹤潛在路徑，C++可以幫助你。

來源

2016-02-28 18:42:26 wally

繪製二維座標系統的曲線軌跡

回答

相關問題