language-agnostic - 将二维图中的 N 个点分成 2 组

Question

假设在二维图中有N 个点。每个点都有一些权重。我需要画一条直线，这样直线将点分成两组，这样总权重（总权重该组中的点）重量较小的部分尽可能多。我的任务是找到这个值。如何去做？

注意：没有三点在同一条线上。

这不是作业或任何比赛的一部分。

Answer 1

您可以扫描所有角度和偏移量，直到找到最佳解决方案。

为了便于计算，我将使用一个简单的旋转矩阵旋转所有点，以将这些点与扫描线对齐，这样您只需查看它们的 x 坐标。

您只需要检查半个圆，然后扫描线自身就会翻倍，假设您使用的是弧度，而不是度数，那就是 0 到 PI 的角度。还假设可以从数据中读取点作为具有 x、y 和权重值的某种对象。

伪代码：

Initialize points from input data
Initialize bestDifference to sum(weights of points)
Initialize bestAngle to 0
Initialize bestOffset to 0
Initialize angleStepSize to an arbitrary small value (e.g. PI/100)

For angle = 0:angleStepSize:PI
    Initialize rotatedpoints from points and rotationMatrix(angle)

    For offset = (lowest x in rotatedpoints) to (highest x in rotatedpoints)
        weightsLeft = sum of the weights of all nodes with x < offset
        weightsRight = sum of the weights of all nodes with x > offset
        difference = abs(weightsLeft - weightsRight)
        If difference < bestDifference 
            bestAngle = angle
            bestOffset = offset
            bestDifference = difference

    Increment angle by stepsize
Return bestAngle, bestOffset, bestDifference

这是一个粗略的 Paint 图像来阐明我的方法：