javarecursionstddraw

Drawing a tree using recursion

I am trying to draw a tree using recursion. The tree needs to look like this:

Desired output

A short summary of how I'm supposed to do it:

Here's how I tackled the problem. I wanted to just draw the trunk, left branch and right branch. I managed to do this, with the following function:

public void drawTree(double length, double min_length, double width, double alpha) {
        //Draws the trunk of the tree
        StdDraw.setPenRadius(width);
        StdDraw.line(250, 150, 250, 150+length);        

        //Left branch
        double hypotenuse = (3.0/4.0)*length;
        double opposite = Math.sin(alpha) * hypotenuse;
        double adjacent = Math.sqrt(Math.pow(hypotenuse, 2)-Math.pow(opposite, 2));
        StdDraw.setPenRadius(width*3.0/4.0);
        StdDraw.line(250,150+length,250-adjacent,150+length+opposite);

        //Right branch
        double hypotenuse2 = (2.0/3.0)*length;
        double opposite2 = Math.sin(alpha) * hypotenuse2;
        double adjacent2 = Math.sqrt(Math.pow(hypotenuse2, 2)-Math.pow(opposite2, 2));
        StdDraw.setPenRadius(width*1.0/2.0);
        StdDraw.line(250,150+length,250+adjacent2,150+length+opposite2);       

    }

This is the output and it is just as I wanted it to be:

First part

I thought the rest would be easy, but I haven't made any progress in the last 3 hours :/. I included the if statement for the stopping condition. But I don't have an idea about the recursive part. I've tried this:

if (length > min_length) {
    //Left branch
    double hypotenuse = (3.0/4.0)*length;
    double opposite = Math.sin(alpha) * hypotenuse;
    double adjacent = Math.sqrt(Math.pow(hypotenuse, 2)-Math.pow(opposite, 2));
    StdDraw.setPenRadius(width*3.0/4.0);
    StdDraw.line(250,150+length,250-adjacent,150+length+opposite);
    //Right branch
    double hypotenuse2 = (2.0/3.0)*length;
    double opposite2 = Math.sin(alpha) * hypotenuse2;
    double adjacent2 = Math.sqrt(Math.pow(hypotenuse2, 2)-Math.pow(opposite2, 2));
    StdDraw.setPenRadius(width*1.0/2.0);
    StdDraw.line(250,150+length,250+adjacent2,150+length+opposite2);
    //My first attempt
    drawTree(hypotenuse*hypotenuse, min_length, width, alpha);
    drawTree(hypotenuse2*hypotenuse2, min_length, width, alpha);
    //My second attempt
    drawTree(hypotenuse, min_length, width, alpha);
    drawTree(hypotenuse2, min_length, width, alpha);       
}

I understand simple recursion like factorials, palindrome, etc, but I'm stuck on this one and I'd appreciate any help.

Solution

  • As already pointed out in the comments and the current answer, it's crucial to make the drawTree method agnostic of which part of the tree is currently drawn.

    You may not use absolute coordinates in this method. And you have to keep track of where you currently are. This can be done, for example, by passing a Point2D through the recursive method that describes the starting point of the current tree part.

    You don't even need explicit code to draw the branches: Note that a single line already is a tree. The branches are then just "smaller trees": They are, again, single lines, but with different length and widths.

    (And with a certain angle compared to the previous tree. You did not mention this, but the angle seems to be Math.PI / 5 according to the screenshot)

    RecursiveTree

    import java.awt.BasicStroke;
import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.GridLayout;
import java.awt.RenderingHints;
import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.util.function.DoubleConsumer;

import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.JSlider;
import javax.swing.SwingUtilities;
import javax.swing.event.ChangeEvent;
import javax.swing.event.ChangeListener;

public class RecursiveTreeDrawing
{
    public static void main(String[] args) 
    {
        SwingUtilities.invokeLater(new Runnable()
        {
            @Override
            public void run()
            {
                createAndShowGUI();
            }
        });
    }    

