如何实现一个解决2D几何约束问题的求解器？

Question

我有一组金属滑块，它们在以下方式上被限制在x和y轴上：

我需要在相同滑块的所有部分之间最大化水平距离，并在滑动部分和滑块本身之间最大化垂直距离。如何解决这个问题？

任何可以解决此问题的建议和建议将不胜感激。

我首先查看了一些非常强大的库，如cassowary和jsLPSolver，但我有些困难理解核心算法以及如何检查约束的可行性以及如何对可能的解进行排名。

如何在JavaScript中实现用于解决此类问题的2-D几何约束求解器的（简单）存根？

编辑：

我有以下输入数据：

maxW = 300, maxH = 320

以下是碎片的定义（非强制性，接受任何解决方案）：

slidingPiece = [pX, pY, width, height, anchorPoint, loopDistance];

我将尝试解释一下我所说的“最大化”。

水平间距：

a0-b1、b1-b2、b2-b4、b4-b5和b5-maxX将相同，即最大X除以垂直相交部分的最大数量加1（5）。 b1-b3和b3-b5将由剩余可用空间确定。

垂直间距：

b1-a3、a3-a4和a0-b5将相同。理想情况下，a0-b3、b3-b4、a2-b2、b4-a3和b2-a4也应该是相同的值。最大化a1-b4和b3-a2等同于最大化b3-b4。对于a2-b2和b4-a3也是如此：距离b2-b4将是最大负值。

因此，我需要最大化每个滑动块与其最近的上方或下方Y约束之间的距离。

这个问题的二维几何表示表明，由于锚定件的垂直交叉，水平间距取决于锚点的垂直距离，而锚定件本身的水平位置也取决于此。例如，b2在上面略短。在这种情况下，b1和b2不再相交，并且将成为相同的x值，即最大X除以4。

在其他一些情况下，例如b2在上部分要长得多 - 并且将穿过锚点a2，则它应该被间隔到a1。这就是为什么会有一组解决方案的原因，其中一些是可行的，而另一些则不可行，因为例如全局最大Y约束将被打破。

- deblocker

---

你可以添加数字数据，而不仅仅是图片，对我来说，只有图片并不能清楚地展示你需要的内容。 - Nina Scholz

我认为你应该为你的任务编写目标函数，并使用任何优化算法。例如，单纯形法：https://en.wikipedia.org/wiki/Simplex_algorithm - stdob--

@stdob-- 很可能目标映射将充满局部最优解。然而，考虑到问题的维度（在x轴上有5个滑块，在y轴上有5个滑块），我建议首先尝试纯蒙特卡罗探索，以找到另一种优化方法的初始位置的更窄区域。 - Adrian Colomitchi

@NinaScholz: 我在这里添加了列的详细信息：https://jsfiddle.net/0ntbkg1r/2/，可行数组只是手工组合的，但我有很多样本数据来测试许多情况。 - deblocker

然后我会采取另一个函数来移动整个结构以最小化（最大）误差，再次进行判断并重复移动。但是这对于依赖约束非常困难，就像你在这里所拥有的一样。为了开始，您可以将所有约束条件简化为非常简单的方法，并尝试动态解决它。然后进行额外的步骤，继续前进，直到达到您的完整问题。 - Nina Scholz

Answer 1

我会尝试类似这个的领域方法。

1. 每个滑块都会收回所有滑块

   力度按距离的平方缩放，就像它们都具有相同极性的电荷或彼此之间连接着弹簧一样。

2. 在此基础上添加随速度缩放的摩擦力

   无论是空气中的v^2还是液体中的v^3都不重要。

3. 实现运动学约束

   对于仅水平和垂直滑动，这应该非常容易。

4. 进行物理模拟，并等待其收敛到稳定状态v = ~ 0

   如果碰到局部最小/最大，则将整个事物摇晃一下或随机排列整个事物并重试。您也可以这样做以获得另一个解决方案。

[Edit4] C++求解器示例

1. structures/classes to represent the slider system

   To ease up later code I will not support closed loops or double anchoring. That is why the i1 slider (most right) is not anchored to anything (will just provide forcefield). I ended up with this slider definition:

   

   look at the source of class _slider for more info.

