禮品包裝算法共線點

所以我寫了基於尋找一組點的凸包的禮品包裝算法的例子下面的代碼：禮品包裝算法共線點

std::vector<sf::Vector2f> convexHull(const std::vector<sf::Vector2f>& _shape) 
{ 
    std::vector<sf::Vector2f> returnValue;  
    returnValue.push_back(leftmostPoint(_shape)); 
    for (std::vector<sf::Vector2f>::const_iterator it = _shape.begin(), end = _shape.end(); it != end; ++it) 
    { 
     if (elementIncludedInVector(*it, returnValue)) continue; 
     bool allPointWereToTheLeft = true; 
     for (std::vector<sf::Vector2f>::const_iterator it1 = _shape.begin(); it1 != end; ++it1) 
     { 
      if (*it1 == *it || elementIncludedInVector(*it1, returnValue)) continue; 
      if (pointPositionRelativeToLine(returnValue.back(), *it, *it1) > 0.0f) 
      { 
       allPointWereToTheLeft = false; 
       break; 
      } 
     } 
     if (allPointWereToTheLeft) 
     { 
      returnValue.push_back(*it); 
      it = _shape.begin(); 
     } 
    } 
    return returnValue; 
}

這是我決定的功能其中一個線路的側的第三點是：

float pointPositionRelativeToLine(const sf::Vector2f& A, const sf::Vector2f& B, const sf::Vector2f& C) 
{ 
    return (B.x - A.x)*(C.y - A.y) - (B.y - A.y)*(C.x - A.x); 
}

返回一個負數表示點是在一側上，正對其他，0表示這三個點是共線的。現在，問題：如何修改上述代碼，使其即使在_shape中存在共線點時也能正常工作？

來源

2015-08-31 Stefan Dimitrov

如果一些點共線，你必須選擇從他們的最遠點（最大距離當前點）

來源

2015-08-31 18:26:02 MBo

最遠的點不一定是所有其他點都在新形成的線的左側，導致錯誤。 –

離共線最遠！ – MBo

這條規則非常正確。實際上，你實現了一個詞典對比：首先在角度上（通過簽名區域），然後在關係的情況下在距離上。 –

這是有點棘手比你展示的代碼做正確。我只關注你的謂詞的穩定性，而不是你如何處理共線點。謂詞是你做幾何計算的地方 - pointPositionRelativeToLine。

你的代碼設計的很好，你只需要在謂詞中進行幾何計算。這是必須的，以使其健壯。唉，你的斷言不應該返回一個浮動，但是從一小一個結果：要麼LEFT，RIGHT或COLLINEAR：

enum RelPos { LEFT, RIGHT, COLLINEAR }; 

RelPos pointPositionRelativeToLine(const sf::Vector2f& A, const sf::Vector2f& B, const sf::Vector2f& C) 
{ 
    auto result = (B.x - A.x)*(C.y - A.y) - (B.y - A.y)*(C.x - A.x); 
    if (result < 0.0) return LEFT; 
    else if (result > 0.0) return RIGHT; 
    return COLLINEAR; 
}

然後，您可以弄清楚如何保證提供給任何三點，正確的答案是返回任何他們的排列。這是必要的，否則，你的算法不能保證工作。

一般有兩種方法：

使用您的謂語使用時，保證準確結果的正確的數據類型。
接受使用您正在使用的不精確數據類型，有一些輸入無法計算結果。具體而言，您可以讓謂詞提供第四個值INDETERMINATE，並在這種情況下返回它。

的第二個方法是很容易通過調用原有的謂詞輸入的所有排列來實現：

enum RelPos { LEFT, RIGHT, COLLINEAR, INDETERMINATE }; 
typedef sf::Vector2f Point_2; 

RelPos ppImpl(const Point_2 & A, const Point_2 & B, const Point_2 & C) 
{ 
    auto result = (B.x - A.x)*(C.y - A.y) - (B.y - A.y)*(C.x - A.x); 
    if (result < 0.0) return LEFT; 
    else if (result > 0.0) return RIGHT; 
    return COLLINEAR; 
} 

bool inverse(RelPos a, RelPos b) { 
    return a == LEFT && b == RIGHT || a == RIGHT && b == LEFT; 
} 

bool equal(RelPos a, RelPos b, RelPos c, RelPos d, RelPos e, RelPos f) { 
    return a==b && b==c && c==d && d==e && e==f; 
} 

RelPos pointPositionRelativeToLine(const Point_2 & A, const Point_2 & B, const Point_2 & C) { 
    auto abc = ppImpl(A, B, C); 
    auto bac = ppImpl(B, A, C); 
    auto acb = ppImpl(A, C, B); 
    auto cab = ppImpl(C, A, B); 
    auto bca = ppImpl(B, C, A); 
    auto cba = ppImpl(C, B, A); 
    if (abc == COLLINEAR) return equal(abc, bac, acb, cab, bca, cba) ? 
    COLLINEAR : INDETERMINATE; 
    if (!inverse(abc, bac) || !inverse(acb, cab) || !inverse(bca, cba)) 
    return INDETERMINATE; 
    if (abc != bca || abc != cab) 
    return INDETERMINATE; 
    return abc; 
}

可能有邏輯錯誤之上，讓我們希望我得到了它的權利。但這是這裏的一般方法。至少以上測試對於給定數據集必須通過才能使算法在數據集上工作。但是，如果這是一個充分的條件，我不會記得。

當然，算法必須終止時，從上游獲得INDETERMINATE結果：

const auto errVal = std::vector<sf::Vector2f>(); 
... 
auto rel = pointPositionRelativeToLine(returnValue.back(), *it, *it1); 
if (rel == INDETERMINATE) return errVal; 
if (rel == RIGHT) { 
    allPointWereToTheLeft = false; 
    break; 
}

來源

2015-08-31 19:04:54

您可以基於你的推理上的兩個點之間的「排除」關係（圍繞一個共同的中心），與如果A和B的相對位置證明B不能在凸包上，則A排除B的含義。

在圖上，綠色的點不包括藍色，而紅色不包含藍色。在兩個對齊的點中，離中心最遠的點排除了另一點。排除軌跡是開放的半平面和半線。

需要注意的是「排除」是及物動詞，共定義了排序。

來源

2015-09-02 08:33:29

禮品包裝算法共線點

回答

相關問題