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

Question

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

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

提前致谢。

Answer 1

据我了解您的问题，您正在寻找四个点中的 centroid，该点与所有点的距离相等（因此最小）。它被计算为每个坐标的平均值：

$avg_x = \frac{p1_x + ... + pn_x}{n}$

$avg_y = \frac{p1_y + ... + pn_y}{n}$

$avg_z = \frac{p1_z + ... + pn_z}{n}$

虽然正方形的边长与位置无关。

更新

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

像上面描述的那样计算质心 c 并将正方形放在那里。
想象一个圆，圆心在 c，直径是正方形的边长。
对于每个机器人位置，计算圆上与机器人距离最短的点，并将其用作正方形的角。

Answer 2

原来的 poster 似乎不会回来分享他的解决方案，所以我会 post 我正在做的事情。

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

当您从正方形的一个角绘制矢量到最近的机器人时，此矢量会向您显示正方形应朝哪个方向移动以减少从该角到最近的机器人的距离。如果您计算这四个向量的方向之和（通过在将它们相加之前将向量的大小更改为 1），那么在结果方向上移动正方形将减少总距离。

我害怕在这里冒险进入微分方程领域，所以我设计了一个简单的算法，反复计算移动方向，并以越来越小的步长移动正方形，直到达到一定的精度。
对于问题中的示例，它找到的最佳位置是（10,18），总距离为21.814，比中心位置（假设正方形大小为10）提高了0.874。

按 "run code snippet" 查看随机生成位置的算法。分散的绿点是搜索正方形最佳位置时考虑的中心点。

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>

进一步改进：我还没有考虑角和机器人在同一个位置时会发生什么，但整体位置不是最佳的。由于从角到机器人的方向是未定义的，它可能应该暂时从等式中取出。

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

Developing an Algorithm to Transform Four Cartesian Coordinates Into Square Coordinates

algorithm

math

computer-science