Kann ich Hilfe zu einem geradlinigen Polygon-Rumpf-Algorithmus bekommen (in Javascript wenn möglich)

Question

Bearbeitet Titel und hier, um meine Frage besser zu reflektieren. Meine erste Beschreibung erhielt keine Antworten von der Art, nach der ich suchte, und ich wusste nicht, dass es einen phantastischen Namen für diese Art von Form gab, die ich versuche zu machen. Ich habe Graham Scan-Algorithmen studiert, aber sie decken die Antwort, die ich suche, nicht vollständig ab, da sie dazu neigen, "Ecken zu schneiden", wenn die Form seltsam wird.

Basierend auf einigen Artikeln, die ich gefunden habe, habe ich angefangen, meinen eigenen Algorithmus zu schreiben und es funktioniert eine Menge der Fälle, um sicher zu sein, aber ich komme zu Problemen, die ich nicht vollständig ausstechen kann, ich glaube, das Problem könnte sein wo ich versuche, jede der Ecken zu berechnen.

Das ist die Logik meines Algorithmus -

1. = die Ecken finden, oben links, oben rechts, unten rechts, unten links

2. = Geben Sie eine while-Schleife, Reisen in Richtung ein Ziel, beginnend von oben links nach oben rechts, dann nach unten rechts nach unten links und zurück nach oben links.

3 = In jeder Iteration dieser while-Schleife finden wir die Nachbarn jeder Kachel, wenn sie in dieser Liste vorhanden sind, und wählen die nächste Kachel aus, basierend auf welcher zuerst in einer Reihenfolge nach Priorität kommt.

Priorität erklärt, wenn die Priorität ist, um zur oberen rechten Ecke zu kommen, nehmen wir uns Zeit, indem wir zunächst versuchen, nach links zu reisen, dann nach oben, rechts und unten, aber NUR, wenn ein Kachel in dieser Richtung existiert und NUR wenn Dieses Plättchen ist nicht das vorherige Plättchen, auf dem wir standen. Nachdem wir in der oberen rechten Ecke angekommen sind, verschieben wir die Prioritätenliste, wobei die erste Priorität die letzte wird. So

Priorität = [links, oben, rechts, unten]

wird

Priorität = [oben, rechts, unten, links]

In der Mehrzahl der Fälle meinen Code ausführt als erwartet, wie die Logik klingt, aber es gibt ein paar Anomalie Momente, in denen es scheint nicht die richtige Kachel basierend auf der Priorität, die ich gebe es zu wählen, und stattdessen wandert um das gesamte Array. Wenn mir jemand helfen kann, wo ich einen Fehler mache, würde ich das schätzen.

