coordinates_generator
functions.hpp
Go to the documentation of this file.
1 #pragma once
2 
3 #include <cmath>
4 #include <memory>
5 #include <iterator>
6 #include <iostream>
7 #include <vector>
8 #include <list>
9 #include <algorithm>
10 #include <set>
11 #include <unordered_map>
12 #include <fstream>
13 #include <string>
14 
15 #include "triangulation.hpp"
16 #include <queue>
17 #include <unordered_set>
18 
19 #include <boost/geometry.hpp>
20 #include <boost/geometry/geometries/polygon.hpp>
21 #include <boost/geometry/geometries/adapted/boost_tuple.hpp>
22 #include <boost/geometry/algorithms/assign.hpp>
23 
24 BOOST_GEOMETRY_REGISTER_BOOST_TUPLE_CS(cs::cartesian)
25 
26 using namespace std;
27 
28 #ifndef M_PI
29 #define M_PI 3.14159265358979323846
30 #endif
31 
32 #ifndef INF
33 #define INF 100000000
34 #endif // !INF
35 
36 #ifndef EPSILON
37 #define EPSILON 0.0001
38 #endif
39 
40 #define x first
41 #define y second
42 
43 inline bool print_bool = false;
44 
45 using array_4D = vector<vector<vector<vector<bool> > > >;
46 
47 struct Vertex;
48 struct Edge;
49 struct Face;
50 
54 struct Vertex {
56 
57  int index_ = 0;
58 
59  double x_, y_;
60 
61  pair<double, double> shift_first = make_pair(0, 0);
62  pair<double, double> shift_second = make_pair(0, 0);
63 
64  Vertex() {}
65 
66  Vertex(double x, double y) : x_(x), y_(y) {}
67 
68  //it is really good to be the opposite one because when you create new vertex
69  //from the edge side then it is good to go from the intersection opposite side
70  Vertex(Edge* to) : to_(to) {}
71 
72  bool operator==(const Vertex& a) {
73  return x_ == a.x_ && y_ == a.y_;
74  }
75 
76  bool operator!=(const Vertex& a) {
77  return !(*this == a);
78  }
79 
80  bool operator==(Vertex* a) {
81  return a->x_ == x_ && a->y_ == y_;
82  }
83 
84  bool operator!=(Vertex* a) {
85  return !(this == a);
86  }
87 
88 
89  bool operator==(const Vertex* a) {
90  return a->x_ == x_ && a->y_ == y_;
91  }
92 
93  bool operator!=(const Vertex* a) {
94  return !(this == a);
95  }
96 };
97 
101 struct Face {
103 
104  Face() {}
105 
106  Face(Edge* edge) : edge_(edge) {}
107 };
108 
112 struct Edge {
113  int index_ = 0;
114 
118 
119  vector<shared_ptr<Vertex> > vertices_;
120 
121  shared_ptr<Face> face_;
122 
123  Edge() {}
124 
125  Edge(Edge* next, Edge* prev, Edge* opposite, vector<shared_ptr<Vertex> > vertices, shared_ptr<Face> face, int index) :
126  next_(next), prev_(prev), opposite_(opposite), vertices_(vertices), face_(face), index_(index) {}
127 
128  bool operator==(const Edge& a) {
129  return (vertices_[0] == a.vertices_[0] && vertices_.back() == a.vertices_.back());
130  }
131 
132  bool operator!=(const Edge& a) {
133  return !(*this == a);
134  }
135 
136 };
137 
141 struct graph {
142 
143  /*normal part*/
144  int number_of_vertices = 0; //just real vertices
145 
146  vector<Vertex> outer_vertices{Vertex(336, 341), Vertex(310, -337), Vertex(-329, -283), Vertex(-302, 297)};
147 
148  int realized = 0;
149  bool done = false;
150 
151  int counter = 0;
152 
153  vector< pair<double, double> > most_away;
154 
155  list<Edge> edges;
156 
157  shared_ptr<Face> outer_face;
158 
159  ofstream output_file;
160 
161  vector<pair<double, double> > vertices_;
162 
163  vector<pair<double, double> > coordinates_of_special_vertices;
164 
165  int index;
166 
167  void close_files() {
168  output_file.close();
169  }
170 
171  graph(int n, int ii) {
172  index = ii;
173 
174  number_of_vertices = n;
175  outer_face = make_shared<Face>();
176 
177  starts.resize(number_of_vertices);
178  for (int i = 0; i < number_of_vertices;i++) {
179  starts[i].resize(number_of_vertices);
180  }
181 
182  blocked.resize(number_of_vertices);
183  for (int i = 0; i < number_of_vertices;i++) {
184  blocked[i].resize(number_of_vertices);
185  for (int j = 0; j < number_of_vertices;j++) {
186  blocked[i][j].resize(number_of_vertices);
187  for (int k = 0; k < number_of_vertices;k++) {
188  blocked[i][j][k].resize(number_of_vertices);
189  for (int l = 0; l < number_of_vertices;l++) {
190  blocked[i][j][k][l] = false;
191  }
192  }
193  }
194  }
195 
196  string string_index = index < 10 ? "0" + to_string(index) : to_string(index);
197  auto output_path = "../VizualizerWPF/data/graph"
198  + to_string(n) + "_" + string_index + ".txt";
199  output_file.open(output_path);
200  }
201 
202  void add_edge(
203  shared_ptr<Vertex> a,
204  shared_ptr<Vertex> b,
205  shared_ptr<Face> face,
206  int a_index,
207  int b_index,
208  pair<double, double> previous_vertex,
209  pair<double, double> next_vertex,
210  bool outer_face_bool = false);
211  void add_vertex(Edge* edge);
212 
213  void delete_edge_back(bool outer_face_bool = false);
214  void delete_vertex(Vertex* a);
215 
216  //void redirect_previous_segment(int a, int b, shared_ptr<Vertex> destination);
217  shared_ptr<Vertex> tearup_lines_in_half(
218  Edge* edge,
219  vector<shared_ptr<Vertex> >& a_half,
220  vector<shared_ptr<Vertex> >& b_half
221  );
222 
223  vector<shared_ptr<Vertex> > find_path_through_triangulation(
224  shared_ptr<Vertex> a,
225  shared_ptr<Vertex> b,
226  shared_ptr<Face> face,
227  int a_index,
228  int b_index,
229  pair<double, double> shift_previous,
230  pair<double, double> shift_next,
231  bool outer_face_bool = false
232  );
233  /*finger print part*/
234 
235  //number of edges indexer
239  vector<Edge*> segments;
240 
245 
250  vector<vector<int> > starts;
251 
252  // to store canonic fingerprints
253 
254  void create_special_vertex(int index, int x, int y);
255  void recolor_fingerprint(const string& rotation);
256  void create_base_star();
257  void create_all_special_vertices();
258  void find_the_way_to_intersect(int s_index, int t_index, int a, int b);
259  //void intersect();
260  //bool is_correct_fingerprint(const string& fingerprint);
261  void create_all_possible_drawings();
262 
263  void write_coordinates();
264 
265  vector<shared_ptr<Vertex> > find_shortest_path(const vector<vector<double> >& distances, vector<shared_ptr<Vertex> >& face_vertices);
266 
267  //string find_canonic_fingerprint(const string& fingerprint);
268 
269  void update_most_away(vector<pair<double, double> > vertices);
270 
271 };
272 
273 
280 inline bool if_two_segmetns_intersects(pair<shared_ptr<Vertex>, shared_ptr<Vertex> > line1, pair<shared_ptr<Vertex>, shared_ptr<Vertex> > line2)
281 {
282  auto denominator = (line2.second->y_ - line2.first->y_) * (line1.second->x_ - line1.first->x_) - (line2.second->x_ - line2.first->x_) * (line1.second->y_ - line1.first->y_);
283 
284  auto numT = -line1.first->x_ * (line2.second->y_ - line2.first->y_) + line1.first->y_ * (line2.second->x_ - line2.first->x_) +
285  line2.first->x_ * (line2.second->y_ - line2.first->y_) - line2.first->y_ * (line2.second->x_ - line2.first->x_);
286  auto numS = -line1.first->x_ * (line1.second->y_ - line1.first->y_) + line1.first->y_ * (line1.second->x_ - line1.first->x_) +
287  line2.first->x_ * (line1.second->y_ - line1.first->y_) - line2.first->y_ * (line1.second->x_ - line1.first->x_);
288 
289 
290  auto s = numS / denominator;
291  auto t = numT / denominator;
292 
293  if (abs(denominator) < EPSILON && (s >= -EPSILON && s <= 1 + EPSILON) && (t >= -EPSILON && t <= 1 + EPSILON))
294  return true;
295  return false;
296 }
297 
298 
305 inline void create_coordinates(const vector<shared_ptr<Vertex> >& points, vector<vector<double> >& distances) {
306 
307  for (int i = 0; i < points.size();i++) {
308  for (int j = 0; j < points.size();j++) {
309  distances[i][j] = sqrt((points[i]->x_ - points[j]->x_) * (points[i]->x_ - points[j]->x_) + (points[i]->y_ - points[j]->y_) * (points[i]->y_ - points[j]->y_));
310  }
311  }
312 }
313 
314 
322 inline void dijsktra(vector<shared_ptr<Vertex> >& points, vector<vector<double> > distances, vector<int>& parent) {
323 
324  vector<double> shortest;
325  shortest.resize(points.size());
326 
327  priority_queue<pair<double, int>, vector<pair<double, int> >, greater<pair<double, int> > > pq;
328  vector<bool> visited;
329  visited.resize(points.size());
330 
331  for (int i = 0; i < points.size(); i++) {
332  shortest[i] = INF;
333  }
334 
335  shortest[0] = 0;
336  pq.push(make_pair(shortest[0], 0));
337 
338  while (!pq.empty()) {
339  auto top = pq.top();pq.pop();
340 
341  if (visited[top.second]) continue;
342  visited[top.second] = true;
343 
344  for (int w = 0; w < points.size();w++) {
345  if (top.second != w) {
346 
347  if (shortest[w] > shortest[top.second] + distances[top.second][w]) {
348  shortest[w] = top.first + distances[top.second][w];
349  pq.push(make_pair(shortest[w], w));
350  parent[w] = top.second;
351  }
352  }
353  }
354  }
355 }
356 
357 
358 inline void print_graph(graph* g) {
359  cout << "number of edges: " << g->edges.size() << endl;
360 
361  int i = 0;
362  for (auto it : g->edges) {
363  cout << it.vertices_[0] << ":from to:" << it.vertices_.back() << " face:" << it.face_ << " prev:" << it.prev_->index_ << " next:" << it.next_->index_
364  << " opp:" << ((it.opposite_ == nullptr) ? -1 : it.opposite_->index_) << " index:" << it.index_ << " s: " << i << endl;
365  i++;
366  }
367 
368 }
369 
376 inline vector<shared_ptr<Vertex> > graph::find_shortest_path(const vector<vector<double> > & distances, vector<shared_ptr<Vertex > >& all_vertices) {
377 
378 
379  /*
380  for (int i = 0; i < distances.size();i++) {
381  for (int j = 0; j < distances[i].size();j++) {
382  cout << distances[i][j] << " ";
383  }
384  cout << endl;
385  }
386  */
387 
388  vector<int> parent;
389  parent.resize(all_vertices.size());
390  dijsktra(all_vertices, distances, parent);
391 
392  vector<shared_ptr<Vertex> > result;
393 
394  int v = 1;
395  while (v != 0) {
396  result.push_back(all_vertices[v]);
397  v = parent[v];
398  }
399  result.push_back(all_vertices[0]);
400  return result;
401 }
402 
411 inline vector<pair<double, double> > create_circle(double radius, double cx, double cy, int n) {
412  vector<pair<double, double> > circle;
413 
414  double unit_angle = (double)360 / n;
415 
416  for (int i = 0; i < n;i++) {
417  circle.push_back(make_pair((int)(cx + radius * cos((i + 1) * (unit_angle / 180) * M_PI)),(int)(cy + radius * sin((i + 1) * (unit_angle / 180) * M_PI))));
418  }
419 
420  /*
421  for (int i = 0; i < n;i++) {
422  cout << circle[i].x << " " << circle[i].y << endl;
423  }
424  */
425  return circle;
426 }
427 
428 inline double distance(pair<double, double> a) {
429  return sqrt((a.x ) * (a.x) + (a.y) * (a.y ));
430 }
431 
432 inline double distance(pair<double, double> a, pair<double, double> b) {
433  return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
434 }
435 
436 inline double distance(shared_ptr<Vertex> a, shared_ptr<Vertex> b) {
437  return sqrt((a->x_ - b->x_) * (a->x_ - b->x_) + (a->y_ - b->y_) * (a->y_ - b->y_));
438 }
439 
440 
441 
447 inline vector<pair<double, double> > make_convex_hull(vector<pair<double, double> > vertices) {
448  typedef boost::tuple<double, double> point;
449  typedef boost::geometry::model::polygon<point> polygon;
450 
451  polygon poly;
452 
453 
454  vector<point> points;
455 
456  for(int i = 0; i < vertices.size();i++){
457  points.push_back(
458  boost::make_tuple<double, double>(vertices[i].x, vertices[i].y));
459  }
460 
461  boost::geometry::assign_points(poly, points);
462 
463  polygon hull;
464  boost::geometry::convex_hull(poly, hull);
465 
466  /*
467  using boost::geometry::dsv;
468  std::cout
469  << "polygon: " << dsv(poly) << std::endl
470  << "hull: " << dsv(hull) << std::endl;
471  */
472  vector<pair<double, double> > result;
473 
474  for (int i = 0; i < hull.outer().size();i++) {
475  result.push_back(make_pair(hull.outer()[i].get_head(), hull.outer()[i].get_tail().get_head()));
476  }
477  return result;
478 }
479 
486 inline bool compare(pair<double, double> a, pair<double, double> b) {
487  if (abs(a.x - b.x) < EPSILON && abs(a.y - b.y) < EPSILON)
488  return true;
489  return false;
490 }
491 
496 inline void graph::update_most_away(vector<pair<double, double> > vertices) {
497  most_away = make_convex_hull(vertices);
498 }
499 
506 inline double det(pair<double, double> vec1, pair<double, double> vec2) {
507  return vec1.x * vec2.y - vec1.y * vec2.x;
508 }
509 
510 //shifting to the right
511 
512 
513 /*
514  <----
515  | ^
516  | | \\shift -->
517  | |
518  v --->
519 */
520 
528 inline pair<double, double> get_shift(shared_ptr<Vertex> vertex, pair<double, double> vect) {
529 
530  pair<double, double> first_neg_vect;
531  pair<double, double> second_neg_vect;
532 
533  //negative one is to the right
534 
535  first_neg_vect = make_pair(-vect.y, vect.x);
536  second_neg_vect = make_pair(vect.y, -vect.x);
537 
538 
539  if (det(vect, first_neg_vect) < 0) { //negative der is to the right
540  return make_pair(10 * EPSILON * first_neg_vect.x, 10 * EPSILON * first_neg_vect.y); // 10* EPSILON to be recognizable
541  }
542  else {
543  return make_pair(10 * EPSILON * second_neg_vect.x, 10 * EPSILON * second_neg_vect.y);
544  }
545 }
546 
547 
555 inline pair<double, double> find_vertex_in_right_direction(shared_ptr<Vertex> vertex, pair<double, double> vect) {
556 
557  auto shift = get_shift(vertex, vect);
558  return make_pair(100 * (shift.x / distance(shift)), 100 * ((shift.y / distance(shift))));
559 
560 }
561 
562 
571 inline double get_value(int a, int b, int c, shared_ptr<Vertex> point) {
572  return a * point->x_ + b * point->y_ + c;
573 }
574 
584 inline bool is_on_right_side_of(shared_ptr<Vertex>asked_point, shared_ptr<Vertex> point, pair<double, double> vect, shared_ptr<Vertex> on_right_side) {
585 
586  double a = vect.x;
587  double b = vect.y;
588  double c = -(a * point->x_ + b * point->y_);
589 
590  if (get_value(a, b, c, asked_point) * get_value(a, b, c, on_right_side) > 0)
591  return true;
592  return false;
593 }
594 
595 
596 
597 /*
598 inline bool check_if_its_line_between_inner_and_outer_part(int size, int index1, int index2) {
599  vector<pair<int, int> > indices_between{ make_pair(0, size - 5), make_pair(0, size - 1), make_pair(size - 6, size - 5), make_pair(size - 6, size - 1) };
600 
601  if (index1 > index2)
602  swap(index1, index2);
603 
604  pair<int, int> indices = make_pair(index1, index2);
605 
606  for (int i = 0; i < indices_between.size(); i++) {
607  if (indices_between[i] == indices)
608  return true;
609  }
610  return false;
611 }
612 */
613 
614 inline bool are_collinear(shared_ptr<Vertex> v1, shared_ptr<Vertex> v2, shared_ptr<Vertex> v3) {
615 
616  /* Calculation the area of
617  triangle.We have skipped
618  multiplication with 0.5 to
619  avoid floating point computations */
620 
621  double a = v1->x_ * (v2->y_ - v3->y_) + v2->x_ * (v3->y_ - v1->y_) + v3->x_ * (v1->y_ - v2->y_);
622 
623  if (abs(a) < EPSILON)
624  return true;
625  return false;
626 }
627 
641 inline vector<shared_ptr<Vertex> > graph::find_path_through_triangulation(shared_ptr<Vertex> a, shared_ptr<Vertex> b,
642  shared_ptr<Face> face, int a_index, int b_index,
643  pair<double, double> shift_previous,
644  pair<double, double> shift_next, bool outer_face_bool) {
645  Edge* toa = nullptr, * tob = nullptr, * froma = nullptr, * fromb = nullptr;
646 
647  toa = a->to_;
648  froma = toa->next_;
649 
650  tob = b->to_;
651  fromb = tob->next_;
652 
653  /* triangulation */
654 
655  vector<shared_ptr<Vertex> > vertices;
656 
657  if (!outer_face_bool) {
658 
659  bool second_outer_face_bool = true;
660 
661  update_most_away(vertices_);
662 
663  vector<shared_ptr<Vertex> > faces_vertices;
664  auto start = face->edge_;
665  auto cur = start->next_;
666  faces_vertices.insert(faces_vertices.end(), start->vertices_.begin(), start->vertices_.end() - 1);
667 
668  while (cur != start) {
669  faces_vertices.insert(faces_vertices.end(), cur->vertices_.begin(), cur->vertices_.end() - 1);
670  cur = cur->next_;
671  }
672 
673  //find_vertex_shortest to outside layer
674  vector<vector<double> > outside_distances; outside_distances.resize(faces_vertices.size() + outer_vertices.size());
675  for (int i = 0; i < outside_distances.size(); i++)
676  outside_distances[i].resize(outside_distances.size());
677 
678  vector<shared_ptr<Vertex> > outside_points;
679  for (int i = 0; i < outer_vertices.size(); i++)
680  outside_points.push_back(make_shared<Vertex>(outer_vertices[i]));
681  outside_points.insert(outside_points.end(), faces_vertices.begin(), faces_vertices.end());
682  create_coordinates(outside_points, outside_distances);
683 
684  double mn = INF; int mn_index = -1;
685  for (int i = 0; i < outer_vertices.size(); i++) {
686  for (int j = outer_vertices.size(); j < outside_distances[i].size(); j++) {
687  if (outside_distances[i][j] < mn) {
688  mn = outside_distances[i][j];
689  mn_index = j - outer_vertices.size();
690  }
691  }
692  }
693 
694  rotate(faces_vertices.begin(), faces_vertices.begin() + mn_index, faces_vertices.end());
695 
696  //if (*start->vertices_[0] == Vertex(0, 0))
697  // rotate(faces_vertices.begin(), faces_vertices.begin() + 1, faces_vertices.end());
698 
699  faces_vertices.push_back(faces_vertices[0]);
700 
701  vector<pair<double, double> > coords;
702  vector<pair<double, double> > indices_coords;
703 
704  vector<bool> local_most_away; local_most_away.resize(most_away.size());
705 
706  coords.push_back(make_pair(faces_vertices[0]->x_, faces_vertices[0]->y_)); indices_coords.push_back(make_pair(faces_vertices[0]->x_, faces_vertices[0]->y_));
707  for (int i = 1; i < faces_vertices.size(); i++) {
708  if (*faces_vertices[i] != *faces_vertices[i - 1]) {
709  if ((faces_vertices[i]->index_ == -1) &&
710  (compare(make_pair(faces_vertices[i]->x_ - faces_vertices[i - 1]->x_, faces_vertices[i]->y_ - faces_vertices[i - 1]->y_), faces_vertices[i]->shift_first)
711  ||
712  compare(make_pair(faces_vertices[i]->x_ - faces_vertices[i - 1]->x_, faces_vertices[i]->y_ - faces_vertices[i - 1]->y_), faces_vertices[i]->shift_second))) {
713  auto shift = get_shift(
714  faces_vertices[i],
715  make_pair(faces_vertices[i]->x_ - faces_vertices[i - 1]->x_,
716  faces_vertices[i]->y_ - faces_vertices[i - 1]->y_));
717 
718  indices_coords.push_back(make_pair(
719  faces_vertices[i]->x_ + shift.x,
720  faces_vertices[i]->y_ + shift.y
721  ));
722  }
723  else {
724  indices_coords.push_back(make_pair(faces_vertices[i]->x_, faces_vertices[i]->y_));
725  }
726  coords.push_back(make_pair(faces_vertices[i]->x_, faces_vertices[i]->y_));
727  }
728  for (int j = 0; j < most_away.size(); j++) {
729  if (abs(faces_vertices[i]->x_ - most_away[j].x) < EPSILON && abs(faces_vertices[i]->y_ - most_away[j].y) < EPSILON) {
730  local_most_away[j] = true;
731  }
732  }
733 
734  }
735 
736  for (int j = 0; j < most_away.size(); j++) {
737  if (!local_most_away[j]) {
738  second_outer_face_bool = false;
739  break;
740  }
741  }
742 
743  /* checking outer face */
744 
745  if (second_outer_face_bool) {
746  /* minimum rotation of outer part*/
747  double mn = INF;
748  int index_min;
749  for (int i = 0; i < outer_vertices.size(); i++) {
750  if ((outer_vertices[i].x_ - faces_vertices.back()->x_) * (outer_vertices[i].x_ - faces_vertices.back()->x_) +
751  (outer_vertices[i].y_ - faces_vertices.back()->y_) * (outer_vertices[i].y_ - faces_vertices.back()->y_) < mn) {
752  index_min = i;
753  mn = (outer_vertices[i].x_ - faces_vertices.back()->x_) * (outer_vertices[i].x_ - faces_vertices.back()->x_) +
754  (outer_vertices[i].y_ - faces_vertices.back()->y_) * (outer_vertices[i].y_ - faces_vertices.back()->y_);
755  }
756  }
757 
758  rotate(outer_vertices.begin(), outer_vertices.begin() + index_min, outer_vertices.end());
759 
760 
761  for (int i = 0; i < outer_vertices.size(); i++) {
762  coords.push_back(make_pair(outer_vertices[i].x_, outer_vertices[i].y_));
763  indices_coords.push_back(make_pair(outer_vertices[i].x_, outer_vertices[i].y_));
764  }
765  coords.push_back(make_pair(outer_vertices[0].x_, outer_vertices[0].y_));
766  indices_coords.push_back(make_pair(outer_vertices[0].x_, outer_vertices[0].y_));
767 
768  }
769 
770  vector<vector<pair<double, double> > > polygon{ indices_coords };
771 
772  std::vector<int> indices = mapbox::earcut<int>(polygon);
773 
774 
775  // rename duplicate vertices if neededs
776  if (second_outer_face_bool) {
777  int size = coords.size();
778  for (int i = 0; i < indices.size(); i++) {
779  indices[i] = indices[i] == size - 5 ? size - 1 : indices[i];
780  indices[i] = indices[i] == size - 6 ? 0 : indices[i];
781  }
782  }
783  /*
784  else {
785  int size = coords.size();
786  for (int i = 0; i < indices.size(); i++) {
787  indices[i] = indices[i] == size - 1 ? 0 : indices[i];
788  }
789  }
790  */
791 
792 
793  set<pair<double, double> > visited_vertices;
794 
795  auto mids = vector<shared_ptr<Vertex> >();
796  for (int i = 0; i < indices.size(); i += 3){
797 
798  for (int j = 0; j < 3; j++) {
799  auto vertex = make_shared<Vertex>((coords[indices[i + j]].x + coords[indices[i + ((j + 1) % 3)]].x) / 2,
800  (coords[indices[i + j]].y + coords[indices[i + ((j + 1) % 3)]].y) / 2);
801  if (!visited_vertices.count(make_pair(vertex->x_, vertex->y_)) //should be first one there
802  &&
803  !(second_outer_face_bool &&
804  ((min(indices[i + j], indices[i + ((j + 1) % 3)]) == 0)
805  && (max(indices[i + j], indices[i + ((j + 1) % 3)]) == coords.size() - 7)))
806  &&
807  !(second_outer_face_bool &&
808  ((min(indices[i + j], indices[i + ((j + 1) % 3)]) == coords.size() - 4)
809  && (max(indices[i + j], indices[i + ((j + 1) % 3)]) == coords.size() - 1)))
810  &&
811  !(!second_outer_face_bool && (abs(indices[i + j] - indices[i + ((j + 1) % 3)]) == coords.size() - 2))
812  &&
813  (abs(indices[i + j] - indices[i + ((j + 1) % 3)]) != 1)
814  ) {
815  visited_vertices.insert(make_pair(vertex->x_, vertex->y_));
816  mids.push_back(vertex);
817  }
818  }
819  }
820 
821  vector<shared_ptr<Vertex> > all_vertices{ a };
822  all_vertices.push_back(b);
823  all_vertices.insert(all_vertices.end(), mids.begin(), mids.end());
824 
825 
826  vector<vector<double> > distances;
827  distances.resize(all_vertices.size());
828  for (int i = 0; i < all_vertices.size(); i++) {
829  for (int j = 0; j < all_vertices.size(); j++) {
830  distances[i].push_back(INF);
831  }
832  }
833 
834  /*
835  vector<vector<double> > real_distances;
836  real_distances.resize(all_vertices.size());
837  for (int i = 0; i < all_vertices.size(); i++) {
838  real_distances[i].resize(all_vertices.size());
839  }
840 
841  create_coordinates(all_vertices, real_distances);
842  */
843 
844  //visited_vertices.clear();
845 
846  auto cmp = [](pair<pair<double, double>, int> a, pair<pair<double, double>, int> b) {return a.first < b.first; };
847  set<pair<pair<double, double>, int>, decltype(cmp)> visited_vertices2(cmp);
848 
849  int mid_index = 0;
850 
851  for (int i = 0; i < indices.size(); i += 3){
852 
853  vector<int> triangle_indices;
854  bool contains_a = false;
855  bool contains_b = false;
856 
857  for (int j = 0; j < 3; j++) {
858  auto vertex = make_shared<Vertex>((coords[indices[i + j]].x + coords[indices[i + ((j + 1) % 3)]].x) / 2,
859  (coords[indices[i + j]].y + coords[indices[i + ((j + 1) % 3)]].y) / 2);
860  if (!(second_outer_face_bool &&
861  ((min(indices[i + j], indices[i + ((j + 1) % 3)]) == 0)
862  && (max(indices[i + j], indices[i + ((j + 1) % 3)]) == coords.size() - 7)))
863  &&
864  !(second_outer_face_bool &&
865  ((min(indices[i + j], indices[i + ((j + 1) % 3)]) == coords.size() - 4)
866  && (max(indices[i + j], indices[i + ((j + 1) % 3)]) == coords.size() - 1)))
867  &&
868  !(!second_outer_face_bool && (abs(indices[i + j] - indices[i + ((j + 1) % 3)]) == coords.size() - 2))
869  &&
870  (abs(indices[i + j] - indices[i + ((j + 1) % 3)]) != 1)
871  ) {
872 
873  if (visited_vertices2.count(make_pair(make_pair(vertex->x_, vertex->y_), -1))) {
874  triangle_indices.push_back(visited_vertices2.find(make_pair(make_pair(vertex->x_, vertex->y_), -1))->second);
875  }
876  else {
877  visited_vertices2.insert(make_pair(make_pair(vertex->x_, vertex->y_), mid_index));
878  triangle_indices.push_back(mid_index);
879  mid_index++;
880  }
881  }
882  if (distance(coords[indices[i + (j % 3)]], make_pair(a->x_, a->y_)) < EPSILON) {
883  contains_a = true;
884  }
885 
886  if (distance(coords[indices[i + (j % 3)]], make_pair(b->x_, b->y_)) < EPSILON) {
887  contains_b = true;
888  }
889  }
890 
891  for(int u = 0;u < triangle_indices.size();u++){
892  for(int v = u + 1;v < triangle_indices.size();v++){
893  distances[triangle_indices[u]+2][triangle_indices[v]+2] = distance(mids[triangle_indices[u]], mids[triangle_indices[v]]);
894  distances[triangle_indices[v]+2][triangle_indices[u]+2] = distance(mids[triangle_indices[v]], mids[triangle_indices[u]]);
895  }
896  }
897 
898  for (int u = 0; u < triangle_indices.size(); u++) {
899  if (contains_a) {
900  distances[triangle_indices[u] + 2][0] = distance(mids[triangle_indices[u]], a);
901  distances[0][triangle_indices[u] + 2] = distance(a, mids[triangle_indices[u]]);
902  }
903  if(contains_b) {
904  distances[triangle_indices[u] + 2][1] = distance(mids[triangle_indices[u]], b);
905  distances[1][triangle_indices[u] + 2] = distance(b, mids[triangle_indices[u]]);
906  }
907  }
908 
909  }
910 
911 
912  /*finding if points can be connected with line*/
913 
914  for (int i = 0; i < indices.size(); i += 3) {
915  for (int j = 0; j < 3; j++) {
916  if (((a->x_ == coords[indices[i + j]].x) && (a->y_ == coords[indices[i + j]].y))
917  &&
918  ((b->x_ == coords[indices[i + ((j + 1) % 3)]].x) && (b->y_ == coords[indices[i + ((j + 1) % 3)]].y))
919  ) {
920  distances[0][1] = distance(a, b) - EPSILON; //substracting epsilon in order to choose a -- b instead of a -- mid -- b which is also possible
921  distances[1][0] = distance(b, a) - EPSILON;
922  }
923  }
924  }
925 
926 
927  for (int i = 0; i < indices.size(); i += 3) {
928  for (int j = 0; j < 3; j++) {
929  if (((b->x_ == coords[indices[i + j]].x) && (b->y_ == coords[indices[i + j]].y))
930  &&
931  ((a->x_ == coords[indices[i + ((j + 1) % 3)]].x) && (a->y_ == coords[indices[i + ((j + 1) % 3)]].y))
932  ) {
933  distances[0][1] = distance(a, b) - EPSILON;
934  distances[1][0] = distance(b, a) - EPSILON;
935  }
936  }
937  }
938 
939  /*choosing the most in the one direction one*/
940 
941  auto next_vertex = make_shared<Vertex>();
942 
943  next_vertex->x_ = b->x_ + shift_next.x;//(second_outer_face_bool ? shift_next.x : -shift_next.x);
944  next_vertex->y_ = b->y_ + shift_next.y;//(second_outer_face_bool ? shift_next.y : -shift_next.y);
945  if (b->index_ == -1) { // (b->shift_epsilon.x != 0 || b->shift_epsilon.y != 0) instead of b->index_ == -1
946  if (!is_on_right_side_of(a, b, shift_next, next_vertex)) {
947  distances[1][0] = INF;
948  distances[0][1] = INF;
949  }
950  for (int i = 2; i < distances.size(); i++) {
951  if (!is_on_right_side_of(mids[i - 2], b, shift_next, next_vertex)) { // coordinates_of_special_vertices[b_index - 1]
952  distances[1][i] = INF;
953  distances[i][1] = INF;
954  }
955  }
956  }
957  // a also wants right direction
958 
959  auto previous_vertex = make_shared<Vertex>();
960  previous_vertex->x_ = a->x_ + shift_previous.x;//(second_outer_face_bool ? shift_previous.x : -shift_previous.x);
961  previous_vertex->y_ = a->y_ + shift_previous.y;//(second_outer_face_bool ? shift_previous.y : -shift_previous.y);
962  if (a->index_ == -1) { // (b->shift_epsilon.x != 0 || b->shift_epsilon.y != 0) instead of b->index_ == -1
963  if (!is_on_right_side_of(b, a, shift_previous, previous_vertex)) {
964  distances[0][1] = INF;
965  distances[1][0] = INF;
966  }
967  for (int i = 2; i < distances.size(); i++) {
968  if (!is_on_right_side_of(mids[i-2], a, shift_previous, previous_vertex)) {
969  distances[0][i] = INF;
970  distances[i][0] = INF;
971  }
972  }
973  }
974 
975  vertices = find_shortest_path(distances, all_vertices);
976 
977  /*remove duplicates because mid can be in mids and as well normal vertex*/
978  vector<shared_ptr<Vertex> > temp_uniques; temp_uniques.push_back(vertices[0]);
979  for (int i = 1; i < vertices.size(); i++) {
980  if (*vertices[i] != *vertices[i - 1])
981  temp_uniques.push_back(vertices[i]);
982  }
983  vertices = temp_uniques;
984 
985  /*resolve knots */
986 
987  /*
988  for (int i = 3; i < vertices.size(); i++) {
989  if (if_two_segmetns_intersects(make_pair(vertices[i - 3], vertices[i - 2]), make_pair(vertices[i - 1], vertices[i])))
990  swap(vertices[i - 2], vertices[i - 1]);
991  }
992  */
993 
994  /*remove collinear ones*/
995 
996 
997  vector<shared_ptr<Vertex> > non_colinear;
998  non_colinear.push_back(vertices[0]); non_colinear.push_back(vertices[1]); //there are always at least two vertices
999  for (int i = 2; i < vertices.size(); i++) {
1000  if (are_collinear(non_colinear[non_colinear.size()-2], non_colinear[non_colinear.size()-1], vertices[i])) {
1001  non_colinear.pop_back(); non_colinear.push_back(vertices[i]); //skip when collinear
1002  }
1003  else {
1004  non_colinear.push_back(vertices[i]);
1005  }
1006  }
1007  vertices = non_colinear;
1008 
1009  return vertices;
1010 
1011  //print_graph(this);
1012 
1013 
1014  }
1015  else {
1016  return vector<shared_ptr<Vertex> >{ b, a };
1017  }
1018 
1019 
1020 }
1021 
1033 inline void graph::add_edge(shared_ptr<Vertex> a, shared_ptr<Vertex> b, shared_ptr<Face> face, int a_index, int b_index, pair<double, double> shift_previous, pair<double, double> shift_next, bool outer_face_bool) {
1034 
1035  Edge* toa = nullptr, * tob = nullptr, * froma = nullptr, * fromb = nullptr;
1036 
1037  toa = a->to_;
1038  froma = toa->next_;
1039 
1040  tob = b->to_;
1041  fromb = tob->next_;
1042 
1043  auto vertices = find_path_through_triangulation(a, b, face, a_index, b_index, shift_previous, shift_next, outer_face_bool);
1044 
1045  for (int i = 1; i < vertices.size() - 1; i++) {
1046  vertices_.push_back(make_pair(vertices[i]->x_, vertices[i]->y_));
1047  }
1048 
1049  auto new_face = !outer_face_bool ? make_shared<Face>() : outer_face; //new face or old face when creating star
1050 
1051  reverse(vertices.begin(), vertices.end());
1052  Edge ab_edge(fromb, toa, nullptr, vertices, face, a_index*100 + b_index); //edge from a to b
1053  edges.push_back(ab_edge); //number_of_edges++;
1054  Edge* ab_edge_ptr = &edges.back();
1055  segments.push_back(ab_edge_ptr);
1056 
1057  //print_graph(this);
1058 
1059  reverse(vertices.begin(), vertices.end());
1060  Edge ba_edge(froma, tob, ab_edge_ptr, vertices, new_face, b_index*100 + a_index); //edge from b to a
1061  edges.push_back(ba_edge); //number_of_edges++;
1062  Edge* ba_edge_ptr = &edges.back();
1063  segments.push_back(ba_edge_ptr);
1064 
1065  //print_graph(this);
1066 
1067  ab_edge_ptr->opposite_ = ba_edge_ptr; //setting opposite edge that has been already made and face edge
1068  new_face->edge_ = ba_edge_ptr;
1069 
1070  /*if it throws an exception it is allright because we are tryint to connect unconnectable vertices*/
1071  froma->prev_ = ba_edge_ptr; //changing neighborhood edges
1072  toa->next_ = ab_edge_ptr;
1073  fromb->prev_ = ab_edge_ptr;
1074  tob->next_ = ba_edge_ptr;
1075 
1076  //print_graph(this);
1077 
1078  if (!outer_face_bool) { //because if it is outer face it is not needed so it can be quicker
1079  auto start_edge = ba_edge_ptr; //setting the face property to all edges around this face
1080  auto cur_edge = start_edge->next_;
1081  while (start_edge != cur_edge) {
1082  cur_edge->face_ = new_face;
1083  cur_edge = cur_edge->next_;
1084  }
1085  }
1086 
1087  face->edge_ = ab_edge_ptr;
1088 }
1089 
1097 inline shared_ptr<Vertex> graph::tearup_lines_in_half(Edge* edge, vector<shared_ptr<Vertex> >& a_half, vector<shared_ptr<Vertex> >& b_half) {
1098 
1099  a_half = vector<shared_ptr<Vertex> >(edge->vertices_.begin(), edge->vertices_.begin() + edge->vertices_.size() / 2);
1100  b_half = vector<shared_ptr<Vertex> >(edge->vertices_.begin() + edge->vertices_.size() / 2, edge->vertices_.end());
1101 
1102 
1103  auto a = a_half.back();
1104  auto b = b_half[0];
1105 
1106  auto new_vertex = make_shared<Vertex>(edge); //edge is going to this vertex //"edge" it is important because after adding vertex we add teh edge to the same direction (not face, face can be same anyway)
1107  new_vertex->index_ = ((edge->index_ / 100 == 0) || (edge->index_ % 100 == 0)) ? -1 : -2;
1108  new_vertex->x_ = (a->x_ + b->x_) / 2; new_vertex->y_ = (a->y_ + b->y_) / 2;
1109 
1110  new_vertex->shift_first = make_pair(new_vertex->x_ - a->x_, new_vertex->y_ - a->y_);
1111  new_vertex->shift_second = make_pair(new_vertex->x_ - b->x_, new_vertex->y_ - b->y_);
1112 
1113  vertices_.push_back(make_pair(new_vertex->x_, new_vertex->y_));
1114 
1115  a_half.push_back(new_vertex);
1116  reverse(a_half.begin(), a_half.end());
1117 
1118  b_half.push_back(new_vertex);
1119  rotate(b_half.rbegin(), b_half.rbegin() + 1, b_half.rend());
1120 
1121 
1122 
1123  return new_vertex;
1124 }
1125 
1126 
1131 inline void graph::add_vertex(Edge* edge) {
1132 
1133  auto opposite = edge->opposite_;
1134 
1135  vector<shared_ptr<Vertex> > a_half;
1136  vector<shared_ptr<Vertex> > b_half;
1137 
1138  tearup_lines_in_half(edge, a_half, b_half);
1139 
1140  edges.push_back(Edge(edge->next_, edge, opposite, b_half, edge->face_, edge->index_)); //new vertex to b, part of normal edge
1141  auto tob = &edges.back();
1142  segments.push_back(tob);
1143 
1144  edges.push_back(Edge(opposite->next_, opposite, edge, a_half, opposite->face_, opposite->index_)); //create from new_vertex to a, part of opposite
1145  auto toa = &edges.back();
1146  segments.push_back(toa);
1147 
1148  reverse(a_half.begin(), a_half.end());
1149  edge->vertices_ = a_half; //changing properties of edge
1150  edge->next_ = tob;
1151  edge->opposite_ = toa;
1152 
1153  reverse(b_half.begin(), b_half.end());
1154  opposite->vertices_ = b_half; //changing properties of opposite
1155  opposite->next_ = toa;
1156  opposite->opposite_ = tob;
1157 
1158 }
1159 
1160 
1165 inline void graph::delete_edge_back(bool outer_face_bool) {
1166 
1167  auto edge = edges.back();
1168  auto opposite = *edge.opposite_;
1169 
1170  auto a = edge.vertices_[0];
1171  auto b = edge.vertices_.back();
1172 
1173  auto face = edge.face_;
1174 
1175  auto froma = opposite.next_;
1176  auto toa = edge.prev_;
1177  auto fromb = edge.next_;
1178  auto tob = opposite.prev_;
1179 
1180  /*update faces first!*/
1181 
1182  auto cur_edge = opposite.next_;
1183  if (!outer_face_bool) {
1184  while (opposite != *cur_edge) {
1185  cur_edge->face_ = face;
1186  cur_edge = cur_edge->next_;
1187  }
1188  }
1189 
1190  //print_graph(this);
1191 
1192  /*recconect edges*/
1193  froma->prev_ = toa;
1194  toa->next_ = froma;
1195  fromb->prev_ = tob;
1196  tob->next_ = fromb;
1197 
1198  /*update edges if there the bad ones*/
1199  a->to_ = toa;
1200  b->to_ = tob;
1201 
1202  face->edge_ = froma;
1203 
1204  outer_face = face; //just to end up with outer face
1205 
1206  /* delete the edge from list, pop from segments should be out of this function */
1207 
1208  for (int i = 1; i < edge.vertices_.size() - 1;i++) {
1209  vertices_.pop_back();
1210  }
1211 
1212  segments.pop_back();segments.pop_back();
1213  edges.pop_back();edges.pop_back();
1214 
1215  //number_of_edges -= 2;
1216 }
1217 
1218 
1223 inline void graph::delete_vertex(Vertex* vertex) {
1224 
1225  // getting the right variables
1226  auto edge = vertex->to_;
1227 
1228  auto toa = edge->opposite_;
1229  auto tob = edge->next_;
1230  auto edge_opposite = tob->opposite_;
1231 
1232  auto a = toa->vertices_.back();
1233  auto b = tob->vertices_.back();
1234 
1235  // reconnecting edges and therefore removing the vertex
1236 
1237  vector<shared_ptr<Vertex> > former_vertices = edge->vertices_; former_vertices.pop_back();
1238  edge_opposite->vertices_.pop_back(); reverse(edge_opposite->vertices_.begin(), edge_opposite->vertices_.end());
1239 
1240  former_vertices.insert(former_vertices.end(), edge_opposite->vertices_.begin(), edge_opposite->vertices_.end());
1241 
1242  edge->vertices_ = former_vertices;reverse(former_vertices.begin(), former_vertices.end());
1243  edge_opposite->vertices_ = former_vertices; //reversed
1244  edge->next_ = tob->next_;
1245  edge_opposite->next_ = toa->next_;
1246 
1247  //setting opposites
1248  edge->opposite_ = edge_opposite;
1249  edge_opposite->opposite_ = edge;
1250 
1251  edge->face_->edge_ = edge;
1252  edge_opposite->face_->edge_ = edge_opposite;
1253 
1254  //removig the edges from the back of segments and edges
1255  //because of the order and recursive algorithm we know they are the last one
1256 
1257  vertices_.pop_back();
1258 
1259  segments.pop_back(); segments.pop_back();
1260  edges.pop_back(); edges.pop_back();
1261 
1262 }
1263 
1264 
1269 inline void graph::create_special_vertex(int index, int x, int y) {
1270 
1271  vector<shared_ptr<Vertex> > special_vertices;
1272 
1273  /*create vertices with coordinates*/
1274  for (int i = 0; i < number_of_vertices - 1;i++) {
1275  auto new_vertex = make_shared<Vertex>();
1276  new_vertex->index_ = index; //the real index of vertex
1277  new_vertex->x_ = x; new_vertex->y_ = y;
1278  special_vertices.push_back(new_vertex);
1279  }
1280 
1281 
1282  /* edges created */
1283  for (int i = 0; i < number_of_vertices - 1;i++) {
1284  auto first_vertex = special_vertices[i];
1285  auto second_vertex = special_vertices[(i + 1) % (number_of_vertices - 1)];
1286  edges.push_back(Edge(nullptr, nullptr, nullptr, vector<shared_ptr<Vertex> > {first_vertex, second_vertex}, outer_face, 100 * index + index));
1287  second_vertex->to_ = &edges.back();
1288  segments.push_back(&edges.back());
1289  }
1290 
1291  /* dependencies set */
1292  for (int i = 0; i < number_of_vertices - 1;i++) {
1293  special_vertices[i]->to_->prev_ = special_vertices[((i - 1) + (number_of_vertices - 1)) % (number_of_vertices - 1)]->to_;
1294  special_vertices[i]->to_->next_ = special_vertices[(i + 1) % (number_of_vertices - 1)]->to_;
1295  }
1296 
1297  /* outer face needs face*/
1298  outer_face->edge_ = &edges.back();
1299 
1300 }
1301 
1306 inline void graph::recolor_fingerprint(const string& fingerprint) { //fingerprint does include the first ro (0..n), otherwise do the first rotation manually
1307 
1308  for(int i = 0; i < number_of_vertices;i++){
1309  for (int j = 0; j < number_of_vertices - 1;j++) { //every vertex has n-1 around itself
1310  starts[i][fingerprint[i * (number_of_vertices - 1) + j] - '0'] = i * (number_of_vertices - 1) + j;
1311  }
1312  }
1313 }
1314 
1319  for (int i = 1; i < number_of_vertices;i++) {
1320  add_edge(segments[starts[0][i]]->vertices_[0], segments[starts[i][0]]->vertices_[0], outer_face, 0, i, make_pair(0, 0), make_pair(0, 0), true); //from vertex is that in rotation
1321  }
1322 }
1323 
1324 
1329 
1330  create_special_vertex(0, 0, 0); // zero ones
1331 
1332  coordinates_of_special_vertices = create_circle(150, 0, 0, number_of_vertices - 1);
1333 
1334  for (int i = 1; i < number_of_vertices;i++) { //the rest of a star
1335  create_special_vertex(i, coordinates_of_special_vertices[i - 1].x, coordinates_of_special_vertices[i - 1].y);
1336  vertices_.push_back(make_pair((int)coordinates_of_special_vertices[i - 1].x, (int)coordinates_of_special_vertices[i - 1].y));
1337  }
1338 }
1339 
1340 /*
1341 inline void graph::redirect_previous_segment(int a_index, int b_index, shared_ptr<Vertex> destination) {
1342  if (segments[segments.size() - 2]->index_ == 100 * a_index + b_index) {
1343 
1344  auto edge_to_change = segments[segments.size() - 2];
1345 
1346  auto a = edge_to_change->vertices_[0];
1347  auto b = edge_to_change->vertices_.back();
1348 
1349 
1350  //find which face is the the stable one by maintaning
1351  //pointer to i.e. prev_ edge of edge_to change
1352 
1353  auto prev = edge_to_change->prev_;
1354  delete_edge_back();
1355 
1356  if(print_bool)
1357  write_coordinates();
1358 
1359  auto face = prev->face_;
1360 
1361  // swaping to_ attribute of divided edge new vertex is important!
1362  segments[edges.size() - 1]->vertices_[0]->to_ = segments[edges.size() - 2]->prev_;
1363  add_edge(a, b, face, a_index, b_index, make_pair(0, 0), make_pair(0, 0));
1364  segments[edges.size() - 3]->vertices_[0]->to_ = segments[edges.size() - 3]->prev_;
1365  if (print_bool)
1366  write_coordinates();
1367  }
1368 }
1369 */
1370 
1371 
1381 inline void graph::find_the_way_to_intersect(int s_index, int t_index, int a, int b) {
1382 
1383  auto seg = segments[s_index]->next_;
1384 
1385 
1386  while (seg != segments[s_index]) { //the first doesnt have to be considered because it is either beggining segment so it cannot be intersected or it has been already intersected
1387 
1388  if (seg == segments[t_index]) {
1389 
1390  auto shift_previous = find_vertex_in_right_direction(segments[s_index]->vertices_[0],
1391  make_pair(segments[segments.size() - 3]->vertices_[1]->x_ - segments[segments.size() - 3]->vertices_[0]->x_,
1392  segments[segments.size() - 3]->vertices_[1]->y_ - segments[segments.size() - 3]->vertices_[0]->y_
1393  ));
1394  if (segments[s_index]->vertices_[0]->index_ != -1)
1395  shift_previous = make_pair(0, 0);
1396 
1397  add_edge(
1398  segments[s_index]->vertices_[0],
1399  segments[t_index]->vertices_[0],
1400  segments[s_index]->face_,
1401  a,
1402  b,
1403  shift_previous,
1404  make_pair(0, 0)
1405  );
1406  if (print_bool)
1407  write_coordinates();
1408 
1409  if (b < number_of_vertices - 1) {
1410  find_the_way_to_intersect(starts[a][b + 1], starts[b + 1][a], a, b + 1);
1411 
1412  if (done) return;
1413 
1414  }
1415  else if (a < number_of_vertices - 2) {
1416  find_the_way_to_intersect(starts[a + 1][a + 2], starts[a + 2][a + 1], a + 1, a + 2);
1417 
1418  if (done) return;
1419  }
1420  else {
1421 
1422  //print_graph(this);
1423  realized++;
1424  done = true;
1425  return;
1426 
1427  }
1428 
1429  delete_edge_back();
1430  if (print_bool)
1431  write_coordinates();
1432  }
1433 
1434  auto index_first_end = seg->index_ / 100;
1435  auto index_second_end = seg->index_ % 100;
1436 
1437  if (!blocked[min(a, b)][max(a, b)][min(index_first_end, index_second_end)][max(index_first_end, index_second_end)]) { //if there is same index, always true // it can be divided edge so we need to look at the ends of it to get the indices of vertices
1438 
1439  //intersecting
1440  blocked[min(a, b)][max(a, b)][min(index_first_end, index_second_end)][max(index_first_end, index_second_end)] = true;
1441 
1442  add_vertex(seg);
1443 
1444  auto shift_previous = find_vertex_in_right_direction(segments[s_index]->vertices_[0],
1445  make_pair(segments[segments.size() - 5]->vertices_[1]->x_ - segments[segments.size() - 5]->vertices_[0]->x_,
1446  segments[segments.size() - 5]->vertices_[1]->y_ - segments[segments.size() - 5]->vertices_[0]->y_
1447  ));
1448 
1449  auto shift_next = find_vertex_in_right_direction(segments[edges.size() - 2]->vertices_[0],
1450  make_pair(segments[edges.size() - 2]->vertices_[1]->x_ - segments[edges.size() - 2]->vertices_[0]->x_,
1451  segments[edges.size() - 2]->vertices_[1]->y_ - segments[edges.size() - 2]->vertices_[0]->y_));
1452 
1453  if (segments[s_index]->vertices_[0]->index_ != -1)
1454  shift_previous = make_pair(0, 0);
1455 
1456  if (segments[edges.size() - 1]->vertices_[0]->index_ != -1)
1457  shift_next = make_pair(0, 0);
1458 
1459  add_edge(
1460  segments[s_index]->vertices_[0],
1461  segments[edges.size() - 1]->vertices_[0],
1462  segments[s_index]->face_,
1463  a,
1464  b,
1465  shift_previous,
1466  shift_next
1467  );
1468  if(print_bool)
1469  write_coordinates();
1470 
1471  /*important! changing to_ to the opposite direction */
1472  segments[edges.size() - 3]->vertices_[0]->to_ = segments[edges.size() - 3]->prev_;
1473 
1474  //try to go further
1475  find_the_way_to_intersect(edges.size() - 3, t_index, a, b); //it is 3rd from the end, because it was added as second in add_vertex and then 2 more were added in add_edge
1476  if (done) {
1477  blocked[min(a, b)][max(a, b)][min(index_first_end, index_second_end)][max(index_first_end, index_second_end)] = false;
1478  return;
1479  }
1480 
1481  //segments[edges.size() - 3]->vertices_[0]->to_ = segments[edges.size() - 3];
1482 
1483  //undo-intersect //not commutative!
1484  delete_edge_back();
1485  delete_vertex((seg->vertices_.back()).get());
1486  blocked[min(a, b)][max(a, b)][min(index_first_end, index_second_end)][max(index_first_end, index_second_end)] = false;
1487  if (print_bool)
1488  write_coordinates();
1489  }
1490  seg = seg->next_;
1491  }
1492 }
1493 
1494 inline long long factorial(int n) {
1495  return (n == 1 || n == 0) ? 1 : n * factorial(n - 1);
1496 }
1497 
1498 
1503  bool done = false;
1505 
1506  ifstream input_file;
1507 
1508  fingerprints(int n, int index) {
1509 
1510  string string_index = index < 10 ? "0" + to_string(index) : to_string(index);
1511  auto input_path = "data/graph"
1512  + to_string(n) + "_" + string_index + ".txt";
1513  cout << input_path << endl;
1514  input_file.open(input_path);
1515 
1516 
1517  if (!getline(input_file, rotation_system))
1518  done = true;
1519 
1520  }
1521 
1523  // Return state and then move to the next one until it is posible
1525  string get_next() {
1526 
1527  string previous_one = rotation_system;
1528 
1529  if (!getline(input_file, rotation_system)) {
1530  done = true;
1531  input_file.close();
1532  }
1533 
1534  return previous_one;
1535  }
1536 };
1537 
1545 inline bool are_there_ends(Edge* edge, int a, int b) {
1546  if (a > b) swap(a, b);
1547  if ((min(edge->index_ % 100, edge->index_ / 100) == a) && (max(edge->index_ % 100, edge->index_ / 100) == b))
1548  return true;
1549  return false;
1550 }
1551 
1552 //bool debug_bool = false;
1553 
1558 
1559  cout << counter++ << endl;
1560 
1561  vector<vector<vector<Edge> > > drawing_edges;
1562  drawing_edges.resize(number_of_vertices);
1563  for (int i = 0; i < number_of_vertices;i++)
1564  drawing_edges[i].resize(number_of_vertices);
1565 
1566  for (auto cur = edges.begin(); cur != edges.end();cur++) {
1567  int a = cur->index_ / 100;
1568  int b = cur->index_ % 100;
1569 
1570  drawing_edges[a][b].push_back(*cur);
1571  }
1572 
1573  for (int i = 0; i < number_of_vertices;i++) {
1574  for (int j = i + 1;j < number_of_vertices;j++) {
1575  for (int k = 0; k < drawing_edges[i][j].size();k++) {
1576  if (drawing_edges[i][j][k].vertices_.size() == 1)
1577  cout << "HELP" << endl;
1578  output_file << "( ";
1579  for (int l = 0; l < drawing_edges[i][j][k].vertices_.size();l++) {
1580  output_file
1581  << drawing_edges[i][j][k].vertices_[l]->x_ << " "
1582  << drawing_edges[i][j][k].vertices_[l]->y_ << " ";
1583  }
1584  output_file << ") ";
1585  }
1586  output_file << endl;
1587  }
1588  }
1589 
1590  output_file << "#" << endl;
1591 }
1592 
1593 
1601 
1602  for (int i = 0; i < number_of_vertices;i++) {
1603  for (int j = 0; j < number_of_vertices;j++) {
1604  for (int k = 0; k < number_of_vertices;k++) {
1605  for (int l = 0; l < number_of_vertices;l++) {
1606  set<int> tmp = { i, j, k, l };
1607  if (tmp.size() < 4) {
1608  blocked[i][j][k][l] = true;
1609  }
1610 
1611  }
1612  }
1613  }
1614  }
1615 
1616  auto generator_of_fingerprints = fingerprints(number_of_vertices, index);
1617  while (!generator_of_fingerprints.done) {
1618  auto fingerprint = generator_of_fingerprints.get_next();
1619 
1620  create_all_special_vertices();
1621 
1622  recolor_fingerprint(fingerprint);
1623  create_base_star();
1624 
1625 
1626  /*
1627  if (counter <= 600) {
1628  done = true;
1629  }
1630  */
1631 
1632  //else {
1633  find_the_way_to_intersect(starts[1][2], starts[2][1], 1, 2);
1634  //}
1635 
1636  if (done) {
1637  cout << "yes" << endl;
1638 
1639  write_coordinates();
1640 
1641  }
1642 
1643  vertices_.resize(0);
1644  most_away.resize(0);
1645 
1646  edges.resize(0); segments.resize(0);
1647  done = false;
1648  outer_face = make_shared<Face>();
1649  }
1650 
1651  close_files();
1652 
1653  cout << "realized " << realized << endl;
1654 }
1655 
#define EPSILON
Definition: functions.hpp:37
bool are_there_ends(Edge *edge, int a, int b)
Function to check whether the ends of edge are a and b.
Definition: functions.hpp:1545
pair< double, double > get_shift(shared_ptr< Vertex > vertex, pair< double, double > vect)
Function to generate shift perpendicular to given vector vect in order to be able to move same vertic...
Definition: functions.hpp:528
#define y
Definition: functions.hpp:41
double get_value(int a, int b, int c, shared_ptr< Vertex > point)
Get value of linear function f(x, y) = ax+by+c.
Definition: functions.hpp:571
void print_graph(graph *g)
Definition: functions.hpp:358
#define INF
Definition: functions.hpp:33
bool are_collinear(shared_ptr< Vertex > v1, shared_ptr< Vertex > v2, shared_ptr< Vertex > v3)
Definition: functions.hpp:614
bool if_two_segmetns_intersects(pair< shared_ptr< Vertex >, shared_ptr< Vertex > > line1, pair< shared_ptr< Vertex >, shared_ptr< Vertex > > line2)
Function to detect whether line1 and line2 intersect.
Definition: functions.hpp:280
void create_coordinates(const vector< shared_ptr< Vertex > > &points, vector< vector< double > > &distances)
Function to set distance Euclidian distance for all pair of points i, j in points into matrix distanc...
Definition: functions.hpp:305
bool compare(pair< double, double > a, pair< double, double > b)
Check whether the two pairs are "almost" the same.
Definition: functions.hpp:486
#define x
Definition: functions.hpp:40
bool is_on_right_side_of(shared_ptr< Vertex >asked_point, shared_ptr< Vertex > point, pair< double, double > vect, shared_ptr< Vertex > on_right_side)
Function to check whether asked_point and on_right_side points are on the same side of line given by ...
Definition: functions.hpp:584
void dijsktra(vector< shared_ptr< Vertex > > &points, vector< vector< double > > distances, vector< int > &parent)
Standart dijsktra algorithm returning shortest paths from vertex 0 with paths stored in vector parent...
Definition: functions.hpp:322
double distance(pair< double, double > a)
Definition: functions.hpp:428
vector< pair< double, double > > make_convex_hull(vector< pair< double, double > > vertices)
Function to create convex hull of vertices.
Definition: functions.hpp:447
pair< double, double > find_vertex_in_right_direction(shared_ptr< Vertex > vertex, pair< double, double > vect)
Get vertex perpendicular to vect from vertex and on the right side depending on the clockwise,...
Definition: functions.hpp:555
long long factorial(int n)
Definition: functions.hpp:1494
double det(pair< double, double > vec1, pair< double, double > vec2)
Fucntion to count the determinant.
Definition: functions.hpp:506
vector< pair< double, double > > create_circle(double radius, double cx, double cy, int n)
Function to create "dummy" vertices for one vertex.
Definition: functions.hpp:411
#define M_PI
Definition: functions.hpp:29
vector< vector< vector< vector< bool > > > > array_4D
Definition: functions.hpp:45
bool print_bool
Definition: functions.hpp:43
Structure to store the edge containing information about next_, prev_, opposite_ edges and vertices a...
Definition: functions.hpp:112
Edge * prev_
Definition: functions.hpp:116
Edge()
Definition: functions.hpp:123
bool operator!=(const Edge &a)
Definition: functions.hpp:132
bool operator==(const Edge &a)
Definition: functions.hpp:128
Edge(Edge *next, Edge *prev, Edge *opposite, vector< shared_ptr< Vertex > > vertices, shared_ptr< Face > face, int index)
Definition: functions.hpp:125
Edge * opposite_
Definition: functions.hpp:117
shared_ptr< Face > face_
Definition: functions.hpp:121
int index_
Definition: functions.hpp:113
vector< shared_ptr< Vertex > > vertices_
Definition: functions.hpp:119
Edge * next_
Definition: functions.hpp:115
Structure to store a face containing about one edge incident to it
Definition: functions.hpp:101
Edge * edge_
Definition: functions.hpp:102
Face(Edge *edge)
Definition: functions.hpp:106
Face()
Definition: functions.hpp:104
Class to store vertex, containing information about edge to_ going into it
Definition: functions.hpp:54
Vertex(double x, double y)
Definition: functions.hpp:66
Edge * to_
Definition: functions.hpp:55
double y_
Definition: functions.hpp:59
bool operator==(const Vertex &a)
Definition: functions.hpp:72
bool operator!=(const Vertex &a)
Definition: functions.hpp:76
bool operator==(const Vertex *a)
Definition: functions.hpp:89
Vertex(Edge *to)
Definition: functions.hpp:70
Vertex()
Definition: functions.hpp:64
bool operator==(Vertex *a)
Definition: functions.hpp:80
bool operator!=(Vertex *a)
Definition: functions.hpp:84
bool operator!=(const Vertex *a)
Definition: functions.hpp:93
double x_
Definition: functions.hpp:59
Structure for generating all fingerprints iteratively.
Definition: functions.hpp:1502
ifstream input_file
Definition: functions.hpp:1506
string rotation_system
Definition: functions.hpp:1504
fingerprints(int n, int index)
summary>
Definition: functions.hpp:1508
string get_next()
Definition: functions.hpp:1525
Main class to store all the information about graph, edges, vertices, ...
Definition: functions.hpp:141
graph(int n, int ii)
Definition: functions.hpp:171
ofstream output_file
Definition: functions.hpp:159
void find_the_way_to_intersect(int s_index, int t_index, int a, int b)
Main algorithm similar to described in psedocode in thesis. It recursively tries all the possible way...
Definition: functions.hpp:1381
vector< vector< int > > starts
Array which for given pair of vertice i, j return the index in vector segments so the "dummy" edge ("...
Definition: functions.hpp:250
int index
Definition: functions.hpp:165
vector< pair< double, double > > most_away
Definition: functions.hpp:153
void create_special_vertex(int index, int x, int y)
Creating the "dummy" vertex (circle) representing real vertex.
Definition: functions.hpp:1269
void delete_vertex(Vertex *a)
Deleting given intersection vertex.
Definition: functions.hpp:1223
void close_files()
Definition: functions.hpp:167
void create_base_star()
Function to create all edges incident to vertex 0.
Definition: functions.hpp:1318
void write_coordinates()
Function to write coordinates of graph into a file.
Definition: functions.hpp:1557
void recolor_fingerprint(const string &rotation)
Setting values of array starts to values of given fingerprint.
Definition: functions.hpp:1306
shared_ptr< Face > outer_face
Definition: functions.hpp:157
void update_most_away(vector< pair< double, double > > vertices)
Function to update the convex hull of vertices of a graph.
Definition: functions.hpp:496
void add_edge(shared_ptr< Vertex > a, shared_ptr< Vertex > b, shared_ptr< Face > face, int a_index, int b_index, pair< double, double > previous_vertex, pair< double, double > next_vertex, bool outer_face_bool=false)
Function to add edge between a and b.
Definition: functions.hpp:1033
void create_all_special_vertices()
Function to create all "dummy" vertices
Definition: functions.hpp:1328
array_4D blocked
4D array to check which edges already intersect
Definition: functions.hpp:244
shared_ptr< Vertex > tearup_lines_in_half(Edge *edge, vector< shared_ptr< Vertex > > &a_half, vector< shared_ptr< Vertex > > &b_half)
Function to tear up edge into two halves a_half and b_half.
Definition: functions.hpp:1097
list< Edge > edges
Definition: functions.hpp:155
vector< Edge * > segments
Vector to store (pointers on) edges.
Definition: functions.hpp:239
vector< shared_ptr< Vertex > > find_path_through_triangulation(shared_ptr< Vertex > a, shared_ptr< Vertex > b, shared_ptr< Face > face, int a_index, int b_index, pair< double, double > shift_previous, pair< double, double > shift_next, bool outer_face_bool=false)
Function to find correct way (preserving crossing properties) from vertex a to vertex b through the f...
Definition: functions.hpp:641
void create_all_possible_drawings()
Function to try all possible drawings, It tries all the pullings of edges for given fingerprint until...
Definition: functions.hpp:1600
vector< shared_ptr< Vertex > > find_shortest_path(const vector< vector< double > > &distances, vector< shared_ptr< Vertex > > &face_vertices)
Function to find shortest path between vertices (all_vertices) 0 and 1.
Definition: functions.hpp:376
void delete_edge_back(bool outer_face_bool=false)
Deleting the last added edge.
Definition: functions.hpp:1165
void add_vertex(Edge *edge)
Creating new vertec on the edge as a new intersection.
Definition: functions.hpp:1131
vector< pair< double, double > > coordinates_of_special_vertices
Definition: functions.hpp:163
vector< pair< double, double > > vertices_
Definition: functions.hpp:161