[Boost-commit] svn:boost r80597 - trunk/boost/polygon/detail

Subject: [Boost-commit] svn:boost r80597 - trunk/boost/polygon/detail
From: lucanus.j.simonson_at_[hidden]
Date: 2012-09-19 14:08:45

Author: ljsimons
Date: 2012-09-19 14:08:44 EDT (Wed, 19 Sep 2012)
New Revision: 80597
URL: http://svn.boost.org/trac/boost/changeset/80597

Log:
using Andrii's event point construction and added support for multiple split edge handling
Text files modified: 
   trunk/boost/polygon/detail/skeleton_detail.hpp |   563 +++++++++++++++++++++------------------ 
   1 files changed, 305 insertions(+), 258 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-19 14:08:44 EDT (Wed, 19 Sep 2012)
@@ -108,10 +108,26 @@
         UnitOut x_out = gint.x() + ((p1.x() - gint.x())*dist2/dist1 + (p2.x()-gint.x()))/2;
         UnitOut y_out = gint.y() + ((p1.y() - gint.y())*dist2/dist1 + (p2.y()-gint.y()))/2;
         point_data<UnitOut> end_point(x_out, y_out);
+        if(orientation(segment2, end_point) < 0) {
+          x_out = gint.x() - ((p1.x() - gint.x())*dist2/dist1 + (p2.x()-gint.x()))/2;
+          y_out = gint.y() - ((p1.y() - gint.y())*dist2/dist1 + (p2.y()-gint.y()))/2;
+          end_point = point_data<UnitOut>(x_out, y_out);
+        }
+        std::cout << x_out << " " << y_out << "\n";
         if(orientation(segment2, end_point) != orientation(segment3, end_point)) { 
           std::cout << "we want the other bisector in this case\n";
           y_out = gint.y() + ((p1.x() - gint.x())*dist2/dist1 + (p2.x()-gint.x()))/2;
           x_out = gint.x() - ((p1.y() - gint.y())*dist2/dist1 + (p2.y()-gint.y()))/2;
+          end_point = point_data<UnitOut>(x_out, y_out);
+          std::cout << x_out << " " << y_out << "\n";
+          std::cout << segment2.low().x() << " " << segment2.low().y() << " " << 
+            segment2.high().x() << " " << segment2.high().y() << " " << std::endl;
+          if(orientation(segment2, end_point) < 0) {
+            y_out = gint.y() - ((p1.x() - gint.x())*dist2/dist1 + (p2.x()-gint.x()))/2;
+            x_out = gint.x() + ((p1.y() - gint.y())*dist2/dist1 + (p2.y()-gint.y()))/2;
+            end_point = point_data<UnitOut>(x_out, y_out);
+            std::cout << x_out << " " << y_out << "\n";
+          }
         }
         end_point = point_data<UnitOut>(x_out, y_out);
         segment1.high(end_point);
@@ -172,13 +188,15 @@
         edge_type edge; //the edge that is next between this future intersection and the one stored in *next
         future_intersection* prev;
         future_intersection* next;
+        future_intersection* next_split_edge;
         skeleton_node* parent_node;
         output_coordinate_type active_distance;
         //split events that refer to the edge between this and next
         std::vector<typename std::set<event>::iterator> active_splits_on_next;
         std::string label;
         bool is_dead;