Heres meine aktuellen Algorithmus code>

  draw_hull = function() { 
       var list = [], 
        coordinates = [], 
        original_list = this.territory, 
        _x = 0, // coords are in arrays, [x,y] style. 
        _y = 1; // this is just for readers readability 



       // make list to be looped through, for each tile I deliberately added 4, 
       //it'll look more readable in the final product. 
       for (var i = 0; i < original_list.length; i++) { 
        list.push([ (original_list[i][_x] * 32) + 8, (original_list[i][_y] * 32) + 8 ]); 
        list.push([ (original_list[i][_x] * 32) + 24, (original_list[i][_y] * 32) + 8 ]); 
        list.push([ (original_list[i][_x] * 32) + 24, (original_list[i][_y] * 32) + 24 ]); 
        list.push([ (original_list[i][_x] * 32) + 8, (original_list[i][_y] * 32) + 24 ]); 
       } 

       // find corners 
       var topleft = 0, topright = 0, bottomright = 0, bottomleft = 0, hull = []; 

       for (var i = 0; i < list.length; i++) { 
        var x = list[i][_x]; 
        var y = list[i][1]; 

        if (x <= list[topleft][_x] && y <= list[topleft][_y]) topleft = i; 
        if (x >= list[topright][_x] && y <= list[topright][_y]) topright = i; 
        if (x >= list[bottomright][_x] && y >= list[bottomright][_y]) bottomright = i; 
        if (x <= list[bottomleft][_x] && y >= list[bottomleft][_y]) bottomleft = i; 
       } 

       // start drawing paths from one corner to the next, repeating until a full loop has been made 
       var priorities = ["l","u","r","d"], // travel the outline in this order, left up right down 
        current = topleft, // current tile 
        last = topleft; // last tile 
        target = [topright,bottomright,bottomleft,topleft], 
        target_iterator = 0, // target iterator so we know which corner we're striving towards 
        xx = 0, // an iterator to make sure this loop doesnt go on forever 
        done = false; 

       while(!done) { 
        // add the current tile to our hull list. 
        hull.push(current); 

        var next = {}, 
         cx = list[current][_x], 
         cy = list[current][_y]; 

        for (var i = 0; i < list.length; i++) { 
         var x = list[i][_x], y = list[i][_y]; 
         if (x === cx && y === cy -16) { next.up = i; continue; } 
         if (x === cx && y === cy +16) { next.down = i; continue; } 
         if (x === cx -16 && y === cy) { next.left = i; continue; } 
         if (x === cx +16 && y === cy) { next.right = i; continue; } 
        } 

        var i = 0, check = priorities; 
        for (var i = 0; i < priorities.length; i++) { 
         var check = priorities[i]; 

         // skip this if next check doesnt exist, or is the tile we just came from 
         if (next[check] == null || next[check] == undefined|| next[check] === last) continue; 

         var visited = false; 

         for (var j = 1; j < hull.length; j++) { 
          if (hull[j] === next[check]) { 
           visited = true; 
           continue; 
          } 
         } 

         if (visited) { 
          continue; 
         } 
         break; 
        } 

        last = current; 
        current = next[check]; 

        xcoords = list[current][_x]; 
        ycoords = list[current][_y]; 
        coordinates.push([xcoords,ycoords]); 

        if (current === target[target_iterator]) { 
         priorities.push(priorities.shift()); 
         target_iterator++; 
         if (target_iterator === 4) break; 
        } 

        xx++; 
        if (xx > 50) {break; debugger;} 
       } 

       if (xx < 50) this.hull = coordinates; 
      } 

Answer 1

Sie können ganz einfach eine "unbegrenzte" Menge an Ecken Schlaganfall oder Eckpunkte einer Form mit moveTo() und lineTo(). Im Folgenden sehen Sie ein Beispiel, wie Sie ein Dreieck zeichnen können, aber Sie können es problemlos erweitern, indem Sie weitere Pfadmethoden hinzufügen.

var ctx = canvas.getContext('2d'); 
 

 
// Filled triangle 
 
ctx.beginPath(); 
 
ctx.moveTo(25,25); //moves 'pen' to coords 
 
ctx.lineTo(105,25); //draws line from prior coords to new specified coords. 
 
ctx.lineTo(25,105); 
 
ctx.fill(); //fills in shape 
 

 
// Stroked triangle 
 
ctx.beginPath(); 
 
ctx.moveTo(125,125); 
 
ctx.lineTo(125,45); 
 
ctx.lineTo(45,125); 
 
ctx.closePath(); 
 
ctx.stroke(); //strokes along path (i.e shape outline)

<canvas id="canvas" width="200" height="200"></canvas>

Dieser Code kann bei https://developer.mozilla.org/en-US/docs/Web/API/Canvas_API/Tutorial/Drawing_shapes gefunden werden zusammen mit ausführlichen Tipps, wie komplexere Formen zu zeichnen.

Answer 2

Ok, weitere Studien, ich fand einen Namen für die Art der Form, die ich versuche zu zeichnen. Es heißt ein geradliniges Polygon.

Wikipedia's article

Stack Overflow bereits eine Antwort für diese hat, war nur schwer zu finden.

Answer 3

Sie sollten moveTo() und lineTo() mit einem stroke() verwenden. Weitere Dokumentationen finden Sie unter MDN.

Eine einfache Zeichnung Funktion könnte wie folgt aussehen: (oder überprüfen Fiddle)

function drawShape(coords) { 

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

    ctx.beginPath(); 

    for(var i = 0; i < coords.length; i++) { 
     if(i === 0) { 
      ctx.moveTo(coords[i].x, coords[i].y); 
     } else { 
      ctx.lineTo(coords[i].x, coords[i].y); 
     } 
    } 

    ctx.closePath(); 
    ctx.stroke(); 

}