Algorithm : Calc Convex Hull & Draw HTML5 Canvas (Part 2 of N)

• Download TrapPoints_v006.zip - 2.9 KB
• Download TrapPoints_v005.zip - 2.5 KB

Introduction

This article continues the walk-through examination of calculating the Convex Hull algorithm and the HTML5 Canvas work that I'm creating to investigate the algorithm which was started in the first article :
Algorithm : Calc Convex Hull & Draw HTML5 Canvas (Part 1 of 2)[^]  

You can see the latest working copy at my site:  http://raddev.us/TrapPoints[^]

Background

In order to continue writing this article series as a progressive tutorial, I've decided that this time we'll add some more functionality which will allow us to investigate the algorithm more closely.  In this article I'll add two additional steps as code downloads (TrapPoints_v005.zip and TrapPoints_v006.zip).

TrapPoints_v005.zip will add:

The first version of DrawTriangle() method which attempts to iterate through the allPoints[] array and draw a triangle for each set of three points.

TrapPoints_v006.zip will add:

1. ability to select any three points and draw a triangle from those points (user has to press shift key to select points)
2. ability to clear only the lines that are drawn on screen -- does not delete the set of points user added (allPoints[]).
3. Additional buttons which allow the user to run the new functionality.

Why This Set of Functionality?

Algorithm Study

All of the added functionality is an attempt to provide a way to analyze the work that needs to be done to get to the calculation of the Convex Hull.  With this functionality the user will be able to examine how that he may attempt to find all points on the hull by drawing triangles around the points that exist on the canvas. 

HTML5 Canvas / JavaScript Study

This work also allows us to see what JavaScript we can write to manipulate the HTML5 Canvas.  Working on these two items together is an attempt to make both of the subjects more interesting and to help solidify the reader's knowledge of both.

Step 5 (TrapPoints_v005) Begins Here

This version of the code adds just one new function which looks like the following.

function drawTriangle(){

    if (allPoints.length < 3){
        console.log("not enough points to draw a triangle");
        return;
    }
    var triIndex = $("#triangleNumber").val();
    
    if (triIndex < 1){
        return;
    }
    console.log(triIndex);
    var offset = (triIndex - 1);
    maxIdx = allPoints.length;
    
    var firstPoint = null;
    for (var count = 0; count < 2; count++)
    {
        var idxPoint1 = (offset +count) % maxIdx;
        console.log("(offset +count) % maxIdx : " +(offset +count) % maxIdx);
        var idxPoint2 = (offset + count + 1) % maxIdx;
        drawLine(allPoints[idxPoint1], allPoints[idxPoint2]);
        if (count == 0)
        {
            firstPoint = allPoints[idxPoint1];
        }
        else if (count > 0){
            drawLine(allPoints[idxPoint2], firstPoint);
        }
    }
}

Triangle: Need At Least Three Points

The first thing we do in the method is insure that the user has drawn at least three points on the screen.  If he has not added at least three points, we write to the console and exit the method.  Note: This is somewhat of a manual tool so I don't pop up a dialog or anything.  You can add that functionality if you like.

jQuery : Get Value From Input Control

The next thing we do is use jQuery to get the value from the newly added input control.  The following selects the input control: $("#triangleNumber")

We call a jQuery method called val() on that jQuery object and it returns the current value that the control is set to.

We store that value in a variable named triIndex (triangle index) which represents the index of the triangle we want to draw.  This will be the index value of the point in allPoint[] array.  However, I want to make sure the user wants to draw a triangle so if the value is 0 or undefined (not set) then I again return from the method.

I want the user to say, "I want to draw triangle number X" and meaning that Triangle 1 starts with point 0 from the allPoints[] array.  Triangle 0 would be a way to say I don't want to draw a triangle. I do that because I want to use this functionality later so that if the user doesn't want to draw a specific triangle by index he the program will draw a triangle based upon selected points.  

Once the user sets the value to 1 or greater I calculate the offset value using the following line of code: var offset = (triIndex - 1);

Do Not Allow User to Exceed Index Value of Points

I also need to know the max index value of that a point can have in our allPoints[] array (which is the length -1) so I can calculate points within allPoints without every blowing up the index.  That way if the user inputs a huge value in the input box I will never exceed the index value.  Yes, even if there are only 3 points in the array and the user types 3489 into the input box, the drawTrianlge() method will draw the appropriate triangle using offset point indices.  Here's a snapshot of that exact thing:

Modulus Math Works Perfectly For This

To do this work think about what we know. 

1. a triangle is always three points
2. the max number of points in the allPoints[] array.
3. we want to start drawing our triangle with some specific point in the original array of points allPoints[] which is an offset value (for where to begin).
4. the first point will always be the last point also since we are closing the triangle

With that information we can loop through the set of points quite easily using modulus division.

Triangles Always Have Three Points

