visilibity.hpp

Go to the documentation of this file.

 
#ifndef VISILIBITY_H
#define VISILIBITY_H
 
// Uncomment these lines when compiling under
// Microsoft Visual Studio
/*
#include <limits>
#define NAN std::numeric_limits<double>::quiet_NaN()
#define INFINITY std::numeric_limits<double>::infinity()
#define M_PI 3.141592653589793238462643
#define and &&
#define or ||
*/
 
#include <cmath> //math functions in std namespace
#include <queue> //queue and priority_queue.
#include <set>   //priority queues with iteration,
#include <vector>
// integrated keys
#include <algorithm> //sorting, min, max, reverse
#include <array>
#include <cassert> //assertions
#include <cstdlib> //rand and srand
#include <cstring> //C-string manipulation
#include <ctime>   //Unix time
#include <fstream> //file I/O
#include <iostream>
#include <list>
#include <string> //string class
 
namespace VisiLibity {
 
// Fwd declaration of all classes and structs serves as index.
struct Bounding_Box;
class Point;
class Line_Segment;
class Angle;
class Ray;
class Polar_Point;
class Polyline;
class Polygon;
class Environment;
class Guards;
class Visibility_Polygon;
class Visibility_Graph;
 
const int FIOS_PRECISION = 10;
 
double uniform_random_sample(double lower_bound, double upper_bound);
 
struct Bounding_Box {
  double x_min, x_max, y_min, y_max;
};
 
class Point {
public:
  // Constructors
  Point() : x_(NAN), y_(NAN) {}
  Point(double x_temp, double y_temp) {
    x_ = x_temp;
    y_ = y_temp;
  }
  // Accessors
  double x() const { return x_; }
  double y() const { return y_; }
  Point projection_onto(const Line_Segment &line_segment_temp) const;
  Point projection_onto(const Ray &ray_temp) const;
  Point projection_onto(const Polyline &polyline_temp) const;
  Point projection_onto_vertices_of(const Polygon &polygon_temp) const;
  Point projection_onto_vertices_of(const Environment &enviroment_temp) const;
  Point projection_onto_boundary_of(const Polygon &polygon_temp) const;
  Point projection_onto_boundary_of(const Environment &enviroment_temp) const;
  bool on_boundary_of(const Polygon &polygon_temp, double epsilon = 0.0) const;
  bool on_boundary_of(const Environment &environment_temp,
                      double epsilon = 0.0) const;
  bool in(const Line_Segment &line_segment_temp, double epsilon = 0.0) const;
  bool in_relative_interior_of(const Line_Segment &line_segment_temp,
                               double epsilon = 0.0) const;
  bool in(const Polygon &polygon_temp, double epsilon = 0.0) const;
  bool in(const Environment &environment_temp, double epsilon = 0.0) const;
  bool is_endpoint_of(const Line_Segment &line_segment_temp,
                      double epsilon = 0.0) const;
  // Mutators
  void set_x(double x_temp) { x_ = x_temp; }
  void set_y(double y_temp) { y_ = y_temp; }
  void snap_to_vertices_of(const Polygon &polygon_temp, double epsilon = 0.0);
  void snap_to_vertices_of(const Environment &environment_temp,
                           double epsilon = 0.0);
  void snap_to_boundary_of(const Polygon &polygon_temp, double epsilon = 0.0);
  void snap_to_boundary_of(const Environment &environment_temp,
                           double epsilon = 0.0);
 
protected:
  double x_;
  double y_;
};
 
bool operator==(const Point &point1, const Point &point2);
bool operator!=(const Point &point1, const Point &point2);
 
bool operator<(const Point &point1, const Point &point2);
bool operator>(const Point &point1, const Point &point2);
bool operator>=(const Point &point1, const Point &point2);
bool operator<=(const Point &point1, const Point &point2);
 
Point operator+(const Point &point1, const Point &point2);
Point operator-(const Point &point1, const Point &point2);
 
Point operator*(const Point &point1, const Point &point2);
 
Point operator*(double scalar, const Point &point2);
Point operator*(const Point &point1, double scalar);
 
double cross(const Point &point1, const Point &point2);
 
double distance(const Point &point1, const Point &point2);
 
double distance(const Point &point_temp, const Line_Segment &line_segment_temp);
double distance(const Line_Segment &line_segment_temp, const Point &point_temp);
 
double distance(const Point &point_temp, const Ray &ray_temp);
double distance(const Ray &ray_temp, const Point &point_temp);
 
double distance(const Point &point_temp, const Polyline &polyline_temp);
double distance(const Polyline &polyline_temp, const Point &point_temp);
 
double boundary_distance(const Point &point_temp, const Polygon &polygon_temp);
double boundary_distance(const Polygon &polygon_temp, const Point &point_temp);
 
double boundary_distance(const Point &point_temp,
                         const Environment &environment_temp);
double boundary_distance(const Environment &environment_temp,
                         const Point &point_temp);
 
std::ostream &operator<<(std::ostream &outs, const Point &point_temp);
 
class Line_Segment {
public:
  // Constructors
  Line_Segment();
  Line_Segment(const Line_Segment &line_segment_temp);
  Line_Segment(const Point &point_temp);
  Line_Segment(const Point &first_point_temp, const Point &second_point_temp,
               double epsilon = 0);
  // Accessors
  Point first() const;
  Point second() const;
  unsigned size() const { return size_; }
  Point midpoint() const;
  double length() const;
  bool is_in_standard_form() const;
  // Mutators
  Line_Segment &operator=(const Line_Segment &line_segment_temp);
  void set_first(const Point &point_temp, double epsilon = 0.0);
  void set_second(const Point &point_temp, double epsilon = 0.0);
  void reverse();
  void enforce_standard_form();
  void clear();
  virtual ~Line_Segment();
 
protected:
  // Pointer to dynamic array of endpoints.
  Point *endpoints_;
  // See size() comments.
  unsigned size_;
};
 
bool operator==(const Line_Segment &line_segment1,
                const Line_Segment &line_segment2);
bool operator!=(const Line_Segment &line_segment1,
                const Line_Segment &line_segment2);
 
bool equivalent(Line_Segment line_segment1, Line_Segment line_segment2,
                double epsilon = 0);
 
double distance(const Line_Segment &line_segment1,
                const Line_Segment &line_segment2);
 
double boundary_distance(const Line_Segment &line_segment,
                         const Polygon &polygon);
 
double boundary_distance(const Polygon &polygon,
                         const Line_Segment &line_segment);
 
bool intersect(const Line_Segment &line_segment1,
               const Line_Segment &line_segment2, double epsilon = 0.0);
 
bool intersect_proper(const Line_Segment &line_segment1,
                      const Line_Segment &line_segment2, double epsilon = 0.0);
 
Line_Segment intersection(const Line_Segment &line_segment1,
                          const Line_Segment &line_segment2,
                          double epsilon = 0.0);
 
std::ostream &operator<<(std::ostream &outs,
                         const Line_Segment &line_segment_temp);
 
class Angle {
public:
  // Constructors
  Angle() : angle_radians_(NAN) {}
  Angle(double data_temp);
  Angle(double rise_temp, double run_temp);
  // Accessors
  double get() const { return angle_radians_; }
  // Mutators
  void set(double data_temp);
  void set_to_2pi() { angle_radians_ = 2 * M_PI; }
  void randomize();
 
private:
  double angle_radians_;
};
 
bool operator==(const Angle &angle1, const Angle &angle2);
bool operator!=(const Angle &angle1, const Angle &angle2);
 
bool operator>(const Angle &angle1, const Angle &angle2);
bool operator<(const Angle &angle1, const Angle &angle2);
bool operator>=(const Angle &angle1, const Angle &angle2);
bool operator<=(const Angle &angle1, const Angle &angle2);
 
Angle operator+(const Angle &angle1, const Angle &angle2);
Angle operator-(const Angle &angle1, const Angle &angle2);
 
double geodesic_distance(const Angle &angle1, const Angle &angle2);
 
double geodesic_direction(const Angle &angle1, const Angle &angle2);
 
std::ostream &operator<<(std::ostream &outs, const Angle &angle_temp);
 
class Polar_Point : public Point {
public:
  // Constructors
  Polar_Point() : Point(), range_(NAN), bearing_(NAN) {}
  Polar_Point(const Point &polar_origin_temp, const Point &point_temp,
              double epsilon = 0.0);
  // Accessors
  Point polar_origin() const { return polar_origin_; }
  double range() const { return range_; }
  Angle bearing() const { return bearing_; }
  // Mutators
  void set_polar_origin(const Point &polar_origin_temp);
  void set_x(double x_temp);
  void set_y(double y_temp);
  void set_range(double range_temp);
  void set_bearing(const Angle &bearing_temp);
  void set_bearing_to_2pi() { bearing_.set_to_2pi(); }
 
protected:
  // Origin of the polar coordinate system in world coordinates.
  Point polar_origin_;
  // Polar coordinates where radius always positive, and angle
  // measured ccw from the world coordinate system's x-axis.
  double range_;
  Angle bearing_;
};
 
bool operator==(const Polar_Point &polar_point1,
                const Polar_Point &polar_point2);
bool operator!=(const Polar_Point &polar_point1,
                const Polar_Point &polar_point2);
 
bool operator>(const Polar_Point &polar_point1,
               const Polar_Point &polar_point2);
bool operator<(const Polar_Point &polar_point1,
               const Polar_Point &polar_point2);
bool operator>=(const Polar_Point &polar_point1,
                const Polar_Point &polar_point2);
bool operator<=(const Polar_Point &polar_point1,
                const Polar_Point &polar_point2);
 
std::ostream &operator<<(std::ostream &outs,
                         const Polar_Point &polar_point_temp);
 
class Ray {
public:
  // Constructors
  Ray() {}
  Ray(Point base_point_temp, Angle bearing_temp)
      : base_point_(base_point_temp), bearing_(bearing_temp) {}
  Ray(Point base_point_temp, Point bearing_point);
  // Accessors
  Point base_point() const { return base_point_; }
  Angle bearing() const { return bearing_; }
  // Mutators
  void set_base_point(const Point &point_temp) { base_point_ = point_temp; }
  void set_bearing(const Angle &angle_temp) { bearing_ = angle_temp; }
 
private:
  Point base_point_;
  Angle bearing_;
};
 
bool operator==(const Ray &ray1, const Ray &ray2);
bool operator!=(const Ray &ray1, const Ray &ray2);
 
Line_Segment intersection(const Ray ray_temp,
                          const Line_Segment &line_segment_temp,
                          double epsilon = 0.0);
Line_Segment intersection(const Line_Segment &line_segment_temp,
                          const Ray &ray_temp, double epsilon = 0.0);
 
class Polyline {
public:
  friend class Point;
  // Constructors
  Polyline() {}
  Polyline(const std::vector<Point> &vertices_temp) {
    vertices_ = vertices_temp;
  }
  Polyline(const std::string &filename);
 
