c++ - 如何检查点是否属于 ConvexShape？

Question

我为我的平台游戏编写了 map 编辑器。我正在使用 SFML。 map 由多边形 - 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;
}

我认为检查点 C 是否属于线段(由点 A 和 B 定义)的最简单方法是距离检查，如:

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

一些捕获:

可能是一篇很长的文章，但我已经尽力表达清楚了。