2. render

   Dash-dash means fixed slider. Silver ones are horizontal, aqua means vertical and yellow is selected by mouse. May be later on red will mean some kind of error/stuck or something for debug purposes. For force field solvers I sometimes add the field strength as red-blue scale but not sure if I will implement it here or not.

   To keep this simple I will not implement zoom/pan functions as your dimensions are convenient for direct render without transforms.

   

3. implement initial setup

   sliders sys;
   int i0,i1,a0,a1,a2,a3,a4,b1,b2,b3,b4,b5;
   sys.slider_beg();//ia,ib,   x,    y,    a0,    a1,    b0,    b1,_horizontal
   i0=sys.slider_add(-1,-1, 25.0, 25.0,  -5.0, 405.0,   0.0,   0.0, 0);
   a0=sys.slider_add(i0,-1,  0.0,  0.0,   0.0, 400.0,   0.0,   0.0, 1);
   a1=sys.slider_add(i0,-1,  0.0,100.0,   0.0, 400.0,   0.0,   0.0, 1);
   a2=sys.slider_add(i0,-1,  0.0,200.0,   0.0, 400.0,   0.0,   0.0, 1);
   a3=sys.slider_add(i0,-1,  0.0,300.0,   0.0, 400.0,   0.0,   0.0, 1);
   a4=sys.slider_add(i0,-1,  0.0,400.0,   0.0, 400.0,   0.0,   0.0, 1);
   b1=sys.slider_add(a0,a2, 20.0,  0.0,   0.0, 125.0, 125.0, 250.0, 0);
   b2=sys.slider_add(a3,-1, 40.0,  0.0, -70.0,  30.0,   0.0,   0.0, 0);
   b3=sys.slider_add(a1,-1, 60.0,  0.0, -70.0,  30.0,   0.0,   0.0, 0);
   b4=sys.slider_add(a2,-1, 80.0,  0.0, -30.0,  70.0,   0.0,   0.0, 0);
   b5=sys.slider_add(a3,a1,100.0,  0.0,-125.0,   0.0,-125.0,-250.0, 0);
   i1=sys.slider_add(-1,-1,425.0, 25.0,  -5.0, 405.0,   0.0,   0.0, 0);
   sys.slider_end();
   

   Where ia is parent index and ib is child index (the slider class itself holds ib as parent but that would be confusing to init as you would need to link to item that do not exist yet so the ib transformation is handled in the sys.add function). sys is class holding the whole thing and sys.add just add new slider to it and returns its index counting from zero. The x,y is relative position to parent.

   To ease up amount of coding this setup must not conflict the constraints. The overview of this setup is in previous bullet.

   Beware the order of sliders must be left to right for vertical and top to bottom for horizontal sliders to ensure correct constraint functionality.

4. mouse interaction

   just simple slider movement for debug and adjusting initial setup values. And or handling stuck cases. You need to handle mouse events, select closest slider if not editing already. And if mouse button is pressed move selected slider to mouse position...

5. physical constraint/interaction

   I simplify this a bit so I just created a predicate function that is called for specified slider and it returns if it or any its child/anchor is in conflict with defined constraints. This is much more easy to code and debug then to update the position to match actual constraint.

   Usage is then a bit more code. First store actual position for updated slider. Then update slider to new position/state. After that if constraints are not met stop actual slider speeds and restore its original position.

   It will be a bit slower but I am too lazy to code the full constraint updater (that code could get really complex...).

   I recognize 2 interactions parallel and perpendicular. The parallel is straight forward. But the perpendicular is interaction between edge of slider and perpendicular sliders near it not including the already intersecting sliders (a,b anchored or just crossing) during initial state. So I created a list of intersecting sliders (ic) at start which will be ignored for this interaction.

6. physical simulation

   Simple Newton - D'Alembert physics for non relativistic speeds will do. Just on each iteration set the accelerations ax,ay to the field strength and frictions.

7. field solver

   This is set of rules/equations to set simulation accelerations for each slider to converge to solution. I ended up with electrostatic retracting force F = -Q/r^2 and linear dampening of speed. Also have implemented absolute velocity and acceleration limiters to avoid numeric problems.

   To boost solution time and stability I added precision control modes where the electric charge is lowering when overall max speed of sliders is decreasing.

这是完整的C++/VCL类代码：

