一种将四个笛卡尔坐标转换为平方坐标的算法

Question

我正在做一个项目，其中四个随机放置的机器人，每个机器人都有唯一的笛卡尔坐标。我需要找到一种方法，将这些坐标转换为由程序用户定义的具有边长的正方形坐标。

例如，假设我有四个坐标(5,13)，(8,17)，(13,2)和(6,24)，表示四个机器人的坐标。我需要找到一个正方形的坐标，这样四个机器人最接近这些坐标。

提前谢谢。

Answer 1

就我理解您的问题而言，您正在寻找四点的质心，即与所有点的等距，也就是最小距离的点。它是以每个坐标的平均值计算的：

​

​

​

​

​

​

不过，正方形的边长与位置无关。

更新

如果您还希望最小化方角到机器人位置的距离，可以执行以下操作：

1. 像上面描述的那样计算质心c，并将正方形放置在那里。
2. 想象一个圆，中心在c和直径的平方的边缘长度。
3. 对于每个机器人位置，计算出与机器人距离最短的圆上的点，并将其作为正方形的一个角。

Answer 2

似乎原来的海报没有回来分享他的解决方案，所以我会张贴我所做的工作。

找到四个机器人的中心点，然后在这个点周围画正方形确实是一个很好的开始，但它不一定给出最优的结果。对于问题中给出的例子，中心点为(8,14)，总距离为22.688 (假设平方大小为10)。

​

当你把矢量从正方形的一个角画到最近的机器人时，这个矢量显示了方格应该向哪个方向移动，以减少从那个角到它最近的机器人的距离。如果你计算这四个矢量的方向之和(在把它们加起来之前，把它们改变为1)，那么在结果的方向上移动方格将减少总距离。

​

​

我害怕在这里冒险进入微分方程领域，所以我设计了一个简单的算法，它反复计算移动的方向，并以不断减小的步数移动方格，直到达到一定的精度。

对于问题中的例子，它找到的最佳位置是(10,18)，总距离为21.814，这比中心位置(假设平方大小为10)提高了0.874。

​

​

按“运行代码段”以查看该算法在随机生成的位置上的作用。散落的绿色点是在搜索最优位置时所考虑的中心点。

​

function positionSquare(points, size) {

    var center = {x: 0, y:0};
    for (var i in points) {
        center.x += points[i].x / points.length;
        center.y += points[i].y / points.length;
    }

    paintSquare(canvas, square(center), 1, "#D0D0D0");
    order(points);
    textOutput("<P>center position: " + center.x.toFixed(3) + "," + center.y.toFixed(3) + "<BR>total distance: " + distance(center, points).toFixed(3) + "</P>");

    for (var step = 1; step > 0.0001; step /= 2)
    {
        var point = center;
        var shortest, dist = distance(center, points);

        do
        {
            center = point;
            shortest = dist;
            var dir = direction();
            paintDot(canvas, center.x, center.y, 1, "green");
            point.x = center.x + Math.cos(dir) * step;
            point.y = center.y + Math.sin(dir) * step;
            dist = distance(point, points);
        }
        while (dist < shortest)
    }
    textOutput("<P>optimal position: " + center.x.toFixed(3) + "," + center.y.toFixed(3) + "<BR>total distance: " + distance(point, points).toFixed(3) + "</P>");
    return square(center);

    function order(points) {
        var clone = [], best = 0;
        for (var i = 0; i < 2; i++) {
            clone[i] = points.slice();
            for (var j in clone[i]) clone[i][j].n = j;

            if (i) {
                clone[i].sort(function(a, b) {return b.y - a.y});
                if (clone[i][0].x > clone[i][1].x) swap(clone[i], 0, 1);
                if (clone[i][2].x < clone[i][3].x) swap(clone[i], 2, 3);
            } else {
                clone[i].sort(function(a, b) {return a.x - b.x});
                swap(clone[i], 1, 3);
                if (clone[i][0].y < clone[i][3].y) swap(clone[i], 0, 3);
                if (clone[i][1].y < clone[i][2].y) swap(clone[i], 1, 2);
            }
        }
        if (distance(center, clone[0]) > distance(center, clone[1])) best = 1;
        for (var i in points) points[i] = {x: clone[best][i].x, y: clone[best][i].y};

        function swap(a, i, j) {
            var temp = a[i]; a[i] = a[j]; a[j] = temp;
        }
    }

    function direction() {
        var d, dx = 0, dy = 0, corners = square(center);
        for (var i in points) {
            d = Math.atan2(points[i].y - corners[i].y, points[i].x - corners[i].x);
            dx += Math.cos(d);
            dy += Math.sin(d);
        }
        return Math.atan2(dy, dx);
    }

    function distance(center, points) {
        var d = 0, corners = square(center);
        for (var i in points) {
            var dx = points[i].x - corners[i].x;
            var dy = points[i].y - corners[i].y;
            d += Math.sqrt(Math.pow(dx, 2) + Math.pow(dy, 2));
        }
        return d;
    }

    function square(center) {
        return [{x: center.x - size / 2, y: center.y + size / 2},
                {x: center.x + size / 2, y: center.y + size / 2},
                {x: center.x + size / 2, y: center.y - size / 2},
                {x: center.x - size / 2, y: center.y - size / 2}];
    }
}

// PREPARE CANVAS
var canvas = document.getElementById("canvas");
canvas.width = 200; canvas.height = 200;
canvas = canvas.getContext("2d");

// GENERATE TEST DATA AND RUN FUNCTION
var points = [{x:5, y:13}, {x:8, y:17}, {x:13, y:2}, {x:6, y:24}];
for (var i = 0; i < 4; i++) {
    points[i].x = 1 + 23 * Math.random(); points[i].y = 1 + 23 * Math.random();
}
for (var i in points) textOutput("point: " + points[i].x.toFixed(3) + "," + points[i].y.toFixed(3) + "<BR>");
var size = 10;
var square = positionSquare(points, size);

// SHOW RESULT ON CANVAS
for (var i in points) {
    paintDot(canvas, points[i].x, points[i].y, 5, "red");
    paintLine(canvas, points[i].x, points[i].y, square[i].x, square[i].y, 1, "blue");
}
paintSquare(canvas, square, 1, "green");

function paintDot(canvas, x, y, size, color) {
canvas.beginPath();
canvas.arc(8 * x, 200 - 8 * y, size, 0, 6.2831853);
canvas.closePath();
canvas.fillStyle = color;
canvas.fill();
}
function paintLine(canvas, x1, y1, x2, y2, width, color) {
canvas.beginPath();
canvas.moveTo(8 * x1, 200 - 8 * y1);
canvas.lineTo(8 * x2, 200 - 8 * y2);
canvas.strokeStyle = color;
canvas.stroke();
}
function paintSquare(canvas, square, width, color) {
    canvas.rect(8 * square[0].x , 200 - 8 * square[0].y, 8 * size, 8 * size);
canvas.strokeStyle = color;
canvas.stroke();
}

// TEXT OUTPUT
function textOutput(t) {
    var output = document.getElementById("output");
    output.innerHTML += t;
}

<BODY STYLE="margin: 0; border: 0; padding: 0;">
<CANVAS ID="canvas" STYLE="width: 200px; height: 200px; float: left; background-color: #F8F8F8;"></CANVAS>
<DIV ID="output" STYLE="width: 400px; height: 200px; float: left; margin-left: 10px;"></DIV>
</BODY>

​

进一步的改进:我还没有考虑到当一个角落和一个机器人处于同一位置时会发生什么，但是总体位置并不是最佳的。由于从拐角到机器人的方向是未知的，很可能应该暂时从方程中取出来。