new: add nodes at extreme values of selected subpaths

(bzr r10839)

6 files changed, 82 insertions, 6 deletions

diff --git a/src/ui/tool/manipulator.h b/src/ui/tool/manipulator.h
index 474ccd8f3..68185b4d4 100644
--- a/src/ui/tool/manipulator.h
+++ b/src/ui/tool/manipulator.h
@@ -53,6 +53,14 @@ public:
         : Manipulator(d)
         , _selection(sel)
     {}
+
+    /// Type of extremum points to add in PathManipulator::insertNodeAtExtremum
+    enum ExtremumType {
+        EXTR_MIN_X = 0,
+        EXTR_MAX_X,
+        EXTR_MIN_Y,
+        EXTR_MAX_Y
+    };
 protected:
     ControlPointSelection &_selection;
 };
diff --git a/src/ui/tool/multi-path-manipulator.cpp b/src/ui/tool/multi-path-manipulator.cpp
index 2316058ed..6a671feb6 100644
--- a/src/ui/tool/multi-path-manipulator.cpp
+++ b/src/ui/tool/multi-path-manipulator.cpp
@@ -336,6 +336,11 @@ void MultiPathManipulator::insertNodes()
     invokeForAll(&PathManipulator::insertNodes);
     _done(_("Add nodes"));
 }
+void MultiPathManipulator::insertNodesAtExtrema(ExtremumType extremum)
+{
+    invokeForAll(&PathManipulator::insertNodeAtExtremum, extremum);
+    _done(_("Add extremum nodes"));
+}
 
 void MultiPathManipulator::duplicateNodes()
 {
diff --git a/src/ui/tool/multi-path-manipulator.h b/src/ui/tool/multi-path-manipulator.h
index 6b5686139..36ea8831c 100644
--- a/src/ui/tool/multi-path-manipulator.h
+++ b/src/ui/tool/multi-path-manipulator.h
@@ -51,6 +51,7 @@ public:
     void setNodeType(NodeType t);
     void setSegmentType(SegmentType t);
 
+    void insertNodesAtExtrema(ExtremumType extremum);
     void insertNodes();
     void duplicateNodes();
     void joinNodes();
diff --git a/src/ui/tool/path-manipulator.cpp b/src/ui/tool/path-manipulator.cpp
index 96b3a1bb1..826c3d818 100644
--- a/src/ui/tool/path-manipulator.cpp
+++ b/src/ui/tool/path-manipulator.cpp
@@ -268,6 +268,67 @@ void PathManipulator::insertNodes()
     }
 }
 
+static void
+add_or_replace_if_extremum(std::vector< std::pair<NodeList::iterator, double> > &vec,
+                           double & extrvalue, double testvalue, NodeList::iterator const& node, double t)
+{
+    if (testvalue > extrvalue) {
+        // replace all extreme nodes with the new one
+        vec.clear();
+        vec.push_back( std::pair<NodeList::iterator, double>( node, t ) );
+        extrvalue = testvalue;
+    } else if ( Geom::are_near(testvalue, extrvalue) ) {
+        // very rare but: extremum node at the same extreme value!!! so add it to the list
+        vec.push_back( std::pair<NodeList::iterator, double>( node, t ) );
+    }
+}
+
+/** Insert a new node at the extremum of the selected segments. */
+void PathManipulator::insertNodeAtExtremum(ExtremumType extremum)
+{
+    if (_num_selected < 2) return;
+
+    double sign    = (extremum == EXTR_MIN_X || extremum == EXTR_MIN_Y) ? -1. : 1.;
+    Geom::Dim2 dim = (extremum == EXTR_MIN_X || extremum == EXTR_MAX_X) ? Geom::X : Geom::Y;
+
+    for (SubpathList::iterator subp = _subpaths.begin(); subp != _subpaths.end(); ++subp) {
+        Geom::Coord extrvalue = - Geom::infinity();
+        std::vector< std::pair<NodeList::iterator, double> > extremum_vector;
+
+        for (NodeList::iterator first = (*subp)->begin(); first != (*subp)->end(); ++first) {
+            NodeList::iterator second = first.next();
+            if (second && first->selected() && second->selected()) {
+                add_or_replace_if_extremum(extremum_vector, extrvalue, sign * first->position()[dim], first, 0.);
+                add_or_replace_if_extremum(extremum_vector, extrvalue, sign * second->position()[dim], first, 1.);
+                if (first->front()->isDegenerate() && second->back()->isDegenerate()) {
+                    // a line segment has is extrema at the start and end, no node should be added
+                    continue;
+                } else {
+                    // build 1D cubic bezier curve
+                    Geom::Bezier temp1d(first->position()[dim], first->front()->position()[dim],
+                                        second->back()->position()[dim], second->position()[dim]);
+                    // and determine extremum
+                    Geom::Bezier deriv1d = derivative(temp1d);
+                    std::vector<double> rs = deriv1d.roots();
+                    for (std::vector<double>::iterator it = rs.begin(); it != rs.end(); ++it) {
+                        add_or_replace_if_extremum(extremum_vector, extrvalue, sign * temp1d.valueAt(*it), first, *it);
+                    }
+                }
+            }
+        }
+
+        for (unsigned i = 0; i < extremum_vector.size(); ++i) {
+            // don't insert node at the start or end of a segment, i.e. round values for extr_t
+            double t = extremum_vector[i].second;
+            if ( !Geom::are_near(t - std::floor(t+0.5),0.) )  //  std::floor(t+0.5) is another way of writing round(t)
+            {
+                _selection.insert( subdivideSegment(extremum_vector[i].first, t).ptr() );
+            }
+        }
+    }
+}
+
+
 /** Insert new nodes exactly at the positions of selected nodes while preserving shape.
  * This is equivalent to breaking, except that it doesn't split into subpaths. */
 void PathManipulator::duplicateNodes()