  // Accessors
  Point operator[](unsigned i) const { return vertices_[i]; }
  unsigned size() const { return vertices_.size(); }
  double length() const;
  double diameter() const;
  // a box which fits snugly around the Polyline
  Bounding_Box bbox() const;
  // Mutators
  Point &operator[](unsigned i) { return vertices_[i]; }
  void clear() { vertices_.clear(); }
  void push_back(const Point &point_temp) { vertices_.push_back(point_temp); }
  void pop_back() { vertices_.pop_back(); }
  void set_vertices(const std::vector<Point> &vertices_temp) {
    vertices_ = vertices_temp;
  }
  void eliminate_redundant_vertices(double epsilon = 0.0);
  // Reduce number of vertices in representation...
  // void smooth(double epsilon);
  void reverse();
  void append(const Polyline &polyline);
 
  bool operator==(const VisiLibity::Polyline &other) {
    return vertices_ == other.vertices_;
  }
 
private:
  std::vector<Point> vertices_;
};
 
// print Polyline
std::ostream &operator<<(std::ostream &outs, const Polyline &polyline_temp);
 
class Polygon {
public:
  friend class Point;
  // Constructors
  Polygon() {}
  Polygon(const std::string &filename);
  Polygon(const std::vector<Point> &vertices_temp);
  Polygon(const Point &point0, const Point &point1, const Point &point2);
  // Accessors
  const Point &operator[](unsigned i) const {
    return vertices_[i % vertices_.size()];
  }
  unsigned n() const { return vertices_.size(); }
  unsigned r() const;
  bool is_simple(double epsilon = 0.0) const;
  bool is_in_standard_form() const;
  double boundary_length() const;
  double area() const;
  Point centroid() const;
  double diameter() const;
  Bounding_Box bbox() const;
  // Returns a vector of n pts randomly situated in the polygon.
  std::vector<Point> random_points(const unsigned &count,
                                   double epsilon = 0.0) const;
  void write_to_file(const std::string &filename,
                     int fios_precision_temp = FIOS_PRECISION);
  // Mutators
  Point &operator[](unsigned i) { return vertices_[i % vertices_.size()]; }
  void set_vertices(const std::vector<Point> &vertices_temp) {
    vertices_ = vertices_temp;
  }
  void push_back(const Point &vertex_temp) { vertices_.push_back(vertex_temp); }
  void clear() { vertices_.clear(); }
  void enforce_standard_form();
  void eliminate_redundant_vertices(double epsilon = 0.0);
  void reverse();
 
protected:
  std::vector<Point> vertices_;
};
 
bool operator==(Polygon polygon1, Polygon polygon2);
bool operator!=(Polygon polygon1, Polygon polygon2);
bool equivalent(Polygon polygon1, Polygon polygon2, double epsilon = 0.0);
 
double boundary_distance(const Polygon &polygon1, const Polygon &polygon2);
 
// print Polygon
std::ostream &operator<<(std::ostream &outs, const Polygon &polygon_temp);
 
class Environment {
public:
  friend class Point;
  // Constructors
  Environment() {}
  Environment(const Polygon &polygon_temp) {
    outer_boundary_ = polygon_temp;
    update_flattened_index_key();
  }
  Environment(const std::vector<Polygon> &polygons);
  Environment(const std::string &filename);
  // Accessors
  const Polygon &operator[](unsigned i) const {
    if (i == 0) {
      return outer_boundary_;
    } else {
      return holes_[i - 1];
    }
  }
  const Point &operator()(unsigned k) const;
  unsigned h() const { return holes_.size(); }
  unsigned n() const;
  unsigned r() const;
  bool is_in_standard_form() const;
  bool is_valid(double epsilon = 0.0) const;
  double boundary_length() const;
  double area() const;
  double diameter() const { return outer_boundary_.diameter(); }
  Bounding_Box bbox() const { return outer_boundary_.bbox(); }
  std::vector<Point> random_points(const unsigned &count,
                                   double epsilon = 0.0) const;
  Polyline shortest_path(const Point &start, const Point &finish,
                         const Visibility_Graph &visibility_graph,
                         double epsilon = 0.0);
  Polyline shortest_path(const Point &start, const Point &finish,
                         double epsilon = 0.0);
  std::vector<Polygon>
  compute_partition_cells(std::vector<Line_Segment> partition_inducing_segments,
                          double epsilon = 0.0) {
    std::vector<Polygon> cells;
    return cells;
  }
  void write_to_file(const std::string &filename,
                     int fios_precision_temp = FIOS_PRECISION);
  // Mutators
  Polygon &operator[](unsigned i) {
    if (i == 0) {
      return outer_boundary_;
    } else {
      return holes_[i - 1];
    }
  }
  // Mutators
  Point &operator()(unsigned k);
  void set_outer_boundary(const Polygon &polygon_temp) {
    outer_boundary_ = polygon_temp;
    update_flattened_index_key();
  }
  void add_hole(const Polygon &polygon_temp) {
    holes_.push_back(polygon_temp);
    update_flattened_index_key();
  }
  void enforce_standard_form();
  void eliminate_redundant_vertices(double epsilon = 0.0);
  void reverse_holes();
 
private:
  Polygon outer_boundary_;
  // obstacles
  std::vector<Polygon> holes_;
  // allows constant time access to vertices via operator () with
  // flattened index as argument
  std::vector<std::pair<unsigned, unsigned> > flattened_index_key_;
  // Must call if size of outer_boundary and/or holes_ changes.  Time
  // complexity O(n), where n is the number of vertices representing
  // the Environment.
  void update_flattened_index_key();
  // converts flattened index to index pair (hole #, vertex #) in
  // time O(n), where n is the number of vertices representing the
  // Environment
  std::pair<unsigned, unsigned> one_to_two(unsigned k) const;
  // node used for search tree of A* search in shortest_path() method
  class Shortest_Path_Node {
  public:
    // flattened index of corresponding Environment vertex
    // convention vertex_index = n() => corresponds to start Point
    // vertex_index = n() + 1 => corresponds to finish Point
    unsigned vertex_index;
    // pointer to self in search tree.
    std::list<Shortest_Path_Node>::iterator search_tree_location;
    // pointer to parent in search tree.
    std::list<Shortest_Path_Node>::iterator parent_search_tree_location;
    // Geodesic distance from start Point.
    double cost_to_come;
    // Euclidean distance to finish Point.
    double estimated_cost_to_go;
    // std::vector<Shortest_Path_Node> expand();
    bool operator<(const Shortest_Path_Node &spn2) const {
      double f1 = this->cost_to_come + this->estimated_cost_to_go;
      double f2 = spn2.cost_to_come + spn2.estimated_cost_to_go;
      if (f1 < f2)
        return true;
      else if (f2 < f1)
        return false;
      else if (this->vertex_index < spn2.vertex_index)
        return true;
      else if (this->vertex_index > spn2.vertex_index)
        return false;
      else if (&(*(this->parent_search_tree_location)) <
               &(*(spn2.parent_search_tree_location)))
        return true;
      else
        return false;
    }
    // print member data for debugging
    void print() const {
      std::cout << "         vertex_index = " << vertex_index << std::endl
                << "parent's vertex_index = "
                << parent_search_tree_location->vertex_index << std::endl
                << "         cost_to_come = " << cost_to_come << std::endl
                << " estimated_cost_to_go = " << estimated_cost_to_go
                << std::endl;
    }
  };
};
 
std::ostream &operator<<(std::ostream &outs,
                         const Environment &environment_temp);
 
class Guards {
public:
  friend class Visibility_Graph;
  // Constructors
  Guards() {}
  Guards(const std::string &filename);
  Guards(const std::vector<Point> &positions) { positions_ = positions; }
  // Accessors
  const Point &operator[](unsigned i) const { return positions_[i]; }
  unsigned N() const { return positions_.size(); }
  bool are_lex_ordered() const;
  bool noncolocated(double epsilon = 0.0) const;
  bool in(const Polygon &polygon_temp, double epsilon = 0.0) const;
  bool in(const Environment &environment_temp, double epsilon = 0.0) const;
  double diameter() const;
  Bounding_Box bbox() const;
  void write_to_file(const std::string &filename,
                     int fios_precision_temp = FIOS_PRECISION);
  // Mutators
  Point &operator[](unsigned i) { return positions_[i]; }
  void push_back(const Point &point_temp) { positions_.push_back(point_temp); }
  void set_positions(const std::vector<Point> &positions_temp) {
    positions_ = positions_temp;
  }
  void enforce_lex_order();
  void reverse();
  void snap_to_vertices_of(const Environment &environment_temp,
                           double epsilon = 0.0);
 