First of all, the simplest thing we know is that a triangle is always three points.  That sets the bounds of our for loop.  However, you may have noticed that the for loop iterates only twice.  That's because we draw the last two lines in the same loop, because we have all the info we need at that point.  That's because the last line goes from the 3rd point back to the first point to close the triangle.

Get Each Point for Each Line In Triangle

Once inside the loop the first thing we do is calculate the two points we need for each line in the triangle.  We store these index values in two variables (idxPoint1 and idxPoint2).  Calculating the first point is based upon the offset the user has chosen and the iteration of the loop (count) we are on.  However, since we want to insure that we never exceed the largest index of the allPoints array, we calculate the modulus in order to insure the value returned to idxPoint1 will never exceed that max value.

var idxPoint1 = (offset +count) % maxIdx;

The only difference in calculating the second point is that we add one to the index (+ 1 below), but we still do our modulus division to protect from ever exceeding the bounds.  

var idxPoint2 = (offset + count + 1) % maxIdx;

Example Modulus Values

1.     1 % 5 = 1
2.     2 % 5 = 2
3.     3 % 5 = 3
4.     4 % 5 = 4
5.     5 % 5 = 0
6.     6 % 5 = 1
7.     7 % 5 = 2

DrawLine 

Finally, we simply call the drawLine() method we had created in the previous version of TrapPoints and it draws the line between the two points it receives.  It's quite easy.

FirstPoint is LastPoint

Since the last line drawn will always be from the last point to the first point, we store the firstPoint in a variable so we can easily draw the line back to the first point.  

Last Time Through the Loop

The last time (2nd time) through the loop you can see that we call drawLine() twice.  The first time in the normal body of the for loop and the second time in the else if () section.  

Step 5 Conclusion

That's it, now you can draw points on the grid and choose a point to start at (by choosing an index value in the input box) and then click the Draw Triangle button and you'll see a triangle drawn between the points.  

There are some limitations to this code, of course and we'll set out to fix those in the Step 6.  

Step 6 (TrapPoints_v006.zip) Begins Here

Additional Functionality

I added quite a bit of functionality to help the user be able to manipulate points and lines and draw the triangles in places he wants to so he can examine how he might create an Convex Hull algorithm. 

Clear Lines

First of all I wanted you to be able to clear the drawn lines without clearing the points so I added a Clear Lines button that will allow you to redraw the points on the background without any of the triangles or connecting lines being drawn.

Because of the way I cleaned up the code the clearLines() method is extremely simple.

function clearLines(){
    draw();
}

Obviously, that just calls the draw() method so we need to take a look at the altered method.

Main draw() Method

The main draw() method is fairly easy to examine because it is made up of other functionality.  It hasn't changed much since the first article.  

function draw() {
    ctx.globalAlpha = 1;
    // fill the canvas background with white
    ctx.fillStyle="white";
    ctx.fillRect(0,0,ctx.canvas.height,ctx.canvas.width);
    
    // draw the grid background
    for (var lineCount=0;lineCount<LINES;lineCount++)
    {
        ctx.fillStyle=gridColor;
        ctx.fillRect(0,lineInterval*(lineCount+1),ctx.canvas.width,2);
        ctx.fillRect(lineInterval*(lineCount+1),0,2,ctx.canvas.width);
    }
    if (allPoints.length > 0){
        drawPoints();
    }
    drawHighlightPoints();
}

Since the last version I simply added the last if statement and the call to new drawHighlightPoints() method.

The if statement simply checks to see if the allPoints array has any values in it (representing points the user has added).  If it does, then the draw() method will now draw them again. 

Selecting Points To Create A Triangle

Now, let's take a look at the drawHighlightPoints() method and we'll investigate the functionality which allows the user to select three points to draw her own triangle.

drawHightlightPoints() is a simple method that implements a for loop and iterates through some points while calling highlightPoint() so we'll look at both of those methods now.

function drawHighlightPoints(){
    
    for (var x = 0; x < selectedTriangle.length;x++){
        highlightPoint(selectedTriangle[x]);
    }
}
function highlightPoint(point){
    ctx.strokeStyle = "red";
    ctx.lineWidth = 2;
    drawPoint(point);
    // set style back to original
    ctx.strokeStyle = "black";
    ctx.lineWidth = 1;
}

User Can Select Points to Highlight Them

You can see that drawHighlightPoints() works on a new array named selectedTriangle[].  That is the set of (up to) three points that the user has highlighted.  The user can select a point to highlight it by holding the Shift key while clicking a point that is already drawn on the screen.

Choosing the Highlight Point in MouseDownHandler

To see how the code that allows a user to highlight a point we need to look at the new portion of the mouseDownHandler function I've added.  

Here's the entire mouseDownHandler() as it looks now.  The important part is where I determine if the shift key was pressed when the user clicked the mouse.

