我只知道如何使用 for 来绘制树，但现在我想使用递归来绘制树 [英] I just know how to use for to draw the tree, but now I want to use recursion to draw the tree

问题描述

我只知道怎么用for画树(树数据是图一，结果是图二)，但是现在想用递归 画树.

I just know how to use for to draw a tree (the tree data is the picture one, the result is picture two), but now I want to use recursion to draw the tree.

请告诉我如何将书写风格从 for 更改为 递归

Please tell me how change writing style from for to recursive

第一个输入点

//input point 
const line_point =[0, 0, 0,
 2, 151, 2,
 2, 151, 2, 
 -62, 283, 63,
 2, 151, 2,
 62, 297, -58,
 -62, 283, 63,
 -104, 334, 74,
 -62, 283, 63,
 -58, 338,  45,
 62, 297, -58, 
 67, 403, -55,
 62, 297, -58,
 105, 365, -86];

取出星点和终点

const star_line_x= new Array();
const star_line_y= new Array();
const star_line_z= new Array();

const end_line_x= new Array();
const end_line_y= new Array();
const end_line_z= new Array();

for (var q=0; q < line_point.length; q+=6){
    star_line_x.push(line_point[q]);
}
for (var r=1; r < line_point.length; r+=6){
    star_line_y.push(line_point[r]);
}
for (var s=2; s < line_point.length; s+=6){
    star_line_z.push(line_point[s]);
}

for (var t=3; t < line_point.length; t+=6){
    end_line_x.push(line_point[t]);
}
for (var u=4; u < line_point.length; u+=6){
    end_line_y.push(line_point[u]);

}
for (var v=5; v < line_point.length; v+=6){

    end_line_z.push(line_point[v]);
}
var cylinder_star_point = new Array();
var cylinder_end_point = new Array();

//star_point end_point
for (var w=0; w < line_point.length/6; w++){

var star_point = new THREE.Vector3 (star_line_x[w],star_line_y[w],star_line_z[w]);
    var end_point = new THREE.Vector3 (end_line_x[w],end_line_y[w],end_line_z[w]);
    cylinder_star_point.push( star_point);
    cylinder_end_point.push( end_point);
}

计算缸高

//calculation cylinder high
var line_len = new Array();
for (var dd=0; dd < line_point.length/6; dd++){
    var len_x = Math.pow(end_line_x[dd]-star_line_x[dd],2);
    var len_y = Math.pow(end_line_y[dd]-star_line_y[dd],2);
    var len_z = Math.pow(end_line_z[dd]-star_line_z[dd],2);
    var len_direction = Math.sqrt(len_x+len_y+len_z);
    line_len.push(len_direction);//Cylinder high

}

计算中心点

//center_point
const cylinder_center_point= new Array();
for (var bb=0; bb< cylinder_end_point.length; bb++){
    var star_set_point = cylinder_star_point[bb];
    var end_set_point = cylinder_end_point[bb];
    var center_point = end_set_point.clone().add(star_set_point).divideScalar(2);
    cylinder_center_point.push(center_point);
}

计算圆柱方向向量

//cylinder direction
const cylinder_direction= new Array();
for (var cc=0; cc < cylinder_end_point.length; cc++){
    var star_direction = cylinder_star_point[cc];
    var end_direction = cylinder_end_point[cc];
    var center_direction  = end_direction.clone().sub(star_direction);
    cylinder_direction.push(center_direction);
}

画圆柱

   for (var dd=0; dd <cylinder_direction.length;dd++){
    var material = new THREE.MeshPhongMaterial({color:'#ff0000'});
    let upVector = new THREE.Vector3(0, 1, 0);

    var geometry = new THREE.CylinderGeometry(5, 5, line_len[dd], 20, 1, false); 
    var mesh = new THREE.Mesh(geometry, material);
    mesh.position.set(0, line_len[dd]/2, 0);

    var group = new THREE.Group();
    group.position.set(star_line_x[dd],star_line_y[dd],star_line_z[dd]);
    group.add(mesh);

    let targetVector =cylinder_direction[dd];
    let quaternion = new THREE.Quaternion().setFromUnitVectors(upVector, targetVector.normalize());
    group.setRotationFromQuaternion(quaternion) 
    scene.add(group)
} 

图二:用于画树

推荐答案

对于一棵树，最简单的方法是从一个树深度开始并假设有 2 个孩子.该函数创建一个分支，如果深度 > 0，则它会递归调用自身以创建另外 2 个分支.

