二维线段变形算法
创建一个益智游戏，我希望形状根据用户输入而变形。用户单击一个顶点并拖动该点来改变形状。例如，如果用户单击 A 并向下拖动（缩短线段 AG），B 点将向下移动等量（缩短 BC），F 点将向左移动，缩短 AF 和 FG，最后 E 点也会移动到左边与点 F 保持一致。
有一个线段数组，每个线段本身就是一个包含两个端点的数组。移位时，我会循环搜索所有相等的点。这一切都不是一成不变的，没有人愿意做出任何必要的改变来使其发挥作用。
我已经为此工作了两天，完全被难住了。
A
B-------------\
| | \
| | \
| | \
| | \
C------------------\F
| G |
| |
| |
D-------------------E
Creating a puzzle game where I want the shapes to morph based on user input. A user clicks on a vertex and drags the point changing the shape. For example if a user clicks on A and drags downward (shortening segment AG), point B would would down an equal amount (shortening BC), point F would move to the left shortening both AF and FG, finally point E would also shift to the left to stay in line with point F.
There is an array of line segments, each line segment is itself an array that contains the two end points. When shifting I have a loop search for all the equal points. None of this is set in stone willing to make any changes needed to get this to work.
I've been working on this for two days and am completely stumped.
A
B-------------\
| | \
| | \
| | \
| | \
C------------------\F
| G |
| |
| |
D-------------------E
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
联立方程，不是吗？
我假设每条线都应该保留其坡度。那么你的图满足这些方程（或几乎这些方程，我不能 100% 确定 AF 线的斜率）：
当玩家拖动 A 时，Ay 和 Ax 实际上是常数，因此你有十一个方程和十二个未知数。 （正如 Beta 指出的那样，存在一些约束不足，因为三个方程 Bx = Cx = Dx 与其他任何方程都不相关，Dy = Ey 也不相关）
您可能想要的是改变最少的解决方案你的变量。我不知道该怎么做。但由于这是一款游戏，如果偶尔您没有获得足够的最小更改集，也可能并不重要。因此，也许贪心算法会起作用，如下所示：
Simultaneous equations, innit?
I'm assuming that each line is supposed to retain its slope. Then your figure satisfies these equations (or nearly these equations, I'm not 100% sure about the slope of the AF line):
When the player is dragging A, then A.y and A.x are effectively constant, so you have eleven equations and twelve unknowns. (There's some under-constraining, as Beta points out, because the three equations B.x = C.x = D.x don't relate to any of the others, and neither does D.y = E.y.)
What you probably want is the solution that changes the fewest of your variables. I don't know how to do that. But since this is a game, it probably doesn't matter if occasionally you don't get quite the minimum set of changes. So maybe a greedy algorithm would work, like this:
我的第一个想法是使用单纯形算法进行线性规划，但我认为这要么是错误的，要么至少是不完整的。基本上，大多数（如果不是全部）规则都是线性“等于”规则，其中线性编程处理“小于”（或 <= 或其他）规则。
解决办法可能是统一。也就是说，用尽可能少的变量来表达你的规则。如果有规则 f(a) = g(b)，则可以通过定义 b=g'(f(a)) 并替换找到 b 的其他位置来有效地消除 b。由于实际替换效率很低，因此只需记下 a 和 b 之间的关系即可。
对于轻微的并发症，基本方法是并查找。在完全相等的情况下，您可以通过添加从 b 到 a 的链接来消除 b。当“找到”b 时，您就会识别 a（或它所链接的任何内容）。因此，您可以随时将任何规则有效地转换为仅使用非消除变量的形式。这种情况下的复杂性是 - 当您点击链接时，您需要跟踪 g'(f(a)) 样式的内容。由于这都是线性的，所以这不应该是一个大问题，但也不是微不足道的。
您可能需要能够回溯统一 - 记下您在堆栈上设置的链接，以便在展开堆栈时可以按照正确的顺序再次将它们清空。
我不确定你是否有任何相对条件（小于或其他），但如果是这样，一旦你消除了尽可能多的变量，你仍然需要一些线性规划。如果还有两个剩余变量，这在概念上很简单。对于这两个变量的每个线性条件，在二维图上画一条线，使线的一侧代表有效区域。传统上，条件是“标准化”的，因此有效方始终包括原点。基于交叉点，最接近原点的线段形成凸多边形。最佳解决方案位于其中一个角落，并使用线性评分规则（您正在优化的东西）进行评估，在您的情况下，该规则将被定义为给出“最佳”形状，其中存在一些模糊性或优先级冲突您的规则 - 例如，您不能将一个点一直推过一条线，因此事物会在某些点处被阻挡。
如果剩下两个以上的变量，则需要凸多边形的多维等价物 - 这称为单纯形。单纯形算法的实际实现涉及矩阵。
这已经过于简单化了，以至于在某些细节上可能是错误的，这就是我所能解释的。 IIRC 您可以在 Sedgewick 中获得对这些组件技术的详细描述，尽管现在 Wikipedia 可能也同样好。
单纯形求解器有时用于窗口布局 - 例如，我认为 wxWidgets 使用一个来调整窗口中控件的大小。统一是逻辑编程（Prolog 等）的一个定义特征，但底层的并查原理非常简单。关键技巧是弄清楚如何将二维图形转换为一组表达它将如何变化的规则，并理解如何表示和操纵这些规则，尤其是矩阵形式。
My first thought was linear programming with the simplex algorithm, but I think this is either wrong or at least incomplete. Basically, most if not all of your rules are linear this-equals-that rules, where linear programming deals with this-is-less-than-that (or <= or whatever) rules.
The fix may be unification. That is, express your rules WRT as few variables as possible. Where you have a rule f(a) = g(b), you can effectively eliminate b by defining b=g'(f(a)) and substituting everywhere else you find the b. Since actually substituting is inefficient, you can just make a note of the relationship between a and b.
With minor complications, the basic approach is union-find. In the exact-equality case, you would eliminate b by adding a link from b to a. When 'finding' b, you then identify a (or whatever it has been linked to) instead. So at any time, you can efficiently translate any rule to a form that uses only non-eliminated variables. The complication in this case - you need to keep a running track of the g'(f(a)) style stuff as you follow the links. As this is all linear, it shouldn't be that big a problem, but not trivial either.
You might need to be able to backtrack the unification - make a note of the links you set on a stack, so you can null them again in the correct order as you unwind the stack.
I'm not sure if you have any relative conditions at all (less than or whatever), but if so, once you've eliminated as many variables as possible, you'll still need some linear programming. If you have two remaining variables, this is conceptually simple. For each linear condition on those two variables, draw a line on a 2D graph such that one side of the line represents the valid region. The conditions are traditionally "normalised" so the valid side always includes the origin. Based on crossing points, the line-segments nearest the origin form a convex polygon. An optimal solution is on one of the corners, and is assessed using a linear scoring rule (the thing you're optimising) which would in your case be defined to give the "best" shape where there's some ambiguity or some conflict of priorities in your rules - e.g. you can't push a point all the way through a line, so things get blocked at certain points.
If you have more than two variables remaining, you need a multi-dimensional equivalent of a convex polygon - and that is called a simplex. Practical implementation of the simplex algorithm involves matrices.
This is already oversimplified to the point that it's probably wrong in some of the details, and it's about as far as I can explain. IIRC you can get good descriptions of these component techniques in Sedgewick, though Wikipedia may be just as good these days.
Simplex solvers are sometimes used for Window layouts - I think wxWidgets uses one for resizing the controls in a window, for example. Unification is a defining feature of logic programming (Prolog etc), but the underlying union-find principles are simple enough. The key trick is figuring out how to translate a 2D figure into a set of rules expressing how it will change, and understanding how to represent and manipulate those rules, particularly in matrix form.
这个怎么样……你的拼图只有三角形、长方形和正方形吗？在这种情况下，您可以开发一种方法来处理每个形状，具体取决于哪个顶点被移动以及哪些形状受到该顶点移动的影响...在您的示例中，移动顶点 A 将影响正方形 ABCG 和三角形 AGF。所以，当 A 移动时，顶点 C 保持不受影响......你只需要“重新定位”B 和 G。除非我理解你的例子错误，否则我不明白移动 A 会如何影响 F。 HTH。
How about this...does your puzzle only have triangles, rectangles and squares? In that case, you may develop a method to deal with each shape depending on which vertex is moved and which shapes are affected by that vertex's move...In your example, moving vertex A will impact square ABCG and triangle AGF. So, when A moves, vertex C remains unaffected...you only need to "reposition" B and G. Unless I understand your example wrong, I dont see how moving A will affect F, though. HTH.