Diskuze: Grahamův algoritmus

V předchozím kvízu, Online test znalostí JavaScript, jsme si ověřili nabyté zkušenosti z kurzu.

Aktivity

Adam Olecký

Člen

Adam Olecký:2.10.2016 10:12

Ahoj ve spolek,
mám problém - řeším Grahamův algoritmus ten by měl dělat následující: Vzít prvek s nejnižší hodnotou souřadnice y a od ní obalit skupinu bodů po směru hodinových ručiček (rsp. určit body které jsou na obalu). Ale to co jsem napsal obejde jen polovinu skupiny bodů (levou) a pak se zastaví. Mohli byste mi pomoct a mrknout se na to? Sám jsem v koncích a víc oči víc vidí.

Pro puštění stačí vytvořit na lokálu 2 soubory:
1,je index html s tímto obsahem:

<html>
        <head>
                <title>TODO supply a title</title>
                <meta charset="UTF-8">
                <meta name="viewport" content="width=device-width, initial-scale=1.0">
                <script src="https://ajax.googleapis.com/ajax/libs/jquery/1.12.4/jquery.min.js"></script>
                <script src="https://code.jquery.com/jquery-1.10.2.js"></script>

        </head>
        <body>
        <script src="./SVG.js"></script>
        </body>



</html>

2.druhý je tento svg.js