For a tree the simplest method is to start with just a tree depth and assume 2 children. The function makes one branch and if depth > 0 then it recursively calls itself to make 2 more branches.

  const numBranches = 2;
  const spread = 1.5;
  const branchShrinkFactor = 0.8;
  const branchSpreadFactor = 0.8;

  function addBranch(parent, depth, offset, angle, branchLength, spread) {
    const material = new THREE.MeshPhongMaterial({color:'#ff0000'});
    const geometry = new THREE.CylinderBufferGeometry(5, 5, branchLength, 20, 1, false); 
    geometry.translate(0, branchLength / 2, 0);
    const mesh = new THREE.Mesh(geometry, material);
    mesh.position.y = offset;
    mesh.rotation.z = angle;
    parent.add(mesh);
    if (depth > 1) {
      for (let i = 0; i < numBranches; ++i) {
        const a = i / (numBranches - 1) - 0.5;
        addBranch(mesh, depth - 1, branchLength, a * spread, branchLength * branchShrinkFactor, spread * branchSpreadFactor)
      }
    }
  }
  addBranch(scene, 5, 0, 0, 100, 1.5);

body {
  margin: 0;
}
#c {
  width: 100vw;
  height: 100vh;
  display: block;
}

<canvas id="c"></canvas>
<script type="module">
import * as THREE from 'https://threejsfundamentals.org/threejs/resources/threejs/r115/build/three.module.js';

function main() {
  const canvas = document.querySelector('#c');
  const renderer = new THREE.WebGLRenderer({canvas});

  const fov = 75;
  const aspect = 2;  // the canvas default
  const near = 1;
  const far = 1000;
  const camera = new THREE.PerspectiveCamera(fov, aspect, near, far);
  camera.position.set(0, 150, 300);

  const scene = new THREE.Scene();
  scene.background = new THREE.Color('lightskyblue');

  {
    const color = 0xFFFFFF;
    const intensity = 1;
    const light = new THREE.DirectionalLight(color, intensity);
    light.position.set(-1, 2, 4);
    scene.add(light);
  }


  const numBranches = 2;
  const spread = 1.5;
  const branchShrinkFactor = 0.8;
  const branchSpreadFactor = 0.8;

  function addBranch(parent, depth, offset, angle, branchLength, spread) {
    const material = new THREE.MeshPhongMaterial({color:'#ff0000'});
    const geometry = new THREE.CylinderBufferGeometry(5, 5, branchLength, 20, 1, false); 
    geometry.translate(0, branchLength / 2, 0);
    const mesh = new THREE.Mesh(geometry, material);
    mesh.position.y = offset;
    mesh.rotation.z = angle;
    parent.add(mesh);
    if (depth > 1) {
      for (let i = 0; i < numBranches; ++i) {
        const a = i / (numBranches - 1) - 0.5;
        addBranch(mesh, depth - 1, branchLength, a * spread, branchLength * branchShrinkFactor, spread * branchSpreadFactor)
      }
    }
  }
  addBranch(scene, 5, 0, 0, 100, 1.5);

  function resizeRendererToDisplaySize(renderer) {
    const canvas = renderer.domElement;
    const width = canvas.clientWidth;
    const height = canvas.clientHeight;
    const needResize = canvas.width !== width || canvas.height !== height;
    if (needResize) {
      renderer.setSize(width, height, false);
    }
    return needResize;
  }

  function render(time) {
    time *= 0.001;

    if (resizeRendererToDisplaySize(renderer)) {
      const canvas = renderer.domElement;
      camera.aspect = canvas.clientWidth / canvas.clientHeight;
      camera.updateProjectionMatrix();
    }

    renderer.render(scene, camera);

//    requestAnimationFrame(render);
  }

  requestAnimationFrame(render);
}

main();
</script>

如果您想要每个分支的特定数据，则需要将其传入.例如

If you want specific data for each branch then you need to pass that in. For example

  const tree = [
    { length: 100, angle:  0,   branches: 2 },  // root
    { length:  40, angle: -1,   branches: 3 },  // first branch
    { length:  50, angle:  0.8, branches: 0 },  // 1st child branch
    { length:  40, angle:  0.3, branches: 0 },  // 2nd child branch
    { length:  30, angle: -0.3, branches: 0 },  // 3rd child branch
    { length:  50, angle:  0.8, branches: 2 },  // second branch
    { length:  50, angle:  0.5, branches: 0 },  // 1st child branch
    { length:  40, angle: -0.6, branches: 2 },  // 2nd child branch
    { length:  40, angle: -0.3, branches: 0 },  // 1st grandchild branch
    { length:  95, angle:  0.3, branches: 0 },  // 2st grandchild branch
  ];

