为受约束的矩形形状强制指定布局 [英] Force directed layout for constrained rectangular shapes

问题描述

我需要根据滑动形状本身的位置，均匀地分布一组受轴向对齐的最大宽度/高度约束的滑动矩形和一些水平/垂直坐标。矩形被限制在一个方向上，可以沿另一个轴滑动，不会重叠，也不会跨越。

这个问题是基于：

然后计算必须随距离缩放的驱动力。如果线性与否，无关紧要，而是从左/右或上/下均匀隔开的障碍物应该是合力零。缩放主要改变动态行为。只有在约束阻止运动达到均匀间距的状态下，最终结果才会受到影响。因此，您可以使用以下任何一种方式：

  F = c *（d1-d0）
 F = c *（d1 ^ 2  -  d0 ^ 2）
 F = c *（1 / d1 ^ 2  -  1 / d0 ^ 2）
  

其中 c 是一些幅度系数， d0，d1 是最接近的2个在同一个轴上的障碍距离。

现在从这里你将获得2个力（每个轴一个）

• Fx - 水平轴力
  
• Fy - 竖轴力

简而言之就是它。但是这些限制有一个问题。例如，选定的滑块（黄色）是垂直的。这意味着它只能在x轴上移动。所以你把 Fx 驱动力放在它上面。 Fy 力量应该驱动它的父滑块（蓝色），它是水平的并且可以在y轴上移动（如果不是粗糙的）。

这会引入一个问题，因为这个滑块也可以有它自己的 Fy ，所以你应该总是只从每一边选择最强的力。这意味着您需要记住每边的距离/力量，并始终选择最小距离或最高|这是 x0，x1 变量来自它们保持移动中的最小距离的地方

能够轴到最近的障碍物（从包括儿童在内），并且只有在计算所有滑块后才转换为 Fx，Fy 驱动力。

为了检测邻居和碰撞，我认识到3种类型的交互

• 垂直垂直滑块（图像上的底部交互）
  
• 宽平行，它位于相同类型的两个滑块之间并与其较长的边接触（图像上的左右交互）
  
• 短平行
我还介绍了一些速度限制和系数（限制和系数）。 不只是倾销，以避免osci llations）。速度和加速度限制会影响解决方案的时间和稳定性。还有另一个使用它们的原因（我不这样做），那就是保持滑块的顺序，这样它们就不会互相跳过。这可以通过简单地限制最高速度来完成，因此每一次迭代，任何滑块都不会移动超过滑块厚度的一半。因此，如果发生碰撞，碰撞例程将启动。




我跳过了我的代码，因为我的配置设置为滑块的顺序与其索引号一致。因此，如果我发现任何滑块位于某个测试滑块的左侧，而其索引较高，则表示它已跳过，而我通过恢复最后一个位置来处理它。这是便宜的黑客攻击，并且不适用于复杂集合，其中许多儿童滑块不仅仅是一个。


• 反馈由于约束，有时你的驱动力可能会丢失（行进到固定或卡住的父滑块），如果这种行为破坏了结果，你应该以相反的方式传播相反的力量给它造成它的邻居。对于简单的构造来说，这不是必须的，因为它已经包含的驱动力，但对于更复杂的儿童链它可能构成一个可能的威胁（但这是我疯狂的想法，我可能在这方面是错误的）。
  在本质上，这是通过整合来自所有相邻物体的力而提供的，而不仅仅是最接近的物体，但这会导致我认为不等间距。


>


I need to evenly distribute a bunch of axis-aligned sliding rectangles constrained by a maximum width/height and by some horizontal/vertical coordinates depending from the position of the sliding shapes itself. Rectangles are constrained in one direction, can slide along the other axis, may not overlap and not step over as well.

This question is based on: How to implement a constraint solver for 2-D geometry? and Spektre's well accepted proposal for a force-driven constraint solver.

The whole structure is build as usual as a graph where the rectangles represent the nodes.

Now, i need to check the size of each rectangle to get the correct force calculation and to avoid overlap, but i have some trouble to understand how a force field could be applied to a 2-D shape, and how the distance between two rectangles shall be calculated. Maybe the vertices or the sides?

Relevant code is in the function Solver.solve() below, where s.Z represent respectively the height of a shape for the horizontal ones, and the width for the vertical ones:

for(var i=0, l=sliders.length; i<l; i++) {
    var si = sliders[i];
    for(var j=i+1, k=sliders.length; j<k; j++) {
        var sj = sliders[j];
        if(si._horizontal == sj._horizontal) {
            // longer side interaction
            if(si._horizontal == 1) {
                a0 = si.X + si.a; a1 = sj.X + sj.a;
                b0 = si.X + si.b; b1 = sj.X + sj.b;
                x0 = si.Y; x1 = sj.Y;
            } else {
                a0 = si.Y + si.a; a1 = sj.Y + sj.a;
                b0 = si.Y + si.b; b1 = sj.Y + sj.b;
                x0 = si.X; x1 = sj.X;
            }
            if(((a0 <= b1) && (b0 >= a1)) || ((a1 <= b0) && (b1 >= a0))) {
                x0 = x1 - x0;
                if((si.ia >= 0) && (x0 < 0.0) && ((fabs(si.x0) < si.Z) || (fabs(si.x0) > fabs(x0)))) si.x0 = -x0;
                if((si.ia >= 0) && (x0 > 0.0) && ((fabs(si.x1) < si.Z) || (fabs(si.x1) > fabs(x0)))) si.x1 = -x0;
                if((sj.ia >= 0) && (x0 < 0.0) && ((fabs(sj.x0) < sj.Z) || (fabs(sj.x0) > fabs(x0)))) sj.x0 = +x0;
                if((sj.ia >= 0) && (x0 > 0.0) && ((fabs(sj.x1) < sj.Z) || (fabs(sj.x1) > fabs(x0)))) sj.x1 = +x0;
            }
            // shorter side interaction
            if(si._horizontal == 1) {
                a0 = si.Y - si.Z; a1 = sj.Y + sj.Z;
                b0 = si.Y + si.Z; b1 = sj.Y + sj.Z;
                x0 = si.X; x1 = sj.X;
            } else {
                a0 = si.X - si.Z; a1 = sj.X + sj.Z;
                b0 = si.X + si.Z; b1 = sj.X + sj.Z;
                x0 = si.Y; x1 = sj.Y;
            }
            if(((a0 <= b1) && (b0 >= a1)) || ((a1 <= b0) && (b1 >= a0))) {
                if(x0 < x1) {
                    x0 += si.b; x1 += sj.a;
                } else{
                    x0 += si.a; x1 += sj.b;
                }
                x0 = x1 - x0;
                if(si.ia >= 0) {
                    var sa = this.sliders[si.ia];
                    if((sa.ia >= 0) && (x0 < 0.0) && ((fabs(sa.x0) < sa.Z) || (fabs(sa.x0) > fabs(x0)))) sa.x0 = -x0;
                    if((sa.ia >= 0) && (x0 > 0.0) && ((fabs(sa.x1) < sa.Z) || (fabs(sa.x1) > fabs(x0)))) sa.x1 = -x0;
                }
                if(sj.ia >= 0) {
                    var sa = sliders[sj.ia];
                    if((sa.ia >= 0) && (x0 < 0.0) && ((fabs(sa.x0) < sa.Z) || (fabs(sa.x0) > fabs(x0)))) sa.x0 = +x0;
                    if((sa.ia >= 0) && (x0 > 0.0) && ((fabs(sa.x1) < sa.Z) || (fabs(sa.x1) > fabs(x0)))) sa.x1 = +x0;
                }
            }
        }
    }
}
// set x0 as 1D vector to closest perpendicular neighbour before and x1 after
for(var i=0, l=sliders.length; i<l; i++) {
    var si = sliders[i];
    for(var j=i+1, k=sliders.length; j<k; j++) {
        var sj = sliders[j];
        if(si._horizontal != sj._horizontal) {
            // skip ignored sliders for this
            var ignore = false;
            for(var n=0, m=si.ic.length; n<m; n++) {
                if(si.ic[n] == j) {
                    ignore = true;
                    break;
                }
            }
            if(ignore === true) continue;
            if(si._horizontal == 1) {
                a0 = si.X + si.a; a1 = sj.X - sj.Z;
                b0 = si.X + si.b; b1 = sj.X + sj.Z;
                x0 = si.Y;
            } else {
                a0 = si.Y + si.a; a1 = sj.Y - sj.Z;
                b0 = si.Y + si.b; b1 = sj.Y + sj.Z;
                x0 = si.X;
            }
            if(((a0 <= b1) && (b0 >= a1)) || ((a1 <= b0) && (b1 >= a0))){
                if(si._horizontal == 1) {
                    a1 = sj.Y + sj.a;
                    b1 = sj.Y + sj.b;
                        } else {
                    a1 = sj.X + sj.a;
                    b1 = sj.X + sj.b;
                }
                a1 -= x0; b1 -= x0;
                if(fabs(a1) < fabs(b1)) x0 = -a1; else x0 = -b1;
                if((si.ia >= 0) && (x0 < 0.0) && ((fabs(si.x0) < si.Z) || (fabs(si.x0) > fabs(x0)))) si.x0 = +x0;
                if((si.ia >= 0) && (x0 > 0.0) && ((fabs(si.x1) < si.Z) || (fabs(si.x1) > fabs(x0)))) si.x1 = +x0;
                if(sj.ia < 0) continue;
                var sa = sliders[sj.ia];
                if((sa.ia >= 0) && (x0 < 0.0) && ((fabs(sa.x0) < sa.Z) || (fabs(sa.x0) > fabs(x0)))) sa.x0 = -x0;
                if((sa.ia >= 0) && (x0 > 0.0) && ((fabs(sa.x1) < sa.Z) || (fabs(sa.x1) > fabs(x0)))) sa.x1 = -x0;
            }
        }
    }
}