//---------------------------------------------------------------------------
//--- Sliders solver ver: 1.01 ----------------------------------------------
//---------------------------------------------------------------------------
#ifndef _sliders_h
#define _sliders_h
//---------------------------------------------------------------------------
#include <math.h>
#include "list.h"   // linear dynamic array template List<T> similar to std::vector
//---------------------------------------------------------------------------
const double _slider_w   =   3.00;  // [px] slider half width (for rendering)
const double _slider_gap =   4.00;  // [px] min gap between sliders (for colisions)
const double _acc_limit=   100.00;  // [px/s^2]
const double _vel_limit=   100.00;  // [px/s]
const double _friction =     0.90;  // [-]
const double _charge   =250000.00;  // [px^3/s^2]
//---------------------------------------------------------------------------
class _slider   // one slider (helper class)
    {
public:
    // properties
    double x,y;             // actual relative pos
    bool _horizontal;       // orientation
    double a0,a1;           // slider vertexes 0 is anchor point
    double b0,b1;           // anchor zone for another slider
    int ia;                 // -1 for fixed or index of parrent slider
    int ib;                 // -1 or index of parrent slider
    // computed
    List<int> ic;           // list of slider indexes to ignore for perpendicular constraints
    double a,b;             // force field affected part
    double X,Y;             // actual absolute position
    double vx,vy,ax,ay;     // actual relative vel,acc
    // temp
    int flag;               // temp flag for simulation
    double x0,x1;           // temp variables for solver
    // constructors (can ignore this)
    _slider()           {}
    _slider(_slider& a) { *this=a; }
    ~_slider()          {}
    _slider* operator = (const _slider *a) { *this=*a; return this; }
    //_slider* operator = (const _slider &a) { ...copy... return this; }
    };
//---------------------------------------------------------------------------
class sliders   // whole slider system main class
    {
public:
    List<_slider> slider;           // list of sliders

    double vel_max;                 // max abs velocity of sliders for solver precision control
    double charge;                  // actual charge of sliders for solve()
    int    mode;                    // actual solution precision control mode

    // constructors (can ignore this)
    sliders();
    sliders(sliders& a) { *this=a; }
    ~sliders()          {}
    sliders* operator = (const sliders *a) { *this=*a; return this; }
    //sliders* operator = (const sliders &a) { ...copy... return this; }

    // VCL window API variables (can ignore this)
    double mx0,my0,mx1,my1; // last and actual mouse position
    TShiftState sh0,sh1;    // last and actual mouse buttons and control keys state
    int sel;

    // API (this is important stuff)
    void slider_beg(){ slider.num=0; }  // clear slider list
    int  slider_add(int ia,int ib,double x,double y,double a0,double a1,double b0,double b1,bool _h); // add slider to list
    void slider_end();              // compute slider parameters
    bool constraints(int ix);       // return true if constraints hit
    void positions();               // recompute absolute positions
    void update(double dt);         // update physics simulation with time step dt [sec]
    void solve(bool _init=false);   // set sliders accelerations to solve this
    void stop();                    // stop all movements
    // VCL window API for interaction with GUI (can ignore this)
    void mouse(int x,int y,TShiftState sh);
    void draw(TCanvas *scr);
    };
//---------------------------------------------------------------------------
sliders::sliders()
    {
    mx0=0.0; my0=0.0;
    mx1=0.0; my1=0.0;
    sel=-1;
    }
//---------------------------------------------------------------------------
int sliders::slider_add(int ia,int ib,double x,double y,double a0,double a1,double b0,double b1,bool _h)
    {
    _slider s; double q;
    if (a0>a1) { q=a0; a0=a1; a1=q; }
    if (b0>b1) { q=b0; b0=b1; b1=q; }
    s.x=x; s.vx=0.0; s.ax=0.0;
    s.y=y; s.vy=0.0; s.ay=0.0;
    s.ia=ia; s.a0=a0; s.a1=a1;
    s.ib=-1; s.b0=b0; s.b1=b1;
    s.ic.num=0;
    if ((ib>=0)&&(ib<slider.num)) slider[ib].ib=slider.num;
    s._horizontal=_h;
    s.a=a0; // min
    if (s.a>a1) s.a=a1;
    if (s.a>b0) s.a=b0;
    if (s.a>b1) s.a=b1;
    s.b=a0; // max
    if (s.b<a1) s.b=a1;
    if (s.b<b0) s.b=b0;
    if (s.b<b1) s.b=b1;
    slider.add(s);
    return slider.num-1;
    }
