处理 CAD 绘图中的不精确问题
我有一个 CAD 应用程序，允许用户绘制线条和多边形等等。
我面临的一个棘手问题是用户绘图可能非常不精确，例如，用户可能想要绘制两个相互连接的矩形。因此，两个矩形应该共享一条线。然而，用户很容易不画一条线，而是画两条条彼此非常接近的线，彼此如此接近，以至于当从屏幕上看时，你会误认为它们是是同一条线，只是当您放大一点时它们不是同一条线。
我的应用程序需要用户正确绘制线条（或者我的预处理必须能够进行自动校正），否则我的内部算法（我们称之为算法）将无法处理输入正确。
解决此类问题的最佳策略是什么？我正在考虑将点坐标舍入到一定的精度，但是虽然我无法准确指出这种方法的问题，但我感觉这不是正确的做法，这将引入一系列新的问题。
编辑：出于争论的目的，捕捉不是一个可用的选项。就此事而言，各种“输入端”指导都是不可用的。当绘图完成时，但就在我将其提交给我的算法之前，必须通过对我的代码进行预处理来完成纠正。
你说，疯狂的限制。但用户可以在我的应用程序中构建他们的输入，也可以在其他 CAD 软件中构建他们的输入，然后提交给我的引擎进行计算。我无法控制它们在其他 CAD 软件中的输入方式。
编辑 2：我可以让用户指定要发生的“簇半径”，但重要的是，我需要确保我的预处理算法是一致的，不会真正引入一组新的问题。
有什么想法吗？
I have a CAD application, that allows user to draw lines and polygons and all that.
One thorny problem that I face is user drawing can be highly imprecise, for example, a user might want to draw two rectangles that are connected to each other. Hence there should be one line shared by two rectangles. However, it's easy for user to, instead of draw a line, draw two lines that are very close to each other, so close to each other that when look from the screen, you would be mistaken that they are the same line, except that they aren't when you zoom in a little bit.
My application would require user to properly draw the lines ( or my preprocessing must be able to do auto correction), or else my internal algorithm (let's call it The Algorithm) would not be able to process the inputs correctly.
What is the best strategy to combat this kind of problem? I am thinking about rounding the point coordinates to a certain degree of precision, but although I can't exactly pinpoint the problem of this approach, but I feel that this is not the correct way of doing things, that this will introduce a new set of problem.
Edit: For the sake of argument the snapping isn't an available option. For the matter, all sorts of "input-side" guidance are not available. The correction must be done via preprocessing on my code, when the drawing is finished, but just before I submit it to my algorithm.
Crazy restriction, you say. But a user can construct their input either in my application, or they can construct their input in other CAD software and then submit to my engine to do the calculation. I can't control how they input in other CAD software.
Edit 2:I can let user to specify the "cluster radius" to occur, but the important point is, I would need to make sure that my preprocessing algorithm is consistent and won't really introduce a new set of problem.
Any idea?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我看到的一个问题是，您的聚类/捕捉算法必须自行决定将哪个点移动到另一个点。
在实时输入期间，捕捉很简单：第一个点保持不变，第二个点捕捉到第一个点上。如果在离线模式下，您得到一堆您知道应该将它们对齐在一起的点，那么您不知道结果点应该位于哪里。计算平均值，可能会产生一个全新的点？从所有候选者中选择最中心的点？随机选一个？尝试将您的点与 x/y/z 轴上的其他点对齐？
如果您的程序允许任何用户交互，您可以检测可能是合并候选点的点簇，并向用户提供不同的合并目标点以供选择。
否则，您可以使这种行为可配置：采用合并半径（“如果两个或多个点彼此在 n 个单位内……”）和合并算法（“……将它们合并到最中心的点”）。给定的点”）作为参数并从配置文件中读取它们。
One problem I see is that your clustering/snapping algorithm would have to decide on its own which point to move onto which other point.
During live input snapping is simple: the first point stays put, the second point is snapped onto the first. If in offline mode you get a bunch of points that you know should be snapped together, you have no idea where the resulting point should lie. Calculate the average, possibly resulting in a completely new point? Choose the most central point out of all the candidates? Pick one at random? Try to align your point with some other points on the x/y/z-axis?
If your program allows any user interaction at all, you could detect point clusters that might be candidates for merging, and present the user with different merge target points to choose from.
Otherwise, you could make this kind of behaviour configurable: take a merge radius ("if two or more poins are within n units of one another...") and a merging algorithm ("... merge them into the most central of the points given") as parameters and read them from a config file.
捕捉点。用户应该能够捕捉到端点（以及更多点），然后，当您检测到捕捉时，只需将用户单击的点更改为捕捉点即可。检查AutoCAD，功能线末端、中间等。
编辑：如果您想要离线捕捉，那么您只需检查每对点是否彼此靠近。问题是，这在 NP 问题中，因此需要花费大量时间，因为您无法真正达到 O(n^2) 时间复杂度。您需要的该算法应该位于“聚类”下。
EDIT2：我认为你不应该认为输入数据不好。但是如果你真的想这样做，最简单的方法是获取每个点，检查用户定义的半径中是否还有其他点，如果是，找到应该合并为一个点的整个组，找到点和所有点的坐标平均值他们到了那个特定的点。但请记住 - 大多数设计师都知道捕捉点的用途，如果他们不使用它们，他们对此也有正确的想法。
Snapping points. User should be able to snap to end points (and many more) then, when you detect a snap, just change the point user clicked to snap point point. Check AutoCAD, functions line End, Middle and so on.
EDIT: If you want offline snapping then you just need to check every pair of points if they are near each other. The problem is that this in NP-problem so it will take a lot of time as you can't really get under O(n^2) time complexity. This algorithm you need should be under "clustering".
EDIT2: I think you shouldn't consider that input data is bad. But if you reallllllly want to do this, simples way is to take each point, check if there are other points in users defined radius, if yes find whole group that should merge into one point, find avg of coordinates of points and point all of them to that specific point. But remember - most designers KNOW what are snap points for and if they don't use them they have valid idea for that.
在我看来，你的基本问题（我希望我理解正确）是确定两条线是否是“同一”线。
根据我自己的经验，您的感觉是正确的，舍入输入中的坐标可能不是一个好主意。
也许您应该按原样保留输入中的坐标，但实现您的函数，让我们将其命名为您在“算法”中使用的 IsSameLine （如果我理解您的描述，那么谁会确定两个矩形是否相连正确）。
IsSameLine 可以考虑特定（可能可配置）的屏幕分辨率将输入线的端点从源坐标转换为屏幕坐标，并检查它们在屏幕坐标中是否相同。
也就是说，假设您有一个具有以下范围的输入文件（左下）（右上）（（10,10），（24,53））。问题是，如果在 1600x1200 像素屏幕上以“缩放至范围”级别绘制，点 (11,15) 和 (11.1, 15.1) 之间的距离有多远。因此您可以确定从源坐标到“屏幕坐标”的转换。然后，您可以如上所述在 IsSameLine 中使用此转换。
但我不确定这对您来说实际上是一个好的解决方案。
另一种（也许更好？）可能性是实现 IsSameLine，如果两条线的点相距最大 epsilon 距离，则返回 true。 epsilon 可以有一个基于输入矢量数据范围计算的默认值，并且让用户能够为其提供另一个值可能是一个好主意。
Your basic problem seems to me (I hope I understood correctly) to determine if two lines are the "same" line.
Out of my own experience your feeling is correct, rounding the coordinates in the input might prove not to be a good idea.
Maybe you should leave the coordinates in the input as they are but implement your function let's name it IsSameLine That you use in "The Algorithm" (who among others determines if two rectangles are connected if i understood your description correctly).
IsSameLine could transform the endpoints of the input lines from source coordinates to screen coordinates considering a certain (possibly configurable) screen resolution and check if they are the same in screen coordinates.
I.e. let's say you have an input file with the following extent (lowerleft) (upperRight) ((10,10), (24,53)). The question would be how far apart would be points (11,15) and (11.1, 15.1) if drawn at "zoom to extents" level on a 1600x1200 pixels screen. So you can determine a transform from source coordinates to "screen coordinates". You use then this transformation in IsSameLine as described above.
I'm not sure however this would be actually a good solution for you.
Another (maybe better?) possibility is to implement IsSameLine to return true if the points of the two lines are at maximum epsilon distance apart. The epsilon could have a default value computed based on the extent of the input vector data and probably it would be a good idea to give the user the possibility to give another value for it.