polygon.hpp

Go to the documentation of this file.

 
#pragma once
 
#include <zlayout/geometry/point.hpp>
#include <zlayout/geometry/rectangle.hpp>
#include <vector>
#include <string>
#include <utility>
 
namespace zlayout {
namespace geometry {

class Polygon {
public:
    std::vector<Point> vertices; 

    Polygon() = default;

    explicit Polygon(const std::vector<Point>& vertices);

    Polygon(std::initializer_list<Point> vertices);

    Polygon(const Polygon& other) = default;

    Polygon(Polygon&& other) noexcept = default;

    Polygon& operator=(const Polygon& other) = default;

    Polygon& operator=(Polygon&& other) noexcept = default;

    bool operator==(const Polygon& other) const;

    bool operator!=(const Polygon& other) const;
 
    // Basic properties

    size_t vertex_count() const { return vertices.size(); }

    bool is_empty() const { return vertices.empty(); }

    bool is_valid() const { return vertices.size() >= 3; }

    std::vector<std::pair<Point, Point>> edges() const;

    double area() const;

    double signed_area() const;

    double perimeter() const;

    Point centroid() const;

    Rectangle bounding_box() const;
 
    // Geometric properties

    bool is_convex() const;

    bool is_clockwise() const;

    bool is_counterclockwise() const { return !is_clockwise(); }

    bool is_simple() const;
 
    // Point containment

    bool contains_point(const Point& point) const;

    bool point_on_boundary(const Point& point, double tolerance = Point::TOLERANCE) const;
 
    // Sharp angle detection (Interview Problem 1)

    std::vector<size_t> get_sharp_angles(double threshold_degrees = 30.0) const;

    double vertex_angle(size_t vertex_index) const;

    std::vector<double> all_vertex_angles() const;
 
    // Distance calculations (Interview Problem 2)

    double distance_to(const Polygon& other) const;

    double distance_to(const Point& point) const;

    double distance_to_line(const Point& line_start, const Point& line_end) const;

    Point closest_point_to(const Point& point) const;
 
    // Edge operations

    double min_edge_distance_to(const Polygon& other) const;

    std::vector<std::tuple<Point, Point, double>> find_narrow_regions(
        const Polygon& other, double threshold_distance) const;
 
    // Intersection detection (Interview Problem 3)

    bool intersects(const Polygon& other) const;

    std::vector<Point> intersection_points(const Polygon& other) const;

    bool has_self_intersections() const;
 
    // Transformations

    Polygon translate(const Point& offset) const;

    Polygon rotate(double angle) const;

    Polygon rotate_around(const Point& center, double angle) const;

    Polygon scale(double factor) const;

    Polygon scale(double x_factor, double y_factor) const;

    Polygon reverse() const;
 
    // Polygon operations

    Polygon simplify(double tolerance = Point::TOLERANCE) const;

    Polygon ensure_counterclockwise() const;

    Polygon ensure_clockwise() const;
 
    // Utility functions

    void add_vertex(const Point& vertex);

    void insert_vertex(size_t index, const Point& vertex);

    void remove_vertex(size_t index);

    void clear() { vertices.clear(); }

    std::string to_string() const;

    friend std::ostream& operator<<(std::ostream& os, const Polygon& polygon);
 
    // Static utility functions

    static Polygon regular_polygon(const Point& center, double radius, size_t vertex_count);

    static Polygon from_rectangle(const Rectangle& rect);
 
    // Static utility functions for geometry calculations
    
    static double segment_to_segment_distance(
        const Point& seg1_start, const Point& seg1_end,
        const Point& seg2_start, const Point& seg2_end);

    static Point line_segment_intersection(
        const Point& seg1_start, const Point& seg1_end,
        const Point& seg2_start, const Point& seg2_end,
        bool& intersects);

    static bool segments_intersect(
        const Point& seg1_start, const Point& seg1_end,
        const Point& seg2_start, const Point& seg2_end);
 
private:
};

struct PolygonHash {
    std::size_t operator()(const Polygon& polygon) const;
};
 
// Utility functions for line segment operations

bool line_intersection(const Point& line1_start, const Point& line1_end,
                      const Point& line2_start, const Point& line2_end,
                      Point& intersection);

bool segments_intersect(const Point& seg1_start, const Point& seg1_end,
                       const Point& seg2_start, const Point& seg2_end);

double angle_between_vectors(const Point& v1, const Point& v2);
 
} // namespace geometry
} // namespace zlayout