让我解释一下我的问题：
我有一个黑色矢量形状（假设它现在是一系列连接的直线，但如果我也可以支持二次曲线会很好）。
我还有一个预定义宽度和高度的矩形。我将把它放在黑色形状的顶部，然后将两者结合起来。
我的第一个问题是我不知道如何快速提取向量并集，但我认为有一个定义明确的公式我可以自己弄清楚。
我的第二个也是更棘手的问题是如何有效地检测矩形需要所处的位置（即矩阵需要什么平移和旋转），以便最大化黑色，在联合之后剩余（见下图）。
下面的红色轮廓形状是约 33% 的黑色；绿色大约是 85%；并且有这种形状和矩形的位置，其中任何一个都可以有 100% 的覆盖率。
显然，我可以通过对矩形的至少一部分接触黑色形状的每个点尝试每个平移和旋转值来强制执行此操作，然后跟踪具有最多黑色覆盖的那个。问题是，我只能尝试有限数量的位置（因此可能会错过最大值）。除此之外，感觉非常低效！
你能想出一种更有效的方法来解决这个问题吗？
我大学时代的一些事情告诉我，傅里叶变换可能会提高这里的效率，但我不知道如何用矢量形状做到这一点！
有望比蛮力搜索更快和/或更精确的三个想法：
假设您有一个 3d 物理引擎。定义一个“圆锥形”表面，其中顶点位于 (0,0,-1)，z=0 平面上的黑色多边形边界，其质心位于原点，圆锥表面通过连接顶点形成通过多边形边界的半无限光线。想象一顶派对帽倒置并皱成黑色多边形的形状。现在将矩形约束为平行于 z=0 平面，并且最初在锥体上方如此之高（大 z 值），因此很容易找到它肯定在“内部”的地方。然后让矩形在重力作用下下落，绕 z 轴扭转并在 xy 方向平移，直到它接触到圆锥体，一直停留在里面，直到它稳定下来，不能再进一步移动。物理引擎的碰撞检测和力解析处理了复杂性。当它稳定下来时，它将在局部意义上处于黑色多边形最大覆盖的位置。（如果它以 z<0 稳定，则覆盖率为 100%。）对于凸面情况，它可能是全局最大值。为了概率性地改进非凸情况的结果（如您的示例），您将随机化起始位置，多次丢弃多边形，获得最佳结果。请注意，您实际上并不需要一个成熟的物理引擎（尽管 为了概率性地改进非凸情况的结果（如您的示例），您将随机化起始位置，多次丢弃多边形，获得最佳结果。请注意，您实际上并不需要一个成熟的物理引擎（尽管 为了概率性地改进非凸情况的结果（如您的示例），您将随机化起始位置，多次丢弃多边形，获得最佳结果。请注意，您实际上并不需要一个成熟的物理引擎（尽管它们当然存在于开源中）。使用碰撞分辨率来告诉您如何以伪物理方式旋转和平移矩形就足够了，因为它会尽可能地沿着 z 轴均匀地扭曲和滑动。
不同的物理模型。假设黑色区域是二维中的有吸引力的场发生器，遵循通常的平方反比规则，如重力和磁力。现在让矩形在响应该场的阻尼介质中漂移。它应该以与黑色区域重叠的最大区域来解决。像甜甜圈中心的“零点”存在问题，但我认为这些永远不可能是稳定的平衡。他们可以吗？通过将两种形状都建模为粒子群，可以轻松完成模拟。或者由于矩形是一个简单的形状并且您是物理学家，您可以为点和矩形之间的吸引力积分提出一个闭合形式。这样，只有黑色形状需要表示为粒子。想来想去，准确的答案。不幸的是，这个讨论意味着它不能通过分析来完成。所以粒子云可能是最终的解决方案。好消息是现代处理器，尤其是 GPU，以惊人的速度进行非常大的粒子计算。编辑：我实现了这个又快又脏。它适用于凸面形状，但凹面会产生不是您想要的稳定点。使用示例：
这个问题与机器人路径规划有关. 查看这些文献可能会产生一些想法。在 RPP 中，您有障碍物和机器人，并希望找到机器人可以在避开和/或沿着它们滑动的同时行进的路径。如果机器人是不对称的并且可以旋转，那么 2d 规划是在 3d（环形）配置空间（C 空间）中完成的，其中一维是旋转（因此自身闭合）。这个想法是在 C 空间中“增加”障碍物，同时将机器人缩小到一个点。通过计算 Minkowski 差异来增加障碍。）如果将所有多边形分解为凸形，则有一个简单的“边缘合并”算法来计算 MD。）当 C 空间表示完成时，任何 1d 路径都可以不刺破“长大” 障碍物对应于机器人在世界空间中避开原始障碍物的连续平移/旋转。对于您的问题白色区域是障碍物，矩形是机器人。您正在寻找任何开放点。这将对应于 100% 的覆盖率。对于低于 100% 的情况，C 空间必须是 3d 上的函数，它反映了机器人与障碍物的交点有多“糟糕”，而不仅仅是一个二进制值。你正在寻找最小的坏点。C 空间表示是一个开放的研究课题。八叉树可能在这里工作。
在这两种情况下都需要考虑很多细节，它们可能根本不会成功，但至少这些是可以更多地思考问题的框架。物理思路有点像用模拟弹簧系统做图形布局，已经很成功了。
我认为不可能找到这个问题的精确最大值，因此您需要使用近似值。
您可能会将矢量图像渲染为位图并为此使用 Haar 功能 - 它们提供了一种非常快速的 O(1) 方法来计算矩形区域的平均颜色。
对于不同的旋转和位置，您仍然需要多次执行此操作，但它会将算法复杂度从天真的 O(n^5) 降低到 O(n^3)，这可能是可以接受的快。（这里的 n 是您正在扫描的不同自由度的大小）
你有没有想过用 if whitespace !== 0 来跟踪块内剩余的空白？