ポイントが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); 
} 

これらの交点はどうやって取得できますか？私たちは、形状の各辺について、の交点が、与えられた点によって決定された水平線であるかどうかを調べるべきです。交差点は形状から遠く離れている可能性があることに注意してください。交差点を考慮するセグメントではありません。

クロスポイントを取得したら、セグメント。

I点 Cセグメント（点 によって定義と B）に属しているかどうかをチェックする簡単な方法は次のように距離チェックを実行していると思う

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)

しかし、この1つはあまりにも制限されて終わる可能性があるので、私は少し誤差を考慮するためにそれを適応してきました：

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; 
} 

いくつかのキャプチャ：

は長い記事かもしれないが、私が試しました明確にする。