//---------------------------------------------------------------------------
void sliders::slider_end()
    {
    int i,j;
    double a0,a1,b0,b1,x0,x1,w=_slider_gap;
    _slider *si,*sj;
    positions();
    // detect intersecting sliders and add them to propriet ic ignore list
    for (si=slider.dat,i=0;i<slider.num;i++,si++)
     for (sj=si+1   ,j=i+1;j<slider.num;j++,sj++)
      if (si->_horizontal!=sj->_horizontal)
        {
        if (si->_horizontal)
            {
            a0=si->X+si->a; a1=sj->X-w;
            b0=si->X+si->b; b1=sj->X+w;
            x0=si->Y;       x1=sj->Y;
            }
        else{
            a0=si->Y+si->a; a1=sj->Y-w;
            b0=si->Y+si->b; b1=sj->Y+w;
            x0=si->X;       x1=sj->X;
            }
        if (((a0<=b1)&&(b0>=a1))||((a1<=b0)&&(b1>=a0)))
         if ((x0>x1+sj->a-w)&&(x0<x1+sj->b+w))
            {
            si->ic.add(j);
            sj->ic.add(i);
            }
        }
    }
//---------------------------------------------------------------------------
bool sliders::constraints(int ix)
    {
    int i,j;
    double a0,a1,b0,b1,x0,x1,x,w=_slider_gap;
    _slider *si,*sj,*sa,*sb,*s;
    s=slider.dat+ix;
    // check parallel neighbors overlapp
    for (si=slider.dat,i=0;i<slider.num;i++,si++)
     if ((i!=ix)&&(si->_horizontal==s->_horizontal))
        {
        if (s->_horizontal)
            {
            a0=s->X+s->a; a1=si->X+si->a;
            b0=s->X+s->b; b1=si->X+si->b;
            x0=s->Y;      x1=si->Y;
            }
        else{
            a0=s->Y+s->a; a1=si->Y+si->a;
            b0=s->Y+s->b; b1=si->Y+si->b;
            x0=s->X;      x1=si->X;
            }
        if (((a0<=b1)&&(b0>=a1))||((a1<=b0)&&(b1>=a0)))
            {
            if ((i<ix)&&(x0<x1+w)) return true;
            if ((i>ix)&&(x0>x1-w)) return true;
            }
        }
    // check perpendicular neighbors overlapp
    for (si=slider.dat,i=0;i<slider.num;i++,si++)
     if ((i!=ix)&&(si->_horizontal!=s->_horizontal))
        {
        // skip ignored sliders for this
        for (j=0;j<s->ic.num;j++)
         if (s->ic[j]==i) { j=-1; break; }
          if (j<0) continue;
        if (s->_horizontal)
            {
            a0=s->X+s->a; a1=si->X-w;
            b0=s->X+s->b; b1=si->X+w;
            x0=s->Y;      x1=si->Y;
            }
        else{
            a0=s->Y+s->a; a1=si->Y-w;
            b0=s->Y+s->b; b1=si->Y+w;
            x0=s->X;      x1=si->X;
            }
        if (((a0<=b1)&&(b0>=a1))||((a1<=b0)&&(b1>=a0)))
         if ((x0>x1+si->a-w)&&(x0<x1+si->b+w))
          return true;
        }
    // conflict a anchor area of parent?
    if (s->ia>=0)
        {
        si=slider.dat+s->ia;
        if (s->_horizontal)
            {
            x0=si->Y+si->a0;
            x1=si->Y+si->a1;
            x=s->Y;
            }
        else{
            x0=si->X+si->a0;
            x1=si->X+si->a1;
            x=s->X;
            }
        if (x<x0+w) return true;
        if (x>x1-w) return true;
        }
    // conflict b anchor area of parent?
    if (s->ib>=0)
        {
        si=slider.dat+s->ib;
        if (si->_horizontal)
            {
            x0=si->X+si->b0;
            x1=si->X+si->b1;
            x=s->X;
            }
        else{
            x0=si->Y+si->b0;
            x1=si->Y+si->b1;
            x=s->Y;
            }
        if (x<x0+w) return true;
        if (x>x1-w) return true;
        }
    // conflict b anchor area with childs?
    for (si=slider.dat,i=0;i<slider.num;i++,si++)
     if ((i!=ix)&&(si->ib==ix))
        {
        if (s->_horizontal)
            {
            x0=s->X+s->b0;
            x1=s->X+s->b1;
            x=si->X;
            }
        else{
            x0=s->Y+s->b0;
            x1=s->Y+s->b1;
            x=si->Y;
            }
        if (x<x0+w) return true;
        if (x>x1-w) return true;
        }

    // check childs too
    for (si=slider.dat,i=0;i<slider.num;i++,si++)
     if ((i!=ix)&&(si->ia==ix))
      if (constraints(i)) return true;
    return false;
    }
