3

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

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

我想要的输出是一组形成要填充的形状的点。例如，对于此示例，图表将是：

在此处输入图像描述
以及点集：[0,4]、[1,0]、[4,0]。找到这些点的算法是什么？我知道线的交点是线性系统的解决方案，但我不知道如何正确填充。请注意，这个问题不是关于图形系统的实现，而是如何找到填充的形状点。

4

3 回答 3

2

在我看来，您的问题实际上是两个问题：方程式是否定义了一个封闭的多边形，以及如何填充它？

例如，
* 如果你的方程包括 x + y > 10 和 x + y < 5，那么你将无法找到解决方案，没有什么可填充的，* 如果你的方程只是 x > 0， y > 0，您会遇到问题，因为要绘制的表面将是无界/无限的。

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

该解决方案是否形成一个封闭的多边形并不是线性规划通常感兴趣的事情。但是，您可以通过检查 4 个问题来解决这个问题：最小化 x、最大化 x、最小化 y、最大化 y，给定您的不等式，是否有解决方案。如果这些问题中的任何一个都没有，那么您就知道问题是无限的——我认为这意味着多边形没有闭合。

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

于 2013-03-23T18:11:26.407 回答
2

您可以利用这样一个事实，即任何定义为线性半空间并集的区域都必须是单个凸区域，尽管可能是半无限的，这可能会增加混乱。

  1. 首先添加一个矩形的不等式“窗口”，它是您正在绘制的域的超集。这样，您可以忽略结果是半无限空间的情况。

  2. 找到所有边界对之间的交点。这是两个嵌套循环和一个交集检查器。（如果需要，您可以先找到所有非窗口不等式的交集，将窗口设置为包括所有这些，然后添加与窗口相关的交集。）

  3. 扔掉所有不能满足任何不等式的点。

  4. 如果还有点，使用凸包算法找到封闭区域并绘制它。

请注意，如果预先知道图形窗口，则可以通过仅考虑位于窗口内的边界段并使用增强型 Bentley-Ottman 等排列算法来提高相交计算的效率。

于 2013-03-23T18:53:36.347 回答
1

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

  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 for 0 <= k< K 的所有点 (x1_i, y1_j)。这些点应该被填充。
  3. 如果网格分辨率足以进行可视化，那就是全部。如果不是，我们必须确定哪条线通过边界点附近。为此，我们检查每个边界点及其邻居。如果我们发现该点的邻居违反了 Sth 不等式，则意味着 Sth 线在该点和该邻居之间经过。
于 2013-03-23T17:18:40.533 回答