  void snap_to_vertices_of(const Polygon &polygon_temp, double epsilon = 0.0);
  void snap_to_boundary_of(const Environment &environment_temp,
                           double epsilon = 0.0);
  void snap_to_boundary_of(const Polygon &polygon_temp, double epsilon = 0.0);
 
private:
  std::vector<Point> positions_;
};
 
std::ostream &operator<<(std::ostream &outs, const Guards &guards);
 
class Visibility_Polygon : public Polygon {
public:
  // Constructors
  Visibility_Polygon() {}
  //:TRICKY:
  Visibility_Polygon(const Point &observer, const Environment &environment_temp,
                     double epsilon = 0.0);
  Visibility_Polygon(const Point &observer, const Polygon &polygon_temp,
                     double epsilon = 0.0);
  // Accessors
  // std::vector<bool> get_gap_edges(double epsilon=0.0) { return gap_edges_; }
  Point observer() const { return observer_; }
  // Mutators
private:
  // ith entry of gap_edges is true iff the edge following ith vertex
  // is a gap edge (not solid).
  // std::vector<bool> gap_edges_;
  Point observer_;
 
  struct Polar_Edge {
    Polar_Point first;
    Polar_Point second;
    Polar_Edge() {}
    Polar_Edge(const Polar_Point &ppoint1, const Polar_Point &ppoint2)
        : first(ppoint1), second(ppoint2) {}
  };
 