//---------------------------------------------------------------------------
void sliders::positions()
    {
    int i,e;
    _slider *si,*sa;
    // set flag = uncomputed
    for (si=slider.dat,i=0;i<slider.num;i++,si++) si->flag=0;
    // iterate until all sliders are computed
    for (e=1;e;)
     for (e=0,si=slider.dat,i=0;i<slider.num;i++,si++)
      if (!si->flag)
        {
        // fixed
        if (si->ia<0)
            {
            si->X=si->x;
            si->Y=si->y;
            si->flag=1;
            continue;
            }
        // a anchored
        sa=slider.dat+si->ia;
        if (sa->flag)
            {
            si->X=sa->X+si->x;
            si->Y=sa->Y+si->y;
            si->flag=1;
            continue;
            }
        e=1; // not finished yet
        }
    }
//---------------------------------------------------------------------------
void sliders::update(double dt)
    {
    int i;
    _slider *si,*sa;
    double x,X;
    // D'Lamnbert integration
    for (si=slider.dat,i=0;i<slider.num;i++,si++)
     if (si->_horizontal)
        {
        x=si->y; si->vy+=si->ay*dt;     // vel = Integral(acc*dt)
                 si->vy*=_friction;     // friction k*vel
        X=si->Y; si->y +=si->vy*dt;     // pos = Integral(vel*dt)
        positions();                    // recompute childs
        if ((si->ia<0)||(constraints(i))) // if fixed or constraint hit (stop and restore original position)
            {
            si->vy=0.0;
            si->y =x;
            si->Y =X;
            positions();                // recompute childs
            }
        }
    else{
        x=si->x; si->vx+=si->ax*dt;     // vel = Integral(acc*dt)
                 si->vx*=_friction;     // friction k*vel
        X=si->X; si->x +=si->vx*dt;     // pos = Integral(vel*dt)
        positions();                    // recompute childs
        if ((si->ia<0)||(constraints(i))) // if fixed or constraint hit (stop and restore original position)
            {
            si->vx=0.0;
            si->x =x;
            si->X =X;
            positions();                // recompute childs
            }
        }
    }
