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 <string>
 
using namespace Aleph;
 
class Vertex : public Point, public Dlink
{
public:
  Vertex()
  { /* empty */
  }
 
  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]] 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
{
  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)
  {
    Dlink *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:
  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()
    {
      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";
 
      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 Segment(*src, tgt);
    }
  };
 
  [[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 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()
  {
    ah_domain_error_if(vertex_list.is_unitarian_or_empty())
      << "polygon has less than two vertex";
 
    const Vertex & first_vertex = get_first_vertex();
 
    return Segment(first_vertex, first_vertex.next_vertex());
  }
 
  [[nodiscard]] Segment get_last_segment()
  {
    ah_domain_error_if(vertex_list.is_unitarian_or_empty())
      << "polygon has less than two vertex";
 
    const Vertex & last_vertex = get_last_vertex();
 
    return Segment(last_vertex.prev_vertex(), last_vertex);
  }
 
  [[nodiscard]] bool intersects_with(const Segment & sg)
  {
    // Traverse all edges and check for intersection
    for (Segment_Iterator it(*this); it.has_curr(); it.next_ne())
      {
        const Segment & curr_side = it.get_current_segment();
        if (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)
      {
        Segment last_sg = get_last_segment();
        if (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
            Vertex & last_vertex = const_cast<Vertex &>(get_last_vertex());
            Point & last_point = last_vertex;
            last_point = point;
 
            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(), 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 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";
 
    // TODO: Handle colinearity cases
 
    victim->del();
    --num_vertex;
    delete victim;
  }
 
  void close()
  {
    ah_domain_error_if(__is_closed)
      << "Polygon is already closed";
 
    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(), get_last_vertex());
 
        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;
  }
 
  [[nodiscard]] bool contains_to(const Point & p)
  {
    ah_domain_error_if(not __is_closed)
      << "Polygon is not closed";
 
    Segment_Iterator it(*this);
 
    bool test = p.is_to_left_from(it.get_current_segment());
 
    it.next();
 
    for (/* nothing */ ; it.has_curr(); it.next_ne())
      if (p.is_to_left_from(it.get_current_segment()) != test)
        return false;
 
    return true;
  }
 
  Polygon(const Triangle & tr)
    : Geom_Object(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() : side_size(0), num_vertex(0)
  { /* empty */
  }
 
  Regular_Polygon(const Point & c,
                  const double & side_sz,
                  const size_t & n,
                  const double & ang = 0)
    : center(c), side_size(side_sz), num_vertex(n), angle(ang), beta(2 * PI / n)
  {
    ah_domain_error_if(n < 3)
      << "Polygon sides is less than 3";
 
    // 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);
  }
 
  [[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 { return true; }
 
  [[nodiscard]] const Point get_vertex(const size_t & i) const
  {
    ah_out_of_range_error_if(i >= num_vertex)
      << "vertex " << std::to_string(i) << " is greater than "
      << std::to_string(num_vertex);
 
    // 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]] const Point get_first_vertex() const { return get_vertex(0); }
 
  [[nodiscard]] const Point get_last_vertex() const { return get_vertex(num_vertex - 1); }
 
  [[nodiscard]] Segment get_first_segment() const
  {
    return Segment(get_vertex(0), get_vertex(1));
  }
 
  [[nodiscard]] Segment get_last_segment() const
  {
    return Segment(get_vertex(0), get_vertex(num_vertex - 1));
  }
 
  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]] const Segment get_current_segment() const
    {
      ah_overflow_error_if(not has_curr())
  << "Iterator has not current";
 
      return Segment(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();
}
 
#endif // POLYGON_H