  class Polar_Point_With_Edge_Info : public Polar_Point {
  public:
    std::list<Polar_Edge>::iterator incident_edge;
    bool is_first; // True iff polar_point is the first_point of the
                   // Polar_Edge pointed to by
                   // incident_edge.
    void set_polar_point(const Polar_Point &ppoint_temp) {
      set_polar_origin(ppoint_temp.polar_origin());
      set_x(ppoint_temp.x());
      set_y(ppoint_temp.y());
      set_range(ppoint_temp.range());
      set_bearing(ppoint_temp.bearing());
    }
    // The operator < is the same as for Polar_Point with one
    // exception.  If two vertices have equal coordinates, but one is
    // the first point of its respecitve edge and the other is the
    // second point of its respective edge, then the vertex which is
    // the second point of its respective edge is considered
    // lexicographically smaller.
    friend bool operator<(const Polar_Point_With_Edge_Info &ppwei1,
                          const Polar_Point_With_Edge_Info &ppwei2) {
      if (Polar_Point(ppwei1) == Polar_Point(ppwei2) and !ppwei1.is_first and
          ppwei2.is_first)
        return true;
      else
        return Polar_Point(ppwei1) < Polar_Point(ppwei2);
    }
  };
 
  // Strict weak ordering (acts like <) for pointers to Polar_Edges.
  // Used to sort the priority_queue q2 used in the radial line sweep
  // of Visibility_Polygon constructors.  Let p1 be a pointer to
  // Polar_Edge e1 and p2 be a pointer to Polar_Edge e2.  Then p1 is
  // considered greater (higher priority) than p2 if the distance
  // from the observer (pointed to by observer_pointer) to e1 along
  // the direction to current_vertex is smaller than the distance
  // from the observer to e2 along the direction to current_vertex.
  class Incident_Edge_Compare {
    const Point *const observer_pointer;
    const Polar_Point_With_Edge_Info *const current_vertex_pointer;
    double epsilon;
 