//---------------------------------------------------------------------------
void sliders::solve(bool _init)
    {
    int i,j,k;
    double a0,a1,b0,b1,x0,x1;
    _slider *si,*sj,*sa;
    // init solution
    if (_init)
        {
        mode=0;
        charge=_charge;
        }
    // clear accelerations and compute actual max velocity
    vel_max=0.0;
    for (si=slider.dat,i=0;i<slider.num;i++,si++)
        {
        si->ax=0.0;
        si->ay=0.0;
        x0=fabs(si->vx); if (vel_max<x0) vel_max=x0;
        x0=fabs(si->vy); if (vel_max<x0) vel_max=x0;
        }
    // precision control of solver
    if ((mode==0)&&(vel_max>25.0)) { mode++; }                  // wait until speed raises
    if ((mode==1)&&(vel_max<10.0)) { mode++; charge*=0.10; }    // scale down forces to lower jitter
    if ((mode==2)&&(vel_max< 1.0)) { mode++; charge*=0.10; }    // scale down forces to lower jitter
    if ((mode==3)&&(vel_max< 0.1)) { mode++; charge =0.00; stop(); } // solution found
    // set x0 as 1D vector to closest parallel neighbor before and x1 after
    for (si=slider.dat,i=0;i<slider.num;i++,si++) { si->x0=0.0; si->x1=0.0; }
    for (si=slider.dat,i=0;i<slider.num;i++,si++)
     for (sj=si+1   ,j=i+1;j<slider.num;j++,sj++)
      if (si->_horizontal==sj->_horizontal)
        {
        // longer side interaction
        if (si->_horizontal)
            {
            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)<_slider_gap)||(fabs(si->x0)>fabs(x0)))) si->x0=-x0;
            if ((si->ia>=0)&&(x0>0.0)&&((fabs(si->x1)<_slider_gap)||(fabs(si->x1)>fabs(x0)))) si->x1=-x0;
            if ((sj->ia>=0)&&(x0<0.0)&&((fabs(sj->x0)<_slider_gap)||(fabs(sj->x0)>fabs(x0)))) sj->x0=+x0;
            if ((sj->ia>=0)&&(x0>0.0)&&((fabs(sj->x1)<_slider_gap)||(fabs(sj->x1)>fabs(x0)))) sj->x1=+x0;
            }
        // shorter side interaction
        if (si->_horizontal)
            {
            a0=si->Y-_slider_gap; a1=sj->Y+_slider_gap;
            b0=si->Y+_slider_gap; b1=sj->Y+_slider_gap;
            x0=si->X;             x1=sj->X;
            }
        else{
            a0=si->X-_slider_gap; a1=sj->X+_slider_gap;
            b0=si->X+_slider_gap; b1=sj->X+_slider_gap;
            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)
                {
                sa=slider.dat+si->ia;
                if ((sa->ia>=0)&&(x0<0.0)&&((fabs(sa->x0)<_slider_gap)||(fabs(sa->x0)>fabs(x0)))) sa->x0=-x0;
                if ((sa->ia>=0)&&(x0>0.0)&&((fabs(sa->x1)<_slider_gap)||(fabs(sa->x1)>fabs(x0)))) sa->x1=-x0;
                }
            if (sj->ia>=0)
                {
                sa=slider.dat+sj->ia;
                if ((sa->ia>=0)&&(x0<0.0)&&((fabs(sa->x0)<_slider_gap)||(fabs(sa->x0)>fabs(x0)))) sa->x0=+x0;
                if ((sa->ia>=0)&&(x0>0.0)&&((fabs(sa->x1)<_slider_gap)||(fabs(sa->x1)>fabs(x0)))) sa->x1=+x0;
                }
            }
        }
    // set x0 as 1D vector to closest perpendicular neighbor before and x1 after
    for (si=slider.dat,i=0;i<slider.num;i++,si++)
     for (sj=si+1   ,j=i+1;j<slider.num;j++,sj++)
      if (si->_horizontal!=sj->_horizontal)
        {
        // skip ignored sliders for this
        for (k=0;k<si->ic.num;k++)
         if (si->ic[k]==j) { k=-1; break; }
          if (k<0) continue;
        if (si->_horizontal)
            {
            a0=si->X+si->a; a1=sj->X-_slider_w;
            b0=si->X+si->b; b1=sj->X+_slider_w;
            x0=si->Y;
            }
        else{
            a0=si->Y+si->a; a1=sj->Y-_slider_w;
            b0=si->Y+si->b; b1=sj->Y+_slider_w;
            x0=si->X;
            }
        if (((a0<=b1)&&(b0>=a1))||((a1<=b0)&&(b1>=a0)))
            {
            if (si->_horizontal)
                {
                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)<_slider_gap)||(fabs(si->x0)>fabs(x0)))) si->x0=+x0;
            if ((si->ia>=0)&&(x0>0.0)&&((fabs(si->x1)<_slider_gap)||(fabs(si->x1)>fabs(x0)))) si->x1=+x0;
            if (sj->ia<0) continue;
            sa=slider.dat+sj->ia;
            if ((sa->ia>=0)&&(x0<0.0)&&((fabs(sa->x0)<_slider_gap)||(fabs(sa->x0)>fabs(x0)))) sa->x0=-x0;
            if ((sa->ia>=0)&&(x0>0.0)&&((fabs(sa->x1)<_slider_gap)||(fabs(sa->x1)>fabs(x0)))) sa->x1=-x0;
            }
        }
    // convert x0,x1 distances to acceleration
    for (si=slider.dat,i=0;i<slider.num;i++,si++)
        {
        // driving force F = ~ Q / r^2
        if (fabs(si->x0)>1e-10)  x0=charge/(si->x0*si->x0); else x0=0.0; if (si->x0<0.0) x0=-x0;
        if (fabs(si->x1)>1e-10)  x1=charge/(si->x1*si->x1); else x1=0.0; if (si->x1<0.0) x1=-x1;
        a0=x0+x1;
        // limit acc
        if (a0<-_acc_limit) a0=-_acc_limit;
        if (a0>+_acc_limit) a0=+_acc_limit;
        // store parallel acc to correct axis
        if (si->_horizontal) si->ay=a0;
         else                si->ax=a0;
        // limit vel (+/- one iteration overlap)
        if (si->_horizontal) x0=si->vy;
         else                x0=si->vx;
        if (x0<-_vel_limit)  x0=-_vel_limit;
        if (x0>+_vel_limit)  x0=+_vel_limit;
        if (si->_horizontal) si->vy=x0;
         else                si->vx=x0;
        }
    }
