将四边形分成最大

Question

很容易将矩形/正方形分割成更小的区域，并强制每个子区域的最大面积。您只需将区域划分为具有边长sqrt（max_area）的区域，并小心处理剩余部分。在

但是我被一个四边形的人难住了。假设我不知道任何一个角的角度。我们还假设所有四个点都在同一平面上。而且，我不需要所有的小区域都是相同的大小。我唯一的要求是每个区域的面积小于最大面积。在

有没有一种特殊的数据结构可以让这更简单？
有没有我找不到的算法？在

我可以用四叉树来做这个吗？我对树不是很精通，但我知道如何实现这种结构。在

当我这样做的时候，我心里想着地理信息系统的工作，但是我很有信心这不会对分割四边形的算法产生影响。在

Answer 1

您可以递归地将四边形在长边上一分为二，直到生成的区域足够小。在

Answer 2

如果你的四边形是凸的，那么实际上你可以把它分成两个面积相等的部分，这两个部分的周长相等！这被称为公平分区（fairpartitioning），在The Open Problems Project（它对更多的块是开放的，但是对于两个块是解决的）。在

对于非凸四边形，不难找到一条线来划分它 两块相等。
我相信这会起作用的：把一条线穿过那条线 反射顶点，并围绕该顶点旋转，直到它平均划分区域。 如果您的唯一目标是将区域划分为 两半相等。在

一般问题（对于任意多边形）的名称是 “火腿三明治的多边形剖分”。事实上，我写了一篇论文，题目正是这个。在