    private static void createAndShowGUI()
    {
        JFrame f = new JFrame();
        f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        f.getContentPane().setLayout(new BorderLayout());

        RecursiveTreeDrawingPanel p = new RecursiveTreeDrawingPanel();
        p.setPreferredSize(new Dimension(500,500));
        f.getContentPane().add(p, BorderLayout.CENTER);

        JPanel c = new JPanel(new GridLayout(0,1));

        c.add(createControl("left length", 0, 0.9, 
            d -> p.setLeftLengthFactor(d)));
        c.add(createControl("left width", 0, 0.9, 
            d -> p.setLeftWidthFactor(d)));
        c.add(createControl("left angle", 0, Math.PI, 
            d -> p.setLeftAngleDelta(d)));

        c.add(createControl("right length", 0, 0.9, 
            d -> p.setRightLengthFactor(d)));
        c.add(createControl("right width", 0, 0.9, 
            d -> p.setRightWidthFactor(d)));
        c.add(createControl("right angle", -Math.PI, 0, 
            d -> p.setRightAngleDelta(d)));
        f.getContentPane().add(c, BorderLayout.SOUTH);

        f.pack();
        f.setLocationRelativeTo(null);
        f.setVisible(true);
    }

    private static JPanel createControl(
        String name, double min, double max, DoubleConsumer doubleConsumer)
    {
        JPanel p = new JPanel(new GridLayout(1,0));
        p.add(new JLabel(name));
        JSlider slider = new JSlider(0, 100, 0);
        slider.addChangeListener(new ChangeListener()
        {

            @Override
            public void stateChanged(ChangeEvent e)
            {
                int value = slider.getValue();
                double v = value / 100.0;
                double d = min + v * (max - min);
                doubleConsumer.accept(d);
            }
        });
        p.add(slider);

        return p;
    }

}


class RecursiveTreeDrawingPanel extends JPanel
{
    private double leftLengthFactor = 3.0 / 4.0;
    private double leftWidthFactor = 3.0 / 4.0;
    private double leftAngleDelta = Math.PI / 5.0;
    private double rightLengthFactor = 2.0 / 3.0;
    private double rightWidthFactor = 1.0 / 2.0;
    private double rightAngleDelta = - Math.PI / 5.0; 

    @Override
    protected void paintComponent(Graphics gr)
    {
        super.paintComponent(gr);
        Graphics2D g = (Graphics2D)gr;
        g.setColor(Color.BLACK);
        g.fillRect(0,0,getWidth(),getHeight());
        g.setRenderingHint(
            RenderingHints.KEY_ANTIALIASING, 
            RenderingHints.VALUE_ANTIALIAS_ON);
        Point2D start = new Point2D.Double(
            getWidth() * 0.5, 
            getHeight() * 0.7);
        g.setColor(Color.GRAY);
        drawTree(g, start, 100.0, 2.0, 10.0, 0);
    }

    private void drawTree(Graphics2D g, 
        Point2D start, double length, double minLength, 
        double width, double alpha)
    {
        if (length < minLength)
        {
            return;
        }
        g.setStroke(new BasicStroke((float)width, 
            BasicStroke.CAP_ROUND, BasicStroke.JOIN_ROUND));
        Point2D end = new Point2D.Double(
            start.getX() + Math.sin(alpha + Math.PI) * length,
            start.getY() + Math.cos(alpha + Math.PI) * length);
        g.draw(new Line2D.Double(start, end));
        drawTree(g, end, length * leftLengthFactor, minLength, 
            width * leftWidthFactor, alpha + leftAngleDelta);
        drawTree(g, end, length * rightLengthFactor, minLength, 
            width * rightWidthFactor, alpha + rightAngleDelta);
    }

    public void setLeftLengthFactor(double leftLengthFactor)
    {
        this.leftLengthFactor = leftLengthFactor;
        repaint();
    }

    public void setLeftWidthFactor(double leftWidthFactor)
    {
        this.leftWidthFactor = leftWidthFactor;
        repaint();
    }

    public void setLeftAngleDelta(double leftAngleDelta)
    {
        this.leftAngleDelta = leftAngleDelta;
        repaint();
    }

    public void setRightLengthFactor(double rightLengthFactor)
    {
        this.rightLengthFactor = rightLengthFactor;
        repaint();
    }

    public void setRightWidthFactor(double rightWidthFactor)
    {
        this.rightWidthFactor = rightWidthFactor;
        repaint();
    }

    public void setRightAngleDelta(double rightAngleDelta)
    {
        this.rightAngleDelta = rightAngleDelta;
        repaint();
    }

}