//---------------------------------------------------------------------------
void sliders::stop()
    {
    int i;
    _slider *si;
    for (si=slider.dat,i=0;i<slider.num;i++,si++)
        {
        si->vx=0.0;
        si->vy=0.0;
        si->ax=0.0;
        si->ay=0.0;
        }
    }
//---------------------------------------------------------------------------
void sliders::mouse(int x,int y,TShiftState sh)
    {
    int i,q0,q1;
    double d,dd;
    _slider *si;
    // update mouse state
    mx0=mx1; my0=my1; sh0=sh1;
    mx1=x;   my1=y;   sh1=sh;
    // slider movement with left mouse button
    q0=sh0.Contains(ssLeft);
    q1=sh1.Contains(ssLeft);
    if ((sel>=0)&&(q1))
        {
        si=slider.dat+sel;
        // stop simulation for selected slider
        si->vx=0.0;
        si->vy=0.0;
        si->ax=0.0;
        si->ay=0.0;
        // use mouse position instead
        if (si->ia>=0)
            {
            if (si->_horizontal){ d=si->y; dd=si->Y; si->y+=my1-si->Y; si->Y=my1; si->vy=0.0; si->ay=0.0; positions(); if (constraints(sel)) { si->y=d; si->Y=dd; positions(); }}
             else               { d=si->x; dd=si->X; si->x+=mx1-si->X; si->X=mx1; si->vx=0.0; si->ax=0.0; positions(); if (constraints(sel)) { si->x=d; si->X=dd; positions(); }}
            }
        }
    // select slider (if not left mouse button used)
    if (!q1)
     for (sel=-1,d=_slider_w+1.0,si=slider.dat,i=0;i<slider.num;i++,si++)
        {
        dd=_slider_w+1.0;
        if (si->_horizontal){ if ((mx1>=si->X+si->a)&&(mx1<=si->X+si->b)) dd=fabs(my1-si->Y); }
         else               { if ((my1>=si->Y+si->a)&&(my1<=si->Y+si->b)) dd=fabs(mx1-si->X); }
        if ((dd<d)&&(dd<=_slider_w)) { sel=i; d=dd; }
        }
    }
//---------------------------------------------------------------------------
void sliders::draw(TCanvas *scr)
    {
    int i,j,n;
    double w=_slider_w,r,x,y,a0,a1;
    AnsiString txt;
    _slider *s;
    scr->Brush->Style=bsClear;
    #define _line(aa,bb)           \
    if (s->_horizontal)            \
        {                          \
        scr->MoveTo(s->X+aa,s->Y); \
        scr->LineTo(s->X+bb,s->Y); \
        }                          \
    else{                          \
        scr->MoveTo(s->X,s->Y+aa); \
        scr->LineTo(s->X,s->Y+bb); \
        }
    scr->Pen->Color=clSilver;
    scr->Font->Color=clWhite;
    scr->TextOutA(40,40,AnsiString().sprintf("mode %i",mode));
    scr->TextOutA(40,60,AnsiString().sprintf("vel: %.3lf [px/s]",vel_max));
    scr->TextOutA(40,80,AnsiString().sprintf("  Q: %.3lf [px^3/s^2]",charge));
    scr->Font->Color=clYellow;
    for (s=slider.dat,i=0;i<slider.num;i++,s++)
        {
        if (s->_horizontal) scr->Pen->Color=clSilver;
         else               scr->Pen->Color=clAqua;
        if (i==sel)
            {
            scr->Pen->Color=clYellow;
            txt=AnsiString().sprintf(" ix:%i ia:%i ib:%i ic:",sel,s->ia,s->ib);
            for (j=0;j<=s->ic.num;j++) txt+=AnsiString().sprintf(" %i",s->ic[j]);
            scr->TextOutA(40,100,txt);
            scr->TextOutA(40,120,AnsiString().sprintf("pos: %.1lf %.1lf [px]",s->X,s->Y));
            scr->TextOutA(40,140,AnsiString().sprintf("vel: %.3lf %.3lf [px/s]",s->vx,s->vy));
            scr->TextOutA(40,160,AnsiString().sprintf("acc: %.3lf %.3lf [px/s^2]",s->ax,s->ay));
            scr->Pen->Color=clYellow;
            }
        if (s->ia<0) scr->Pen->Style=psDash;
         else        scr->Pen->Style=psSolid;
        // a anchor loop
        x=s->X;
        y=s->Y;
        if (s->ia>=0) scr->Ellipse(x-w,y-w,x+w,y+w);
        // b anchor loop
        r=0.5*fabs(s->b1-s->b0);
        if (s->_horizontal)
            {
            x=s->X+0.5*(s->b0+s->b1);
            y=s->Y;
            scr->RoundRect(x-r,y-w,x+r,y+w,w,w);
            }
        else{
            x=s->X;
            y=s->Y+0.5*(s->b0+s->b1);
            scr->RoundRect(x-w,y-r,x+w,y+r,w,w);
            }
        // a line cutted by a anchor loop
        a0=s->a0; a1=s->a1;
        if ((s->ia>=0)&&(a0<=+w)&&(a1>=-w))
            {
            if (a0<-w) _line(s->a0,-w);
            if (a1>+w) _line( w,s->a1);
            }
        else _line(s->a0,s->a1);
        }
    scr->Font->Color=clDkGray;
    scr->Pen->Style=psSolid;
    scr->Brush->Style=bsSolid;
    #undef _line
    }
