Вычислить координаты окружности последовательно

Мне нужно иметь координаты всех точек для данного круга одну за другой, чтобы я мог заставить объект двигаться по кругу, перескакивая с одной точки на другую. Я попробовал алгоритм круга средней точки, но версия, которую я нашел, предназначена для рисования, а координаты не являются последовательными. Они производятся одновременно для 8 квадрантов и, кроме того, в противоположных направлениях. Если бы, по крайней мере, они были в одном направлении, я мог бы создать отдельный массив для каждого квадранта и добавить их друг к другу в конце. Это адаптированный код JavaScript, который у меня есть сейчас:

  function calcCircle(centerCoordinates, radius) {
    var coordinatesArray = new Array();
    // Translate coordinates
    var x0 = centerCoordinates.left;
    var y0 = centerCoordinates.top;
    // Define variables
    var f = 1 - radius;
    var ddFx = 1;
    var ddFy = -radius << 1;
    var x = 0;
    var y = radius;
    coordinatesArray.push(new Coordinates(x0, y0 + radius));
    coordinatesArray.push(new Coordinates(x0, y0 - radius));
    coordinatesArray.push(new Coordinates(x0 + radius, y0));
    coordinatesArray.push(new Coordinates(x0 - radius, y0));
    // Main loop
    while (x < y) {
      if (f >= 0) {
        y--;
        ddFy += 2;
        f += ddFy;
      }
      x++;
      ddFx += 2;
      f += ddFx;
      coordinatesArray.push(new Coordinates(x0 + x, y0 + y));
      coordinatesArray.push(new Coordinates(x0 - x, y0 + y));
      coordinatesArray.push(new Coordinates(x0 + x, y0 - y));
      coordinatesArray.push(new Coordinates(x0 - x, y0 - y));
      coordinatesArray.push(new Coordinates(x0 + y, y0 + x));
      coordinatesArray.push(new Coordinates(x0 - y, y0 + x));
      coordinatesArray.push(new Coordinates(x0 + y, y0 - x));
      coordinatesArray.push(new Coordinates(x0 - y, y0 - x));
    }
    // Return the result
    return coordinatesArray;
  }

Я предпочитаю быстрый алгоритм без тригонометрии, но любая помощь приветствуется!

ИЗМЕНИТЬ

Это окончательное решение. Спасибо всем!

  function calcCircle(centerCoordinates, radius) {
    var coordinatesArray = new Array();
    var octantArrays =
      {oct1: new Array(), oct2: new Array(), oct3: new Array(), oct4: new Array(),
       oct5: new Array(), oct6: new Array(), oct7: new Array(), oct8: new Array()};
    // Translate coordinates
    var xp = centerCoordinates.left;
    var yp = centerCoordinates.top;
    // Define add coordinates to array
    var setCrd =
      function (targetArray, xC, yC) {
        targetArray.push(new Coordinates(yC, xC));
      };
    // Define variables
    var xoff = 0;
    var yoff = radius;
    var balance = -radius;
    // Main loop
    while (xoff <= yoff) {
      // Quadrant 7 - Reverse
      setCrd(octantArrays.oct7, xp + xoff, yp + yoff);
      // Quadrant 6 - Straight
      setCrd(octantArrays.oct6, xp - xoff, yp + yoff);
      // Quadrant 3 - Reverse
      setCrd(octantArrays.oct3, xp - xoff, yp - yoff);
      // Quadrant 2 - Straight
      setCrd(octantArrays.oct2, xp + xoff, yp - yoff);
      // Avoid duplicates
      if (xoff != yoff) {
        // Quadrant 8 - Straight
        setCrd(octantArrays.oct8, xp + yoff, yp + xoff);
        // Quadrant 5 - Reverse
        setCrd(octantArrays.oct5, xp - yoff, yp + xoff);
        // Quadrant 4 - Straight
        setCrd(octantArrays.oct4, xp - yoff, yp - xoff);
        // Quadrant 1 - Reverse
        setCrd(octantArrays.oct1, xp + yoff, yp - xoff);
      }
      // Some weird stuff
      balance += xoff++ + xoff;
      if (balance >= 0) {
        balance -= --yoff + yoff;
      }
    }
    // Reverse counter clockwise octant arrays
    octantArrays.oct7.reverse();
    octantArrays.oct3.reverse();
    octantArrays.oct5.reverse();
    octantArrays.oct1.reverse();
    // Remove counter clockwise octant arrays last element (avoid duplicates)
    octantArrays.oct7.pop();
    octantArrays.oct3.pop();
    octantArrays.oct5.pop();
    octantArrays.oct1.pop();
    // Append all arrays together
    coordinatesArray =
      octantArrays.oct4.concat(octantArrays.oct3).concat(octantArrays.oct2).concat(octantArrays.oct1).
        concat(octantArrays.oct8).concat(octantArrays.oct7).concat(octantArrays.oct6).concat(octantArrays.oct5);
    // Return the result
    return coordinatesArray;
  }

