程序来查看凸多边形内严格存在多少个点

Question

程序接受一组定义多边形的坐标。然后，它接受了一组点。这样做的目的是找出这些点中有多少严格地位于凸多边形内(而不是在边缘或外部)。首先，程序检查第一组点是否形成凸多边形。如果是的话，节目就会继续进行。然后对每个点进行检查，看看它是否严格地位于凸多边形内。如果是，则增加count变量。以下是代码：

#include <iostream>
#include <vector>

// Calculate perpendicular dot product
int perdot(const std::pair<int, int> a, const std::pair<int, int> b, const std::pair<int, int> c)
{
    int ab_x = b.first - a.first;
    int ab_y = b.second - a.second;
    int ac_x = c.first - a.first;
    int ac_y = c.second - a.second;
    int per_dot = ab_x * ac_y - ab_y * ac_x;
    if(per_dot < 0)
    {
        return -1;
    }
    else if(per_dot > 0)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

// Check if given set of points form a convex polygon
bool is_convex(const std::vector<std::pair<int, int>>& convex_polygon)
{
    int n = convex_polygon.size();
    int sense = perdot(convex_polygon[n - 1], convex_polygon[0], convex_polygon[1]);
    for(int i = 0; i < n - 1; i++)
    {
        int new_sense;
        if(i == (n - 2))
        {
            new_sense = perdot(convex_polygon[i], convex_polygon[i + 1], convex_polygon[0]);
        }
        else
        {
            new_sense = perdot(convex_polygon[i], convex_polygon[i + 1], convex_polygon[i + 2]);
        }
        if(sense == 0)
        {
            sense = new_sense;
        }
        if(new_sense == (-sense) && sense != 0)
        {
            return false;
        }
    }
    return true;
}

// Check if a point is STRICTLY inside the convex polygon
bool is_inside(const std::vector<std::pair<int, int>>& convex_polygon, const std::pair<int, int> point)
{
    int n = convex_polygon.size();
    int sense = perdot(convex_polygon[n - 1], point, convex_polygon[0]);
    if(sense == 0)
    {
        return false;
    }

    for(int i = 0; i < n - 1; i++)
    {
        int new_sense;
        new_sense = perdot(convex_polygon[i], point, convex_polygon[i + 1]);
        if(new_sense == (-sense) || new_sense == 0)
        {
            return false;
        }
    }
    return true;
}

// Count the number of points STRICTLY inside the convex polygon
int p_inside(const std::vector<std::pair<int, int>>& convex_polygon, const std::vector<std::pair<int, int>>& points)
{
    int count = 0;
    for(auto point : points)
    {
        bool inside = is_inside(convex_polygon, point);
        if(inside)
        {
            count++;
        }
    }
    return count;
}

// Main
int main()
{
    int k, n;
    std::cin >> k >> n;
    std::vector<std::pair<int, int>> convex_polygon(k);
    std::vector<std::pair<int, int>> points(n);
    for(size_t i = 0; i < convex_polygon.size(); i++)
    {
        int x, y;
        std::cin >> x >> y;
        convex_polygon[i] = {x, y};
    }
    bool convex = is_convex(convex_polygon);
    if(!convex)
    {
        std::cout << "Input not convex...Exiting" << std::endl;
        return 0;
    }

    for(size_t i = 0; i < points.size(); i++)
    {
        int x, y;
        std::cin >> x >> y;
        points[i] = {x, y};
    }

    int count = p_inside(convex_polygon, points);
    std::cout << "Points inside: " << count << std::endl;
    return 0;
}

( 1)应否以std::pair作为参考？是否有确切的标准来查看给定的对象是否足够大，可以作为引用传递？

2) const的使用正确吗？

3)还可以做哪些其他改进？

4)我计划使用Catch2框架对其进行广泛的测试。我自己正在学习这个框架。你对保持专业考试质量有什么建议？

Answer 1

我对算法不熟悉，所以我不能说明这一点。

perdot()

函数可以用constexpr关键字声明。

当您通过const传递某个东西时，如果它不是基本类型，则应该通过const引用传递它。还有其他需要考虑的事项，但这适用于大多数类型，如std::string和std::pair。如果对象更大，这是正确的，如果没有理由不让它引用const，那么我将继续。

