如何檢查點是否屬於ConvexShape？

Question

我寫了地圖編輯器到我的平臺遊戲。我正在使用SFML。地圖由多邊形組成 - ConvexShapes。我需要點擊它們來添加ConvexShapes的選擇。我知道我可以使用cv.getLocalBounds()來獲得矩形，然後檢查，但我需要更精確的解決方案。如何檢查點擊點是否屬於任何形狀？

Answer 1

根據問題評論link，這就是我得到的。

使用有描述的算法，我們可以確定給定的點狀計數交叉點有多少，每邊

如果它們的數量奇裏面每邊，點屬於形狀。那麼容易：

bool contains(sf::ConvexShape shape, sf::Vector2f point){ 
    std::vector<sf::Vector2f> intersectPoints = getIntersectionPoints(shape, point); 
    int nodesAtLeft = 0; 
    int nodesAtRight = 0; 
    for (sf::Vector2f po : intersectPoints){ 
     if (po.x < point.x){ 
      nodesAtLeft++; 
     } 
     else if(po.x > point.x){ 
      nodesAtRight++; 
     } 
    } 
    return ((nodesAtLeft % 2) == 1) && ((nodesAtRight % 2) == 1); 
} 

那麼，我們如何獲得這些交點呢？我們應該檢查形狀的每一側，其中交叉點，水平線由我們給定的點確定。需要注意的是交叉點可能是遠離形狀，由於交叉點的計算考慮整行，不段

所以，一旦我們得到了交叉點，我們應該檢查它是否屬於細分市場。

std::vector<sf::Vector2f> getIntersectionPoints(sf::ConvexShape shape, sf::Vector2f point){ 
    std::vector<sf::Vector2f> intersectPoints; 
    sf::Vector2f p; 
    bool crossingLine; // This will be used to avoid duplicated points on special cases 

    if (shape.getPointCount() < 3){ 
     return intersectPoints; 
    } 

    sf::FloatRect bounds = shape.getLocalBounds(); 

    // To determine horizontal line, we use two points, one at leftmost side of the shape (in fact, its bound) and the other at rightmost side 
    Line pointLine, shapeLine; 
    pointLine.p1 = sf::Vector2f(bounds.left, point.y); 
    pointLine.p2 = sf::Vector2f(bounds.left + bounds.width, point.y); 

    unsigned int nPoints = shape.getPointCount(); 

    for (int i = 0; i < nPoints; ++i){ 
     try{ 
      shapeLine.p1 = shape.getPoint(i % nPoints);   // Last one will be nPoints-1 
      shapeLine.p2 = shape.getPoint((i + 1) % nPoints); // So this one must be 0 in order to check last side (returning to origin) 
      crossingLine = (shapeLine.p1.y >= point.y && shapeLine.p2.y <= point.y) || (shapeLine.p2.y >= point.y && shapeLine.p1.y <= point.y); 
      p = intersection(shapeLine, pointLine); 
      if (crossingLine && shapeLine.contains(p)) 
       intersectPoints.push_back(p); 
     } 
     catch (std::runtime_error e){ 

     } 
    } 

    return intersectPoints; 
} 

我覺得查詢的更簡單的方法，如果一個點Ç屬於鏈段（由點甲和乙定義）是通過執行一個距離檢查等：

distance(A,C) + distance(C,B) == distance(A,B)

但是，因爲這可能會結束太嚴格，我已經適應它考慮一點誤差：

abs((distance(A, C) + distance(C, B)) - distance(A, B)) < margin

我還沒有忘記，這是怎樣一個Line定義

struct Line{ 
    sf::Vector2f p1; 
    sf::Vector2f p2; 

    bool contains(sf::Vector2f point) const{ 
     float margin = 0.1; 
     return std::abs((distance(p1, point) + distance(point, p2)) - distance(p1, p2)) < margin; 
    } 
}; 

