python - 查找由一组线创建的平面的所有分区

Question

我有一组线(形式为 y = mx + b 的线性函数)(其中 120 条!)，如果我将它们全部绘制成图，那么它们将划分 R^2 平面。这些线不一定穿过原点。

查找由一组这样的行创建的所有分区的最有效方法是什么？就个人而言，我很难想出任何方法，更不用说有效的方法了。为了更清楚，我包括以下仅 4 行的图像:

分区的一个例子是集合 {(x,y)| -30x+28<= y && 60x+2 <= y <= 90x+7} ，这是第一象限中由红、黄、绿线创建的分区。另一个例子是 {(x,y)|y <= -30x+28 && 5x+3 <= y <= 60x+2} , 这是第一象限中由蓝线、红线和绿线包围的三角形。

非 分区的示例是 {(x,y)|5x+3 <= y <= -30x+28} ，这是由上面的绿线和下面的蓝线所界定的集合。这不是一个分区，因为其中包含多个分区(例如上面的第二个分区)，或者与它重叠。套装{(x,y)|5x+3 <= y <= -30x+28 && 90x+7 <= y} , 然而, 将是一个分区。

所需的输出将是此类集合的完整列表: {(x,y)|y <= -30x+28 && 5x+3 <= y <= 60x+2},{(x,y)| -30x+28<= y && 60x+2 <= y <= 90x+7}...等。当然，它们不必以这种表示法给出。

我不确定如何解决这个问题，因此，不幸的是，我无法提供太多我尝试过的方法。理想情况下，我想在 R、Python、Mathematica 或 MATLAB 中执行此操作，但此时我对任何选项都持开放态度。

编辑:由于符号似乎有问题，我会稍微澄清一下。简单地获取点的条件列表就足够了，这样满足该条件的所有点都将准确地定义一个分区。例如，一长串交叉路口就可以了:y <= 5x+3 && y >= 90x+7 && y<= -30x+28是定义分区的完美输出。当然，所需的输出是此类分区的完整列表(如上定义)。

Answer 1

查找分区数遵循以下公式(当没有 3 条或更多条线在同一点相交时 - 此假设贯穿本文):

num_partitions = (n_lines * (n_lines + 1) / 2 ) + 1

可以找到解释here , 和另一个 there .

The desired output would be a complete list of such sets: {(x,y)|y <= -30x+28 && 5x+3 <= y <= 60x+2}, {(x,y)| -30x+28<= y && 60x+2 <= y <= 90x+7}... etc... They don't have to be given in this notation, of course.

缺乏精确的符号是这里的一个障碍。

下面是我的信封尝试的背面。如您所见，可以根据编号区域与每条线的相对位置来识别编号区域。
有 5 个空集，如果行顺序改变，它们将不相同。
用线划分平面上的一组点可能会更容易，试图确定哪个点属于哪个集合；在这种情况下，探索 2^n潜在的分区，返回它们的内容会很容易。 (比试图找到一个好的符号来识别抽象集更容易)

这并没有完全回答你的问题，但对于能够/愿意进一步插入这个问题的人来说可能是一个很好的陈述点。
这是关于 partitioning a set of points with two lines in the plane. 的注释这是一个不同的问题，但它的一些方法可能有用。

其他方法:

识别由线段形成的多边形，计算一个凸包，确定一个点是否在该包内。