还有：ab_x，ab_y；ac_x，ac_y可以是const，因为它们的值从未在它们的范围内被修改过。

请注意，使用if-语句，在C++20中，这可以简单地通过宇宙飞船操作符<=>来完成。然而，这还没有发布。

因此，perdot()变成：

constexpr int perdot(const std::pair<int, int> & a, const std::pair<int, int> & b, const std::pair<int, int> & c)
{
    const int ab_x = b.first - a.first;
    const int ab_y = b.second - a.second;
    const int ac_x = c.first - a.first;
    const int ac_y = c.second - a.second;
    const int per_dot = ab_x * ac_y - ab_y * ac_x;

    if(per_dot < 0)
    {
        return -1;
    }
    else if(per_dot > 0)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

is_convex()

在编译时，通常建议启用(使用g++) -Wall -Wextra -Wconversion -Wshadow之类的标志。如果这样做，您将注意到编译器警告convex_polygon.size()返回一个类型为std::vector<std::pair<int, int> >::size_type的值，您将该值隐式转换为int。

相反，如果不希望键入该长类型，请使用std::size_t。完成此操作后，我们需要将i更改为std::size_t，以避免比较不同符号的整数表达式。

在C++中，在不影响内部循环功能的for循环中，使用预增量通常是首选的。对于现代编译器来说，这没有性能上的差异，这只是一个风格的问题。

同样，我不能评论这个算法，所以我相信它是最优的。

因此，is_convex()变成：

bool is_convex(const std::vector<std::pair<int, int>> & convex_polygon)
{
    const std::size_t n = convex_polygon.size();

    // if n == 0, handle as error, otherwise unsigned value will wrap around in for loop

    int sense = perdot(convex_polygon[n - 1], convex_polygon[0], convex_polygon[1]);
    for(std::size_t i = 0; i < n - 1; ++i)
    {
        int new_sense;
        if(i == (n - 2))
        {
            new_sense = perdot(convex_polygon[i], convex_polygon[i + 1], convex_polygon[0]);
        }
        else
        {
            new_sense = perdot(convex_polygon[i], convex_polygon[i + 1], convex_polygon[i + 2]);
        }
        if(sense == 0)
        {
            sense = new_sense;
        }
        if(new_sense == (-sense) && sense != 0)
        {
            return false;
        }
    }
    return true;
}

is_inside()

同样，在适当的情况下切换到使用std::size_t、预增量和const引用。

sense可以是const，因为它从未被修改过。

在for循环中，声明变量new_sense，然后分别分配给它是没有意义的。相反，将其声明为const并按此方式初始化它。

因此，is_inside()变成：

bool is_inside(const std::vector<std::pair<int, int>> & convex_polygon, const std::pair<int, int> & point)
{
    const std::size_t n = convex_polygon.size();
    const int sense = perdot(convex_polygon[n - 1], point, convex_polygon[0]);
    if(sense == 0)
    {
        return false;
    }

    for(std::size_t i = 0; i < n - 1; ++i)
    {
        const int new_sense = perdot(convex_polygon[i], point, convex_polygon[i + 1]);
        if(new_sense == (-sense) || new_sense == 0)
        {
            return false;
        }
    }
    return true;
}

p_inside()

在您的示例中，您正以严格的正向方式使用count变量。我建议使用std::size_t (无符号)，其辅助好处是签名溢出未定义，而无符号溢出定义。

一旦改变了这一点，p_inside()就应该调整为返回std::size_t。这将需要对main()进行小的更改。

与其声明变量inside，不如将该表达式移动到if-语句中。

当使用增强的for循环迭代std::vector时，可以使用const引用。

main()

不要使用size_t，使用std::size_t。

如果由于错误而退出main()，则从<cstdlib>返回EXIT_FAILURE，否则返回EXIT_SUCCESS。

通常在打印时，您不需要std::endl。您可以只使用\n。在这种情况下并不重要，但是经常使用时会对性能产生影响。

打印错误时，请使用std::cerr而不是std::cout。

最终代码

#include <cstdlib>
#include <iostream>
#include <vector>

// Calculate perpendicular dot product
constexpr int perdot(const std::pair<int, int> & a, const std::pair<int, int> & b, const std::pair<int, int> & c)
{
    const int ab_x = b.first - a.first;
    const int ab_y = b.second - a.second;
    const int ac_x = c.first - a.first;
    const int ac_y = c.second - a.second;
    const int per_dot = ab_x * ac_y - ab_y * ac_x;

    if(per_dot < 0)
    {
        return -1;
    }
    else if(per_dot > 0)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

// Check if given set of points form a convex polygon
bool is_convex(const std::vector<std::pair<int, int>> & convex_polygon)
{
    const std::size_t n = convex_polygon.size();

    // if n == 0, handle as error, otherwise unsigned value will wrap around in for loop

    int sense = perdot(convex_polygon[n - 1], convex_polygon[0], convex_polygon[1]);
    for(std::size_t i = 0; i < n - 1; ++i)
    {
        int new_sense;
        if(i == (n - 2))
        {
            new_sense = perdot(convex_polygon[i], convex_polygon[i + 1], convex_polygon[0]);
        }
        else
        {
            new_sense = perdot(convex_polygon[i], convex_polygon[i + 1], convex_polygon[i + 2]);
        }
        if(sense == 0)
        {
            sense = new_sense;
        }
        if(new_sense == (-sense) && sense != 0)
        {
            return false;
        }
    }
    return true;
}

// Check if a point is STRICTLY inside the convex polygon
bool is_inside(const std::vector<std::pair<int, int>> & convex_polygon, const std::pair<int, int> & point)
{
    const std::size_t n = convex_polygon.size();
    const int sense = perdot(convex_polygon[n - 1], point, convex_polygon[0]);
    if(sense == 0)
    {
        return false;
    }

    for(std::size_t i = 0; i < n - 1; ++i)
    {
        const int new_sense = perdot(convex_polygon[i], point, convex_polygon[i + 1]);
        if(new_sense == (-sense) || new_sense == 0)
        {
            return false;
        }
    }
    return true;
}

// Count the number of points STRICTLY inside the convex polygon
std::size_t p_inside(const std::vector<std::pair<int, int>> & convex_polygon, const std::vector<std::pair<int, int>> & points)
{
    std::size_t count = 0;
    for(const auto & point : points)
    {
        if(is_inside(convex_polygon, point))
        {
            count++;
        }
    }
    return count;
}

// Main
int main()
{
    int k, n;
    std::cin >> k >> n;
    std::vector<std::pair<int, int>> convex_polygon(k);
    std::vector<std::pair<int, int>> points(n);

    for(std::size_t i = 0; i < convex_polygon.size(); ++i)
    {
        int x, y;
        std::cin >> x >> y;
        convex_polygon[i] = {x, y};
    }

    if(!is_convex(convex_polygon))
    {
        std::cerr << "Input not convex...Exiting\n";
        return EXIT_FAILURE;
    }

    for(std::size_t i = 0; i < points.size(); ++i)
    {
        int x, y;
        std::cin >> x >> y;
        points[i] = {x, y};
    }

    const std::size_t count = p_inside(convex_polygon, points);

    std::cout << "Points inside: " << count << '\n';

    return EXIT_SUCCESS;
}

希望这是有帮助的，否则您的代码看起来很好。Catch2是一个很好的测试框架。因为您的代码有许多分支(即is_convex在for循环中有多个分支)，所以测试起来可能比较困难，但不应该是不可能的。

Answer 2

低效的数据结构。

int main() {
    int k, n;
    std::cin >> k >> n;
    std::vector<std::pair<int, int>> convex_polygon(k); <-
    std::vector<std::pair<int, int>> points(n);         <-
    for(size_t i = 0; i < convex_polygon.size(); i++) {
        int x, y;
        std::cin >> x >> y;
        convex_polygon[i] = {x, y};
    }

这两个向量实际上是用k和n默认构造对实例化的，如果类型昂贵，则效率不高。

int main() {
    int k, n;
    std::cin >> k >> n;
    std::vector<std::pair<int, int>> convex_polygon;
    convex_polygon.reserve(k);
    std::vector<std::pair<int, int>> points;
    points.reserve(n);

然后我们也可以在适当的位置构造成对

    for(size_t i = 0; i < k; i++) {
        int x, y;
        std::cin >> x >> y;
        convex_polygon.emplace_back(x, y);
    }