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

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:

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

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?

std::pair

2) Is the use of const correct?

const

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?

Catch2

3 Answers
3

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:

point

std::pair<int, int>

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, ...

std::pair<int, int>

std::map<int, int>

Using a concrete type prevents that kind of confusion.

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

polygon

std::vector<point>

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.

polygon

perdot

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.

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:

line

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

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.

n <= 2

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

false

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.

false

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.

convex_polygon

is_convex

true

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

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(lineconvex_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(lineconvex_polygon[i], convex_polygon[i + 1], p);

if(new_sense != sense)

return false;


return true;



p_inside

p_inside

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

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

std::count_if

<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.

points

polygon

std::vector<point>

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

points

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

typename = std::enable_if_t<...>

point

main

main

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

std::cerr

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.

convex_polygon

points

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.

1

EXIT_FAILURE

<cstdlib>

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

return 0;

EXIT_SUCCESS

Q & A

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.

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

const

const

perpendicular_dot_product

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.

perpendicular_dot_product

determine_side

constexpr

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

is_convex

directed_edge

line

vertex

vector

point

side

side::center

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

perdot()

The function can be declared with the constexpr keyword.

constexpr

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.

const

const

std::string

std::pair

const

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

ab_x

ab_y

ac_x

ac_y

const

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:

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

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.

g++

-Wall -Wextra -Wconversion -Wshadow

convex_polygon.size()

std::vector<std::pair<int, int> >::size_type

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.

std::size_t

i

std::size_t

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:

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

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

std::size_t

const

sense can be const because it is never modified.

sense

const

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.

new_sense

const

Therefore, is_inside() becomes:

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

count

std::size_t

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

p_inside()

std::size_t

main()

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

inside

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

std::vector

const

main()

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

size_t

std::size_t

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

main()

EXIT_FAILURE

<cstdlib>

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.

std::endl

n

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

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)
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...Exitingn";
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.

is_convex

i

size_t

is_convex

std::numeric_limits<std::size_t>::max() - 1

n == 0

n == 0

struct

std::pair

i < n - k

n

k

n

i + k < n

auto

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



reserve

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.