I have a set of metallic sliding pieces which are constrained to the x and y axis in following way:
I would need to maximize the horizontal distance among all pieces constrained by the same slider and the vertical distance among the sliding pieces and the sliders itself. How can this be solved?
Any advice and suggestion which can lead to a solution for this problem would be greatly appreciated.
I looked first at some very powerful libraries like cassowary and jsLPSolver but i had some trouble to understand the core algorithm and how the constraint are checked for feasibility and how the possible solutions are then ranked.
How could be implemented in JavaScript a (simple) stub for a 2-D geometric constraint solver for problems like this one above?
EDIT:
I have following input data:
maxW = 300, maxH = 320
The pieces are defined as follows (not mandatory, every solution is accepted):
slidingPiece = [pX, pY, width, height, anchorPoint, loopDistance];
I will try to explain what i mean under "maximize".
Horizontal spacing:
a0-b1, b1-b2, b2-b4, b4-b5 and b5-maxX will be the same, i.e. max X divided by the greatest number of vertical intersecting pieces + 1 (5). b1-b3 and b3-b5 will be then determined by the available remaining space.
Vertical spacing:
b1-a3, a3-a4 and a0-b5 will be the same. Ideally, a0-b3,b3-b4,a2-b2,b4-a3 and b2-a4 will be also the same value. Maximizing a1-b4 and b3-a2 is the same as maximizing b3-b4. The same applies to a2-b2 and b4-a3: the distance b2-b4 will be then the max negative value.
So, i need to maximize the distance among every sliding piece and his nearest above or below Y-constraint.
The 2-D geometric representation of this problem shows that the horizontal spacing depends from the vertical distance of the anchors (due to the vertical intersection of the anchored pieces), which in turn depends from the horizontal position of the pieces itself. Think for example, b2 is somewhat shorter above. In this case, b1 and b2 are no longer intersecting and would became the same x value, i.e. max X divided by 4.
In some other cases, for example b2 is much longer in the above part - and will cross the anchor a2, then it shall be spaced to a1. This is the reason because there will be a set of solutions, some feasible and some other not, because for example, the global max Y constraint would be broken.
I would try field approach similar to this.
Each slider will retract all sliders away
with force scaled by distance^2 like all of them would have the same polarity electric charge or springs attached in between each other.
On top of that add friction scaled by speed
does not really matter if air
v^2
or liquidv^3
implement kinematic constraints
for horizontal and vertical only sliding it should be really easy.
Do physical simulation and wait until it converges to stable state
v=~0
if hit local min/max shake the whole thing a bit or arrange the whole thing randomly and try again. You can do this also to get another solution.
[Edit4] C++ solver example
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.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.
implement initial setup
Where
ia
is parent index andib
is child index (the slider class itself holdsib
as parent but that would be confusing to init as you would need to link to item that do not exist yet so theib
transformation is handled in thesys.add
function).sys
is class holding the whole thing andsys.add
just add new slider to it and returns its index counting from zero. Thex,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.
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...
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.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.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.
Here The full C++/VCL class code for this:
You can ignore the VCL stuff it is just API for interaction with my App window and rendering. The solver itself does not need anything from it. I used my dynamic linear array template
List<T>
so here few explanations:List<double> xxx;
is the same asdouble xxx[];
xxx.add(5);
adds5
to end of the listxxx[7]
access array element (safe)xxx.dat[7]
access array element (unsafe but fast direct access)xxx.num
is the actual used size of the arrayxxx.reset()
clears the array and setxxx.num=0
xxx.allocate(100)
preallocate space for100
itemsUsage is simple after proper init from bullet #3 like this:
Instead of for cycle I call this in timer and redraw the window so I see the animation:
The choppyness is due to non uniform GIF grabbing sample rate (skipping some frames from the simulation irregularly).
You can play with the constants for
vel,acc
limits, dampening coefficient and the mode controlif
s to change the behavior. If you implement also mouse handler then you can move the sliders with left mouse button so you can get out of stuck cases...Here stand alone Win32 demo (compiled with BDS2006 C++).
For more info about how the solver Force computation works see related/followup QA: