polygon.H

Go to the documentation of this file.

/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
 
# ifndef POLYGON_H
# define POLYGON_H
 
# include <dlink.H>
# include <point.H>
# include <ah-errors.H>
# include <ah-dry.H>
# include <ahDry.H>
# include <ah-iterator.H>
# include <cmath>
# include <string>
# include <utility>
 
namespace Aleph
{
  using Aleph::Dlink;
 
  class Vertex : public Point, public Dlink
  {
  public:
    Vertex() = default;
 
    Vertex(const Point & point) : Point(point)
    { /* empty */
    }
 
    Vertex(const Vertex & vertex) : Point(vertex), Dlink()
    { /* empty */
    }
 
    Vertex &operator=(const Vertex & vertex)
    {
      if (this != &vertex)
        Point::operator=(vertex);
      return *this;
    }
 
    [[nodiscard]] Point to_point() const
    {
      return static_cast<const Point>(*this);
    }
 
    [[nodiscard]] static Vertex * dlink_to_vertex(Dlink *link)
    {
      return static_cast<Vertex *>(link);
    }
 
    [[nodiscard]] static const Vertex * dlink_to_vertex(const Dlink *link)
    {
      return static_cast<const Vertex *>(link);
    }
 
    [[nodiscard]] const Vertex &prev_vertex() const
    {
      assert(not this->is_empty());
 
      ah_domain_error_if(this->is_unitarian()) << "There is an only vertex";
 
      return *dlink_to_vertex(this->get_prev());
    }
 
    [[nodiscard]] const Vertex &next_vertex() const
    {
      assert(not this->is_empty());
 
      ah_domain_error_if(this->is_unitarian()) << "There is an only vertex";
 
      return *dlink_to_vertex(this->get_next());
    }
 
    // TODO: Implement next_segment() and prev_segment() methods
  };
 
 
  class Regular_Polygon;
 
  class Polygon : public Geom_Object,
                  public GenericTraverse<Polygon>,
                  public FunctionalMethods<Polygon, Point>,
                  public LocateFunctions<Polygon, Point>,
                  public StlAlephIterator<Polygon>
  {
    Dlink vertex_list_; 
    size_t num_vertex_; 
    bool is_closed_; 
 
    Point lowest_; 
    Point highest_; 
    Point leftmost_; 
    Point rightmost_; 
 
    void update_extreme_points(const Point & point)
    {
      if (num_vertex_ == 0)
        {
          leftmost_ = rightmost_ = lowest_ = highest_ = point;
          return;
        }
 
      if (point.get_x() < leftmost_.get_x())
        leftmost_ = point;
 
      if (point.get_x() > rightmost_.get_x())
        rightmost_ = point;
 
      if (point.get_y() < lowest_.get_y())
        lowest_ = point;
 
      if (point.get_y() > highest_.get_y())
        highest_ = point;
    }
 
    void delete_points()
    {
      while (not vertex_list_.is_empty())
        delete Vertex::dlink_to_vertex(vertex_list_.remove_next());
 
      num_vertex_ = 0;
      is_closed_ = false;
    }
 
    void copy_points(const Polygon & poly)
    {
      auto *list = const_cast<Dlink *>(&poly.vertex_list_);
 
      for (Dlink::Iterator it(list); it.has_curr(); it.next_ne())
        vertex_list_.append(new Vertex(*Vertex::dlink_to_vertex(it.get_curr())));
    }
 
    void copy_regular_polygon(const Regular_Polygon & poly);
 
  public:
    using Item_Type = Point;
 
    using Key_Type = Point;
 
    class Iterator
    {
      Dlink::Iterator dit_;
 
    public:
      Iterator() noexcept = default;
 
      Iterator(const Polygon & poly) noexcept
        : dit_(poly.vertex_list_) {}
 
      [[nodiscard]] bool has_curr() const noexcept { return dit_.has_curr(); }
 
      void next() { dit_.next(); }
 
      void next_ne() noexcept { dit_.next_ne(); }
 
      void prev() { dit_.prev(); }
 
      void prev_ne() noexcept { dit_.prev_ne(); }
 
      void reset_first() noexcept { dit_.reset_first(); }
 
      void end() noexcept { dit_.end(); }
 
      [[nodiscard]] const Point &get_curr() const
      {
        return *Vertex::dlink_to_vertex(dit_.get_curr());
      }
 
      [[nodiscard]] Dlink * get_pos() const noexcept
      {
        return dit_.get_curr_ne();
      }
 
      [[nodiscard]] bool operator==(const Iterator & o) const noexcept
      {
        return dit_ == o.dit_;
      }
 
      [[nodiscard]] bool operator!=(const Iterator & o) const noexcept
      {
        return dit_ != o.dit_;
      }
    };
 
    Polygon() : num_vertex_(0), is_closed_(false)
    { /* empty */
    }
 
    ~Polygon()
    {
      delete_points();
    }
 
    Polygon(const Polygon & poly)
      : Geom_Object(poly),
        num_vertex_(poly.num_vertex_), is_closed_(poly.is_closed_),
        lowest_(poly.lowest_), highest_(poly.highest_),
        leftmost_(poly.leftmost_), rightmost_(poly.rightmost_)
    {
      copy_points(poly);
    }
 
    Polygon(Polygon && poly) noexcept
      : Polygon()
    {
      vertex_list_.swap(poly.vertex_list_);
      std::swap(num_vertex_, poly.num_vertex_);
      std::swap(is_closed_, poly.is_closed_);
      std::swap(lowest_, poly.lowest_);
      std::swap(highest_, poly.highest_);
      std::swap(leftmost_, poly.leftmost_);
      std::swap(rightmost_, poly.rightmost_);
    }
 
    Polygon(const Regular_Polygon & poly)
      : num_vertex_(0), is_closed_(false)
    {
      copy_regular_polygon(poly);
    }
 
    Polygon &operator =(const Polygon & poly)
    {
      if (this == &poly)
        return *this;
 
      delete_points();
 
      num_vertex_ = poly.num_vertex_;
      is_closed_ = poly.is_closed_;
      lowest_ = poly.lowest_;
      highest_ = poly.highest_;
      leftmost_ = poly.leftmost_;
      rightmost_ = poly.rightmost_;
 
      copy_points(poly);
 
      return *this;
    }
 
    Polygon &operator =(Polygon && poly) noexcept
    {
      vertex_list_.swap(poly.vertex_list_);
      std::swap(num_vertex_, poly.num_vertex_);
      std::swap(is_closed_, poly.is_closed_);
      std::swap(lowest_, poly.lowest_);
      std::swap(highest_, poly.highest_);
      std::swap(leftmost_, poly.leftmost_);
      std::swap(rightmost_, poly.rightmost_);
 
      return *this;
    }
 
    Polygon &operator =(const Regular_Polygon & poly)
    {
      delete_points();
      copy_regular_polygon(poly);
 
      return *this;
    }
 
    [[nodiscard]] const Point &lowest_point() const { return lowest_; }
 
    [[nodiscard]] const Point &highest_point() const { return highest_; }
 
    [[nodiscard]] const Point &leftmost_point() const { return leftmost_; }
 
    [[nodiscard]] const Point &rightmost_point() const { return rightmost_; }
 
    [[nodiscard]] const bool &is_closed() const { return is_closed_; }
 
    [[nodiscard]] const size_t &size() const { return num_vertex_; }
 
    struct Vertex_Iterator : public Dlink::Iterator
    {
      Vertex_Iterator(const Polygon & poly) : Dlink::Iterator(poly.vertex_list_)
      {
        ah_domain_error_if(poly.vertex_list_.is_empty()) << "Polygon has not any vertex";
      }
 
      Vertex &get_current_vertex() const
      {
        return *Vertex::dlink_to_vertex(get_curr());
      }
    };
 
    class Segment_Iterator : public Dlink::Iterator
    {
      Polygon & poly_; 
 
    public:
      Segment_Iterator(const Polygon & poly)
        : Dlink::Iterator(poly.vertex_list_), poly_(const_cast<Polygon &>(poly))
      {
        ah_domain_error_if(poly_.vertex_list_.is_unitarian_or_empty())
        << "Polygon has less than two vertex";
      }
 
      [[nodiscard]] bool has_curr() const
      {
        if (this->is_in_last())
          return poly_.is_closed() ? true : false;
 
        return Dlink::Iterator::has_curr();
      }
 
      [[nodiscard]] Segment get_current_segment() const
      {
        ah_domain_error_if(not poly_.is_closed() and this->is_in_last())
        << "Segment iterator is in the last point and it is not closed";
 
        const Vertex *src = Vertex::dlink_to_vertex(this->get_curr());
 
        // Determine target: if at last vertex, wrap to first; otherwise, next
        const Vertex & tgt =
            this->is_in_last() ? poly_.get_first_vertex() : src->next_vertex();
 
        return {src->to_point(), tgt.to_point()};
      }
    };
 
    [[nodiscard]] bool vertex_belong_polygon(const Vertex & v) const
    {
      for (Vertex_Iterator it(*this); it.has_curr(); it.next_ne())
        if (&it.get_current_vertex() == &v)
          return true;
 
      return false;
    }
 
    [[nodiscard]] const Vertex &get_first_vertex() const
    {
      ah_domain_error_if(vertex_list_.is_empty()) << "Polygon has not any vertex";
 
      return *Vertex::dlink_to_vertex(vertex_list_.get_next());
    }
 
    [[nodiscard]] const Vertex &get_last_vertex() const
    {
      ah_domain_error_if(vertex_list_.is_empty()) << "Polygon has not any vertex";
 
      return *Vertex::dlink_to_vertex(vertex_list_.get_prev());
    }
 
    [[nodiscard]] const Vertex &get_next_vertex(const Vertex & v) const
    {
      // If v is the last vertex (next points to sentinel), wrap to the first vertex
      return v.get_next() == &vertex_list_ ?
               *Vertex::dlink_to_vertex(vertex_list_.get_next()) :
               v.next_vertex();
    }
 
    [[nodiscard]] const Vertex &get_prev_vertex(const Vertex & v) const
    {
      // If v is the first vertex (prev points to sentinel), wrap to last vertex
      return v.get_prev() == &vertex_list_ ?
               *Vertex::dlink_to_vertex(vertex_list_.get_prev()) :
               v.prev_vertex();
    }
 
    [[nodiscard]] Segment get_first_segment() const
    {
      ah_domain_error_if(vertex_list_.is_unitarian_or_empty())
      << "polygon has less than two vertex";
 
      const Vertex & first_vertex = get_first_vertex();
 
      return {first_vertex.to_point(), first_vertex.next_vertex().to_point()};
    }
 
    [[nodiscard]] Segment get_last_segment() const
    {
      ah_domain_error_if(vertex_list_.is_unitarian_or_empty())
      << "polygon has less than two vertex";
 
      const Vertex & last_vertex = get_last_vertex();
 
      return {last_vertex.prev_vertex().to_point(), last_vertex.to_point()};
    }
 
    [[nodiscard]] bool intersects_with(const Segment & sg) const
    {
      // Traverse all edges and check for intersection
      for (Segment_Iterator it(*this); it.has_curr(); it.next_ne())
        if (const Segment & curr_side = it.get_current_segment(); curr_side.intersects_with(sg))
          return true;
 
      return false;
    }
 
    void add_vertex(const Point & point)
    {
      ah_domain_error_if(is_closed_) << "Polygon is already closed";
 
      // Check if the new point is colinear with the last segment
      if (num_vertex_ > 1)
        if (const Segment last_sg = get_last_segment(); point.is_colinear_with(last_sg))
          {
            ah_domain_error_if(point.is_inside(last_sg))
              << "new vertex is inside of last polygon's segment";
 
            // Colinear point: replace the last vertex with this new one
            auto & last_vertex = const_cast<Vertex &>(get_last_vertex());
            Point old_point = last_vertex.to_point();  // Store old point before replacing
            Point & last_point = last_vertex;
            last_point = point;
 
            // Recalculate extremes if the old point was an extreme point
            bool was_extreme = (old_point == lowest_ || old_point == highest_ ||
                                old_point == leftmost_ || old_point == rightmost_);
 
            if (was_extreme)
            {
              // We need a full recalculation of extremes
              lowest_ = highest_ = leftmost_ = rightmost_ = get_first_vertex().to_point();
              
              for (Vertex_Iterator it(*this); it.has_curr(); it.next_ne())
              {
                const Point p = it.get_current_vertex().to_point();
                
                if (p.get_x() < leftmost_.get_x())
                  leftmost_ = p;
                if (p.get_x() > rightmost_.get_x())
                  rightmost_ = p;
                if (p.get_y() < lowest_.get_y())
                  lowest_ = p;
                if (p.get_y() > highest_.get_y())
                  highest_ = p;
              }
            }
            else
            {
              // Just check if the new point is an extreme
              update_extreme_points(point);
            }
 
            return;
          }
 
      // If we have at least 3 vertices, verify no self-intersection
      if (num_vertex_ >= 3)
        {
          // New edge that would be formed by adding this point
          const Segment new_side(get_last_vertex().to_point(), point);
 
          // Check for intersection with all edges except the last one
          // (which shares a vertex with the new edge)
          for (Segment_Iterator it(*this); true; it.next_ne())
            {
              const Segment curr_side = it.get_current_segment();
 
              if (curr_side == get_last_segment())
                break;
 
              ah_domain_error_if(curr_side.intersects_with(new_side)) << "new side intersects";
            }
        }
 
      // Insert new vertex
      vertex_list_.append(new Vertex(point));
      update_extreme_points(point);
      ++num_vertex_;
    }
 
    void add_vertex(const Geom_Number & x, const Geom_Number & y)
    {
      add_vertex(Point(x, y));
    }
 
    void append(const Point & point) { add_vertex(point); }
 
    Special_Ctors(Polygon, Point);
 
    void remove_vertex(const Vertex & v)
    {
      Vertex *victim = nullptr;
      for (Vertex_Iterator it(*this); it.has_curr(); it.next_ne())
        if (&it.get_current_vertex() == &v)
          {
            victim = &const_cast<Vertex &>(it.get_current_vertex());
            break;
          }
 
      ah_domain_error_if(victim == nullptr) << "Vertex does not belong to polygon";
 
      // Store point for later comparison with extremes
      // cppcheck-suppress nullPointer
      const Point victim_point = victim->to_point();
 
      // Delete the vertex
      // cppcheck-suppress nullPointer
      victim->del();
      --num_vertex_;
      delete victim;
 
      // Recalculate extremes if needed
      if (victim_point == lowest_ || victim_point == highest_ ||
          victim_point == leftmost_ || victim_point == rightmost_)
        {
          if (num_vertex_ == 0)
            // No vertices left, reset extremes
            lowest_ = highest_ = leftmost_ = rightmost_ = Point();
          else
            {
              // Recalculate extremes from remaining vertices
              const Point first_point = get_first_vertex().to_point();
              lowest_ = highest_ = leftmost_ = rightmost_ = first_point;
 
              for (Vertex_Iterator it(*this); it.has_curr(); it.next_ne())
                {
                  const Point point = it.get_current_vertex().to_point();
                  if (point.get_x() < leftmost_.get_x())
                    leftmost_ = point;
                  if (point.get_x() > rightmost_.get_x())
                    rightmost_ = point;
                  if (point.get_y() < lowest_.get_y())
                    lowest_ = point;
                  if (point.get_y() > highest_.get_y())
                    highest_ = point;
                }
            }
        }
 
      // Reset the closed state if the polygon now has fewer than 3 vertices
      if (is_closed_ && num_vertex_ < 3)
        is_closed_ = false;
    }
 
    void close()
    {
      ah_domain_error_if(is_closed_) << "Polygon is already closed";
      ah_domain_error_if(num_vertex_ < 3)
        << "Polygon needs at least 3 vertices to close (has " << num_vertex_ << ")";
 
      if (num_vertex_ >= 4)
        {
          // Check for intersection with all edges except the first
          // and last (which share endpoints with the closing edge)
          const Segment last_side(get_first_vertex().to_point(), get_last_vertex().to_point());
 
          Segment_Iterator it(*this);
 
          for (it.next(); true; it.next_ne())
            {
              const Segment curr_side = it.get_current_segment();
 
              if (curr_side == get_last_segment())
                break;
 
              ah_domain_error_if(curr_side.intersects_with(last_side))
                << "closing causes an intersection";
            }
        }
 
      is_closed_ = true;
    }
 
    enum class PointLocation
    {
      Outside,
      Boundary,
      Inside
    };
 
    [[nodiscard]] PointLocation locate_point(const Point & p) const
    {
      ah_domain_error_if(not is_closed_) << "Polygon is not closed";
 
      int winding = 0;
 
      for (Segment_Iterator it(*this); it.has_curr(); it.next_ne())
        {
          const Segment edge = it.get_current_segment();
          const Point & a = edge.get_src_point();
          const Point & b = edge.get_tgt_point();
 
          if (on_segment(edge, p))
            return PointLocation::Boundary;
 
          if (a.get_y() <= p.get_y())
            {
              if (b.get_y() > p.get_y() and
                  orientation(a, b, p) == Orientation::CCW)
                ++winding;
            }
          else
            {
              if (b.get_y() <= p.get_y() and
                  orientation(a, b, p) == Orientation::CW)
                --winding;
            }
        }
 
      return winding == 0 ? PointLocation::Outside : PointLocation::Inside;
    }
 
    [[nodiscard]] bool contains(const Point & p) const
    {
      return locate_point(p) != PointLocation::Outside;
    }
 
    [[deprecated("Use contains() instead")]]
    [[nodiscard]] bool contains_to(const Point & p) const { return contains(p); }
 
    [[nodiscard]] Geom_Number signed_area() const
    {
      ah_domain_error_if(num_vertex_ < 3) << "Polygon must have at least 3 vertices";
 
      Geom_Number sum = 0;
      for (Segment_Iterator it(*this); it.has_curr(); it.next_ne())
        {
          const Segment seg = it.get_current_segment();
          const Point & a = seg.get_src_point();
          const Point & b = seg.get_tgt_point();
          sum += a.get_x() * b.get_y() - a.get_y() * b.get_x();
        }
      return sum / 2;
    }
 
    [[nodiscard]] Geom_Number area() const
    {
      Geom_Number a = signed_area();
      return a < 0 ? Geom_Number(-a) : a;
    }
 
    [[nodiscard]] Geom_Number perimeter() const
    {
      ah_domain_error_if(num_vertex_ < 2) << "Polygon must have at least 2 vertices";
 
      Geom_Number sum = 0;
      for (Segment_Iterator it(*this); it.has_curr(); it.next_ne())
        sum += it.get_current_segment().length();
      return sum;
    }
 
    [[nodiscard]] Point centroid() const
    {
      ah_domain_error_if(num_vertex_ < 3) << "Polygon must have at least 3 vertices";
 
      Geom_Number cx = 0, cy = 0, a6 = 0;
      for (Segment_Iterator it(*this); it.has_curr(); it.next_ne())
        {
          const Segment seg = it.get_current_segment();
          const Point & p = seg.get_src_point();
          const Point & q = seg.get_tgt_point();
          const Geom_Number cross = p.get_x() * q.get_y() - q.get_x() * p.get_y();
          cx += (p.get_x() + q.get_x()) * cross;
          cy += (p.get_y() + q.get_y()) * cross;
          a6 += cross;
        }
 
      ah_domain_error_if(a6 == 0) << "Polygon has zero area";
      return {cx / (3 * a6), cy / (3 * a6)};
    }
 
    [[nodiscard]] bool is_convex() const
    {
      ah_domain_error_if(num_vertex_ < 3) << "Polygon must have at least 3 vertices";
 
      // Check turn direction at each vertex using segment iterator
      int sign = 0;
      Segment_Iterator it(*this);
      Segment prev_seg = it.get_current_segment();
      it.next_ne();
 
      while (it.has_curr())
        {
          const Segment curr_seg = it.get_current_segment();
          // Turn at the shared vertex (prev_seg.tgt == curr_seg.src)
          const Geom_Number turn = area_of_parallelogram(
              prev_seg.get_src_point(), prev_seg.get_tgt_point(),
              curr_seg.get_tgt_point());
 
          if (turn != 0)
            {
              const int curr_sign = turn > 0 ? 1 : -1;
              if (sign == 0)
                sign = curr_sign;
              else if (sign != curr_sign)
                return false;
            }
 
          prev_seg = curr_seg;
          it.next_ne();
        }
 
      // Check the wrap-around turn (last vertex to first)
      const Segment first_seg = Segment_Iterator(*this).get_current_segment();
      const Geom_Number turn = area_of_parallelogram(
          prev_seg.get_src_point(), prev_seg.get_tgt_point(),
          first_seg.get_tgt_point());
 
      if (turn != 0)
          if (const int curr_sign = turn > 0 ? 1 : -1; sign != 0 and sign != curr_sign)
            return false;
 
      return true;
    }
 
    Polygon(const Triangle & tr)
      : num_vertex_(0), is_closed_(false)
    {
      add_vertex(tr.get_p1());
      add_vertex(tr.get_p2());
      add_vertex(tr.get_p3());
 
      close();
    }
  };
 
 
  class Regular_Polygon : public Geom_Object
  {
    Point center_; 
    double side_size_; 
    size_t num_vertex_; 
    double angle_; 
    double r_; 
    double beta_; 
 
  public:
    Regular_Polygon()
      : center_(0, 0), side_size_(0), num_vertex_(0), angle_(0), r_(0), beta_(0)
    { /* empty */
    }
 
    Regular_Polygon(Point c,
                    const double & side_sz,
                    const size_t & n,
                    const double & ang = 0)
      : center_(std::move(c)), side_size_(side_sz), num_vertex_(n), angle_(ang),
        r_(0), beta_(0)
    {
      ah_domain_error_if(n < 3) << "Regular polygon must have at least 3 sides";
      ah_domain_error_if(not std::isfinite(side_sz) or side_sz <= 0)
        << "Regular polygon side length must be positive and finite";
      ah_domain_error_if(not std::isfinite(ang))
        << "Regular polygon angle must be finite";
 
      beta_ = 2 * PI / static_cast<double>(n);
 
      // Calculate radius using law of sines with angles between vertices
      // and the angle between radius and side
      const double alpha = (PI - beta_) / 2; // angle between radius and side
      r_ = side_size_ * sin(alpha) / sin(beta_);
      ah_domain_error_if(not std::isfinite(r_) or r_ <= 0)
        << "Regular polygon circumradius is not representable";
    }
 
    [[nodiscard]] const double &get_side_size() const { return side_size_; }
 
    [[nodiscard]] const Point &get_center() const { return center_; }
 
    [[nodiscard]] const size_t &size() const { return num_vertex_; }
 
    [[nodiscard]] const double &radius() const { return r_; }
 
    [[nodiscard]] bool is_closed() const noexcept { return num_vertex_ >= 3; }
 
    [[nodiscard]] Point get_vertex(const size_t & i) const
    {
      ah_out_of_range_error_if(i >= num_vertex_)
        << "vertex " << i << " is greater than " << num_vertex_;
 
      // The first segment is the negative vertical from center
      // Initial point is the target of this segment with origin at center
      Segment sg(center_, center_ - Point(0, r_));
 
      sg.rotate(i * beta_ + angle_);
 
      return sg.get_tgt_point();
    }
 
    [[nodiscard]] Point get_first_vertex() const { return get_vertex(0); }
 
    [[nodiscard]] Point get_last_vertex() const { return get_vertex(num_vertex_ - 1); }
 
    [[nodiscard]] Segment get_first_segment() const
    {
      return {get_vertex(0), get_vertex(1)};
    }
 
    [[nodiscard]] Segment get_last_segment() const
    {
      return {get_vertex(num_vertex_ - 1), get_vertex(0)};
    }
 
    class Vertex_Iterator
    {
      const Regular_Polygon & poly_; 
      size_t curr_; 
      Vertex vertex_; 
 
    public:
      Vertex_Iterator(const Regular_Polygon & poly)
        : poly_(poly), curr_(0)
      {
        // empty
      }
 
      [[nodiscard]] bool has_curr() const { return curr_ < poly_.size(); }
 
      Vertex &get_current_vertex()
      {
        ah_overflow_error_if(not has_curr()) << "Iterator has not current";
 
        vertex_ = poly_.get_vertex(curr_);
 
        return vertex_;
      }
 
      void next_ne() noexcept { ++curr_; }
 
      void next()
      {
        ah_overflow_error_if(not has_curr()) << "Iterator has not current";
        next_ne();
      }
 
      void prev()
      {
        --curr_;
 
        ah_underflow_error_if(not has_curr()) << "Iterator has not current";
      }
    };
 
    class Segment_Iterator
    {
      const Regular_Polygon & poly_; 
      size_t curr_; 
 
    public:
      Segment_Iterator(const Regular_Polygon & poly)
        : poly_(poly), curr_(0)
      {
        // empty
      }
 
      [[nodiscard]] bool has_curr() const { return curr_ < poly_.size(); }
 
      [[nodiscard]] Segment get_current_segment() const
      {
        ah_overflow_error_if(not has_curr()) << "Iterator has not current";
 
        return {poly_.get_vertex(curr_), poly_.get_vertex((curr_ + 1) % poly_.size())};
      }
 
      void next_ne() noexcept { ++curr_; }
 
      void next()
      {
        ah_overflow_error_if(not has_curr()) << "Iterator has not current";
        next_ne();
      }
 
      void prev()
      {
        --curr_;
 
        ah_underflow_error_if(not has_curr()) << "Iterator has not current";
      }
    };
 
    [[nodiscard]] Point lowest_point() const { return center_ + Point(0, -r_); }
 
    [[nodiscard]] Point highest_point() const { return center_ + Point(0, r_); }
 
    [[nodiscard]] Point leftmost_point() const { return center_ + Point(-r_, 0); }
 
    [[nodiscard]] Point rightmost_point() const { return center_ + Point(r_, 0); }
  };
 
  inline void Polygon::copy_regular_polygon(const Regular_Polygon & poly)
  {
    assert(num_vertex_ == 0 and not is_closed_);
 
    for (size_t i = 0; i < poly.size(); ++i)
      add_vertex(poly.get_vertex(i));
 
    close();
  }
 
  // ============================================================================
  // Stream output operators for polygon classes
  // ============================================================================
 
  inline std::ostream &operator<<(std::ostream & o, const Polygon & p)
  {
    o << "Polygon(n=" << p.size() << ", "
        << (p.is_closed() ? "closed" : "open") << ", [";
    size_t count = 0;
    for (Polygon::Vertex_Iterator it(p); it.has_curr(); it.next_ne())
      {
        if (count > 0) o << ", ";
        o << it.get_current_vertex();
        ++count;
      }
    o << "])";
    return o;
  }
 
  inline std::ostream &operator<<(std::ostream & o, const Regular_Polygon & p)
  {
    o << "Regular_Polygon(center=" << p.get_center()
        << ", n=" << p.size()
        << ", radius=" << p.radius() << ")";
    return o;
  }
} // namespace Aleph
 
#endif // POLYGON_H