The intersection of two polygons in C++

Question

I implemented the intersection of two (convex) polygons in C++. It finds the polygon in the intersection like in this image.

Looking for any and all feedback. I left the logic for line intersection and point containment out.

#include <algorithm>
#include <cmath>
#include <iostream>
#include <optional>
using std::atan2;
using std::move;
using std::optional;
using std::vector;
using std::sort;
struct Point {
 double x;
 double y;
};
struct LineSegment {
 Point u;
 Point v;
};
// Returns the intersection point of l1 and l2 if it exists, nullopt otherwise.
// Unimplemented.
optional<Point> lineIntersection(const LineSegment& l1, const LineSegment& l2);
class Polygon {
public:
 Polygon(const vector<Point>& points) : points_{points} {};
 Polygon(const vector<Point>&& points) : points_{move(points)} {};
 
 // Returns true if point is in Polygon, false otherwise.
 // Unimplemented.
 bool contains(const Point& point) const;
 
 static Polygon intersect(const Polygon& p1, const Polygon& p2) {
 vector<Point> points;
 for (size_t i = 0; i < p1.points_.size(); ++i) {
 // Add points of p1 contained in p2.
 if (p2.contains(p1.points_[i])) {
 points.emplace_back(p1.points_[i]);
 }
 for (size_t j = 0; j < p2.points_.size(); ++j) {
 // Add points of intersection.
 auto intersection = lineIntersection(
 LineSegment{p1.points_[i], p1.points_[(i+1) % p1.points_.size()]},
 LineSegment{p2.points_[j], p2.points_[(j+1) % p2.points_.size()]});
 if (intersection != nullopt) {
 points.emplace_back(move(intersection.value()));
 }
 }
 }
 
 // Add points of p2 contained in p1.
 for (size_t i = 0; i < p2.points_.size(); ++i) {
 if (p1.contains(p2.points_[i])) {
 points.emplace_back(p2.points_[i]);
 }
 }
 
 // Sort into counter-clockwise order.
 sort(points.begin(), points.end(), [](Point a, Point b){ return atan2(a.y, a.x) > atan2(b.y, b.x); });
 return Polygon{points};
 }
 
private:
 vector<Point> points_;
};

Answer 1

Avoid using in header files

It looks like the code you have written is in a header file, which is to be included in an actual application that needs to intersect polygons. If you include this file, it also means you pull in all the using declarations, which could result in unexpected behavior. It might be safe to move the using declarations into class Polygon, but I'd rather avoid doing it altogether.

You also forgot using std::nullopt.

The move constructor should take a non-const reference

Since you want to move things from an object, that object might have to be modified, so move constructors should take non-const references.

Consider adding operator&()

Polygon intersection shares a lot of similarities with bitwise AND operations. It makes sense to add an operator&() to your class, so you can write:

Polygon a{...}, b{...};
Polygon c = a & b;

Your sorting function is wrong

You can't sort polygons into counter-clockwise order the way you did. The angles you calculate are relative to coordinate (0, 0), but the polygons themselves can be anywhere. You have to calculate the angles relative to a point inside the intersection.

See this StackOverflow question for a possible algorithm.

Alternatively, since the points of the input polygons are already sorted, and the intersection of two convex polygons is just two pieces of each polygon concatenated, you should not need to sort at all.