-        future_intersection() : prev(0x0), next(0x0), parent_node(0x0), is_dead(false), active_distance(-1.0) {
+        future_intersection() : prev(0x0), next(0x0), next_split_edge(0x0), 
+                                parent_node(0x0), is_dead(false), active_distance(-1.0) {
           static char local_label = 'a';
           label = local_label;
           if(local_label == 'z')
@@ -287,7 +305,7 @@
         do {
           debug1("loop");
           if(orientation(current->prev->edge, current->edge) < 1) {
-            std::cout << "initialize reflex vertex\n";
+            //std::cout << "initialize reflex vertex\n";
             future_intersection* inner = current->next->next;
             while(inner != current) {
               event e2;
@@ -385,8 +403,7 @@
         std::cout << s.low().x() << "," << s.low().y() << "->" << s.high().x() << "," << s.high().y() << "\n";
       }
 
-      static bool compute_split_event_point(point_data<output_coordinate_type>& point, 
-                                           edge_type e1, edge_type e2, edge_type e3, edge_type e4, edge_type e5) {
+      static bool compute_split_event_point(event& e, edge_type e1, edge_type e2, edge_type e3, edge_type e4, edge_type e5) {
         debug1("compute_split_event_point");
         segment_type segment1, segment2, segment3, segment4, segment5;
         print_segment(e1);
@@ -403,51 +420,45 @@
           return false;
         }
         //compute the bisector of e1 and e2, this is the reflex vertex bisector
-        if(bisector(segment1, e1, e2)) {
-          debug1("has bisector1");
-          if(bisector(segment2, e3, e4)) {
-            debug1("has bisector2");
-            if(bisector(segment3, e4, e5)) {
-              debug1("has bisector3");
-              //compute the edge event point using e1, e2, e2, e4 or e1, e2, e1, e4 if e4 is parallel to e2
-              if(bisector(segment4, e1, e4)) {
-                if(!generalized_intersection(point, segment1, segment4)) {
-                  debug1("no intersection 2");
-                  return false;
-                }
-              } else if(bisector(segment5, e2, e4)) {
-                if(!generalized_intersection(point, segment1, segment5)) {
-                  debug1("no intersection 2");
-                  return false;
-                }
-              } else {
-                debug1("no bisector4");
-                return false;
-              }
-              std::cout << point.x() << " " << point.y() << std::endl;
-              //test that point is on the coorect side of e1 and e2 and e4
-              if(orientation(e1, point) <= 0)
-                return false;
-              if(orientation(e2, point) <= 0)
-                return false;
-              if(orientation(e4, point) <= 0)
-                return false;
-              debug1("passed simple orientation tests");
+        if(bisector(segment2, e3, e4)) {
+          debug1("has bisector2");
+          if(bisector(segment3, e4, e5)) {
+            debug1("has bisector3");
+            segment_data<coordinate_type> s1, s2, s3;
+            assign(s1, e1);
+            assign(s2, e2);
+            assign(s3, e4);
+            if(!create_event()(s1, s2, s3, &e)) {
+              return false;
+            }
+            
+            point_data<output_coordinate_type> point = e.point;
+            std::cout << point.x() << " " << point.y() << std::endl;
+            //test that point is on the coorect side of e1 and e2 and e4
+            if(orientation(e1, point) <= 0)
+              return false;
+            if(orientation(e2, point) <= 0)
+              return false;
+            if(orientation(e4, 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
-              if(orientation(e3, e4) == orientation(segment2, point))
-                return false;
-              debug1("passed complex orientation test1");
-              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;
-            }
+            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))
+              return false;
+            debug1("passed complex orientation test1");
+            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;
           }
         }
-          
         return false;
       }
 
@@ -478,21 +489,6 @@
         point_data<output_coordinate_type> pt;
         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";
-          segment_type s1;
-          assign(s1, opposite->edge);
-          print_segment(opposite->edge);
-          std::cout << pt.x() << " " << pt.y() << std::endl;
-          output_coordinate_type dist = distance_squared_to_line(pt, s1);
-          std::cout << "distance to split " << sqrt(dist) << std::endl;
-          segment_data<coordinate_type> segment1, segment2, segment3;
-          assign(segment1, first->prev->edge);
-          assign(segment2, first->edge);
-          assign(segment3, opposite->edge);
-          event e2;
-          create_event()(segment1, segment2, segment3, &e);
-          std::cout << "Andrii's point " << e.x() << " " << e.y() << " " << e.r() << std::endl;
-          e.point = pt;
-          e.distance = dist;
           e.parent = first;
           e.split_on_next = opposite;
           return true;
@@ -500,23 +496,21 @@
         return false;
       }
 
-      static bool compute_edge_event_point(point_data<output_coordinate_type>& point, 
+      static bool compute_edge_event_point(event& e, 
                                            edge_type e1, edge_type e2, edge_type e3, edge_type e4) {
-        segment_type segment1, segment2;
-        if(bisector(segment1, e1, e2)) {
-          if(bisector(segment2, e3, e4)) {
-            return (generalized_intersection(point, segment1, segment2));
-          }
-        }
-        return false;
-          
+        segment_data<coordinate_type> s1, s2, s3;
+        assign(s1, e1);
+        assign(s2, e2);
+        assign(s3, e4);
+        return create_event()(s1, s2, s3, &e);
       }
 
       static bool compute_edge_event(event& e, future_intersection* first, future_intersection* second, 
                                      const rectangle_data<output_coordinate_type>& domain) {
         point_data<output_coordinate_type> pt;
-        if(compute_edge_event_point(pt, first->prev->edge, first->edge, second->prev->edge, second->edge)) {
+        if(compute_edge_event_point(e, first->prev->edge, first->edge, second->prev->edge, second->edge)) {
           debug1("domain");
+          point_data<output_coordinate_type> pt = e.point;
           std::cout << pt.x() << " " << pt.y() << std::endl;
           //edge event points outside (or on the boundary of) the polygon bounding box are useless and not worth processing
           //they would never be reached by the forward progress of the algorithm through the event queue
@@ -525,19 +519,6 @@
             //compute distance from point to edge
             segment_type s1;
             assign(s1, first->edge);
-            output_coordinate_type dist = distance_squared_to_line(pt, s1);
-            output_coordinate_type dist2 = euclidean_distance(s1, pt);
-            std::cout << "distance " << dist2 << std::endl;
-            std::cout << "distance^2 " << dist << std::endl;
-            segment_data<coordinate_type> segment1, segment2, segment3;
-            assign(segment1, first->prev->edge);
-            assign(segment2, first->edge);
-            assign(segment3, second->edge);
-            event e2;
-            create_event()(segment1, segment2, segment3, &e);
-            std::cout << "Andrii's point " << e.x() << " " << e.y() << " " << e.r() << std::endl;
-            e.point = pt;
-            e.distance = dist;
             e.parent = first;
             e.parent2 = second;
             e.split_on_next = 0x0;
@@ -607,6 +588,26 @@
           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
+          if(current_event.split_on_next->next_split_edge) {
+            future_intersection* current = current_event.split_on_next;
+            do{
+              std::cout << current << std::endl;
+              if(!current->is_dead) {
+                debug1("is alive");
+                event e2;
+                if(compute_split_event(e2, current_event.parent, current)) {
+                  debug1("found correct split edge");
+                  current_event.split_on_next = current;
+                  break;
+                }
+              }
+              current = current->next_split_edge;
+            } while (current != current_event.split_on_next);
+          }
+
           //event parent node is not dead
           //create one new future intersection associated with the with a copy of the "opposite" edge as its edge
           //that split edge will appear in both rings
@@ -617,6 +618,16 @@
           new_active->edge = current_event.split_on_next->edge;
           new_active->prev = current_event.parent->prev;
           new_active->next = current_event.split_on_next->next;
+
+          //link new future intersection into the circular list of future intersections
+          //associated with splits of this edge
+          new_active->next_split_edge = current_event.split_on_next->next_split_edge;
+          if(new_active->next_split_edge == 0x0)
+            new_active->next_split_edge = current_event.split_on_next;
+          std::cout << "next split edge " << new_active->next_split_edge << std::endl;
+          current_event.split_on_next->next_split_edge = new_active;
+          std::cout << "next split edge " << new_active << std::endl;
+
           new_active->parent_node = skeleton.back();
           new_active->active_distance = -1;
           new_active->next->prev = new_active;
@@ -658,7 +669,7 @@
             current_event.parent->next->parent_node->add_edge(current_event.parent->prev->parent_node);
             std::cout << current_event.parent->next->parent_node->label << "->" << current_event.parent->prev->parent_node->label << std::endl;
             current_event.parent->prev->is_dead = true;
-            current_event.parent->prev->parent_node->linked_nodes[0] = current_event.parent->next->parent_node;
+            current_event.parent->prev->parent_node->add_edge(current_event.parent->next->parent_node);
             std::cout << current_event.parent->prev->parent_node->label << "->" << current_event.parent->next->parent_node->label << std::endl;
             current_event.parent->next->is_dead = true;
             return;
@@ -680,7 +691,7 @@
         while(!event_queue.empty()) {
           event current_event = event_queue.top();
           event_queue.pop();
-          if(bound >=0 && current_event.distance > bound*bound)
+          if(bound >=0 && current_event.distance > bound)
             break;
           if(!current_event.parent->is_dead &&
              (current_event.parent2 == 0x0 || !current_event.parent2->is_dead))
@@ -715,180 +726,147 @@
         std::vector<skeleton_node*> skeleton; 
         std::vector<future_intersection*> all_faces;
         event_queue_type event_queue;
-        // initialize_skeleton(skeleton, all_faces, event_queue, rect);
-        // if(skeleton.size() == 4 && all_faces.size() == 4) {
-        //   stdcout << event_queue.size() << stdendl;
-        //   for(typename std::vector<skeleton_node*>::iterator itr = skeleton.begin();
-        //       itr != skeleton.end(); ++itr) {
-        //     std::cout << (*itr) << " " << (*itr)->vertex.x() << " " << (*itr)->vertex.y() << " " <<
-        //       ((*itr)->linked_nodes[0]) << " " <<
-        //       ((*itr)->linked_nodes[1]) << " " << 
-        //       ((*itr)->linked_nodes[2]) << "\n";
-        //   }
-        //   execute_skeleton(skeleton, all_faces, event_queue, domain, 1000);
-        //   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) {
-        //     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<skeleton_node*>::iterator itr = skeleton.begin();
-        //       itr != skeleton.end(); ++itr) 
-        //     delete *itr;
-        //   skeleton.clear();
-        //   {
-        //   point_data<coordinate_type> pts[] = {point_data<coordinate_type>(120, 200),
-        //                                        point_data<coordinate_type>(300, 200),
-        //                                        point_data<coordinate_type>(300, 500),
-        //                                        point_data<coordinate_type>(100, 500),
-        //                                        point_data<coordinate_type>(100, 220),
-        //   };
-        //   polygon_data<coordinate_type> poly(pts, pts+5);
-        //   stdcout << "five point case\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();
-
-        //   {
-        //   point_data<coordinate_type> pts[] = {point_data<coordinate_type>(120, 200),
-        //                                        point_data<coordinate_type>(280, 200),
-        //                                        point_data<coordinate_type>(300, 220),
-        //                                        point_data<coordinate_type>(300, 480),
-        //                                        point_data<coordinate_type>(280, 500),
-        //                                        point_data<coordinate_type>(120, 500),
-        //                                        point_data<coordinate_type>(100, 480),
-        //                                        point_data<coordinate_type>(100, 220),
-        //   };
-        //   polygon_data<coordinate_type> poly(pts, pts+8);
-        //   stdcout << "eight point case\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();
-        //   {
-        //   point_data<coordinate_type> pts[] = {point_data<coordinate_type>(120, 200),
-        //                                        point_data<coordinate_type>(280, 200),
-        //                                        point_data<coordinate_type>(300, 220),
-        //                                        point_data<coordinate_type>(300, 480-100),
-        //                                        point_data<coordinate_type>(280, 500-100),
-        //                                        point_data<coordinate_type>(120, 500-100),
-        //                                        point_data<coordinate_type>(100, 480-100),
-        //                                        point_data<coordinate_type>(100, 220),
-        //   };
-        //   polygon_data<coordinate_type> poly(pts, pts+8);
-        //   stdcout << "co-circular eight point case\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();
-
-
-
-        //   {
-        //   point_data<coordinate_type> pts[] = {point_data<coordinate_type>(100, 200),
-        //                                        point_data<coordinate_type>(150, 220),
-        //                                        point_data<coordinate_type>(200, 200),
-        //                                        point_data<coordinate_type>(180, 250),
-        //                                        point_data<coordinate_type>(200, 300),
-        //                                        point_data<coordinate_type>(150, 280),
-        //                                        point_data<coordinate_type>(100, 300),
-        //                                        point_data<coordinate_type>(120, 250),
-        //   };
-        //   polygon_data<coordinate_type> poly(pts, pts+8);
-        //   stdcout << "ninja star\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();
-
-        //   {
-        //   point_data<coordinate_type> pts[] = {point_data<coordinate_type>(100, 200),
-        //                                        point_data<coordinate_type>(140, 240),
-        //                                        point_data<coordinate_type>(200, 200),
-        //                                        point_data<coordinate_type>(160, 240),
-        //                                        point_data<coordinate_type>(200, 300),
-        //                                        point_data<coordinate_type>(160, 260),
-        //                                        point_data<coordinate_type>(100, 300),
-        //                                        point_data<coordinate_type>(140, 260),
-        //   };
-        //   polygon_data<coordinate_type> poly(pts, pts+8);
-        //   stdcout << "evil ninja star\n";
-        //   initialize_skeleton(skeleton, all_faces, event_queue, poly);
-        //   std::cout << event_queue.size() << " GREP\n";
-        //   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";
-        //   }
-        //   }
+        initialize_skeleton(skeleton, all_faces, event_queue, rect);
+        if(skeleton.size() == 4 && all_faces.size() == 4) {
+          stdcout << event_queue.size() << stdendl;
+          for(typename std::vector<skeleton_node*>::iterator itr = skeleton.begin();
+              itr != skeleton.end(); ++itr) {
+            std::cout << (*itr) << " " << (*itr)->vertex.x() << " " << (*itr)->vertex.y() << " " <<
+              ((*itr)->linked_nodes[0]) << " " <<
+              ((*itr)->linked_nodes[1]) << " " << 
+              ((*itr)->linked_nodes[2]) << "\n";
+          }
+          execute_skeleton(skeleton, all_faces, event_queue, domain, 1000);
+          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) {
+            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<skeleton_node*>::iterator itr = skeleton.begin();
+              itr != skeleton.end(); ++itr) 
+            delete *itr;
+          skeleton.clear();
+          {
+          point_data<coordinate_type> pts[] = {point_data<coordinate_type>(120, 200),
+                                               point_data<coordinate_type>(300, 200),
+                                               point_data<coordinate_type>(300, 500),
+                                               point_data<coordinate_type>(100, 500),
+                                               point_data<coordinate_type>(100, 220),
+          };
+          polygon_data<coordinate_type> poly(pts, pts+5);
+          stdcout << "five point case\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();
+
+          {
+          point_data<coordinate_type> pts[] = {point_data<coordinate_type>(120, 200),
+                                               point_data<coordinate_type>(280, 200),
+                                               point_data<coordinate_type>(300, 220),
+                                               point_data<coordinate_type>(300, 480),
+                                               point_data<coordinate_type>(280, 500),
+                                               point_data<coordinate_type>(120, 500),
+                                               point_data<coordinate_type>(100, 480),
+                                               point_data<coordinate_type>(100, 220),
+          };
+          polygon_data<coordinate_type> poly(pts, pts+8);
+          stdcout << "eight point case\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();
+          {
+          point_data<coordinate_type> pts[] = {point_data<coordinate_type>(120, 200),
+                                               point_data<coordinate_type>(280, 200),
+                                               point_data<coordinate_type>(300, 220),
+                                               point_data<coordinate_type>(300, 480-100),
+                                               point_data<coordinate_type>(280, 500-100),
+                                               point_data<coordinate_type>(120, 500-100),
+                                               point_data<coordinate_type>(100, 480-100),
+                                               point_data<coordinate_type>(100, 220),
+          };
+          polygon_data<coordinate_type> poly(pts, pts+8);
+          stdcout << "co-circular eight point case\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();
+
+
+
+          {
+          point_data<coordinate_type> pts[] = {point_data<coordinate_type>(100, 200),
+                                               point_data<coordinate_type>(150, 220),
+                                               point_data<coordinate_type>(200, 200),
+                                               point_data<coordinate_type>(180, 250),
+                                               point_data<coordinate_type>(200, 300),
+                                               point_data<coordinate_type>(150, 280),
+                                               point_data<coordinate_type>(100, 300),
+                                               point_data<coordinate_type>(120, 250),
+          };
+          polygon_data<coordinate_type> poly(pts, pts+8);
+          stdcout << "ninja star\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)
@@ -900,6 +878,38 @@
           skeleton.clear();
 
           {
+          point_data<coordinate_type> pts[] = {point_data<coordinate_type>(100, 200),
+                                               point_data<coordinate_type>(140, 240),
+                                               point_data<coordinate_type>(200, 200),
+                                               point_data<coordinate_type>(160, 240),
+                                               point_data<coordinate_type>(200, 300),
+                                               point_data<coordinate_type>(160, 260),
+                                               point_data<coordinate_type>(100, 300),
+                                               point_data<coordinate_type>(140, 260),
+          };
+          polygon_data<coordinate_type> poly(pts, pts+8);
+          stdcout << "evil ninja star\n";
+          initialize_skeleton(skeleton, all_faces, event_queue, poly);
+          std::cout << event_queue.size() << " GREP\n";
+          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();
+
           {
           point_data<coordinate_type> pts[] = {point_data<coordinate_type>(100, 200),
                                                point_data<coordinate_type>(300, 200),
@@ -929,6 +939,43 @@
             delete *itr;
           skeleton.clear();
 
+          {
+          point_data<coordinate_type> pts[] = {point_data<coordinate_type>(100, 200),
+                                               point_data<coordinate_type>(300, 200),
+                                               point_data<coordinate_type>(300, 500),
+                                               point_data<coordinate_type>(100, 500),
+                                               point_data<coordinate_type>(100, 490),
+                                               point_data<coordinate_type>(120, 490),
+                                               point_data<coordinate_type>(100, 489),
+                                               point_data<coordinate_type>(100, 450),
+                                               point_data<coordinate_type>(122, 450),
+                                               point_data<coordinate_type>(100, 449),
+                                               point_data<coordinate_type>(100, 420),
+                                               point_data<coordinate_type>(120, 420),
+                                               point_data<coordinate_type>(100, 419),
+          };
+          polygon_data<coordinate_type> poly(pts, pts+10);
+          stdcout << "multiple split\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("null"))  << " " <<
+              ( ((*itr)->linked_nodes[1]) ? (*itr)->linked_nodes[1]->label : std::string("null"))  << " " <<
+              ( ((*itr)->linked_nodes[2]) ? (*itr)->linked_nodes[2]->label : std::string("null"))  << "\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;