通過四叉樹進行二進制搜索

Question

我有一個四叉樹，葉節點代表像素。有一種方法可以修剪四叉樹，另一種方法是計算在修剪樹時將留下的葉子數量。剪枝方法接受一個整數tolerance，它用作節點之間差異的限制來檢查是否剪枝。無論如何，我想寫一個函數，它只需要一個參數leavesLeft。這應該做的是計算必要的最小容差，以確保修剪後，樹中不會超過leavesLeft。提示是遞歸地使用二進制搜索來做到這一點。我的問題是我無法在二進制搜索和我需要編寫的這個函數之間建立連接。我不確定這將如何實施。我知道允許的最大容差是256 * 256 * 3 = 196,608，但除此之外，我不知道如何開始。任何人都可以引導我在正確的方向嗎？

Answer 1

你想尋找尼克的空間索引四叉樹和希爾伯特曲線。

Answer 2

1. 編寫一個方法，只是嘗試所有可能的容差值，並檢查是否會留下足夠的節點。
2. 編寫一個測試用例，看看它是否有效。
3. 不要執行步驟1.在所有可能的公差值中使用二分查找與步驟1相同，但速度更快。

如果你不知道如何實現二分搜索，你可以先嚐試一個簡單的整數數組。無論如何，如果您執行第1步，只需將數組留在陣列中（以容差作爲索引）。然後執行二進制搜索。要將其轉換爲步驟3，請注意您不需要整個陣列。只需用計算值的函數替換數組即可完成。

Answer 3

假設你插入的容差爲0.然後你會得到一個極端的答案，如零葉左或所有的葉左（不知道它是如何工作的，從你的問題）。假設你插入寬容= 196,608。你會在另一個極端得到答案。你知道你要找的答案是介於兩者之間的。

因此，您插入一個介於0和196,608之間的公差數：公差爲98,304。如果剩下的葉子數量太高，那麼您知道正確的容差在0到98,304之間;如果它太低，正確的容忍度介於98,304和196,608之間。 （或者也許高/低部分是相反的;我不確定你的問題。）

這是二分搜索。通過檢查中間的值，可以將可能值的範圍縮小一半。最終你將它縮小到正確的容差。當然，您需要查看二進制搜索才能正確實施。