How shall be the force calculation for rectangular shapes, to get from the force field an evenly distribution, i.e. such as the distance between rectangles will be the largest possible? Think like the rectangles are really hot and must be spaced at most, with respect to their custom x/y constraints.

Any help will be greatly appreciated.

EDIT:

Sample: https://plnkr.co/edit/3xGmAKsly2qCGMp3fPrJ?p=preview

解决方案

If I get this question right OP asks for set of rules for driving the sliders so the final simulation state is leading to valid solution.

So here is my approach it is really recapitulation of my solver code from linked answer in OP but it would not fit in there as I already hit the 30 KByte limit and I feel it needs a bit more explaining then just commented code so here it is:

1. Forces

   To ensure equal spacing as much as possible you need to change the rules a bit (apart from real physics) so you are accounting only the nearest obstacle to driving Force instead of all of them as in real world. Also the force is affected only by distance and not weighted also by area of contact/overlap as most physical forces do (electrostatic included).

   So during iteration of i-th slider (Yellow) find the distances to closest obstacle in all 4 directions (Red):

   And compute the driving force which has to be scaled with distance. Does not really matter if linearly or not but for evenly spaced obstacles from left/right or up/down should be the resultant force zero. Scaling changes mostly the dynamics behavior. The final outcome is affected by it only in states where constrains blocks the movement to achieve even spacing. So you can use for example any of these:

   F = c * (d1-d0)
   F = c * (d1^2 - d0^2)
   F = c * (1/d1^2 - 1/d0^2)
   

   Where c is some magnitude coefficient and d0,d1 are the 2 closest obstacle distances in the same axis.

   Now from this you will obtain 2 forces (one for each axis)

   • Fx - horizontal axis force
   • Fy - vertical axis force

   In a nutshell that is it. But there is a problem with the constrains. For example selected slider (Yellow) is vertical. That means it can move only in x axis. So you put the Fx driving force to it. The Fy force should drive its parent slider (Blue) which is horizontal and can move in y axis (if not fixed of coarse).

   This introduce a problem because that slider can also have its own Fy so you should always select only the strongest force from each side. That means you need to remember both distances/forces from each side and select always the smallest distance or |highest| force from each side.

   That is where the x0,x1 variables come from they hold the min distance in movement able axis to nearest obstacles (from child included) and only after computation of all sliders are converted to Fx,Fy driving forces.

   To detect neighbors and collisions I recognize 3 types of interaction

   • perpendicular which is between horizontal and vertical slider (bottom interaction on image)
   • wide parallel which is between two sliders of the same type contacting with its longer sides (left,right interaction on image)
   • short parallel which is between two sliders of the same type contacting with its shorter sides (top interaction on image)

2. Limits and coefficients

   I also introduced some speed limits and coefficients (not just for dumping to avoid oscillations). The speed and acceleration limits affects the solution time and stability. There is also another reason to use them (I do not do) and that is to preserve the order of sliders so they do not skip through each other. That can be done by simply limiting the top speed so per single iteration any slider will not move more then the half of thickness of sliders. So in case of collision the collision routine will kick in.

   I am skipping that in my code because my config is set so the order of sliders is consistent with its index number. So if I detect that any slider is on left side of some tested slider while its index is higher it means it has skipped and I handle it by restoring last position instead... This is cheap hack and will not work in complex sets where are many child sliders in chain not just one.

3. Feedback

   Due to constraints sometimes your driving force can get lost (traveling to fixed or stuck parent slider) in case this behavior corrupts the result you should propagate opposite force the other way around too to the neighbor it caused it. For simple constructs is this not necessary as the driving force it already contain but for more complicated children chains It could pose a possible threat (but that is my wild thinking and I may be wrong in this). In nature this is provided by integrating force from all of the neighboar objects instead of just the closest ones but that would lead to non equal spacing I think.

这篇关于为受约束的矩形形状强制指定布局的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！