CODEWITHSUNDEEP
javascriptcoordinatesdraw
dhdz
dhdz

Reputation: 899

JS: Calculate midpoints of lines recursively

I'm writing a simple drawing application in JS that works with coordinates. I need to find the midpoint of two points recursively in order to draw a line(The midpoint between point A and B, and then the two midpoints between the three resulting points, and so on). See this GIF for a clearer example.

This is a grid/coordinate based drawing app, so simply drawing a line is not possible. It is necessary to get all the coordinates between the points.

I have a function that finds midpoints

function findMidpoint(p1,p2){
    return Math.floor((p1+p2)/2);
}

And a function that draws the point (I'm also storing the previous points as prevX and prevY

setPoint(X,Y);

So what I'm doing to draw the midpoints is the following:

setPoint(findMidpoint(X,prevX),findMidpoint(Y,prevY));

The next set of midpoints:

setPoint(findMidpoint(findMidpoint(X,prevX),prevX),findMidpoint(findMidpoint(Y,prevY),prevY));
setPoint(findMidpoint(X,findMidpoint(X,prevX)),findMidpoint(Y,findMidpoint(Y,prevY));

As you can see this gets messy very very quickly. I guess there's a recursive way to do this, or some sort of way of looping it a given amount of times, but I can't seem to figure it out. Any help would be greatly appreciated!

Upvotes: 2

Views: 1708

Answers (3)

Nina Scholz
Nina Scholz

Reputation: 386550

You could calculate the mid points and call the recusion only if the mid point is different than one of the left or right point.

function midpoint(a, b) {
    return Math.floor((a + b) / 2);
}

function drawPoints(p0, p1) {
    var middle = [midpoint(p0[0], p1[0]), midpoint(p0[1], p1[1])];
    ctx.beginPath();
    ctx.fillRect(middle[0], middle[1], 1, 1);
    ctx.closePath();
    if ((p0[0] !== middle[0] || p0[1] !== middle[1]) && (p1[0] !== middle[0] || p1[1] !== middle[1])) {
        drawPoints(p0, middle);
        drawPoints(middle, p1);
    }
}

var ctx = document.getElementById("canvas").getContext("2d");

drawPoints([0,0], [600, 20]);
<canvas id="canvas" style="border-width: 0; display: block; padding: 0; margin: 0;" width="600" height="200"></canvas>

Upvotes: 3

vassiliskrikonis
vassiliskrikonis

Reputation: 596

Your recursive function on each recursion should

  1. Create the midpoint between A and B, say C
  2. Call itself on (A, C) and (B, C)
  3. Stop if A == B or A is very close to B

In code this would be like this:

function placeMidPoint(Ax, Ay, Bx, By) {
  var e = 0; // some small number, if e==0 then you're stopping when A==B
  if( (Ax - Bx) < e && (Ay - By) < e )
    return;
  var Cx = findMidpoint(Ax, Bx);
  var Cy = findMidpoint(Ay, By);
  setPoint(Cx, Cy);

  placeMidPoint(Ax, Ay, Cx, Cy);
  placeMidPoint(Cx, Cy, Bx, By);
}

Upvotes: 0

Hitesh Saini
Hitesh Saini

Reputation: 46

            var points = [];
            function findMid(x,y){ 
                var mid  = parseInt((x+y)/2);
                if(x!=mid && y!=mid){
                    points.push(mid);
                    console.log("x:"+x+" y:"+y+" mid:"+mid);
                    findMid(x,mid);
                    findMid(y,mid);
              }     
            }
            initialPointX = 4;
            initialPointY = 10;
            console.log(findMid(initialPointX,initialPointY));

Upvotes: 1

Related Questions