// Generated by CoffeeScript 1.10.0
  $(document).ready(function() {
    var iterations = 20;


    var svg = document.createElementNS("http://www.w3.org/2000/svg", "svg");
    var svgNS = svg.namespaceURI;

    svg.setAttribute('width', 500);
    svg.setAttribute('height', 500);

    var rect = document.createElementNS(svgNS,'rect');
    rect.setAttribute('x',5);
    rect.setAttribute('y',5);
    rect.setAttribute('width',500);
    rect.setAttribute('height',500);
    rect.setAttribute('fill','#95B3D7');
    svg.appendChild(rect);


    var axisX = document.createElementNS(svgNS,'line');
    axisX.setAttribute('x1', 50);
    axisX.setAttribute('y1',400);
    axisX.setAttribute('x2',50);
    axisX.setAttribute('y2',50);
    axisX.setAttribute('style', 'stroke:rgb(255,0,0);stroke-width:2');
    svg.appendChild(axisX);

    var axisY = document.createElementNS(svgNS,'line');
    axisY.setAttribute('x1', 50);
    axisY.setAttribute('y1',400);
    axisY.setAttribute('x2',400);
    axisY.setAttribute('y2',400);
    axisY.setAttribute('style', 'stroke:rgb(255,0,0);stroke-width:2');
    svg.appendChild(axisY);

    var textY = document.createElementNS(svgNS,'text');
    textY.setAttribute('x', 25);
    textY.setAttribute('y',75);
    textY.innerHTML = 'Y';
    svg.appendChild(textY);

    var textY = document.createElementNS(svgNS,'text');
    textY.setAttribute('x', 375);
    textY.setAttribute('y',425);
    textY.innerHTML = 'X';
    svg.appendChild(textY);

    var textY = document.createElementNS(svgNS,'text');
    textY.setAttribute('x', 25);
    textY.setAttribute('y',425);
    textY.innerHTML = '0';
    svg.appendChild(textY);

    for (var i=0; i <= iterations; i++) {
      var xPos = Math.floor((Math.random() * 350) + 1) +50;
      var yPos = Math.floor((Math.random() * 350) + 1) +50;

      var shape = document.createElementNS(svgNS, "circle");
      shape.setAttributeNS(null, "cx", xPos);
      shape.setAttributeNS(null, "cy", yPos);
      shape.setAttributeNS(null, "r",  2.5);
      shape.setAttributeNS(null, "fill", "green");
      svg.appendChild(shape);
    }

    document.body.appendChild(svg);

    var xMid =($('circle')[0].getAttribute('cx'));
    var yMid =($('circle')[0].getAttribute('cy'));
    console.log(i, 'MID:', xMid, ' ', yMid);


    //cyklus vypisujici usecky
    for (var i = 1; i <= iterations; i++) {
      setTimeout(function(i) {
        var x2 =($('circle')[i].getAttribute('cx'));
        var y2 =($('circle')[i].getAttribute('cy'));


        //console.log(i, 'puvodni :', x2, ' ', y2);

        x2 = (x2 - xMid);
        y2 = (y2 - yMid);

        //console.log(i, 'abs :', x2, ' ', y2);

        x2 = x2*1.5;
        y2 = y2*1.5;

        //console.log(i, '1.5x :', x2, ' ', y2);

        x2=x2+Number(xMid);
        y2=y2+Number(yMid);

        //console.log(i, '+mid :', x2, ' ', y2);

        var Linium = document.createElementNS(svgNS,'line');
        Linium.setAttribute('x1', xMid );
        Linium.setAttribute('y1', yMid );
        Linium.setAttribute('x2',x2);
        Linium.setAttribute('y2',y2);
        Linium.setAttribute('style', 'stroke:rgb(0,0,255);stroke-width:');

        svg.appendChild(Linium);
      }, i * 200, i);
    }


    //vyber s nejnizsim y
    var lowest_y = Number(500);
    var lowest_x = 500;

    for (var i = 0; i < iterations; i++) {

      //console.log(Number($('circle')[i].getAttribute('cy')));

      if (Number($('circle')[i].getAttribute('cy')) < lowest_y) {
        lowest_y = $('circle')[i].getAttribute('cy');
        lowest_x = $('circle')[i].getAttribute('cx');

      }

    }
    console.log(lowest_x, lowest_y);

    var shape = document.createElementNS(svgNS, "circle");
    shape.setAttributeNS(null, "cx", Number(lowest_x));
    shape.setAttributeNS(null, "cy", Number(lowest_y));
    shape.setAttributeNS(null, "r",  5);
    shape.setAttributeNS(null, "fill", "purple");
    svg.appendChild(shape);




    //vypocet nejmenciho uhlu pro danny bod + opakovani pro veskere body vybrane fci na okraji, stejny pocet iteraci zajisti na 100pro obehnuti kola


    var act_alfa = null;
    var min_alfa =0;
    var next_anchor_x = lowest_x;
    var next_anchor_y =lowest_y;

    var prev_doc_x;
    var prev_doc_y;
    var left = true;

    //zleva
    for (var q = 0; q < iterations; q++) {
      act_alfa=null;
      min_alfa =null;
      //var next_anchor_x =null;
      //var next_anchor_y =null;
      prev_x = next_anchor_x;
      prev_y = next_anchor_y;

    if (left==true){
      for (var i = 0; i < iterations; i++) {

          act_alfa = angle(prev_x,prev_y, $('circle')[i].getAttribute('cx'), $('circle')[i].getAttribute('cy'));
          //act_alfa -= 180;
          console.log('act angle:', act_alfa);

          if(act_alfa >= min_alfa && act_alfa!=0 && act_alfa!=null){
            next_anchor_x = $('circle')[i].getAttribute('cx');
            next_anchor_y = $('circle')[i].getAttribute('cy');

            min_alfa=act_alfa;

          }

      }
    }

    console.log('lowest angle:', min_alfa);
    console.log('next:', next_anchor_x, next_anchor_y);
    console.log('prev:', prev_x, prev_y);



    var shape = document.createElementNS(svgNS, "circle");
    shape.setAttributeNS(null, "cx", Number(next_anchor_x));
    shape.setAttributeNS(null, "cy", Number(next_anchor_y));
    shape.setAttributeNS(null, "r",  5);
    shape.setAttributeNS(null, "fill", "red");
    svg.appendChild(shape);
    left = true;

    }

    //fce ktera zpracuje uhly vzhledem k danemu prvku
    function angle(cx, cy, ex, ey) {
    var dy = Number(ey) - cy;
    var dx = Number(ex) - cx;
    var theta = Math.atan2(dy, dx); // range (-PI, PI]
    theta *= 180 / Math.PI; // rads to degs, range (-180, 180]
    //if (theta < 0) theta = 360 + theta; // range [0, 360)
    return theta;
    }

  });

Editováno 2.10.2016 10:15

Odpovědět

2.10.2016 10:12

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 1 zpráv z 1.

Nejčastěji vyhledáváné

Diskuze: Grahamův algoritmus