2

我有一个 CAD 应用程序，它允许用户绘制线条和多边形等等。

我面临的一个棘手问题是用户绘图可能非常不精确，例如，用户可能想要绘制两个相互连接的矩形。因此，两个矩形应该共享一条线。然而，用户很容易画两条线，而不是画一条线，它们彼此非常接近，彼此如此接近，以至于当从屏幕上看时，你会误认为它们是同一条线，除了当您放大一点时，它们不是。

我的应用程序将要求用户正确绘制线条（或者我的预处理必须能够进行自动校正），否则我的内部算法（我们称之为算法）将无法正确处理输入。

解决此类问题的最佳策略是什么？我正在考虑将点坐标四舍五入到一定的精度，但是虽然我不能准确指出这种做法的问题，但我觉得这不是正确的做事方式，这会引入一个新的集合的问题。

编辑：为了争论，捕捉不是一个可用的选项。就此而言，各种“输入端”指导均不可用。更正必须通过对我的代码进行预处理来完成，当绘图完成时，但就在我将其提交给我的算法之前。

疯狂的限制，你说。但是用户可以在我的应用程序中构建他们的输入，或者他们可以在其他 CAD 软件中构建他们的输入，然后提交给我的引擎进行计算。我无法控制他们在其他 CAD 软件中的输入方式。

编辑 2：我可以让用户指定要发生的“集群半径”，但重要的是，我需要确保我的预处理算法是一致的，并且不会真正引入一组新问题。

任何想法？

4

3 回答 3

3

我看到的一个问题是您的聚类/捕捉算法必须自行决定哪个点移动到另一个点。

在实时输入捕捉过程中很简单：第一个点保持不变，第二个点捕捉到第一个点。如果在离线模式下你得到一堆你知道应该被捕捉在一起的点，你不知道结果点应该在哪里。计算平均值，可能会产生一个全新的点？从所有候选人中选择最中心的一点？随便挑一个？尝试将您的点与 x/y/z 轴上的其他点对齐？

如果您的程序完全允许任何用户交互，您可以检测可能成为合并候选的点簇，并为用户提供不同的合并目标点以供选择。
否则，您可以使这种行为可配置：采用合并半径（“如果两个或多个点在彼此的 n 个单位内……”）和合并算法（“……将它们合并到给定的点”）作为参数并从配置文件中读取它们。

于 2011-01-12T10:54:35.883 回答
2

捕捉点。用户应该能够捕捉到端点（以及更多），然后，当您检测到捕捉时，只需将用户单击的点更改为捕捉点。检查AutoCAD，功能线End，Middle等。

编辑：如果您想要离线捕捉，那么您只需要检查每对点是否彼此靠近。问题是这在 NP 问题中，所以它会花费很多时间，因为你不能真正达到 O(n^2) 时间复杂度。您需要的这个算法应该在“聚类”下。

EDIT2：我认为您不应该认为输入数据不好。但是如果你真的想这样做，简单的方法是获取每个点，检查用户定义的半径中是否有其他点，如果是，找到应该合并为一个点的整个组，找到点坐标的平均值并指向所有他们到那个特定的点。但请记住 - 大多数设计师都知道什么是快照点，如果他们不使用它们，他们对此有正确的想法。

于 2011-01-12T08:00:41.387 回答
2

在我看来，您的基本问题（我希望我理解正确）确定两行是否是“相同”行。

根据我自己的经验，您的感觉是正确的，将输入中的坐标四舍五入可能不是一个好主意。

也许您应该将输入中的坐标保持原样，但实现您的函数，让我们将其命名为 IsSameLine 您在“算法”中使用的（如果我正确理解您的描述，谁确定两个矩形是否连接）。

IsSameLine 可以将输入线的端点从源坐标转换为屏幕坐标，考虑到某个（可能可配置的）屏幕分辨率，并检查它们在屏幕坐标中是否相同。

即假设您有一个输入文件，其范围如下（左下）（右上）（（10,10），（24,53））。问题是如果在 1600x1200 像素屏幕上以“缩放到范围”级别绘制，点 (11,15) 和 (11.1, 15.1) 之间的距离将是多少。因此，您可以确定从源坐标到“屏幕坐标”的转换。然后如上所述在 IsSameLine 中使用此转换。

但是我不确定这对您来说实际上是一个很好的解决方案。

另一种（也许更好？）可能性是如果两条线的点相距最大 epsilon 距离，则实现 IsSameLine 以返回 true。epsilon 可以有一个基于输入矢量数据的范围计算的默认值，并且让用户可以为其提供另一个值可能是一个好主意。

于 2011-01-12T10:13:24.607 回答