Dessin d'un polygone

Question

J'utilise Google Maps API V3 pour dessiner un polygone basé sur un chemin, qui est un tableau de points de coordonnées aléatoires non triés (LatLng). Cela produit la forme ci-dessous:

Polylignes se croisent !!

Problème: Depuis la forme du Polygon dépend de l'ordre des points dans le chemin, comment puis-je trier le chemin pour créer un polygone où aucune ligne coupe et pas de trous sont formés? Il y a aussi un point de référence (non montré dans les images) que le polygone doit entourer. Je crois que cela nécessite un algorithme de tri, que je ne trouve pas!

Aucune intersection :)

Bien que Javascript est utilisé pour produire ce polygone, s'il vous plaît ne hésitez pas à utiliser la langue pour résoudre ce problème

EDIT: Il y a une référence le point que le polygone doit entourer, mais ce point ne sera pas un sommet du polygone

Answer 1

question Fun. Je crois que cela fonctionne, mais s'il vous plaît tester. Ca fait longtemps depuis longtemps.

http://jsfiddle.net/9DHSf/3/

Les commentaires expliquent essentiellement cela. Je trouve un point "central" (je ne sais pas si c'est un pare-balles, il peut y avoir une meilleure façon de calculer ou peu importe), détermine combien de degrés il y a autour de chaque point et les ordonne par là . Testé avec différents points et il semble fonctionner.

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: Après avoir lu votre édition, si ce "point de référence" est connu et dans le polygone, vous devez remplacer "centre" avec ce point.

Answer 2

Si vous avez au plus quelques douzaines de points à considérer, utilisez un algorithme TSP (Travelling Salesman Problem) pour ordonner les points. Pour les chemins TSP à distance euclidienne, le chemin ne se croise pas lui-même. Beaucoup de code TSP est disponible online y compris les applets.

Un chemin TSP traverse tous les points présentés. Si vous voulez passer par des points "externes", utilisez un algorithme de coque convexe. Il donnera des points dans l'ordre sur le plus petit polygone convexe entourant tous les points.

Answer 3

Il semble que "la forme alpha" et "coque concave" sont remarquables