javascript algorithm geometry
person Boris Hamanov    schedule 15.01.2011    source источник
comment
Если вы собираетесь перемещать объект по круговой траектории в браузере, то ПОСЛЕДНЯЯ из ваших проблем должна быть связана со скоростью sin/cos.   -  person 6502    schedule 15.01.2011
comment
Я собираюсь предварительно вычислить координаты, которые объект будет использовать именно по этой причине, а объект на самом деле представляет собой множество объектов. Так что скорость sin/cos МОЖЕТ БЫТЬ проблемой. Особенно с IE на нетбуке.   -  person Boris Hamanov    schedule 15.01.2011
comment
Другой недостаток sin/cos заключается в том, что он генерирует конечное число точек. По мере увеличения радиуса круга кажущаяся скорость визуализируемого элемента будет увеличиваться, если количество вычисляемых точек останется прежним (поскольку их расстояние по окружности увеличивается).   -  person Bob    schedule 14.10.2011

Ответы (3)


arrow_upward
1
arrow_downward

Используйте следующий подход: используйте алгоритм, который вы дали, но переместите свои координаты в восемь разных координатных массивов. После этого вы должны перевернуть половину из них (с (x0+x,y0-y), (x0-x,y0+y), (x0+y,y0+x), (x0-y,y0-x) ) и затем добавить все массивы в правильном порядке. Позаботьтесь о том, чтобы добавить первые четыре точки в правильные массивы.

person Howard    schedule 16.01.2011
comment
Я тоже об этом подумал. Я опередил вас, но все равно отдаю вам должное ;) Другим решением было бы вычисление целого круга вместо одного октанта, но я не знаю, как адаптировать алгоритм. - person Boris Hamanov; 18.01.2011

arrow_upward
1
arrow_downward

Насколько я знаю, без тригонометрии не обойтись, но у меня работает довольно быстро. Извините, я не знаком с Java, поэтому пишу код на VB:


Dim PointList As New List(Of PointF)
For angle = 0 To Math.PI * 2 Step 0.01
    'the smaller the step, the more points you get
    PointList.Add(New PointF(Math.Cos(angle) * r + x0, Math.Sin(angle) * r + y0))
Next

x0 и y0 — координаты центра окружности, r — радиус.

Надеюсь, я ответил на ваш вопрос.

person Dave    schedule 15.01.2011
comment
Интересно, как это может работать, по крайней мере, без радиуса круга. - person Hemlock; 15.01.2011

arrow_upward
0
arrow_downward

Вот реализация javascript, основанная на ответе Дэйва. Немного переусердствовав, я хотел избежать вызова sin и cos больше, чем необходимо. По иронии судьбы, используя первый ответ Дэйва без радиуса :)

function calculateCircle(x,y,radius) {

  var basicPoints = getBasicCircle();
  var i = basicPoints.length;
  var points = []; // don't change basicPoints: that would spoil the cache.
  while (i--) {
    points[i] = {
      x: x + (radius * basicPoints[i].x),
      y: y + (radius * basicPoints[i].y)
    };
  }
  return points;
}

function getBasicCircle() {
  if (!arguments.callee.points) {
    var points = arguments.callee.points = [];
    var end = Math.PI * 2;
    for (var angle=0; angle < end; angle += 0.1) {
      points.push({x: Math.sin(angle), 
                   y: Math.cos(angle)
                  });
    }
  }
  return arguments.callee.points
}
person Hemlock    schedule 15.01.2011
comment
Спасибо Хэмлок! Хотите объяснить, что вы сделали более подробно? Используя какой-то король предварительно рассчитанного круга, а затем расширяя его для разных радиусов? Это не годится, если точек не хватает для большого круга? - person Boris Hamanov; 15.01.2011
comment
Да, он предварительно вычисляет круг радиусом 1. Вам придется изменить функцию кэширования, если вы хотите вернуть круги с более высоким или более низким разрешением. - person Hemlock; 15.01.2011