Program to see how many points lie strictly inside a convex polygon

Question

The program takes in a set of coordinates that defines the polygon. It then takes in a set of points. The idea is to find out how many of these points lie strictly inside the convex polygon (not on the edge or outside). First the program checks if the first set of points form a convex polygon or not. If yes, the program proceeds. Then each point is checked to see if it is strictly inside the convex polygon. If yes, count variable is increased. Here is the code:

#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) Should std::pair be passed as reference? Is there an exact criteria to see if a given object is large enough to be passed as reference?

2) Is the use of const correct?

3) What other improvements can be made?

4) I am planning to test it extensively using Catch2 framework. I am learning this framework myself. What suggestions do you have to maintain professional test quality?

Answer 1

Data types

• Why not use a simple point struct instead of std::pair<int, int>? It doesn't have to do anything, just a simple one would suffice:

  struct point {
      int x = 0;
      int y = 0;
  };
  

  This would increase readability and generally might make the code more bug resistent. Remember, std::pair<int, int> can represent many different things: points, vectors, health + mana points, entry in a std::map<int, int> (which by itself can have many different meanings), exchange rate of apples for oranges, ...

  Using a concrete type prevents that kind of confusion.

• Similarly, one could make a type alias polygon for std::vector<point>, like

  using polygon = std::vector<point>;
  

  A more advanced implementation could instead take a polygon as a range of points (= a pair of iterators), or use its own polygon class.

perdot

• The name doesn't match what it actually does. Yes, the perpendicular dot product is used internally, but the returned value isn't the result of it. The returned value only indicates whether the point is left of, right of or on the line - and the function name should reflect that, e.g. something like determine_side.

• The return values seem kinda arbitrary. Why not use an enum instead, like

  enum class side {
      left,
      right,
      center
  };
  

• The order of the parameters seems kind of arbitrary and unintuitive. Why do the points of the "line" have to be passed as first and third parameter? With a simple help from the type system, this could be clarified a lot by introducing a small line helper struct:

  struct line {
      point from;
      point to;
  };
  

Putting all those fixes together (and refactoring the perpendicular dot product into its own helper function), we get:

int perpendicular_dot_product(point a, point b, point c) noexcept {
    const auto ab_x = b.x - a.x;
    const auto ab_y = b.y - a.y;
    const auto ac_x = c.x - a.x;
    const auto ac_y = c.y - a.y;

    return ab_x * ac_y - ab_y * ac_x;
}


side determine_side(line l, point p) noexcept {
    const auto per_dot = perpendicular_dot_product(l.from, p, l.to);

    if(per_dot < 0)
    {
        return side::right;
    }
    else if(per_dot > 0)
    {
        return side::left;
    }

    return side::center;
}

Much nicer to read and much clearer in its intent, right?

is_convex

• Bug: If n <= 2 then the code likely doesn't work as intended, and might even access out of bounds memory. Please add checks for those cases.

  Now the question becomes: What should happen in those cases? Always return false, or throw an exception?

  I think always returning false would be better in this case, since it is just a query whether the contained data set conforms to some criteria. YMMV.

• Also, there is another edge case if all points in convex_polygon are on a line. Currently, is_convex returns true for that case, but is this intended? I wouldn't assume so.

Other than that, it seems to be working fine. It would need some adjustments for the changes mentioned above, though, and could be slightly simplified.

bool is_convex(const polygon& convex_polygon) noexcept
{
    const auto n = convex_polygon.size();
    if(n <= 2) return false;

    auto sense = side::center;

    for(auto i = 0u; i < n; ++i)
    {
        auto new_sense = determine_side(line{convex_polygon[i], convex_polygon[(i + 2) % n]}, convex_polygon[(i + 1) % n]);

        if(sense == side::center)
        {
            sense = new_sense;
        }
        else if(new_sense != side::center && new_sense != sense)
        {
            return false;
        }
    }

    return sense != side::center;
}

is_inside

Not much to do here, other than adjusting for above changes and some slight simplification.

bool is_inside(const polygon& convex_polygon, const point p) noexcept
{
    const auto n = convex_polygon.size();

    const auto sense = determine_side(line{convex_polygon[n - 1], convex_polygon[0]}, p);
    if(sense == side::center)
    {
        return false;
    }

    for(auto i = 0u; i + 1 < n; ++i)
    {
        auto new_sense = determine_side(line{convex_polygon[i], convex_polygon[i + 1]}, p);

        if(new_sense != sense)
        {
            return false;
        }
    }
    return true;
}

p_inside

Again, the name is weird: Why not use count_points_inside?

Other than that, the logic seems fine. It could however easily be simplified using an algorithm provided by the standard library: std::count_if (inside header <algorithm>).

int count_points_inside(const polygon& convex_polygon, const std::vector<point>& points)
{
    return std::count_if(std::begin(points), std::end(points), [&](auto p) { return is_inside(convex_polygon, p); });
}