diff --git a/src/ui/tool/path-manipulator.h b/src/ui/tool/path-manipulator.h
index e3b724e37..62daf9a50 100644
--- a/src/ui/tool/path-manipulator.h
+++ b/src/ui/tool/path-manipulator.h
@@ -67,6 +67,7 @@ public:
     void selectSubpaths();
     void invertSelectionInSubpaths();
 
+    void insertNodeAtExtremum(ExtremumType extremum);
     void insertNodes();
     void duplicateNodes();
     void weldNodes(NodeList::iterator preserve_pos = NodeList::iterator());
diff --git a/src/widgets/toolbox.cpp b/src/widgets/toolbox.cpp
index 2da0642ae..3960f2349 100644
--- a/src/widgets/toolbox.cpp
+++ b/src/widgets/toolbox.cpp
@@ -286,10 +286,10 @@ static gchar const * ui_descr =
         "  <toolbar name='NodeToolbar'>"
         "    <separator />"
         "    <toolitem action='NodeInsertAction' />"
-/*        "    <toolitem action='NodeInsertActionMinX' />"
+        "    <toolitem action='NodeInsertActionMinX' />"
         "    <toolitem action='NodeInsertActionMaxX' />"
         "    <toolitem action='NodeInsertActionMinY' />"
-        "    <toolitem action='NodeInsertActionMaxY' />"  */
+        "    <toolitem action='NodeInsertActionMaxY' />"  
         "    <toolitem action='NodeDeleteAction' />"
         "    <separator />"
         "    <toolitem action='NodeJoinAction' />"
@@ -1162,28 +1162,28 @@ static void sp_node_path_edit_add_min_x(void)
 {
     InkNodeTool *nt = get_node_tool();
     if (nt) {
-        nt->_multipath->insertNodes();
+        nt->_multipath->insertNodesAtExtrema(Inkscape::UI::PointManipulator::EXTR_MIN_X);
     }
 }
 static void sp_node_path_edit_add_max_x(void)
 {
     InkNodeTool *nt = get_node_tool();
     if (nt) {
-        nt->_multipath->insertNodes();
+        nt->_multipath->insertNodesAtExtrema(Inkscape::UI::PointManipulator::EXTR_MAX_X);
     }
 }
 static void sp_node_path_edit_add_min_y(void)
 {
     InkNodeTool *nt = get_node_tool();
     if (nt) {
-        nt->_multipath->insertNodes();
+        nt->_multipath->insertNodesAtExtrema(Inkscape::UI::PointManipulator::EXTR_MIN_Y);
     }
 }
 static void sp_node_path_edit_add_max_y(void)
 {
     InkNodeTool *nt = get_node_tool();
     if (nt) {
-        nt->_multipath->insertNodes();
+        nt->_multipath->insertNodesAtExtrema(Inkscape::UI::PointManipulator::EXTR_MAX_Y);
     }
 }