Dubin's Path

Following the discussion about “Rubber Band”

I found this nice page that is related to the rubber band problem, the Dubin’s paths

I implemented 4 of them named the CSC (Curve Straight Curve). Sometime there are not all the 4 solutions.
So I’ll have 2 components in Nautilus plugin. One like the Blend component that uses curve end and start


and the other having point and direction


I made a component with the logic from this paper (just the Dubins part), not a big deal 10 lines of code!

This allows to use points to generate open or closed path through points in 2D and 3D.





9 Likes

Cool stuff, Laurent. I hadn’t heard about Dubin before.

Thanks
I didn’t knew before reading this when I looked the Rubber Band question

This article lead to Dubins path. But for more general things I think the good tool will be to have some blending with Bezier or Nurbs with a limited maximal curvature like something like in this paper “Three-Dimensional Dubins-Path-Guided Continuous Curvature Path Smoothing” or something like Clothoid subject …

1 Like

Yes, I’m familiar. I had implemented the rubber-band thing about one and half years ago now, after seeing Armin Hoffmann’s (Swiss graphic designer) experimental font in a book that they derived with similar principals, but - I guess - analogously by hand.

I first did a prototype in GHPython and later ported the whole thing to C++, because I wanted to compute all possible shapes for a given set of points, which in hindsight was a little naive, given that for the standard set that Hoffmann used, namely 9 points/circles in a grid, already yields a lot of non-intersecting, Hamiltonian paths. :sweat_smile:

It also was a deep, deep, deep rabbit hole to descent into, because I basically implemented everything from scratch (e.g. points, lines, circles, intersections between them, graph, Hamiltion path finder, permutations generator, etc.), a whole fricking mini geometry library that I still use parts of for creative coding projects. :rofl:

It works for a reasonable amount of points, but I still need to perfect the SVG export, which I also did from scratch, and which made me lose interest in the whole thing. :smiling_face_with_tear:

Anyway, here’s what I came up with for circle to circle tangents in GHPython back then, if you’re intereseted:

import Rhino.Geometry as rg

def tangent_lines(from_circle, to_circle, interior=False):
    """Creates two interior or exterior tangent lines to two circles.
        Tangent lines can only be constructed, if neither circle is inscribed
        within the other. Interior tangent lines additionally require the two
        circles to not intersect at any point.
    
    Args:
      from_circle (Rhino.Geometry.Circle): first circle
      to_circle (Rhino.Geometry.Circle): second circle
      interior 
    
    Raises:
      RuntimeError: Unable to create interior tangent lines,
        from_circle/to_circle is inscribed within to_circle/from_circle
      RuntimeError: Unable to create interior tangent lines,
        from_circle and to_circle intersect
    
    Returns:
      The two tangent lines from the first circle to the second.
    """
    circles = [from_circle, to_circle]
    indices = [0, 1]
     
    if from_circle.Radius != to_circle.Radius:
        indices.sort(key=lambda i: circles[i].Radius)
        circles.sort(key=lambda c: c.Radius)
    
    min_circle, max_circle = circles
    
    distance = min_circle.Center.DistanceTo(max_circle.Center)
    if distance <= max_circle.Radius - min_circle.Radius:
        e = "from_circle is inscribed within to_circle"
        if indices[0] == 1:
            e = "to_circle is inscribed within from_circle"
        raise RuntimeError("Unable to create tangent lines, " + e)
    if interior and distance <= max_circle.Radius + min_circle.Radius:
        e = "from_circle and to_circle intersect"
        raise RuntimeError("Unable to create interior tangent lines, " + e)
    
    circles_tan_pts = [[], []]
    if min_circle.Radius != max_circle.Radius or interior:
        radius_x = max_circle.Radius - min_circle.Radius
        if interior:
            radius_x = max_circle.Radius + min_circle.Radius
        circle_x = rg.Circle(max_circle.Center, radius_x)
        
        mid_pt = (min_circle.Center + max_circle.Center) / 2
        mid_circle = rg.Circle(mid_pt, mid_pt.DistanceTo(max_circle.Center))
        
        rc, pt1, pt2 = rg.Intersect.Intersection.CircleCircle(mid_circle, circle_x)
        for pt in [pt1, pt2]:
            vec = pt - max_circle.Center
            vec.Unitize()
            min_vec = vec * min_circle.Radius * -1 if interior else vec * min_circle.Radius
            min_tan_pt = min_circle.Center + min_vec
            circles_tan_pts[0].append(min_tan_pt)
            max_vec = vec * max_circle.Radius if interior else vec * (circle_x.Radius + min_circle.Radius)
            max_tan_pt = max_circle.Center + max_vec
            circles_tan_pts[1].append(max_tan_pt)
    else:
        vec = max_circle.Center - min_circle.Center
        xvec = rg.Vector3d.CrossProduct(vec, max_circle.Normal)
        xvec.Unitize()
        xvec *= max_circle.Radius
        
        min_tan_pt_a = min_circle.Center + xvec
        min_tan_pt_b = min_circle.Center - xvec
        circles_tan_pts[0] = [min_tan_pt_a, min_tan_pt_b]
        max_tan_pt_a= max_circle.Center + xvec
        max_tan_pt_b = max_circle.Center - xvec
        circles_tan_pts[1] = [max_tan_pt_a, max_tan_pt_b]

    sorted_cir_tan_pts = [p for _, p in sorted(zip(indices, circles_tan_pts))]
    tan_line_1 = rg.Line(sorted_cir_tan_pts[0][0], sorted_cir_tan_pts[1][0])
    tan_line_2 = rg.Line(sorted_cir_tan_pts[0][1], sorted_cir_tan_pts[1][1])
    return tan_line_1, tan_line_2
    
    
if __name__ == "__main__":
    tan_lines = tangent_lines(C1, C2, I)
4 Likes

Thanks for the story and the reference to Hamiltonian Path, I surely have to rename my pseudo TSP to something like Hamiltonian Graph. I’ll have to read that to find the correct definition.

Thanks for the code for the circle, I did mine that is very similar to the Grasshopper Component. For me the direction goes from circle c1 to c2 (on XY plane) so there is a first exterior line (the right path) and a second (the left one). Then there is the interior line with same logic


Something like that
image

2 Likes

If you want to visit all nodes in an undirected graph exactly once that’s called a Hamilton path. And if the first and last node are the same, it’s a Hamilton cycle. Where the Travelling Salesman Problem tries to optimize routes by minimum distance or some other weighted value, Hamilton just focuses on visiting every node.

For the rubber band algorithm, I found back then that not all Hamilton cycles were valid, because intersecting ones are possible, and weren’t what I had in mind.

Ah, interesting.

1 Like