  public:
    Incident_Edge_Compare(const Point &observer,
                          const Polar_Point_With_Edge_Info &current_vertex,
                          double epsilon_temp)
        : observer_pointer(&observer), current_vertex_pointer(&current_vertex),
          epsilon(epsilon_temp) {}
    bool operator()(std::list<Polar_Edge>::iterator e1,
                    std::list<Polar_Edge>::iterator e2) const {
      Polar_Point k1, k2;
      Line_Segment xing1 = intersection(
          Ray(*observer_pointer, current_vertex_pointer->bearing()),
          Line_Segment(e1->first, e1->second), epsilon);
      Line_Segment xing2 = intersection(
          Ray(*observer_pointer, current_vertex_pointer->bearing()),
          Line_Segment(e2->first, e2->second), epsilon);
      if (xing1.size() > 0 and xing2.size() > 0) {
        k1 = Polar_Point(*observer_pointer, xing1.first());
        k2 = Polar_Point(*observer_pointer, xing2.first());
        if (k1.range() <= k2.range())
          return false;
        return true;
      }
      // Otherwise infeasible edges are given higher priority, so they
      // get pushed out the top of the priority_queue's (q2's)
      // heap.
      else if (xing1.size() == 0 and xing2.size() > 0)
        return false;
      else if (xing1.size() > 0 and xing2.size() == 0)
        return true;
      else
        return true;
    }
  };
 
