javascript - 如何计算4个点的加权中心点？

Question

如果我有4分

        var x1;
        var y1;
        var x2;
        var y2;
        var x3;
        var y3;
        var x4;
        var y4;

组成一个盒子。所以

(x1,y1) is top left
(x2,y2) is top right
(x3,y3) is bottom left
(x4,y4) is bottom right

然后每个点的权重范围为0-522。如何计算位于框内的坐标 (tx,ty)，其中该点更接近权重最小的位置(但考虑到所有权重)。例如。如果(x3,y3)的权重为0，而其他的权重为522，则(tx,ty)应该是(x3,y3)。如果 (x2,y2) 的权重为 400，那么 (tx,ty) 应该从 (x3,y3) 向 (x2,y2) 靠近一点。

有谁知道这个有公式吗？谢谢

Answer 1

创建一个最小的、完整的、可验证的示例

这里有一个有点棘手的问题，但它真的很有趣。可能有更好的方法来解决它，但我发现使用 Point 和 Vector 数据抽象来更好地建模问题是最可靠的

我将从一个非常简单的数据集开始 - 可以读取下面的数据(例如)点D位于笛卡尔坐标(1,1)，权重> 共 100 个。

|
|
| B(0,1) #10        D(1,1) #100
|                
| 
|         ? solve weighted average
|
| 
| A(0,0) #20        C(1,0) #40
+----------------------------------

我们将这样做

1. 找到未加权的中点，m
2. 使用m作为原点将每个点转换为向量(度，幅度)向量
3. 将所有向量相加，vectorSum
4. 将vectorSum的幅值除以总幅值
5. 将向量转换为点，p
6. 偏移p未加权中点m

<小时/>

可能的 JavaScript 实现

我将一次一个地浏览这些部分，然后底部会有一个完整的可运行示例。

我们将使用 Math.atan2、Math.cos 和 Math.sin 函数以弧度返回结果。这有点麻烦，所以有几个助手在学位上工作。

// math
const pythag = (a,b) => Math.sqrt(a * a + b * b)
const rad2deg = rad => rad * 180 / Math.PI
const deg2rad = deg => deg * Math.PI / 180
const atan2 = (y,x) => rad2deg(Math.atan2(y,x))
const cos = x => Math.cos(deg2rad(x))
const sin = x => Math.sin(deg2rad(x))

现在我们需要一种方法来表示我们的Point和与Point相关的函数

// Point
const Point = (x,y) => ({
  x,
  y,
  add: ({x: x2, y: y2}) =>
    Point(x + x2, y + y2),
  sub: ({x: x2, y: y2}) =>
    Point(x - x2, y - y2),
  bind: f =>
    f(x,y),
  inspect: () =>
    `Point(${x}, ${y})`
})

Point.origin = Point(0,0)
Point.fromVector = ({a,m}) => Point(m * cos(a), m * sin(a))

当然，Vector 也是如此 - 奇怪的是，当您将它们转换回它们的 x 和 y 时，将矢量添加在一起实际上更容易> 笛卡尔坐标。除此之外，这段代码非常简单

// Vector
const Vector = (a,m) => ({
  a,
  m,
  scale: x =>
    Vector(a, m*x),
  add: v =>
    Vector.fromPoint(Point.fromVector(Vector(a,m)).add(Point.fromVector(v))),
  inspect: () =>
    `Vector(${a}, ${m})`
})

Vector.zero = Vector(0,0)
Vector.fromPoint = ({x,y}) => Vector(atan2(y,x), pythag(x,y))

最后，我们需要用 JavaScript 表示上面的数据并创建一个计算加权点的函数。有了 Point 和 Vector 在我们身边，这将是小菜一碟

// data
const data = [
  [Point(0,0), 20],
  [Point(0,1), 10],
  [Point(1,1), 100],
  [Point(1,0), 40],
]

// calc weighted point
const calcWeightedMidpoint = points => {
  let midpoint = calcMidpoint(points)
  let totalWeight = points.reduce((acc, [_, weight]) => acc + weight, 0)
  let vectorSum = points.reduce((acc, [point, weight]) =>
    acc.add(Vector.fromPoint(point.sub(midpoint)).scale(weight/totalWeight)), Vector.zero)
  return Point.fromVector(vectorSum).add(midpoint)
}

console.log(calcWeightedMidpoint(data))
// Point(0.9575396819442366, 0.7079725827019256)

<小时/>

可运行脚本

