缩小多边形到特定区域并偏移。

Question

我有一个二维多边形，我想通过特定偏移量（A）来缩小它，以匹配原多边形的某个面积比例（R）。这种问题是否有公式或算法？我想得到一个简单的三角形/四边形解决方案，也需要一个解决复杂多边形的方案。

我附上了一张图片作为说明。原始多边形被A偏移（每条边等距），必须选择A使新多边形具有特定面积。在这个例子中，它应该是初始多边形面积的一半。

- timkado

Answer 1

我知道这个问题很久了，你可能已经不在意了，但我在为一个正在进行的比赛开发的编程任务中寻找资源时发现了你的问题。

任务可以在这里找到here。

问题的要点是，给定一个多边形，为了得到一个面积是原始面积一半的相似多边形，所有边应该向内移动多少距离。

解决方案是进行二分搜索，每次迭代尝试移动并计算相邻线段的新交点，但你必须小心一点。为了计算交点，你必须暂时将移动后的线段视为直线，然后可以计算它们的起点和终点。

假设你按照相邻线段的交点按逆时针顺序对线段进行排序。在二分搜索中有几种情况：

如果你偏移得太多，可能会导致多边形翻转，但如果发生这种情况，你的逆时针点集通常会变成顺时针。你还需要检查一下某些全局极值是否仍然是局部极值，与其邻居相比。例如，取具有最小y坐标的点，并在每次迭代中验证它的y坐标是否低于其两个相邻点的y坐标。这意味着你应该在下一次迭代中尝试更小的偏移量。

如果你偏移得稍微少一些，多边形可能不再简单，或者可能丢失交点和线段。你可以使用扫描线算法来检测这种情况。这也意味着你应该在下一次迭代中尝试更小的偏移量。

如果你偏移得太多，多边形的面积将小于原始面积的一半，但仍然是正数。你可能想要检查负面积，特别是由于浮点数不精确导致的情况。这也意味着你应该在下一次迭代中尝试更小的偏移量。

如果你偏移得太少，多边形的面积将大于原始面积的一半。这意味着你应该在下一次迭代中尝试更大的偏移量。

如果你的二分搜索在任何迭代中找到的面积小于原始面积的一半，那么有可能找到一个面积恰好是原始面积一半的多边形，并且在二分搜索完成后，你将得到正确的偏移量。

- Arnar Bjarni Arnarson

Answer 2

您的问题非常不具体，但以下是一种实现您所需功能的方法，假设我理解您的问题。请注意，这可能会导致位置上的不良偏移，您需要以某种方式处理它。由于不知道您想要缩放多边形的哪个点，因此这些解决方案假定情况最简单。

所有这些公式中平方根的原因是，面积 tends to change with the square of linear scaling, just as volume does with the cube of linear scaling.

对于一般的多边形：

A = sqrt(R)
for each point in polygon:
    point.x := point.x * A
    point.y := point.y * A

对于圆形：

A = sqrt(R)
circle.radius := circle.radius * A

对于以宽度和高度表示的矩形：

A = sqrt(R)
rect.w := rect.w * A
rect.h := rect.h * A

- Void Star

---

谢谢您的回复。我附上了一张图片以更明确地说明。 - timkado

那张图片中展示的问题有些难以解决，因为一些多边形可能会被分割成两个或更多个独立的形状。让我想一想。 - Void Star