7

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:

  • The trunk of the tree has length of length and width width
  • The trunk splits into two branches
  • The left one has the 3/4 of the trunk length and the right one 2/3 of the trunk length
  • Left branch width is 3/4 of the trunk width and the right branch width is 1/2 of trunk width
  • The parameters that we receive are length, min_length, width, alpha (all doubles)
  • The branches grow until the branches are longer than the min_length

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.

mythic
  • 895
  • 2
  • 13
  • 31
  • You appear to be hard-coding drawing points, something that you cannot do since their location will be relative to the start point, the current branch length, and the initial angle. Instead focus on what would be needed to draw an arbitrary branch of the tree. Work this out on paper first, not in code. – Hovercraft Full Of Eels May 03 '15 at 16:25
  • @HovercraftFullOfEels Working this out on paper now. I was thinking about creating variables x0, y0, x1 and y1. At first I'll set them to the same values I've been starting with now and then updating them accordingly. x0 is x1 after we draw the line, y0 is y1... Am I going in the right direction? At the moment x0 doesn't change the value at all, so this is (a part of) the problem? – mythic May 03 '15 at 17:05
  • I would start with whatever needs to be passed into the `createBranch(...)` method. Perhaps int generationNumber (to allow you to stop recursion when it reaches MAX_GENERATION), double angle, and double branchLength. You'll also need a double SCALE constant that is used to shrink the size of the next branch. – Hovercraft Full Of Eels May 03 '15 at 17:09
  • @HovercraftFullOfEels I'm confused now. So I have to scrap the whole drawTree method? Because I already have a variable that stops the recursion (min_length). We are shrinking the branch size each time, and when it's shrunk down to min_length the recursion stops. – mythic May 03 '15 at 17:42
  • No, that's fine. I didn't see that. – Hovercraft Full Of Eels May 03 '15 at 17:56

2 Answers2

2

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();
    }

}
Marco13
  • 53,703
  • 9
  • 80
  • 159
1

Your drawTree() is too complicated. Call it drawTrunk and just draw the trunk of the tree. Then create a drawTree routine that looks like:

drawTree(basePoint, length, width, angle)
  if length > min_length
    drawTrunk(length, width, angle)
    newBasePoint = top of trunk
    drawTree(newBasePoint, 3/4. * length, 3/4. * width, angle + 45)
    drawTree(newBasePoint, 2/3. * length, 2/3. * width, angle - 45)
Edward Doolittle
  • 4,002
  • 2
  • 14
  • 27