如何检查点是否属于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; 
} 

一些捕获：

可能是一个很长的帖子，但我已经试过要清楚。