// math
const pythag = (a,b) => Math.sqrt(a * a + b * b)
const rad2deg = rad => rad * 180 / Math.PI
const deg2rad = deg => deg * Math.PI / 180
const atan2 = (y,x) => rad2deg(Math.atan2(y,x))
const cos = x => Math.cos(deg2rad(x))
const sin = x => Math.sin(deg2rad(x))

// Point
const Point = (x,y) => ({
  x,
  y,
  add: ({x: x2, y: y2}) =>
    Point(x + x2, y + y2),
  sub: ({x: x2, y: y2}) =>
    Point(x - x2, y - y2),
  bind: f =>
    f(x,y),
  inspect: () =>
    `Point(${x}, ${y})`
})

Point.origin = Point(0,0)
Point.fromVector = ({a,m}) => Point(m * cos(a), m * sin(a))

// Vector
const Vector = (a,m) => ({
  a,
  m,
  scale: x =>
    Vector(a, m*x),
  add: v =>
    Vector.fromPoint(Point.fromVector(Vector(a,m)).add(Point.fromVector(v))),
  inspect: () =>
    `Vector(${a}, ${m})`
})

Vector.zero = Vector(0,0)
Vector.unitFromPoint = ({x,y}) => Vector(atan2(y,x), 1)
Vector.fromPoint = ({x,y}) => Vector(atan2(y,x), pythag(x,y))


// data
const data = [
  [Point(0,0), 20],
  [Point(0,1), 10],
  [Point(1,1), 100],
  [Point(1,0), 40],
]

// calc unweighted midpoint
const calcMidpoint = points => {
  let count = points.length;
  let midpoint = points.reduce((acc, [point, _]) => acc.add(point), Point.origin)
  return midpoint.bind((x,y) => Point(x/count, y/count))
}

// calc weighted point
const calcWeightedMidpoint = points => {
  let midpoint = calcMidpoint(points)
  let totalWeight = points.reduce((acc, [_, weight]) => acc + weight, 0)
  let vectorSum = points.reduce((acc, [point, weight]) =>
    acc.add(Vector.fromPoint(point.sub(midpoint)).scale(weight/totalWeight)), Vector.zero)
  return Point.fromVector(vectorSum).add(midpoint)
}

console.log(calcWeightedMidpoint(data))
// Point(0.9575396819442366, 0.7079725827019256)

回到我们最初的可视化，一切看起来都正确!

|
|
| B(0,1) #10        D(1,1) #100
|
|
|                 * <-- about right here
|
| 
| 
| A(0,0) #20        C(1,0) #40
+----------------------------------

<小时/>

检查我们的工作

使用一组具有相同权重的点，我们知道加权中点应该是多少。让我们验证两个主要函数 calcMidpoint 和 calcWeightedMidpoint 是否正常工作

const data = [
  [Point(0,0), 5],
  [Point(0,1), 5],
  [Point(1,1), 5],
  [Point(1,0), 5],
]

calcMidpoint(data)
// => Point(0.5, 0.5)

calcWeightedMidpoint(data)
// => Point(0.5, 0.5)

太棒了!现在我们将测试一下其他一些权重是如何工作的。首先，让我们尝试除权重零之外的所有点

const data = [
  [Point(0,0), 0],
  [Point(0,1), 0],
  [Point(1,1), 0],
  [Point(1,0), 1],
]

calcWeightedMidpoint(data)
// => Point(1, 0)

请注意，如果我们将权重更改为某个荒谬的数字，那也没关系。矢量的缩放基于点的权重百分比。如果它获得 100% 的权重，它(点)不会将加权中点拉过(点)本身

const data = [
  [Point(0,0), 0],
  [Point(0,1), 0],
  [Point(1,1), 0],
  [Point(1,0), 1000],
]

calcWeightedMidpoint(data)
// => Point(1, 0)

最后，我们将验证另一组以确保权重正常工作 - 这次我们将有两对相同权重的点。输出正是我们所期望的

const data = [
  [Point(0,0), 0],
  [Point(0,1), 0],
  [Point(1,1), 500],
  [Point(1,0), 500],
]

calcWeightedMidpoint(data)
// => Point(1, 0.5)

<小时/>

数百万积分

在这里，我们将创建一个具有随机权重的随机坐标的巨大点云。如果点是随机的并且我们的函数工作正常，则答案应该非常接近 Point(0,0)

const RandomWeightedPoint = () => [
  Point(Math.random() * 1000 - 500, Math.random() * 1000 - 500),
  Math.random() * 1000
]

let data = []
for (let i = 0; i < 1e6; i++)
  data[i] = RandomWeightedPoint()

calcWeightedMidpoint(data)
// => Point(0.008690554978970092, -0.08307212085822799)

A++