然后遍历树描述，如果特定分支的 branches > 0，则它会递归调用自身以添加这些分支.每个分支消耗分支数组中的一行，因此我们传回 ndx 以便我们可以知道消耗了多少行.

and then walk the tree description, if a branches for a particular branch is > 0 then it recursively calls itself to add those branches. Each branches consumes a row in the array of branches so we pass back ndx so we can tell how many rows were consumed.

  function addBranch(parent, offset, tree, ndx = 0) {
    const {length, angle, branches} = tree[ndx];

    const material = new THREE.MeshPhongMaterial({color:'#ff0000'});
    const geometry = new THREE.CylinderGeometry(5, 5, length, 20, 1, false); 
    geometry.translate(0, length / 2, 0);
    const mesh = new THREE.Mesh(geometry, material);
    mesh.position.y = offset;
    mesh.rotation.z = angle;
    parent.add(mesh);
    for (let i = 0; i < branches; ++i) {
      ndx = addBranch(mesh, length, tree, ++ndx);
    }
    return ndx;
  }
  addBranch(scene, 0, tree);

body {
  margin: 0;
}
#c {
  width: 100vw;
  height: 100vh;
  display: block;
}

<canvas id="c"></canvas>
<script type="module">
import * as THREE from 'https://threejsfundamentals.org/threejs/resources/threejs/r115/build/three.module.js';

function main() {
  const canvas = document.querySelector('#c');
  const renderer = new THREE.WebGLRenderer({canvas});

  const fov = 75;
  const aspect = 2;  // the canvas default
  const near = 1;
  const far = 1000;
  const camera = new THREE.PerspectiveCamera(fov, aspect, near, far);
  camera.position.set(0, 150, 300);

  const scene = new THREE.Scene();
  scene.background = new THREE.Color('lightskyblue');

  {
    const color = 0xFFFFFF;
    const intensity = 1;
    const light = new THREE.DirectionalLight(color, intensity);
    light.position.set(-1, 2, 4);
    scene.add(light);
  }


  const tree = [
    { length: 100, angle:  0,   branches: 2 },  // root
    { length:  40, angle: -1,   branches: 3 },  // first branch
    { length:  50, angle:  0.8, branches: 0 },  // 1st child branch
    { length:  40, angle:  0.3, branches: 0 },  // 2nd child branch
    { length:  30, angle: -0.3, branches: 0 },  // 3rd child branch
    { length:  50, angle:  0.8, branches: 2 },  // second branch
    { length:  50, angle:  0.5, branches: 0 },  // 1st child branch
    { length:  40, angle: -0.6, branches: 2 },  // 2nd child branch
    { length:  40, angle: -0.3, branches: 0 },  // 1st grandchild branch
    { length:  95, angle:  0.3, branches: 0 },  // 2st grandchild branch
  ];
  
  function addBranch(parent, offset, tree, ndx = 0) {
    const {length, angle, branches} = tree[ndx];

    const material = new THREE.MeshPhongMaterial({color:'#ff0000'});
    const geometry = new THREE.CylinderGeometry(5, 5, length, 20, 1, false); 
    geometry.translate(0, length / 2, 0);
    const mesh = new THREE.Mesh(geometry, material);
    mesh.position.y = offset;
    mesh.rotation.z = angle;
    parent.add(mesh);
    for (let i = 0; i < branches; ++i) {
      ndx = addBranch(mesh, length, tree, ++ndx);
    }
    return ndx;
  }
  addBranch(scene, 0, tree);

  function resizeRendererToDisplaySize(renderer) {
    const canvas = renderer.domElement;
    const width = canvas.clientWidth;
    const height = canvas.clientHeight;
    const needResize = canvas.width !== width || canvas.height !== height;
    if (needResize) {
      renderer.setSize(width, height, false);
    }
    return needResize;
  }

  function render(time) {
    time *= 0.001;

    if (resizeRendererToDisplaySize(renderer)) {
      const canvas = renderer.domElement;
      camera.aspect = canvas.clientWidth / canvas.clientHeight;
      camera.updateProjectionMatrix();
    }

    renderer.render(scene, camera);

//    requestAnimationFrame(render);
  }

  requestAnimationFrame(render);
}

main();
</script>

我不清楚您的输入数据是什么.你的树每层有 3 个和 2 个分支的深度，所以这个数据可以工作

It's not clear to me what your input data is. Your tree has a depth of 3 and 2 branches per level so this data would work

const endPoints = [
  [   0,   0,   0],  // A
  [   2, 151,   2],  // B
  [ -62, 283,  63],  // C
  [-104, 334,  74],  // E
  [ -58, 338,  45],  // F
  [  62, 296, -58],  // D
  [  67, 403, -55],  // G
  [ 105, 365, -86],  // H
];

