11 #include <unordered_map>
17 #include <unordered_set>
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>
24 BOOST_GEOMETRY_REGISTER_BOOST_TUPLE_CS(cs::cartesian)
29 #define M_PI 3.14159265358979323846
37 #define EPSILON 0.0001
45 using array_4D = vector<vector<vector<vector<bool> > > >;
61 pair<double, double> shift_first = make_pair(0, 0);
62 pair<double, double> shift_second = make_pair(0, 0);
73 return x_ == a.
x_ && y_ == a.
y_;
81 return a->
x_ == x_ && a->
y_ == y_;
90 return a->
x_ == x_ && a->
y_ == y_;
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) {}
133 return !(*
this == a);
144 int number_of_vertices = 0;
174 number_of_vertices = n;
175 outer_face = make_shared<Face>();
177 starts.resize(number_of_vertices);
178 for (
int i = 0; i < number_of_vertices;i++) {
179 starts[i].resize(number_of_vertices);
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;
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);
203 shared_ptr<Vertex> a,
204 shared_ptr<Vertex> b,
205 shared_ptr<Face> face,
208 pair<double, double> previous_vertex,
209 pair<double, double> next_vertex,
210 bool outer_face_bool =
false);
211 void add_vertex(
Edge* edge);
213 void delete_edge_back(
bool outer_face_bool =
false);
214 void delete_vertex(
Vertex* a);
217 shared_ptr<Vertex> tearup_lines_in_half(
219 vector<shared_ptr<Vertex> >& a_half,
220 vector<shared_ptr<Vertex> >& b_half
223 vector<shared_ptr<Vertex> > find_path_through_triangulation(
224 shared_ptr<Vertex> a,
225 shared_ptr<Vertex> b,
226 shared_ptr<Face> face,
229 pair<double, double> shift_previous,
230 pair<double, double> shift_next,
231 bool outer_face_bool =
false
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);
261 void create_all_possible_drawings();
263 void write_coordinates();
265 vector<shared_ptr<Vertex> > find_shortest_path(
const vector<vector<double> >& distances, vector<shared_ptr<Vertex> >& face_vertices);
269 void update_most_away(vector<pair<double, double> > vertices);
280 inline bool if_two_segmetns_intersects(pair<shared_ptr<Vertex>, shared_ptr<Vertex> > line1, pair<shared_ptr<Vertex>, shared_ptr<Vertex> > line2)
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_);
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_);
290 auto s = numS / denominator;
291 auto t = numT / denominator;
305 inline void create_coordinates(
const vector<shared_ptr<Vertex> >& points, vector<vector<double> >& distances) {
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_));
322 inline void dijsktra(vector<shared_ptr<Vertex> >& points, vector<vector<double> > distances, vector<int>& parent) {
324 vector<double> shortest;
325 shortest.resize(points.size());
327 priority_queue<pair<double, int>, vector<pair<double, int> >, greater<pair<double, int> > > pq;
328 vector<bool> visited;
329 visited.resize(points.size());
331 for (
int i = 0; i < points.size(); i++) {
336 pq.push(make_pair(shortest[0], 0));
338 while (!pq.empty()) {
339 auto top = pq.top();pq.pop();
341 if (visited[top.second])
continue;
342 visited[top.second] =
true;
344 for (
int w = 0; w < points.size();w++) {
345 if (top.second != w) {
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;
359 cout <<
"number of edges: " << g->
edges.size() << endl;
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;
376 inline vector<shared_ptr<Vertex> >
graph::find_shortest_path(
const vector<vector<double> > & distances, vector<shared_ptr<Vertex > >& all_vertices) {
389 parent.resize(all_vertices.size());
390 dijsktra(all_vertices, distances, parent);
392 vector<shared_ptr<Vertex> > result;
396 result.push_back(all_vertices[v]);
399 result.push_back(all_vertices[0]);
411 inline vector<pair<double, double> >
create_circle(
double radius,
double cx,
double cy,
int n) {
412 vector<pair<double, double> > circle;
414 double unit_angle = (double)360 / n;
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))));
429 return sqrt((a.x ) * (a.x) + (a.y) * (a.y ));
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));
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_));
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;
454 vector<point> points;
456 for(
int i = 0; i < vertices.size();i++){
458 boost::make_tuple<double, double>(vertices[i].
x, vertices[i].
y));
461 boost::geometry::assign_points(poly, points);
464 boost::geometry::convex_hull(poly, hull);
472 vector<pair<double, double> > result;
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()));
486 inline bool compare(pair<double, double> a, pair<double, double> b) {
506 inline double det(pair<double, double> vec1, pair<double, double> vec2) {
507 return vec1.x * vec2.y - vec1.y * vec2.x;
528 inline pair<double, double>
get_shift(shared_ptr<Vertex> vertex, pair<double, double> vect) {
530 pair<double, double> first_neg_vect;
531 pair<double, double> second_neg_vect;
535 first_neg_vect = make_pair(-vect.y, vect.x);
536 second_neg_vect = make_pair(vect.y, -vect.x);
539 if (
det(vect, first_neg_vect) < 0) {
540 return make_pair(10 *
EPSILON * first_neg_vect.x, 10 *
EPSILON * first_neg_vect.y);
543 return make_pair(10 *
EPSILON * second_neg_vect.x, 10 *
EPSILON * second_neg_vect.y);
558 return make_pair(100 * (shift.x /
distance(shift)), 100 * ((shift.y /
distance(shift))));
571 inline double get_value(
int a,
int b,
int c, shared_ptr<Vertex> point) {
572 return a * point->x_ + b * point->y_ + c;
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) {
588 double c = -(a * point->x_ + b * point->y_);
614 inline bool are_collinear(shared_ptr<Vertex> v1, shared_ptr<Vertex> v2, shared_ptr<Vertex> v3) {
621 double a = v1->x_ * (v2->y_ - v3->y_) + v2->x_ * (v3->y_ - v1->y_) + v3->x_ * (v1->y_ - v2->y_);
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;
655 vector<shared_ptr<Vertex> > vertices;
657 if (!outer_face_bool) {
659 bool second_outer_face_bool =
true;
661 update_most_away(vertices_);
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);
668 while (cur != start) {
669 faces_vertices.insert(faces_vertices.end(), cur->vertices_.begin(), cur->vertices_.end() - 1);
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());
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());
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();
694 rotate(faces_vertices.begin(), faces_vertices.begin() + mn_index, faces_vertices.end());
699 faces_vertices.push_back(faces_vertices[0]);
701 vector<pair<double, double> > coords;
702 vector<pair<double, double> > indices_coords;
704 vector<bool> local_most_away; local_most_away.resize(most_away.size());
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)
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))) {
715 make_pair(faces_vertices[i]->x_ - faces_vertices[i - 1]->x_,
716 faces_vertices[i]->y_ - faces_vertices[i - 1]->y_));
718 indices_coords.push_back(make_pair(
719 faces_vertices[i]->x_ + shift.x,
720 faces_vertices[i]->y_ + shift.y
724 indices_coords.push_back(make_pair(faces_vertices[i]->x_, faces_vertices[i]->y_));
726 coords.push_back(make_pair(faces_vertices[i]->x_, faces_vertices[i]->y_));
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;
736 for (
int j = 0; j < most_away.size(); j++) {
737 if (!local_most_away[j]) {
738 second_outer_face_bool =
false;
745 if (second_outer_face_bool) {
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) {
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_);
758 rotate(outer_vertices.begin(), outer_vertices.begin() + index_min, outer_vertices.end());
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_));
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_));
770 vector<vector<pair<double, double> > > polygon{ indices_coords };
772 std::vector<int> indices = mapbox::earcut<int>(polygon);
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];
793 set<pair<double, double> > visited_vertices;
795 auto mids = vector<shared_ptr<Vertex> >();
796 for (
int i = 0; i < indices.size(); i += 3){
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_))
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)))
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)))
811 !(!second_outer_face_bool && (abs(indices[i + j] - indices[i + ((j + 1) % 3)]) == coords.size() - 2))
813 (abs(indices[i + j] - indices[i + ((j + 1) % 3)]) != 1)
815 visited_vertices.insert(make_pair(vertex->x_, vertex->y_));
816 mids.push_back(vertex);
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());
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);
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);
851 for (
int i = 0; i < indices.size(); i += 3){
853 vector<int> triangle_indices;
854 bool contains_a =
false;
855 bool contains_b =
false;
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)))
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)))
868 !(!second_outer_face_bool && (abs(indices[i + j] - indices[i + ((j + 1) % 3)]) == coords.size() - 2))
870 (abs(indices[i + j] - indices[i + ((j + 1) % 3)]) != 1)
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);
877 visited_vertices2.insert(make_pair(make_pair(vertex->x_, vertex->y_), mid_index));
878 triangle_indices.push_back(mid_index);
882 if (
distance(coords[indices[i + (j % 3)]], make_pair(a->x_, a->y_)) <
EPSILON) {
886 if (
distance(coords[indices[i + (j % 3)]], make_pair(b->x_, b->y_)) <
EPSILON) {
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]]);
898 for (
int u = 0; u < triangle_indices.size(); u++) {
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]]);
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]]);
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))
918 ((b->x_ == coords[indices[i + ((j + 1) % 3)]].x) && (b->y_ == coords[indices[i + ((j + 1) % 3)]].y))
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))
931 ((a->x_ == coords[indices[i + ((j + 1) % 3)]].x) && (a->y_ == coords[indices[i + ((j + 1) % 3)]].y))
941 auto next_vertex = make_shared<Vertex>();
943 next_vertex->x_ = b->x_ + shift_next.x;
944 next_vertex->y_ = b->y_ + shift_next.y;
945 if (b->index_ == -1) {
947 distances[1][0] =
INF;
948 distances[0][1] =
INF;
950 for (
int i = 2; i < distances.size(); i++) {
952 distances[1][i] =
INF;
953 distances[i][1] =
INF;
959 auto previous_vertex = make_shared<Vertex>();
960 previous_vertex->x_ = a->x_ + shift_previous.x;
961 previous_vertex->y_ = a->y_ + shift_previous.y;
962 if (a->index_ == -1) {
964 distances[0][1] =
INF;
965 distances[1][0] =
INF;
967 for (
int i = 2; i < distances.size(); i++) {
969 distances[0][i] =
INF;
970 distances[i][0] =
INF;
975 vertices = find_shortest_path(distances, all_vertices);
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]);
983 vertices = temp_uniques;
997 vector<shared_ptr<Vertex> > non_colinear;
998 non_colinear.push_back(vertices[0]); non_colinear.push_back(vertices[1]);
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]);
1004 non_colinear.push_back(vertices[i]);
1007 vertices = non_colinear;
1016 return vector<shared_ptr<Vertex> >{ b, a };
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) {
1035 Edge* toa =
nullptr, * tob =
nullptr, * froma =
nullptr, * fromb =
nullptr;
1043 auto vertices = find_path_through_triangulation(a, b, face, a_index, b_index, shift_previous, shift_next, outer_face_bool);
1045 for (
int i = 1; i < vertices.size() - 1; i++) {
1046 vertices_.push_back(make_pair(vertices[i]->x_, vertices[i]->y_));
1049 auto new_face = !outer_face_bool ? make_shared<Face>() : outer_face;
1051 reverse(vertices.begin(), vertices.end());
1052 Edge ab_edge(fromb, toa,
nullptr, vertices, face, a_index*100 + b_index);
1053 edges.push_back(ab_edge);
1054 Edge* ab_edge_ptr = &edges.back();
1055 segments.push_back(ab_edge_ptr);
1059 reverse(vertices.begin(), vertices.end());
1060 Edge ba_edge(froma, tob, ab_edge_ptr, vertices, new_face, b_index*100 + a_index);
1061 edges.push_back(ba_edge);
1062 Edge* ba_edge_ptr = &edges.back();
1063 segments.push_back(ba_edge_ptr);
1068 new_face->edge_ = ba_edge_ptr;
1071 froma->
prev_ = ba_edge_ptr;
1072 toa->
next_ = ab_edge_ptr;
1073 fromb->
prev_ = ab_edge_ptr;
1074 tob->
next_ = ba_edge_ptr;
1078 if (!outer_face_bool) {
1079 auto start_edge = ba_edge_ptr;
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_;
1087 face->edge_ = ab_edge_ptr;
1103 auto a = a_half.back();
1106 auto new_vertex = make_shared<Vertex>(edge);
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;
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_);
1113 vertices_.push_back(make_pair(new_vertex->x_, new_vertex->y_));
1115 a_half.push_back(new_vertex);
1116 reverse(a_half.begin(), a_half.end());
1118 b_half.push_back(new_vertex);
1119 rotate(b_half.rbegin(), b_half.rbegin() + 1, b_half.rend());
1135 vector<shared_ptr<Vertex> > a_half;
1136 vector<shared_ptr<Vertex> > b_half;
1138 tearup_lines_in_half(edge, a_half, b_half);
1141 auto tob = &edges.back();
1142 segments.push_back(tob);
1144 edges.push_back(
Edge(opposite->next_, opposite, edge, a_half, opposite->
face_, opposite->index_));
1145 auto toa = &edges.back();
1146 segments.push_back(toa);
1148 reverse(a_half.begin(), a_half.end());
1153 reverse(b_half.begin(), b_half.end());
1154 opposite->vertices_ = b_half;
1155 opposite->next_ = toa;
1156 opposite->opposite_ = tob;
1167 auto edge = edges.back();
1168 auto opposite = *edge.opposite_;
1170 auto a = edge.vertices_[0];
1171 auto b = edge.vertices_.back();
1173 auto face = edge.face_;
1175 auto froma = opposite.next_;
1176 auto toa = edge.prev_;
1177 auto fromb = edge.next_;
1178 auto tob = opposite.prev_;
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_;
1202 face->edge_ = froma;
1208 for (
int i = 1; i < edge.vertices_.size() - 1;i++) {
1209 vertices_.pop_back();
1212 segments.pop_back();segments.pop_back();
1213 edges.pop_back();edges.pop_back();
1226 auto edge = vertex->
to_;
1229 auto tob = edge->
next_;
1233 auto b = tob->vertices_.back();
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());
1240 former_vertices.insert(former_vertices.end(), edge_opposite->vertices_.begin(), edge_opposite->vertices_.end());
1242 edge->vertices_ = former_vertices;reverse(former_vertices.begin(), former_vertices.end());
1243 edge_opposite->vertices_ = former_vertices;
1244 edge->next_ = tob->next_;
1245 edge_opposite->next_ = toa->next_;
1248 edge->opposite_ = edge_opposite;
1249 edge_opposite->opposite_ = edge;
1251 edge->face_->edge_ = edge;
1252 edge_opposite->face_->edge_ = edge_opposite;
1257 vertices_.pop_back();
1259 segments.pop_back(); segments.pop_back();
1260 edges.pop_back(); edges.pop_back();
1271 vector<shared_ptr<Vertex> > special_vertices;
1274 for (
int i = 0; i < number_of_vertices - 1;i++) {
1275 auto new_vertex = make_shared<Vertex>();
1276 new_vertex->index_ = index;
1277 new_vertex->x_ =
x; new_vertex->y_ =
y;
1278 special_vertices.push_back(new_vertex);
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());
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_;
1298 outer_face->edge_ = &edges.back();
1308 for(
int i = 0; i < number_of_vertices;i++){
1309 for (
int j = 0; j < number_of_vertices - 1;j++) {
1310 starts[i][fingerprint[i * (number_of_vertices - 1) + j] -
'0'] = i * (number_of_vertices - 1) + j;
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);
1330 create_special_vertex(0, 0, 0);
1332 coordinates_of_special_vertices =
create_circle(150, 0, 0, number_of_vertices - 1);
1334 for (
int i = 1; i < number_of_vertices;i++) {
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));
1383 auto seg = segments[s_index]->next_;
1386 while (seg != segments[s_index]) {
1388 if (seg == segments[t_index]) {
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_
1394 if (segments[s_index]->vertices_[0]->index_ != -1)
1395 shift_previous = make_pair(0, 0);
1398 segments[s_index]->vertices_[0],
1399 segments[t_index]->vertices_[0],
1400 segments[s_index]->face_,
1407 write_coordinates();
1409 if (b < number_of_vertices - 1) {
1410 find_the_way_to_intersect(starts[a][b + 1], starts[b + 1][a], a, b + 1);
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);
1431 write_coordinates();
1434 auto index_first_end = seg->index_ / 100;
1435 auto index_second_end = seg->index_ % 100;
1437 if (!blocked[min(a, b)][max(a, b)][min(index_first_end, index_second_end)][max(index_first_end, index_second_end)]) {
1440 blocked[min(a, b)][max(a, b)][min(index_first_end, index_second_end)][max(index_first_end, index_second_end)] =
true;
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_
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_));
1453 if (segments[s_index]->vertices_[0]->index_ != -1)
1454 shift_previous = make_pair(0, 0);
1456 if (segments[edges.size() - 1]->vertices_[0]->index_ != -1)
1457 shift_next = make_pair(0, 0);
1460 segments[s_index]->vertices_[0],
1461 segments[edges.size() - 1]->vertices_[0],
1462 segments[s_index]->face_,
1469 write_coordinates();
1472 segments[edges.size() - 3]->vertices_[0]->to_ = segments[edges.size() - 3]->prev_;
1475 find_the_way_to_intersect(edges.size() - 3, t_index, a, b);
1477 blocked[min(a, b)][max(a, b)][min(index_first_end, index_second_end)][max(index_first_end, index_second_end)] =
false;
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;
1488 write_coordinates();
1495 return (n == 1 || n == 0) ? 1 : n *
factorial(n - 1);
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);
1517 if (!getline(input_file, rotation_system))
1527 string previous_one = rotation_system;
1529 if (!getline(input_file, rotation_system)) {
1534 return previous_one;
1546 if (a > b) swap(a, b);
1559 cout << counter++ << endl;
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);
1566 for (
auto cur = edges.begin(); cur != edges.end();cur++) {
1567 int a = cur->index_ / 100;
1568 int b = cur->index_ % 100;
1570 drawing_edges[a][b].push_back(*cur);
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++) {
1581 << drawing_edges[i][j][k].vertices_[l]->x_ <<
" "
1582 << drawing_edges[i][j][k].vertices_[l]->y_ <<
" ";
1584 output_file <<
") ";
1586 output_file << endl;
1590 output_file <<
"#" << endl;
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;
1616 auto generator_of_fingerprints =
fingerprints(number_of_vertices, index);
1617 while (!generator_of_fingerprints.done) {
1618 auto fingerprint = generator_of_fingerprints.get_next();
1620 create_all_special_vertices();
1622 recolor_fingerprint(fingerprint);
1633 find_the_way_to_intersect(starts[1][2], starts[2][1], 1, 2);
1637 cout <<
"yes" << endl;
1639 write_coordinates();
1643 vertices_.resize(0);
1644 most_away.resize(0);
1646 edges.resize(0); segments.resize(0);
1648 outer_face = make_shared<Face>();
1653 cout <<
"realized " << realized << endl;
#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