computational-geometry

3熱度

2回答

我想找到一個快速算法來找到（近似的，如果需要的話）在二維空間中給定點的最近鄰居，其中點經常從數據集和新的點被添加。（與此相關的，也有這個問題的兩個變種是引起我的興趣：一個在哪些點可以被看作是補充和隨機取出，另一種所有的點都在不斷地運動）一些想法： KD樹提供了良好的性能，但只適用於靜態的點集 R * - 樹似乎提供良好的性能，適用於各種尺寸，但其設計的通用性（任意尺寸，一般內容幾何）表明可能性

0熱度

3回答

調整地形高度圖中的道路

假設我們有一張表示地形高程的高度圖，其形式爲每個像素指示高度的圖像。假設同一圖像上的另一圖層正被用於指示穿過地形的道路，因此亮像素表示道路上的點，暗像素指示道路偏離，中間像素表示沿着邊緣的位置的道路。這似乎是在這種情況下代表道路的一種自然方式，但我們也可以使用行進方塊將其轉換爲道路的多邊形輪廓。問題是：算法如何調整高度圖以保持道路左右水平。通過平均道路上每個點的高程來使道路完全水平很容易，但這不

1熱度

3回答

高效的方式來找到一個數組中的最小差異對

我想解決一個問題，需要我找到一個數組中的最小差異對。例如，如果陣列是 6,7,1,3,9 輸出是 (6,7) 具有1差是最小的。我能想出的最快解決方案是對數組進行排序並遍歷排序後的數組，以找到最小差異[O（nlogn）]。有沒有一種方法來優化或更好地解決O（n）或O（logn）？編輯：數組的所有元素都是不同的。

-1熱度

1回答

連接兩個三角形網格

我想問問你如何連接兩個三維網格。我附上一個截圖與兩個半球三角形和打開。如何將它們連接成無孔的單個網格（單個球體）。兩個網格的三角剖分應保持不變（無重新網格算法）。在此先感謝。 screenshot

0熱度

1回答

查找一組間隔的最大深度

給定一組間隔I，形式爲[a_i，b_i]的每個元素在O（n * logn）時間內找到最大深度的結束點b_i。將x的深度定義爲點「刺入」（或相交）的間隔數。如果兩個端點具有相同的深度，則返回較小的一個。嘗試：我不知道如何找到它的O（N * LOGN）的時間。我理解尋找一組間隔的插入集合的貪婪算法，但嚴格地用O（n * log n）時間找到一個終點似乎是非常不同的。我可以嘗試先排序間隔，然後蠻力

0熱度

2回答

如何離散線段

如何找出一條線段經過的網格單元？例如，線段可以作爲(8.3555 9.1654) -> (1.4123 5.6312)（以任意精度）給出。我要像頂部的第二圖像中看到，改造成一個基於網格的表示這樣的：我目前正在研究CGAL。它有包裝Snap Rounding哪種做我正在尋找的，但僅用於細分市場的起點和終點。

0熱度

1回答

凹面實現

我正在嘗試實現下面描述的算法http://repositorium.sdum.uminho.pt/bitstream/1822/6429/1/ConcaveHull_ACM_MYS.pdf 我正在使用以下類庫。 Loyc庫來自http://core.loyc.net/ using System; using System.Collections.Generic; using System.Li

0熱度

2回答

擁有最終的泰森多邊形，是否有可能找到最初的一組點？

我試圖找到一種方法來扭轉Voronoi算法。基本上，有一些連接的形狀，這主要是由三角形和正方形的，我試圖找到一套，使用的Voronoi算法將重新創建初始形狀點。

3熱度

3回答

將兩個凸的非相交多邊形合併爲一個

我需要將兩個凸的非交叉多邊形合併爲一個連接的凸多邊形，以最小化所產生的面積，如下圖所示：我正在尋找一個這樣做的算法。如果有人向我提供相應的python實現，我也將不勝感激。

3熱度

1回答

使用CGAL的Voronoi圖：僅提取邊緣點（凸包）

我想使用Voronoi圖提取邊緣點（點位於凸包的邊界邊緣上）。我知道一個無界單元格包含一個邊界站點點，但是如何使用迭代器訪問該信息？解決方案 VD vd; //initialise your voronoi diagram VD::Face_iterator it = vd.faces_begin(), beyond = vd.faces_end(); for (int f = 0; it