這樣，唯一的事情是現在兩個給定線之間計算的交叉點。真誠，我不打算解釋這個（主要是因爲我剛剛複製這個從wikipedia）

sf::Vector2f intersection(Line lineA, Line lineB){ 
    int x1 = lineA.p1.x; 
    int y1 = lineA.p1.y; 
    int x2 = lineA.p2.x; 
    int y2 = lineA.p2.y; 

    int x3 = lineB.p1.x; 
    int y3 = lineB.p1.y; 
    int x4 = lineB.p2.x; 
    int y4 = lineB.p2.y; 

    try{ 
     double retX = ((x1*y2 - y1*x2)*(x3 - x4) - (x1 - x2)*(x3*y4 - y3*x4))/((x1 - x2)*(y3 - y4) - (y1 - y2)*(x3 - x4)); 
     double retY = ((x1*y2 - y1*x2)*(y3 - y4) - (y1 - y2)*(x3*y4 - y3*x4))/((x1 - x2)*(y3 - y4) - (y1 - y2)*(x3 - x4)); 
     return sf::Vector2f(retX, retY); 
    } 
    catch (std::exception){ 
     throw new std::exception(""); 
    } 
} 

如果線是平行或同一直線上，無論是分母爲零，它會拋出一個DivideByZero例外，不是真的只是沒有交集的問題。

我也做了一個片段來測試這一點：

int main() 
{ 
    sf::RenderWindow v(sf::VideoMode(600,400), "SFML"); 
    sf::ConvexShape shape; 
    std::vector<sf::Vector2i> points; 
    std::vector<sf::CircleShape> intPoints; 

    shape.setPointCount(0); 
    shape.setOutlineColor(sf::Color::Blue); 
    shape.setFillColor(sf::Color::Black); 
    shape.setOutlineThickness(1); 

    while (v.isOpen()){ 
     sf::Event event; 
     while (v.pollEvent(event)){ 
      if (event.type == sf::Event::Closed) 
       v.close(); 
      else if (event.type == sf::Event::MouseButtonPressed){ 
       if (event.mouseButton.button == sf::Mouse::Button::Left){ 
        // Add a point to the shape 
        intPoints.clear(); 
        sf::Vector2i p = sf::Mouse::getPosition(v); 
        points.push_back(p); 
        shape.setPointCount(points.size()); 
        for (int i = 0; i < points.size(); ++i){ 
         shape.setPoint(i, sf::Vector2f(points[i])); 
        } 
       } 
       else if (event.mouseButton.button == sf::Mouse::Button::Right){ 
        // Delete shape 
        points.clear(); 
        intPoints.clear(); 
        shape.setPointCount(0); 
       } 
       else if (event.mouseButton.button == sf::Mouse::Button::Middle){ 
        // Set testing point 
        intPoints.clear(); 
        sf::Vector2i p = sf::Mouse::getPosition(v); 
        if (contains(shape, sf::Vector2f(p))){ 
         std::cout << "Point inside shape" << std::endl; 
        } 
        else{ 
         std::cout << "Point outside shape" << std::endl; 
        } 
        auto v = getIntersectionPoints(shape, sf::Vector2f(p)); 
        for (sf::Vector2f po : v){ 
         sf::CircleShape c(2); 
         c.setFillColor(sf::Color::Green); 
         c.setOrigin(1, 1); 
         c.setPosition(po); 
         intPoints.push_back(c); 
        } 
        // testing point added too, to be visualized 
        sf::CircleShape c(2); 
        c.setFillColor(sf::Color::Red); 
        c.setOrigin(1, 1); 
        c.setPosition(sf::Vector2f(p)); 
        intPoints.push_back(c); 

       } 
      } 
     } 
     v.clear(); 
     v.draw(shape); 
     for (sf::CircleShape c : intPoints){ 
      v.draw(c); 
     } 
     v.display(); 
    } 

    return 0; 
} 

一些捕獲：

可能是一個很長的帖子，但我已經試過要清楚。