  bool is_spike(const Point &observer, const Point &point1, const Point &point2,
                const Point &point3, double epsilon = 0.0) const;
 
  // For eliminating spikes as they appear.  In the
  // Visibility_Polygon constructors, these are checked every time a
  // Point is added to vertices.
  void chop_spikes_at_back(const Point &observer, double epsilon);
  void chop_spikes_at_wrap_around(const Point &observer, double epsilon);
  void chop_spikes(const Point &observer, double epsilon);
  // For debugging Visibility_Polygon constructors.
  // Prints current_vertex and active_edge data to screen.
  void print_cv_and_ae(const Polar_Point_With_Edge_Info &current_vertex,
                       const std::list<Polar_Edge>::iterator &active_edge);
};
 
class Visibility_Graph {
public:
  // Constructors
  Visibility_Graph() {
    n_ = 0;
    adjacency_matrix_ = NULL;
  }
  Visibility_Graph(const Visibility_Graph &vg2);
  Visibility_Graph(const Environment &environment, double epsilon = 0.0);
  // Constructors
  Visibility_Graph(const std::vector<Point> points,
                   const Environment &environment, double epsilon = 0.0);
  // Constructors
  Visibility_Graph(const Guards &guards, const Environment &environment,
                   double epsilon = 0.0);
  // Accessors
  bool operator()(unsigned i1, unsigned j1, unsigned i2, unsigned j2) const;
  bool operator()(unsigned k1, unsigned k2) const;
  unsigned n() const { return n_; }
  // Mutators
  bool &operator()(unsigned i1, unsigned j1, unsigned i2, unsigned j2);
  bool &operator()(unsigned k1, unsigned k2);
  Visibility_Graph &operator=(const Visibility_Graph &visibility_graph_temp);
  virtual ~Visibility_Graph();
 
private:
  // total number of vertices of corresponding Environment
  unsigned n_;
  // the number of vertices in each Polygon of corresponding Environment
  std::vector<unsigned> vertex_counts_;
  // n_-by-n_ adjacency matrix data stored as 2D dynamic array
  bool **adjacency_matrix_;
  // converts vertex pairs (hole #, vertex #) to flattened index
  unsigned two_to_one(unsigned i, unsigned j) const;
};
 
std::ostream &operator<<(std::ostream &outs,
                         const Visibility_Graph &visibility_graph);
 
class Unit_Test {
public:
  static void set_output_precision();
 
  static void seed_random();
 
  template <std::size_t N>
  static std::vector<Point> make_point_vector(std::array<double, N> vertices) {
    static_assert(N % 2 == 0,
                  "Specify an even number of points to make a point array.");
    std::vector<Point> point_vector;
    for (size_t i = 0; i < N; i += 2) {
      point_vector.push_back(Point(vertices[i], vertices[i + 1]));
    }
    return point_vector;
  }
};
 
class Shortest_Path_Test : public Unit_Test {
public:
  static bool validate(const VisiLibity::Environment &environment,
                       const double epsilon, const VisiLibity::Guards &guards);
};
 
} // namespace VisiLibity
 
#endif // VISILIBITY_H