javascript - Drawing a Polygon - Stack Overflow

admin管理员组

文章数量:1325236

I am using Google Maps API V3 to draw a polygon based on a path, which is an array of random unsorted coordinate points (LatLng). This produces the shape below:

Polylines intersect!!

Problem: Since the shape of the Polygon depends on the order of the points in the path, how can I sort the path to create a polygon where no line intersects and no holes are formed? There is also a reference point (not shown in images) that the polygon must enclose. I believe this require a sorting algorithm, which I cannot find!

No intersection :)

Although Javascript is used to produce this polygon, please feel free to use any language to solve this problem

EDIT: There is a reference point that the polygon must enclose, but this point will not be any vertex of the polygon

I am using Google Maps API V3 to draw a polygon based on a path, which is an array of random unsorted coordinate points (LatLng). This produces the shape below:

Polylines intersect!!

Problem: Since the shape of the Polygon depends on the order of the points in the path, how can I sort the path to create a polygon where no line intersects and no holes are formed? There is also a reference point (not shown in images) that the polygon must enclose. I believe this require a sorting algorithm, which I cannot find!

No intersection :)

Although Javascript is used to produce this polygon, please feel free to use any language to solve this problem

EDIT: There is a reference point that the polygon must enclose, but this point will not be any vertex of the polygon

• javascript
• algorithm
• google-maps
• graphics
• polygon

Share Improve this question Follow edited Nov 16, 2011 at 17:35 Nyxynyx asked Nov 16, 2011 at 16:15 NyxynyxNyxynyx 63.7k163163 gold badges507507 silver badges856856 bronze badges 4

• 3 There are multiple polygons that could be created from those points. Is the one in the picture the exact one you are looking for? And if so, what defines that one to be the right one? – James Montagne Commented Nov 16, 2011 at 16:19
• The right polygon that I am looking for is one where all the points map out one continuous area with no holes or intersecting of lines. If there are different solutions to this, all should work. – Nyxynyx Commented Nov 16, 2011 at 16:23
• @Nyxynyx - What do you mean by "all should work"? Do you mean the algorithm should identify all valid solutions for the set of points, or any 1 valid solution? – mbeckish Commented Nov 16, 2011 at 16:39
• I see what a few of you meant. There is a reference point that the polygon must enclose, but this point will not be any vertex of the polygon. – Nyxynyx Commented Nov 16, 2011 at 17:35

Add a ment  | 

3 Answers 3

Sorted by: Reset to default 7

Fun question. I believe this works, but please test it out. It's been a long long time since trig.

http://jsfiddle/9DHSf/3/

The ments basically explain it. I find a "central" point (not sure if this is bulletproof, there may be a better way of calculating this or it may not matter that much), figure out how many degrees around that point each point is and then order them by that. Tested it with various points and it seems to work.

var points = [
                {x: 40, y: 40},
                {x: 60, y: 40},
                {x: 60, y: 60},
                {x: 40, y: 60},                
                {x: 0, y: 50},
                {x: 50, y: 0},
                {x: 50, y: 100},
                {x: 100, y: 50}
            ];



// get the canvas element using the DOM
var canvas = document.getElementById('canvas');

// Make sure we don't execute when canvas isn't supported
if (canvas.getContext) {

    // use getContext to use the canvas for drawing
    var ctx = canvas.getContext('2d');

    ctx.fillStyle = "red";


    // calculate max and min x and y
    var minX = points[0].x;
    var maxX = points[0].x;
    var minY = points[0].y;
    var maxY = points[0].y;

    for (var i = 1; i < points.length; i++) {
        if (points[i].x < minX) minX = points[i].x;
        if (points[i].x > maxX) maxX = points[i].x;
        if (points[i].y < minY) minY = points[i].y;
        if (points[i].y > maxY) maxY = points[i].y;
    }


    // choose a "central" point
    var center = {
        x: minX + (maxX - minX) / 2,
        y: minY + (maxY - minY) / 2
    };

    // precalculate the angles of each point to avoid multiple calculations on sort
    for (var i = 0; i < points.length; i++) {
        points[i].angle = Math.acos((points[i].x - center.x) / lineDistance(center, points[i]));

        if (points[i].y > center.y) {
            points[i].angle = Math.PI + Math.PI - points[i].angle;
        }
    }

    // sort by angle
    points = points.sort(function(a, b) {
        return a.angle - b.angle;
    });

    // Draw shape
    ctx.beginPath();
    ctx.moveTo(points[0].x, points[0].y);

    for (var i = 1; i < points.length; i++) {
        ctx.lineTo(points[i].x, points[i].y);
    }

    ctx.lineTo(points[0].x, points[0].y);

    ctx.stroke();
    ctx.fill();
}


function lineDistance(point1, point2) {
    var xs = 0;
    var ys = 0;

    xs = point2.x - point1.x;
    xs = xs * xs;

    ys = point2.y - point1.y;
    ys = ys * ys;

    return Math.sqrt(xs + ys);
}

---

EDIT: After reading your edit, if this "reference point" is known and within the polygon, you should replace "center" with this point.

If you have at most a few dozen points to consider, use a TSP (Traveling Salesman Problem) algorithm to order the points. For Euclidean-distance TSP paths, the path does not cross itself. A lot of TSP code is available online including applets.

A TSP path goes through all presented points. If you want to go through only "outer" points, use a Convex Hull algorithm. It will give points in order on the smallest convex polygon enclosing all points.

It seems that "alpha shape" and "concave hull" are noteworthy

本文标签： javascriptDrawing a PolygonStack Overflow