Strategy for drawing tree contour

[ishback]

Hello,
I’m trying to draw the contour of a tree. This is how I’m doing it so far:

• Create the branches (center line, in green)
• Create segments for each branch. Each segment stores a length, an angle, and a thickness.
• Create the offset points to the left (in red) and to the right of the center line based on the angle and the thickness of the segment.
• Draw the contour by following all points in order.

This is what I get:

As you can see the joints are not great, since it’s drawing a shape using all the points without taking into account the overlap of points between master and child, as well as left and right branches of the same order.

I can try to figure this out finding intersections between segments but before getting into that geometry venture, I wanted to learn if there is any other strategy to draw that contour to achieve an outcome like this.

I thought I could try a forces system that keeps a particle moving along the edge being pulled and pushed by points in the center line, but I’m not sure is the right approach.

I’d appreciate any other suggestion, thank you!

[micycle]

What exactly is your aim here? Are you looking to create a tree from a contour, or compute the contour of a tree?

If the latter, this contour is known as the medial axis of a shape. One way to think about finding this is place the largest circles possible (at different points) within the shape such that the circles are flush with at least 2 edges, and then join up circle centers. Fortunately, computing a Delaunay triangulation of the shape’s vertices will provide the circles (which are found by computing the circumcircle of each resulting triangle).

---

Processing Geometry Suite provides a method to find the medial axis of a PShape (and supports medial axis pruning to reject small/noisy segments, as seen below).

[ishback]

Hi micycle,
I believe what you described is the former, and I’m looking for the latter: compute the contour of a tree.
From the library you shared (fantastic!), maybe what I need to do is ‘drawOffsetCurves’?

[micycle]

I described finding the inner axis (what you called “branches”, in green) of a polygonal shape.

If you truly need offset curves, the method is PGS_Contour.offsetCurvesOutward​().

However, you may also want to look at PGS_Morphology.buffer() (buffering the green branches – lines – into a wider tree-like shape).

[paulgoux]

Do you need vertex data? Otherwise you could use a canny implementation. This would produce a contour. You may need to thicken some lines, and if you are basing it on triangles just changing strokesize might be an issue, although if you know where the center vertex of the triangle is making it wider or thinner shouldn’t be a problem or you could just use fill with no stroke then canny.

Alternively some line intersection tests could be an option.

[ishback]

@paulgoux, I do need vertex data since I want to create shading on one side of the tree.

@micycle, I believe the suggested methods need a shape to start with (vs a line) and will offset the shape uniformly (vs applying variable thickness in different parts of the shape). Ideally I’d create an outline based on the center lines (in green) provided a thickness value for each segment, but I can’t find an easy way to do it.

I’m thinking about this:

• Create the branches (center line, in green)
• Create segments for each branch
• Create small rectangles for each segment, using the length and thickness associated to each segment.
• Create the shape union of all rectangles → that should become a single shape tree, with variable thickness branches.

Is there an easier way?

[micycle]

buffer() works on lines.

As you’ve mentioned, first split the center lines into short segments, and then buffer them based on y position.

[solub]

Hi @ishback

Just a thought.

You could offset the line segments of your tree with a dedicated library (preferably one that handles intersections) and then adjust the vertices of the offsetted contour based on the depth of their closest tree node.

A quick example using the Clipper library in Python mode:

import clipper as cp

# List of nodes
nodes = [PVector(320, 682), PVector(332, 397), 
         PVector(194, 250), PVector(33, 205), 
         PVector(410, 175), PVector(255, 98),
         PVector(343, 67), PVector(422, 76), 
         PVector(201, 53), PVector(510, 46)]

# Connectivity information (bottom-up) as a Python dictionary (tree)
d = {0: [1],
     1: [2, 4],
     2: [3, 5],
     3: [],
     4: [7, 9],
     5: [8, 6], 
     6: [],
     7: [],
     8: [],
     9: []}


# Maximum depth of that tree
max_depth = 5

def setup():
    size(550, 700, P2D)
    background(255)
    smooth(8)
    
    # Get all line segments 
    segs = [nodes[:3]]
    for i in d.keys()[1:]:
        p1 = nodes[i]
        for j in d[i]:
            if j != 2:
                p2 = nodes[j]
                segs.append([p1, p2])
            
    # Offset those segments (distance=13)
    contours = cp.OffsetPolyLines(segs, 13) 
    
    # Adjust contour vertices based on the depth of their closest node
    for i, side in enumerate(contours):
        for j, pt in enumerate(side):
            pvec = PVector(*pt)                                        #convert vertex to PVector (original vertices are in Clipper "Point" format)
            closest_node, closest_index = get_closest(pvec, nodes)     #find the index and location of closest node
            dir = closest_node.copy().sub(pvec)                        #compute direction from vertex to closest node
    
            factor = map(get_depth(closest_index), max_depth, 1, 0, 1) #compute a factor value based on the depth of that closest node
            dir.mult(factor)                                           #multiply direction vector by that value (the deeper the node, the closer is the associated vertex)
            
            contours[i][j] = pvec.add(dir)                             #move node in this direction and update contours accordingly
            
            

    # Draw the updated contours
    for side in contours:
        for p1, p2 in zip(side, side[1:] + side[:1]):
            line(p1.x, p1.y, p2.x, p2.y)
    
    
def get_closest(p, cloud):
        
    min_dist = 1000
    closest_p = None
    closest_i = None
    for i, e in enumerate(cloud):
        d = p.dist(e)
        if d < min_dist:
            min_dist = d
            closest_p = e
            closest_i = i
            
    return closest_p, closest_i


def get_depth(k):
    if not d[k]:
        return 1
    return 1 + max(get_depth(child) for child in d[k])