Subject: [Boost-commit] svn:boost r80647 - trunk/boost/polygon/detail
From: lucanus.j.simonson_at_[hidden]
Date: 2012-09-22 18:08:44
Author: ljsimons
Date: 2012-09-22 18:08:43 EDT (Sat, 22 Sep 2012)
New Revision: 80647
URL: http://svn.boost.org/trac/boost/changeset/80647
Log:
added support for pseudo splits, improved existence predicate and added search for 2nd order split events
Text files modified:
trunk/boost/polygon/detail/skeleton_detail.hpp | 203 +++++++++++++++++++++++++++++++++------
1 files changed, 170 insertions(+), 33 deletions(-)
Modified: trunk/boost/polygon/detail/skeleton_detail.hpp
==============================================================================
--- trunk/boost/polygon/detail/skeleton_detail.hpp (original)
+++ trunk/boost/polygon/detail/skeleton_detail.hpp 2012-09-22 18:08:43 EDT (Sat, 22 Sep 2012)
@@ -157,14 +157,14 @@
future_intersection* parent2;
//refer back to the edge between the target and its next
future_intersection* split_on_next; //if null is an edge event
-
+
bool operator<(const event& that) const {
debug1("event::operator<");
- return distance < that.distance;
+ return distance < that.distance;
}
bool operator>(const event& that) const {
debug1("event::operator>");
- return distance > that.distance;
+ return distance > that.distance;
}
output_coordinate_type x() const { return point.x(); }
@@ -271,6 +271,25 @@
//static member functions
+ static void find_split_event(future_intersection* first, future_intersection* second, event_queue_type& event_queue) {
+ if(orientation(first->edge, second->edge) < 1) {
+ //std::cout << "initialize reflex vertex\n";
+ future_intersection* inner = second->next->next;
+ while(inner != second) {
+ event e2;
+ if(compute_split_event(e2, second, inner)) {
+ if(e2.distance <= e2.parent->active_distance || e2.parent->active_distance < 0) {
+ //split event has no parent2
+ std::cout << "inserting split event\n";
+ event_queue.push(e2);
+ e2.parent->active_distance = e2.distance;
+ }
+ }
+ inner = inner->next;
+ }
+ }
+ }
+
//ORIGINAL POLYGON EDGES
//simply copy the original polygon edges into the future intersection edge pair data structure
static void initialize_skeleton_edges(std::vector<skeleton_node*>& skeleton,
@@ -304,22 +323,7 @@
current = head;
do {
debug1("loop");
- if(orientation(current->prev->edge, current->edge) < 1) {
- //std::cout << "initialize reflex vertex\n";
- future_intersection* inner = current->next->next;
- while(inner != current) {
- event e2;
- if(compute_split_event(e2, current, inner)) {
- if(e2.distance <= e2.parent->active_distance || e2.parent->active_distance < 0) {
- //split event has no parent2
- std::cout << "inserting split event\n";
- event_queue.push(e2);
- e2.parent->active_distance = e2.distance;
- }
- }
- inner = inner->next;
- }
- }
+ find_split_event(current->prev, current, event_queue);
event e;
if(compute_edge_event(e, current, current->next, domain)) {
if((e.distance <= e.parent->active_distance || e.parent->active_distance < 0) &&
@@ -439,21 +443,36 @@
return false;
if(orientation(e2, point) <= 0)
return false;
+ if(orientation(e3, point) <= 0)
+ return false;
if(orientation(e4, point) <= 0)
return false;
+ if(orientation(e5, point) <= 0)
+ return false;
debug1("passed simple orientation tests");
//test that the point is on the correct side of the besector of e3,e4 and e4,e5
//it should be clockwise the bisector of e3,e4 and counterclockwise the bisector of e4,e5
//if e3,e4/e4e5 are concave then the correct sides will be reversed
print_segment(e3);
print_segment(e4);
- print_segment(segment2);
- std::cout << orientation(e3, e4) << " " << orientation(segment2, point) << std::endl;
- if(orientation(e3, e4) == orientation(segment2, point))
+ //print_segment(segment2);
+ if((distance_squared_to_line(point, e4) - distance_squared_to_line(point, e3)) > 1e-6)
return false;
+ // std::cout << orientation(e3, e4) << " " << orientation(segment2, point) << std::endl;
+ // if(orientation(e3, e4) == orientation(segment2, point))
+ // return false;
debug1("passed complex orientation test1");
- if(orientation(e4, e5) != orientation(segment3, point))
+ print_segment(e4);
+ print_segment(e5);
+ print_segment(segment3);
+ std::cout << distance_squared_to_line(point, e4) << " " << distance_squared_to_line(point, e5) << "\n";
+ std::cout << (distance_squared_to_line(point, e4) > distance_squared_to_line(point, e5)) << "\n";
+ std::cout << (distance_squared_to_line(point, e4) - distance_squared_to_line(point, e5)) << std::endl;
+ std::cout << (distance_squared_to_line(point, e4) - distance_squared_to_line(point, e5) > 1e-6) << std::endl;
+ if((distance_squared_to_line(point, e4) - distance_squared_to_line(point, e5)) > 1e-6)
return false;
+ //if(orientation(e4, e5) != orientation(segment3, point))
+ // return false;
debug1("passed complex orientation test2");
//we seem to have a good split event point
return true;
@@ -490,6 +509,7 @@
if(compute_split_event_point(e, first->prev->edge, first->edge, opposite->prev->edge, opposite->edge, opposite->next->edge)) {
std::cout << "found split event point\n";
e.parent = first;
+ e.parent2 = first->prev;
e.split_on_next = opposite;
return true;
}
@@ -582,15 +602,9 @@
std::cout << "split event " << current_event.point.x() << " " << current_event.point.y() << std::endl;
print_ring(current_event.parent);
- //create one new skeleton node with the event parent future intersection's parent-node connected to it
- skeleton.push_back(new skeleton_node(current_event.point));
- current_event.parent->parent_node->add_edge(skeleton.back());
- std::cout << current_event.parent->parent_node->label << "->" << skeleton.back()->label << std::endl;
- skeleton.back()->add_edge(current_event.parent->parent_node);
- current_event.parent->parent_node = skeleton.back();
-
//if the split_on_next edge was previously split it will have a circular linked list of potential
//future intersections that we need to search for the right one
+ bool found = false;
if(current_event.split_on_next->next_split_edge) {
future_intersection* current = current_event.split_on_next;
do{
@@ -601,12 +615,99 @@
if(compute_split_event(e2, current_event.parent, current)) {
debug1("found correct split edge");
current_event.split_on_next = current;
+ found = true;
break;
}
}
current = current->next_split_edge;
} while (current != current_event.split_on_next);
+ } else {
+ found = true;
}
+ if(!found)
+ return;
+ //this is the dual split event of a pseudo split
+ if(current_event.parent->prev != current_event.parent2)
+ return;
+ //check for pseudo split
+ std::cout << distance_squared_to_line(current_event.point, current_event.split_on_next->edge) << std::endl;
+ std::cout << distance_squared_to_line(current_event.point, current_event.split_on_next->next->edge) << std::endl;
+
+ if(abs(distance_squared_to_line(current_event.point, current_event.split_on_next->edge) -
+ distance_squared_to_line(current_event.point, current_event.split_on_next->next->edge)) < 1e-6) {
+ std::cout << "pseudo split 1\n";
+
+ skeleton.push_back(new skeleton_node(current_event.point));
+ current_event.parent->parent_node->add_edge(skeleton.back());
+ std::cout << current_event.parent->parent_node->label << "->" << skeleton.back()->label << std::endl;
+ skeleton.back()->add_edge(current_event.parent->parent_node);
+ current_event.parent->parent_node = skeleton.back();
+
+ skeleton.push_back(new skeleton_node(current_event.point));
+ current_event.split_on_next->next->parent_node->add_edge(skeleton.back());
+ std::cout << current_event.split_on_next->next->parent_node->label << "->" << skeleton.back()->label << std::endl;
+ skeleton.back()->add_edge(current_event.split_on_next->next->parent_node);
+ current_event.split_on_next->next->parent_node = skeleton.back();
+
+ skeleton.back()->add_edge(skeleton[skeleton.size()-2]);
+ skeleton[skeleton.size()-2]->add_edge(skeleton.back());
+
+ current_event.parent->prev = current_event.split_on_next;
+ current_event.parent2->next = current_event.split_on_next->next;
+ current_event.split_on_next->next->prev = current_event.parent2;
+ current_event.split_on_next->next = current_event.parent;
+
+ current_event.parent->active_distance = -1;
+ current_event.parent2->active_distance = -1;
+ current_event.parent->prev->active_distance = -1;
+ current_event.parent2->next->active_distance = -1;
+
+ find_edge_event(current_event.parent->prev, current_event.parent, event_queue, domain);
+ find_edge_event(current_event.parent, current_event.parent->next, event_queue, domain);
+ find_edge_event(current_event.parent2, current_event.parent2->next, event_queue, domain);
+ find_edge_event(current_event.parent2->next, current_event.parent2->next->next, event_queue, domain);
+ find_split_event(current_event.parent->prev, current_event.parent, event_queue);
+ find_split_event(current_event.parent2, current_event.parent2->next, event_queue);
+ print_ring(current_event.parent);
+ print_ring(current_event.parent2);
+ return;
+ }
+ if(abs(distance_squared_to_line(current_event.point, current_event.split_on_next->edge) -
+ distance_squared_to_line(current_event.point, current_event.split_on_next->prev->edge)) < 1e-6) {
+ //event point is on the boundary of the "zone" of the opposite edge
+ std::cout << "pseudo split 2\n";
+ skeleton.push_back(new skeleton_node(current_event.point));
+ current_event.parent->parent_node->add_edge(skeleton.back());
+ std::cout << current_event.parent->parent_node->label << "->" << skeleton.back()->label << std::endl;
+ skeleton.back()->add_edge(current_event.parent->parent_node);
+ current_event.parent->parent_node = skeleton.back();
+
+ skeleton.push_back(new skeleton_node(current_event.point));
+ current_event.split_on_next->parent_node->add_edge(skeleton.back());
+ std::cout << current_event.split_on_next->parent_node->label << "->" << skeleton.back()->label << std::endl;
+ skeleton.back()->add_edge(current_event.split_on_next->parent_node);
+ current_event.split_on_next->parent_node = skeleton.back();
+
+
+
+ current_event.parent->prev = current_event.split_on_next->prev;
+ current_event.parent2->next = current_event.split_on_next;
+ current_event.split_on_next->prev->next = current_event.parent;
+ current_event.split_on_next->prev = current_event.parent2;
+ find_edge_event(current_event.parent->prev, current_event.parent, event_queue, domain);
+ find_edge_event(current_event.parent, current_event.parent->next, event_queue, domain);
+ find_edge_event(current_event.parent2, current_event.parent2->next, event_queue, domain);
+ find_edge_event(current_event.parent2->next, current_event.parent2->next->next, event_queue, domain);
+ print_ring(current_event.parent);
+ print_ring(current_event.parent2);
+ return;
+ }
+ //create one new skeleton node with the event parent future intersection's parent-node connected to it
+ skeleton.push_back(new skeleton_node(current_event.point));
+ current_event.parent->parent_node->add_edge(skeleton.back());
+ std::cout << current_event.parent->parent_node->label << "->" << skeleton.back()->label << std::endl;
+ skeleton.back()->add_edge(current_event.parent->parent_node);
+ current_event.parent->parent_node = skeleton.back();
//event parent node is not dead
//create one new future intersection associated with the with a copy of the "opposite" edge as its edge
@@ -644,8 +745,13 @@
find_edge_event(current_event.split_on_next->next, current_event.split_on_next->next->next, event_queue, domain);
print_ring(current_event.split_on_next);
print_ring(new_active);
+
+ //find split event here to handle ties between reflex vertices that generate a new reflect vertex
+ //find_split_event(current_event.parent->prev, current_event.parent->next, event_queue);
} else {
//edge event
+ if(current_event.parent->next != current_event.parent2)
+ return;
std::cout << "event " << current_event.point.x() << " " << current_event.point.y() << std::endl;
std::cout << current_event.parent->parent_node->label << " " << current_event.parent2->parent_node->label << std::endl;
skeleton.push_back(new skeleton_node(current_event.point));
@@ -676,11 +782,11 @@
}
current_event.parent->active_distance = -1;
current_event.parent2->active_distance = -1;
- //the following two blocks should be refactored
find_edge_event(current_event.parent->prev, current_event.parent->next, event_queue, domain);
find_edge_event(current_event.parent->next, current_event.parent->next->next, event_queue, domain);
- //TODO, find split event here to handle ties between reflex vertices that generate a new reflect vertex
+ //we may need to search i-2 and i+2 for edge events
+
}
}
@@ -694,7 +800,7 @@
if(bound >=0 && current_event.distance > bound)
break;
if(!current_event.parent->is_dead &&
- (current_event.parent2 == 0x0 || !current_event.parent2->is_dead))
+ !current_event.parent2->is_dead)
process_event(current_event, skeleton, all_faces, event_queue, domain);
}
}
@@ -976,6 +1082,37 @@
delete *itr;
skeleton.clear();
+ {
+ point_data<coordinate_type> pts[] = {point_data<coordinate_type>(100, 201),
+ point_data<coordinate_type>(120, 220),
+ point_data<coordinate_type>(101, 200),
+ point_data<coordinate_type>(299, 200),
+ point_data<coordinate_type>(280, 220),
+ point_data<coordinate_type>(300, 201),
+ point_data<coordinate_type>(300, 500),
+ point_data<coordinate_type>(100, 500),
+ };
+ polygon_data<coordinate_type> poly(pts, pts+8);
+ stdcout << "2nd order reflex vertex\n";
+ initialize_skeleton(skeleton, all_faces, event_queue, poly);
+ execute_skeleton(skeleton, all_faces, event_queue, domain, 1000);
+ for(typename std::vector<skeleton_node*>::iterator itr = skeleton.begin();
+ itr != skeleton.end(); ++itr) {
+ std::cout << (*itr)->label << " " << (*itr)->vertex.x() << " " << (*itr)->vertex.y() << " " <<
+ ( ((*itr)->linked_nodes[0]) ? (*itr)->linked_nodes[0]->label : std::string("0")) << " " <<
+ ( ((*itr)->linked_nodes[1]) ? (*itr)->linked_nodes[1]->label : std::string("0")) << " " <<
+ ( ((*itr)->linked_nodes[2]) ? (*itr)->linked_nodes[2]->label : std::string("0")) << "\n";
+ }
+ }
+ for(typename std::vector<future_intersection*>::iterator itr = all_faces.begin();
+ itr != all_faces.end(); ++itr)
+ delete *itr;
+ all_faces.clear();
+ for(typename std::vector<skeleton_node*>::iterator itr = skeleton.begin();
+ itr != skeleton.end(); ++itr)
+ delete *itr;
+ skeleton.clear();
+
return true;
}
return false;