使用此代码

  // assumes there are 2 branches per
  function addBranch(parent, depth, offset, tree, parentNdx = 0, childNdx = 1) {
    const start = tree[parentNdx];
    const end = tree[childNdx];
    const length = start.distanceTo(end);

    const material = new THREE.MeshPhongMaterial({color:'#ff0000'});
    const geometry = new THREE.CylinderGeometry(5, 5, length, 20, 1, false); 
    geometry.translate(0, length / 2, 0);
    geometry.rotateX(Math.PI / 2);
    const mesh = new THREE.Mesh(geometry, material);
    mesh.position.z = offset;
    parent.add(mesh);
    mesh.lookAt(end);
    let ndx = childNdx + 1;
    if (depth > 1) {
      const numBranches = 2;
      for (let i = 0; i < numBranches; ++i) {
        ndx = addBranch(mesh, depth - 1, length, tree, childNdx, ndx);
      }
    }
    return ndx;
  }
  addBranch(scene, 3, 0, tree);

我将圆柱体指向正 Z 方向，这意味着我可以使用 lookAt 将圆柱体从起点指向终点.

I pointed the cylinders in the positive Z direction which means I can use lookAt to point the cylinder from its start to its end point.

body {
  margin: 0;
}
#c {
  width: 100vw;
  height: 100vh;
  display: block;
}

<canvas id="c"></canvas>
<script type="module">
import * as THREE from 'https://threejsfundamentals.org/threejs/resources/threejs/r115/build/three.module.js';

function main() {
  const canvas = document.querySelector('#c');
  const renderer = new THREE.WebGLRenderer({canvas});

  const fov = 75;
  const aspect = 2;  // the canvas default
  const near = 1;
  const far = 1000;
  const camera = new THREE.PerspectiveCamera(fov, aspect, near, far);
  camera.position.set(250, 170, 250);
  camera.lookAt(0, 170, 0);

  const scene = new THREE.Scene();
  scene.background = new THREE.Color('lightskyblue');

  {
    const color = 0xFFFFFF;
    const intensity = 1;
    const light = new THREE.DirectionalLight(color, intensity);
    light.position.set(-1, 2, 4);
    scene.add(light);
  }

  const tree = [
    [   0,   0,   0],  // A
    [   2, 151,   2],  // B
    [ -62, 283,  63],  // C
    [-104, 334,  74],  // E
    [ -58, 338,  45],  // F
    [  62, 296, -58],  // D
    [  67, 403, -55],  // G
    [ 105, 365, -86],  // H
  ].map(v => new THREE.Vector3().fromArray(v));

  // assumes there are 2 branches per
  function addBranch(parent, depth, offset, tree, parentNdx = 0, childNdx = 1) {
    const start = tree[parentNdx];
    const end = tree[childNdx];
    const length = start.distanceTo(end);

    const material = new THREE.MeshPhongMaterial({color:'#ff0000'});
    const geometry = new THREE.CylinderGeometry(5, 5, length, 20, 1, false); 
    geometry.translate(0, length / 2, 0);
    geometry.rotateX(Math.PI / 2);
    const mesh = new THREE.Mesh(geometry, material);
    mesh.position.z = offset;
    parent.add(mesh);
    mesh.lookAt(end);
    let ndx = childNdx + 1;
    if (depth > 1) {
      const numBranches = 2;
      for (let i = 0; i < numBranches; ++i) {
        ndx = addBranch(mesh, depth - 1, length, tree, childNdx, ndx);
      }
    }
    return ndx;
  }
  addBranch(scene, 3, 0, tree);

  function resizeRendererToDisplaySize(renderer) {
    const canvas = renderer.domElement;
    const width = canvas.clientWidth;
    const height = canvas.clientHeight;
    const needResize = canvas.width !== width || canvas.height !== height;
    if (needResize) {
      renderer.setSize(width, height, false);
    }
    return needResize;
  }

  function render(time) {
    time *= 0.001;

    if (resizeRendererToDisplaySize(renderer)) {
      const canvas = renderer.domElement;
      camera.aspect = canvas.clientWidth / canvas.clientHeight;
      camera.updateProjectionMatrix();
    }

    renderer.render(scene, camera);

//    requestAnimationFrame(render);
  }

  requestAnimationFrame(render);
}

main();
</script>

注意:这只是递归创建树的无限方式之一.除了深度优先的数组，您还可以创建一个树结构来传递给算法