//---------------------------------------------------------------------------
#endif
//---------------------------------------------------------------------------

你可以忽略VCL部分，它只是与我的应用程序窗口和渲染进行交互的API。求解器本身不需要任何东西。我使用了动态线性数组模板List<T>，因此这里有一些解释：

• List<double> xxx;与double xxx[];相同
• xxx.add(5);将5添加到列表末尾
• xxx[7]访问数组元素（安全）
• xxx.dat[7]访问数组元素（不安全但直接访问速度快）
• xxx.num是数组的实际使用大小
• xxx.reset()清除数组并设置xxx.num=0
• xxx.allocate(100)预分配空间以容纳100个项目

在从bullet #3正确初始化后，使用方法很简单：

sys.solve(true);
for (;;)
 {
 sys.solve();
 sys.update(0.040); // just time step
 if (sys.mode==4) break; // stop if solution found or stuck
 }

我使用定时器调用此方法并重新绘制窗口，以便看到动画，而不是使用for循环：

卡顿是由于非统一的GIF采样率（不规则地跳过仿真中的一些帧）造成的。

您可以修改常量vel,acc极限、阻尼系数和模式控制if来改变行为。如果还实现了鼠标处理程序，那么您可以用左键移动滑块，这样就可以摆脱一些困境...

这里有一个独立的Win32演示（使用BDS2006 C++编译）。

• 演示 点击大洋红色按钮下面的“慢速下载”，输入4位字母数字代码开始下载，无需注册。

关于求解器力计算的更多信息，请参见相关/后续QA：

• 受限矩形形状的力定向布局

- Spektre

---

@deblocker 更新了答案，修复了缺少短边平行交互的问题，并且还忘记在垂直交互中注释掉几行代码。现在它的表现符合预期...至少在我看来是这样。希望我没有删除不该删除的内容，因为我达到了答案大小限制，被迫从源代码中直接删除了调试绘图部分。 - Spektre

@Spektre：这是您工作的JavaScript翻译：静电二维求解器。它运行得很好，但可悲的是，我不能等待x秒钟来知道结构的最终位置 :-( - deblocker

@deblocker，每次迭代只需要几微秒，因此您可以在毫秒内模拟几秒钟。只需不要等待计时器或渲染即可...您还可以通过调整常量来增加解决速度... - Spektre

你需要调整电荷、摩擦和速度限制。首先，在不改变电荷的情况下，你可以看到它的表现如何以及设置什么速度条件。电荷越大，速度越快，但你需要限制速度，以免影响其他因素，并在足够小的距离上减速... 你可以为每个“模式”使用不同的限制，而不仅仅是改变电荷，这需要详细阐述... - Spektre

如果你的最终准确度是整数，那么你可以比我更早停止。 - Spektre