绘制不等式算法

Question

我正在使用HTML5画布编写一个简单的绘图应用程序。输入是一组如下所示的不等式系统（所有函数都是线性的）：

4x + y >= 4
x  + y <= 4
x,y >= 0

我需要的输出是一组形成填充形状的点。例如，对于这个例子，图形将是：
点集为：[0,4]，[1,0]，[4,0]。如何找到这些点的算法？我知道线的交点是线性系统的解，但我无法弄清如何正确地进行填充。请注意，这个问题不是关于绘图系统实现的，而是关于如何找到填充形状的点。

- bvk256

---

你是想要实现这样的算法吗：1）找到线段交点。2）根据这些信息填充区域。或者你正在寻找其他解决方案。无论如何，对于线性方程ax+by=c，考虑到其法向量为（a，b），这可能对你有用。 - Roman Fursenko

是的，这正是我想要的。 - bvk256

Answer 1

我认为你的问题实际上有两个部分：方程是否定义了一个封闭的多边形，以及如何填充它？

例如： * 如果你的方程包括 x + y > 10 和 x + y < 5，那么你将找不到任何解决方案，因为没有东西可以填充。 * 如果你的方程只是 x > 0，y > 0，那么你会遇到问题，因为需要涂漆的表面是无界/无限的。

你的方程组是否有解，我相信大致相当于线性规划中的单纯形算法：算法的第一阶段确定问题是否可行。

那个解决方案是否形成一个封闭的多边形通常并不是线性规划中感兴趣的问题。但是，您可以通过检查以下4个问题中的任何一个问题（最小化x、最大化x、最小化y、最大化y），在给定不等式的情况下是否存在解来处理它：如果这些问题中的任何一个都不存在解，则您就知道问题无界 - 我认为这意味着该多边形不是封闭的。

一旦你知道了多边形是封闭的，我会简单地计算所有线段的交点，可能将其减少到凸包，然后填充结果的多边形。

- Mathias

---

事实上，我的应用程序是使用单纯形法可视化线性规划解决方案过程。x>0，y>0始终成立。目前，我检查每个边界点以查看它是否满足所有不等式，如果是，则该点形成填充形状。是的，对于无界情况来说，这更加复杂。 - bvk256

Answer 2

你可以利用一个区域由线性半空间的并集定义必须是单一凸区域的事实，虽然可能是半无限的，这可能会增加混乱。

1. 首先添加一个包含你正在绘制的域的上限的矩形“窗口”不等式。这样你就可以忽略结果为半无限空间的情况。 2. 找到所有边界之间的交点。这是两个嵌套循环和一个交集检查器。(如果需要，可以首先找到所有非窗口不等式的交点，将窗口设置为包括所有这些交点，然后添加与窗口相关的交点。) 3. 丢弃未满足任何不等式的所有点。 4. 如果剩下任何点，使用凸包算法找到封闭区域并绘制它。

请注意，如果已知图形窗口，则可以通过仅考虑位于窗口内部的边界段并使用增强的 Bentley-Ottman安排算法，使交点计算更加高效。

- Gene

Answer 3

我可以提出以下算法。需要注意的是，这个算法并不基于寻找线交点并以某种方式确定面积的想法，因为这种方法对算法实现来说似乎过于复杂。
由于计算空间在任何情况下都是离散的，因此引入一些正交网格似乎很自然。
所以：

1. 让我们引入带有某些特征单元大小的正交网格。该大小取决于问题陈述的某些细节。假设网格具有N*M个节点(x_i, y_j)，其中0 <= i < N，0 <= j < M
2. 让我们找到所有满足所有K个不等式a_k*x1_i+b_k*y1_j-c_k <= 0 (0 <= k < K)的点(x1_i, y1_j)。这些点应该被填充。
3. 如果网格分辨率足够进行可视化，那就没了。如果不是，我们必须确定哪条线经过边界点附近。为此，我们检查每个边界点及其相邻点。如果我们发现某个不等式在该点的邻居处被违反，则意味着第Sth条线通过该点和该邻居之间。

- Roman Fursenko