有沒有一種方法可以使用單個傳球排序點？

我在空間有一些2d點，我需要找到點[xmin, ymax]。我可以在2次使用x和y的情況下完成，但是我希望一次完成。有沒有一種方法可以使用單個傳球排序點？

有沒有一種方法可以將這些值合併爲一個浮點數，以便我可以通過單一排序找到正確的點？

我想到做x+y，但我不知道這是否可靠，很可能不是，從[5,2]，[2,5]，最後一個將具有更高的優先級。

任何想法？

2014-01-13 Joan Venge

您不應該對點列表進行排序以找到最大值和最小值，因爲這將花費大約O（n * log（n））時間。相反，遍歷列表一次，保持對您找到的最高和最低值的引用。這將花費O（n）時間。

min_x = myPoints[0].x; 
max_y = myPoints[0].y; 
for(Point p in myPoints){ 
    if (p.x < min_x){min_x = p.x;} 
    if (p.y > max_y){max_y = p.y;} 
}

編輯：從維基百科的格雷厄姆掃描文章：

在這個算法的第一步是要找到具有最低y座標點。如果最低的y座標存在於集合中的多個點中，則應該選擇候選者中具有最低x座標的點。

因此，單獨找到最小x和最大y是不恰當的，因爲您正在尋找的點可能不具備這兩個。我們可以修改上面的代碼，以使用這些新的標準。

candidate = myPoints[0]; 
for (Point p in myPoints){ 
    if (p.y < candidate.y or (p.y == candidate.y and px < candidate.x)){ 
     candidate = p; 
    } 
}

根據您對「最低」的定義，可能有必要將這些「少於」符號中的一些更改爲「大於」符號。在某些座標系統中，（0,0）位於圖形的左上角，並且屏幕上越低，則Y越大。在這種情況下，您應該使用if (p.y > candidate.y而不是

來源

2014-01-13 14:49:52 Kevin

由於這是一個很好的點，我沒有想到這一點。 –

其實我只是試過，但在算法中，我認爲我應該找到那些值的實際點，否則純粹是明智的價值觀點，這一點可能不存在。這是格雷厄姆掃描算法。 –

@JoanVenge你的意思是你需要根據字典順序的一些變體找到最小點？ – user3146587

如果您試圖根據字典順序的某種變體（甚至某些其他類型的2D點順序）找到最小點，那麼只需遍歷一組點一次，但使用自定義比較來查找/保持最小值。這是在C++的例子，min_element來自STL和僅僅是一個簡單的循環（http://www.cplusplus.com/reference/algorithm/min_element/）：

#include <algorithm> 
#include <iostream> 

using namespace std; 

struct Point { 
    int x, y; 
}; 

struct PointCompare { 
    bool operator()(const Point& p1, const Point& p2) const { 
     if (p1.x < p2.x) 
      return true; 

     if (p1.x == p2.x) 
      return p1.y > p2.y; // Your order: xmin then ymax? 
      //return p1.y < p2.y; // Standard lexicographic order 

     return false; 
    } 
}; 

int main() 
{ 
    //  + 3 
    // + 4 
    //  + 0 
    // + 2 
    //   + 1 
    const Point points[] = { 
     { 1, 1 }, // 0 
     { 2,-1 }, // 1 
     { 0, 0 }, // 2 
     { 1, 3 }, // 3 
     { 0, 2 }, // 4 
    }; 

    const Point* first = points; 
    const Point* last = points + sizeof(points)/sizeof(Point); 
    const Point* it = min_element(first, last, PointCompare()); 

    cout << it->x << ", " << it->y << endl; 
}

來源

2014-01-14 12:51:28 user3146587

它看起來像你想找到一個最大最小點 - 具有最大Y-點在x座標最小的點之間進行座標對吧？

如果是，則可以將所有點存儲在STL multimap中，將x座標映射到y座標。該地圖將自動排序，並且有一個機會，即具有最小x座標的點在該地圖中只有一個點。如果它不是一個點，那麼您可以掃描具有相同（最小）x座標的所有點以找到具有最大y座標的點。它仍然需要兩次傳球，但統計上的第二次傳球應該很短。

如果你真的想要一個單程的解決方案，那麼您可以將您的點存儲到STL 地圖，映射x座標爲設置y座標。它需要做更多的工作，但最後你會明白你的觀點 - 你將在地圖的開頭看到它的x座標，並且它的y座標將在該集的末尾，對應於這個x座標。

來源

2014-01-14 21:28:06 HEKTO

1.可排序按值：X +（MAX * Y）或y +（MAX * X）

其中MAX是足夠大的值MAX> = ABS（MAX（X）-min（x ）），或者MAX> = ABS（MAX（Y）-min（Y））

2.如果有足夠的存儲器，並且需要再用速度

則可以忽略排序和使用排序值作爲地址
x，y值s必須是移位到非負
的x，y的差異必須> = 1.0（理想= 1.0），這樣他們可被用作地址
有允許或需要排序
創建大後沒有重複的點夠陣列PNT [點]，並將它們設置爲未使用（例如，X = -1，Y = -1）

排序輸入點PNT0 []這樣

for (i=0i<points;i++) 
{ 
x=pnt0[i].x; 
y=pnt0[i].y; 
pnt[x+(MAX*y)]=pnt[0]; 
}

如果需要的話可以包pnt []數組刪除未使用的點，但是這可以被認爲是另一個通過
，但你能記住最小值，最大值地址和唯一差異週期

來源

2014-01-22 13:05:18 Spektre

有沒有一種方法可以使用單個傳球排序點？

回答

相關問題