Find max height-width of irregular shape drawn on HTML 5 canvas

Question

I've been doing some image processing recently, and am looking for a javascript solution to determine the longest line segment that is entirely within a non-regular shape. To sum it up, the line segment should be the longest line segment that touches the shape and not overlaps or moves outside of the shape.

Here are the steps which I have followed

step 1:

step 2:

step 3:

as shown in step 3 Blue line indicates max length. It is working perfectly to determine the length of regular shapes, but in case of irregular shapes it is not working (also in the case of 3 points).

To calculate length first I have taken points (which are mouse coordinates on the canvas down event.

Here is the snippet for Canvas down :

function getXY(e) {
    var el = document.getElementById('canvas');
    var rect = el.getBoundingClientRect();
    /* console.log("widht "+$("#canvas").width());
    console.log("heihgt "+$("#canvas").height());
    console.log("X "+Math.round(e.clientX - rect.left));
    console.log("y "+Math.round(e.clientY - rect.top));*/
    return {
        x: Math.round(e.clientX - rect.left),
        y: Math.round(e.clientY - rect.top)
    }
}


 $('#canvas').mousedown(function(e) {
        var can = document.getElementById("canvas");
        var ctx = can.getContext('2d');
        if (condition == 1) {
            if (e.which == 1) {
                //store the points on mousedown
                var poss = getXY(e);
                i = i + 1;
                if (firstX == poss.x && firstY == poss.y) {
                    console.log(" inside if  poss.x===" + poss.x + " poss.y===" + poss.y);
                    //$('#crop').click();
                } else {
                    console.log(" inside else  poss.x===" + poss.x + " poss.y===" + poss.y);
                    points.push(Math.round(poss.x), Math.round(poss.y));
                    pointsforline.push({ "x": Math.round(poss.x), "y": Math.round(poss.y) });
                    xarray.push(poss.x);
                    yarray.push(poss.y);
                    sendpoints.push(Math.round(poss.x), Math.round(poss.y));
                    if(points.length >= 6){
                        $('#fixMarkingBtn').show();
                    }
                }

                // Type 1 using array


                 if(points.length == 6  && sendpoints.length ==6 ){
                 $('#fixMarkingBtn').show();
                 }

                // Type 2 using counter

               /* if (i == 3) {
                    $('#fixMarkingBtn').show();
                }*/

                if (i == 1) {
                    $('#undoMarkingBtn').show();
                    $('#resetMarkingBtn').show();
                    firstX = poss.x;
                    firstY = poss.y;
                    //change is here
                    Xmax = poss.x;
                    Ymax = poss.y;
                    Xmin = poss.x;
                    Ymin = poss.y;
                    minX1 = poss.x;
                    maxY1 = poss.y;
                    minX1 = poss.x;
                    minY1 = poss.y;

                }
                if (poss.x < Xmin) {
                    Xmin = poss.x;
                    minY1 = poss.y;
                }
                if (poss.x > Xmax) {
                    Xmax = poss.x;
                    maxY1 = poss.y;
                }
                if (poss.y < Ymin) {
                    Ymin = poss.y;
                    minX1 = poss.x;
                }
                if (poss.y > Ymax) {
                    Ymax = poss.y;
                    maxX1 = poss.x;
                }
                ctx.globalCompositeOperation = 'source-over';
                var oldposx = $('#oldposx').html();
                var oldposy = $('#oldposy').html();
                var posx = $('#posx').html();
                var posy = $('#posy').html();
                ctx.beginPath();
                ctx.lineWidth = 13;
                ctx.moveTo(oldposx, oldposy);
                if (oldposx != '') {
                    ctx.lineTo(posx, posy);
                    ctx.stroke();
                }
                $('#oldposx').html(poss.x);
                $('#oldposy').html(poss.y);
            }
            ctx.fillStyle = 'red';
            ctx.strokeStyle = 'red';
            ctx.fillRect(posx, posy, 10, 10);
            $('#posx').html(posx);
            $('#posy').html(posy);
        } //condition

    });

here is the code I have used (point of problem) :

function calMaxMin() {
    for (var i = 0; i < points.length; i += 2) {
        if (i == 0) {
            Xmax = points[i];
            Ymax = points[i + 1];
            Xmin = points[i];
            Ymin = points[i + 1];
            minX1 = points[i];
            maxY1 = points[i + 1];
            minX1 = points[i];
            minY1 = points[i + 1];
        }
        if (points[i] < Xmin) {
            Xmin = points[i];
            minY1 = points[i + 1];
        }
        if (points[i] > Xmax) {
            Xmax = points[i];
            maxY1 = points[i + 1];
        }
        if (points[i + 1] < Ymin) {
            Ymin = points[i + 1];
            minX1 = points[i];
        }
        if (points[i + 1] > Ymax) {
            Ymax = points[i + 1];
            maxX1 = points[i];
        }    
    }
}

Problem image 1

Problem image 2 (what I'm getting right now)

Expected output

Any help would be appreciated.

Thanks in advance!

Answer 1

The problem's complexity changes when you switch from a convex polygon to a concave polygon: you need to check for intersections and "grow" candidate segments.

With a convex polygon, you have one candidate set, defined by all segments (p₁, p₂), (p₁, p₃), ..., (p₂, p₃), ..., (p_n-1, p_n), wherein the longest of those candidates is the result:

This example has a total 10 candidates. You simply select the longest one.

---

When you include concave polygons you must modify the candidate segments to stretch to the edges of the polygon and exclude any segments that intersect the polygon.

The red segments are excluded. The green segments are the modified ones. There are more complicated cases not depicted as well.

NOTE: I've had to play quite a bit with this math in the past and will be linking to functions of an old JavaScript library I built. Points are represented as { x: number, y: number} and polygons as arrays of points.

Segments can be excluded for two reasons:

1. Either endpoint starts with the segment leaving the polygon. You can test this by getting the global angle of the candidate segment (from said endpoint) and the global angles of the two adjacent polygon edges and checking if the candidate segment's angle falls between those two.

2. The candidate segment intersects any of the edges (inclusive of edge endpoints).

Extension of segments is somewhat complicated:

1. Find all segments wherein either endpoint is a concave vertex of the polygon. Include it twice if both endpoints are concave.

2. For said (segment, endpoint) pairs, stretch the segment through the endpoint a long distance (like 10000000) via polar projection.

   1. Detect all intersection points of the elongated segment with the polygon.

   2. Find the intersection point that is nearest the unmodified endpoint. This intersection point and the unmodified endpoint is the new candidate segment.

The result is the longest remaining candidate segment.

HINT: Might I recommend using GeoGebra for diagramming (I am in no way affiliated)?