function mouseDownHandler(event){
     if (event.button == 0){
        var currentPoint = getMousePos(event);
        if ((currentPoint.x > 650) || (currentPoint.y > 650))
        {
            return;
        }
        
        if (event.shiftKey){
                console.log(event.shiftKey);
                var p = hitTest(currentPoint);
                if (p !== undefined)
                {
                    selectedTriangle.push(p);
                    if (selectedTriangle.length > 3){
                        selectedTriangle.shift();
                    }
                    draw();
                }
            }
        else{
                allPoints.push(currentPoint);
                drawPoint(currentPoint);
                console.log(currentPoint);
        }
    }
}

The event object holds a boolean value letting you know if the shift key was pressed so that is easy enough.

Hit Test for the Point

Next, you can see that I call a method I wrote called hitTest() to determine if the place the user clicked has a point which was previously drawn (from allPoints[]). If hitTest is successful it returns a point object that we can use.  Otherwise it returns undefined (no point).

The hitTest() code is interesting and quite simple.

function hitTest(p){
    // iterate through all points
    for (var x = 0;x<allPoints.length;x++){
        if ((Math.abs(p.x - allPoints[x].x) <= RADIUS) && Math.abs(p.y - allPoints[x].y) <=RADIUS){
            console.log("It's a hit..." + allPoints[x]);
            return allPoints[x];
        }
    }
}

hitTest() takes a point representing the current location of the mouse (when the user clicked while holding the shift key).  

Then we just iterate through all the points in the allPoints[] array.  The point value for each point in the allPoints[] array is the center point and the point drawn on screen is actually RADIUS * 2 in size.  That means we need to check if our new point is plus or minus RADIUS away from the value of each point in allPoints[].  

We do that using a simple subtraction statement and the JavaScript Math.abs() (absolute value) function.

If we get a hit, we return the specific point from the allPoints[] array.  Very simple and I think quite elegant.

Back In OnMouseDownHandler

If a valid point is returned we run the following code:

selectedTriangle.push(p);
if (selectedTriangle.length > 3){
         selectedTriangle.shift();
 }
draw();

We push the point onto the selectedTriangle[] array which we use to track points which will be used to draw the triangle selected by the user.  Then you see that we check if the array has more than 3 points on it.  If it does we call the JavaScript shift() method (an array method) which will push the first element off the array and all the items back down on index.  This has the effect of insuring only the last three points are contained in the array.

Cannot Highlight More Than 3 Points

This way the user can never select more than three points at a time.

Finally, we call the draw() method because it will, in turn, call the drawHighlightPoints() method and then all the correct points will be drawn in red.  Here's what it looks like.

DrawTriangle : Altered to Handle User Selected

The last thing we need to look at is the drawTriangle() method which I altered to handle both the indexed triangle and the user selected triangle.  If the index value in the input box is 0 or less and there is a selected triangle defined (user has selected three points) then it will draw a triangle using the red highlighted points. 

function drawTriangle(){
    var tempAllPoints = null;
    if (allPoints.length < 3){
        console.log("not enough points to draw a triangle");
        return;
    }
    var triIndex = $("#triangleNumber").val();
    
    if (triIndex < 1){
        if (selectedTriangle.length == 3){
            tempAllPoints = allPoints;
            allPoints = selectedTriangle;
        }
    }
    console.log(triIndex);
    var offset = (triIndex - 1);
    offset = offset > 0 ? offset :0;
    maxIdx = allPoints.length;
    
    var firstPoint = null;
    for (var count = 0; count < 2; count++)
    {
        var idxPoint1 = (offset +count) % maxIdx;
        console.log("(offset +count) % maxIdx : " +(offset +count) % maxIdx);
        var idxPoint2 = (offset + count + 1) % maxIdx;
        drawLine(allPoints[idxPoint1], allPoints[idxPoint2]);
        if (count == 0)
        {
            firstPoint = allPoints[idxPoint1];
        }
        else if (count > 0){
            drawLine(allPoints[idxPoint2], firstPoint);
        }
    }
    if (tempAllPoints !== null){
        allPoints = tempAllPoints;
    }
}

Basic Functionality (Examine Bold Code Above)

The first line of bolded code simply represents a temp object variable we will use to hold the original allPoints[] array so we can restore it after we draw the user selected triangle.

After that I simply check to see if there is a valid selectedTriangle array (contains 3 points).  If there is I swap out the array with the allPoints array because it is easy to use that same array to do the original drawTriangle() work.

Finally, if the tempAllPoints isn't null then it contains the copy of the original allPoints array and we restore it.

It will look like the following when you highlight three points and click the [Draw Triangle] button.

I hope you learned a lot here and you'll try it out.

Next Article

I'm planning on

1. adding a button to create randomly generated points
2. make it so you can move points -- seems like an interesting challenge
3. start doing some Convex Hull generation implementing first try algorithm.
4. other things as I think of them.

History

First version of this article with two versions of code; 04-26-2016