Note how I didn't replace the type of points with polygon and used a std::vector<point> instead, since (at least for the human reader) there is a semantic difference between a polygon and a set of points.

A better version would takes points as a range of points instead:

template<typename Iter, typename = std::enable_if_t<std::is_same_v<point, typename std::iterator_traits<Iter>::value_type>>
int count_points_inside(const polygon& convex_polygon, Iter first, Iter last)
{
    return std::count_if(first, last, [&](auto p) { return is_inside(convex_polygon, p); });
}

(The typename = std::enable_if_t<...> part is only there to verify that the passed iterators point to points. The code would work without that.)

main

• Errors should be printed to std::cerr instead of std::cout.

• Some better instructions for the user would be nice. Currently, the user only ever gets notified if something goes wrong and thus has no clue what actually is expected of him.

• The entering procedures of convex_polygon and points could be refactored out into a helper function, since the logic overlaps quite a lot.

• In the error case, a different return value should be used, like 1 (or EXIT_FAILURE from the <cstdlib> header, to be more descriptive) in order to indicate that the program didn't execute as planned.

• The final return 0; statement could be removed, as the compiler will autogenerate that one. (If it isn't removed, EXIT_SUCCESS could be returned instead as a more descriptive value).

Q & A

1. Generally, I try to pass everything but containers (including classes that contain containers as data members) and non-copyable types by value as default. I only switch to references if I either know that the type is very large, or performance measurements show that passing by reference is a performance benefit.

   If in doubt, measure.

2. const is used well for function parameters. However, local variables that aren't being changed can also benefit from being marked const (see snippets above, e.g. for perpendicular_dot_product).

3. See above. Other than that, some functions like perpendicular_dot_product or determine_side could be made constexpr, as esote mentions in his answer. This would allow the compiler to precalculate those calls at compile time if the values are known.

4. I'd suggest trying test-driven development (i.e. write test before writing the actual implementation). Other than that, know your edge cases, and test those specifically (that way, you're unlikely to get bugs like the ones in is_convex).

Answer 2

I'm unfamiliar with the algorithm, so I cannot speak for that.

perdot()

The function can be declared with the constexpr keyword.

When you are passing something by const, if it is not a fundamental type, you should pass it by const reference. There are other considerations to take into account, but that works with most types such as std::string, and std::pair. You're right that it matters more if the object is larger, and if there's no reason not to make it const reference, then I would go ahead.

As well: ab_x, ab_y; ac_x, ac_y can be const, because their value is never modified within their scope.

Note that, with your if-statement, in C++20 this can be done simply with the spaceship operator <=>. However, this hasn't been released yet.

Therefore, perdot() becomes:

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()

When compiling, it's generally advisable to enable flags such as (with g++) -Wall -Wextra -Wconversion -Wshadow. If you do so, you will notice that your compiler warns that convex_polygon.size() returns a value of type std::vector<std::pair<int, int> >::size_type, which you implicitly convert to int.

Instead, if you do not wish to type that long type, use std::size_t. Once this is done, we need to change i to std::size_t to avoid comparison of integer expressions of different signedness.

In C++ using preincrement is usually preferred in for loops where it has no impact on the function of the inner loop. With modern compilers, this has no performance difference, it's just a matter of style at this point.

Again, I can't comment on the algorithm, so I'll trust it's optimal.

Therefore, is_convex() becomes:

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()

Again, switch to use std::size_t, preincrement, and const references where appropriate.

sense can be const because it is never modified.

Inside of your for loop, there's no purpose in declaring the variable new_sense, and then assigning to it separately. Instead declare it as const and initialize it as such.

Therefore, is_inside() becomes:

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()

In your case, you are using the count variable in a strictly positive manner. I would suggest using std::size_t (unsigned), with the auxiliary benefit that signed overflow is undefined, while unsigned overflow is defined.

Once this is changed, p_inside() should be adapted to return std::size_t. This will require a small change in main().

Instead of declaring a variable inside, just move that expression into the if-statement.

When iterating over an std::vector using the enhanced for loop, you can use const references.

main()

Don't use size_t, use std::size_t.

If you're exiting main() because of an error, return EXIT_FAILURE from <cstdlib>, otherwise EXIT_SUCCESS.

Usually when printing, you don't need std::endl. You can use just \n. Doesn't matter in this case, but has performance impact when used very often.

When printing an error, use std::cerr instead of std::cout.

Final code

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

Hopefully this was helpful, your code looks good otherwise. Catch2 is a good testing framework. Because your code has many branches (ie is_convex has more than a couple branches inside the for loop), it may be harder to test, but shouldn't be impossible.

Answer 3

Inefficient data construction.

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

The two vectors are actually instantiated with k and n default constructed pairs, not that efficient if the type is expensive instead do.

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

Then we can also construct the pairs in place

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