Commits

Manfred Moitzi committed 428bb75

optimized polybezier.find_position()

Comments (0)

Files changed (3)

geoalg/polybezier.py

             points.extend(pts)
         return points
 
-    def find_position(self, p, segments=100):
+    def find_position(self, p, passes=1, segments=100, epsilon=0.00001):
         """ Find curve position near point p.
 
         :param 2-tuple p: curve position
+        :param int passes: count of search passes
+        :param float epsilon: precision (min distance of result position)
         """
-        def interpolate(start, end):
-            if start > end:
-                start, end = end, start
-            ps = Vec2(self.get_point(start))
-            pe = Vec2(self.get_point(end))
-            ray1 = Ray2D(ps, pe)
-            ip =  ray1.intersect(ray1.normal_through(p))
-            a = ps.distance(ip)
-            b = pe.distance(ip)
-            return start + (end - start) * (a / (a + b))
+        def _find_position(startpos, endpos):
+            """ Find curve position near point p in range from  startpos to endpos.
+            """
+            def interpolate(start, end):
+                if start > end:
+                    start, end = end, start
+                ps = Vec2(self.get_point(start))
+                pe = Vec2(self.get_point(end))
+                ray1 = Ray2D(ps, pe)
+                ip =  ray1.intersect(ray1.normal_through(p))
+                a = ps.distance(ip)
+                b = pe.distance(ip)
+                return start + (end - start) * (a / (a + b))
 
-        def curve_distances():
-            delta = self.length / segments
-            for i in range(segments+1):
-                position = i * delta
-                curve_point = Vec2(self.get_point(position))
-                yield p.distance(curve_point), position
+            def curve_distances(startpos, delta):
+                for i in range(segments+1):
+                    position = startpos + i * delta
+                    curve_point = Vec2(self.get_point(position))
+                    yield p.distance(curve_point), position
+
+            if startpos > endpos:
+                startpos, endpos = endpos, startpos
+
+            delta = (endpos - startpos) / segments
+            start, end = sorted(curve_distances(startpos, delta))[:2]
+            if start[0] < epsilon:
+                return start[1], 0.
+            else:
+                return interpolate(start[1], end[1]), abs(start[1] - end[1])
 
         p = Vec2(p)
-        start, end = sorted(curve_distances())[:2]
-        return interpolate(start[1], end[1])
+        startpos = 0.
+        endpos = self.length
+        passes = max(1, passes)
+        while passes:
+            pos, distance_of_best_results = _find_position(startpos, endpos)
+            if distance_of_best_results > 0.: #refine search
+                passes -= 1
+                d2 = 2 * distance_of_best_results
+                startpos = max(pos - d2, 0.)
+                endpos = min(pos + d2, self.length)
+            else: # distance get_point(pos) to p < epsilon
+                break
+        return pos
 
     def find_part(self, position):
         """ Find bezier curve part associated to curve position.

polybezier_examples.py

             dwg.add(dxf.line(p, p+tangent.right, color=4))
 
     def add_curvepoint(p1):
-        cpos = bezier.find_position(p1, 300)
+        cpos = bezier.find_position(p1, passes=2, segments=20)
         p2 = bezier.get_point(cpos)
         for p in (p1, p2):
             dwg.add(dxf.circle(radius=.2, center=p, color=5))

tests/test_polybezier.py

         self.assertAlmostEqual(p[Y], expected[Y], places=6)
 
     def test_find_position_on_curve_DEFPOINT1(self):
-        pos = self.bezier.find_position(DEFPOINTS[1])
-        self.assertAlmostEqual(pos, 23.21235, places=3)
+        pos = self.bezier.find_position(DEFPOINTS[1], passes=2)
+        self.assertAlmostEqual(pos, 23.21235, places=5)
 
     def test_find_position_on_curve_DEFPOINT4(self):
         pos = self.bezier.find_position(DEFPOINTS[4])