note: this only one of infinite ways to create the tree recursively. Rather than an array in depth first order you could also create a tree structure to pass into the algorithm

  const E = { 
    pos: [-104, 334,  74],
  };
  const F = {
    pos: [ -58, 338,  45], 
  };
  const C = {
    pos: [ -62, 283,  63],
    children: [E, F],
  };
  const G = {
    pos: [  67, 403, -55],
  };
  const H = {
    pos: [ 105, 365, -86],
  };
  const D = {
    pos: [  62, 296, -58],
    children: [G, H],
  };
  const B = {
    pos: [   2, 151,   2],
    children: [C, D],
  };
  const A = {
    pos: [0, 0, 0],
    children: [B],
  };

  function addBranch(parent, branch, offset = 0) {
    const {pos, children} = branch;
    const start = new THREE.Vector3().fromArray(pos);
    for (const child of children) {
      const end = new THREE.Vector3().fromArray(child.pos);
      const length = start.distanceTo(end);
      const geometry = new THREE.CylinderGeometry(5, 5, length, 20, 1, false); 
      geometry.translate(0, length / 2, 0);
      geometry.rotateX(Math.PI / 2);
      const material = new THREE.MeshPhongMaterial({color: 'red'});
      const mesh = new THREE.Mesh(geometry, material);
      mesh.position.z = offset;
      parent.add(mesh);
      mesh.lookAt(end);
      if (child.children) {
        addBranch(mesh, child, length);
      }
    }
  }
  addBranch(scene, A);

body {
  margin: 0;
}
#c {
  width: 100vw;
  height: 100vh;
  display: block;
}

<canvas id="c"></canvas>
<script type="module">
import * as THREE from 'https://threejsfundamentals.org/threejs/resources/threejs/r115/build/three.module.js';

function main() {
  const canvas = document.querySelector('#c');
  const renderer = new THREE.WebGLRenderer({canvas});

  const fov = 75;
  const aspect = 2;  // the canvas default
  const near = 1;
  const far = 1000;
  const camera = new THREE.PerspectiveCamera(fov, aspect, near, far);
  camera.position.set(250, 170, 250);
  camera.lookAt(0, 170, 0);

  const scene = new THREE.Scene();
  scene.background = new THREE.Color('lightskyblue');

  {
    const color = 0xFFFFFF;
    const intensity = 1;
    const light = new THREE.DirectionalLight(color, intensity);
    light.position.set(-1, 2, 4);
    scene.add(light);
  }

  const E = { 
    pos: [-104, 334,  74],
  };
  const F = {
    pos: [ -58, 338,  45], 
  };
  const C = {
    pos: [ -62, 283,  63],
    children: [E, F],
  };
  const G = {
    pos: [  67, 403, -55],
  };
  const H = {
    pos: [ 105, 365, -86],
  };
  const D = {
    pos: [  62, 296, -58],
    children: [G, H],
  };
  const B = {
    pos: [   2, 151,   2],
    children: [C, D],
  };
  const A = {
    pos: [0, 0, 0],
    children: [B],
  };
  
  function addBranch(parent, branch, offset = 0) {
    const {pos, children} = branch;
    const start = new THREE.Vector3().fromArray(pos);
    for (const child of children) {
      const end = new THREE.Vector3().fromArray(child.pos);
      const length = start.distanceTo(end);
      const geometry = new THREE.CylinderGeometry(5, 5, length, 20, 1, false); 
      geometry.translate(0, length / 2, 0);
      geometry.rotateX(Math.PI / 2);
      const material = new THREE.MeshPhongMaterial({color: 'red'});
      const mesh = new THREE.Mesh(geometry, material);
      mesh.position.z = offset;
      parent.add(mesh);
      mesh.lookAt(end);
      if (child.children) {
        addBranch(mesh, child, length);
      }
    }
  }
  addBranch(scene, A);

  function resizeRendererToDisplaySize(renderer) {
    const canvas = renderer.domElement;
    const width = canvas.clientWidth;
    const height = canvas.clientHeight;
    const needResize = canvas.width !== width || canvas.height !== height;
    if (needResize) {
      renderer.setSize(width, height, false);
    }
    return needResize;
  }

  function render(time) {
    time *= 0.001;

    if (resizeRendererToDisplaySize(renderer)) {
      const canvas = renderer.domElement;
      camera.aspect = canvas.clientWidth / canvas.clientHeight;
      camera.updateProjectionMatrix();
    }

    renderer.render(scene, camera);

//    requestAnimationFrame(render);
  }

  requestAnimationFrame(render);
}

main();
</script>

这篇关于我只知道如何使用 for 来绘制树，但现在我想使用递归来绘制树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！