add forceExtent

[Fil]

fixes #89

note that the extent's definition in this PR is [[xmin, ymin], [xmax, ymax]], more in line with, for example zoom.extent. Defaults to [[0,0], [960,500]].

by @gka

[Fil]

oops @john-guerra I realize this duplicates https://github.com/d3/d3-force/pull/115 in some (simpler) way.

[john-guerra]

Seems to me that this pull request establishes hard boundary, which is undesired as you will get node overlapping. #115 uses forces instead, which should work better. This notebook showcases it https://observablehq.com/@john-guerra/d3-force-boundary

[john-guerra]

Here is a comparison #163 https://observablehq.com/d/606866e6c1db4809 #115 https://observablehq.com/@john-guerra/d3-forceboundary

[vasturiano]

Just in case there is interest in a solution that includes bouncing off the container walls, there is https://github.com/vasturiano/d3-force-surface

[john-guerra]

Thank you for ruining my "productivity" with you awesome game of pong!!!! 👏

[Fil]

Sorry I went really too fast on this issue. I've now made a test bed with the three forces here: https://observablehq.com/d/21d2053b3bc85bce Unfortunately in this specific situation (in particular, there is no forceCollide), as you progressively shrink the box, I don't think anything works really well :(

[john-guerra]

Randomizing positions every time we move the slider might be the issue, here it is keeping node positions https://observablehq.com/d/7acdd31a46c120be

Seems to me (and my bias) that forceBoundary does the better job

[Fil]

Agree with you that forceBoundary is currently the best (or "least worst") in this playground, but for me it's still not "good enough" in the sense that the nodes end up all on top of each other on the boundary (as they do with that version of "forceExtent"). I tend to think we need more research if we want something simple and solid for the core of d3-force. But it's surprisingly hard!

[john-guerra]

If you set the strength of force boundary to a high value then you can overpower the other forces

https://observablehq.com/d/7acdd31a46c120be

[Fil]

Sure, but in that case it's not a "boundary" force anymore—it becomes more like a central gravitation. What would be the ideal force to contain a simulation in a box? It should behave properly (no jumps etc), it should not let points get out of the box, and I believe it should not impact points if they're not near the boundary (or near points that are near the boundary). Current state of the art to achieve this with D3 seems to be a mix of forceBoundary + forceCollide, why not—but d3-force is the only module where you have to do so much tweaking and tuning to get things looking right. And you have to do it again each time you change the data.

[vasturiano]

There is another possibility which is to have a force that forces (excuse the pun) the nodes inside the container by manipulating the nodes positions instead of just the velocities. This is semi unusual in forces but is perhaps appropriate here. forceCenter does that too by the way. It also may be the only way to guarantee that a node does not escape the container.

I've just made one that hard limits the nodes positions to specified range. It also slows down nodes if it predicts they will land outside the range in the following iteration, so it applies the restriction proactively. https://github.com/vasturiano/d3-force-limit

It also allows for setting restrictions in just one dimension, and also setting different ranges for different nodes, via accessor functions. That may be overkill for the specific case of container walls, but maybe useful in other scenarios in which you want certain nodes to cross some boundaries.

@fil I've added a suggestion on your notebook that adds forceLimit to compare the behaviour.

[john-guerra]

I think I'm closer to @mbostock's answer to this question https://stackoverflow.com/questions/9573178/d3-force-directed-layout-with-bounding-box I do think that nodes should be allowed to exit the boundary, for instance when users drag them.

With forceBoundary you can also define what is the distance to the border in which the force will come in effect. That will address @Fil desire of

I believe it should not impact points if they're not near the boundary (or near points that are near the boundary

I need to look more into @vasturiano's approach, but I have found weird results in the pasts changing the node positions instead of their velocities. Having said that, the bouncing nodes demos look amazing. Seems like a really good solution when what you want is a wall that cannot be crossed by any means. It force limit works extremely well as a wall in https://observablehq.com/d/21d2053b3bc85bce

In my use cases what I have usually wanted is a force that tries to keep my nodes visible inside my drawing canvas. I don't mind if they have to leave for a moment, as long as they try to return. And I don't want nodes to stay in the limit of the canvas as that generates overlapping

[vasturiano]

As an attempt to address the issue of nodes gathering on the container's edge I've added an enhancement that lets you specify a soft repelling force away from the edges, with configurable intensity. This acts only within a certain margin of proximity of the boundary and the intensity decays linearly with the distance within this margin. A bit like having a cushioning effect.

I've put together a demo here: https://observablehq.com/@vasturiano/d3-force-limit

I don't know if it's perfect, but it does handles the limit a bit more gracefully.

This really feels like a more challenging problem than it appears initially, but it's such a common use case that it's important to get just right. 😃

[Fil]

I've added a collision force in the test notebook, making sure the constraint force was coming in last (a requirement for d3-force-limit because it's using look-ahead). I think it works very well—I'm adding a few suggestions at https://github.com/vasturiano/d3-force-limit/issues/1

PS: It's a bit strange that this discussion happens on this failed PR—but hey, it's so good to see the progress!

[Fil]

And now forceWalls appeared in https://observablehq.com/d/21d2053b3bc85bce ; I think we're getting a bit closer with each step (as suits a force simulation).

[john-guerra]

... This acts only within a certain margin of proximity of the boundary and the intensity decays linearly with the distance within this margin. A bit like having a cushioning effect.

Forcebounday also features a similar effect, https://www.npmjs.com/package/d3-force-boundary#boundary_border

But seems like my implementation draws nodes to the center whereas @vasturiano's drive them perpendicularly out of the border. I looks good in the observable. Not sure if it was intentional, but changed the left cushion from 0 to 10 in https://observablehq.com/d/21d2053b3bc85bce

[Fil]

Not sure if it was intentional

yes it was to show the cushion's "impact" ( can a cushion have an impact? :) )—but it's ugly.

[Fil]

here's a new iteration of forceWalls, with a simpler API : https://observablehq.com/d/66b419d51abee995

[vasturiano]

I like that api schema a lot. The way you can specify a complex polygon like an ellipse using a set of hyperplane walls is extremely cool.

Actually, it gave me another idea. What if we'd be able to specify a wall as an x => y function in addition to the hyperplane fashion. Something like:

.walls([{ y: 30 }, x => (x + 3)**2])

Then we could have curved walls without having to quantize them out of multiple planes.

[Fil]

I've taken another route completely and came up with a solution using a Sliced Optimal Transport approach.

Test forceTransport at https://observablehq.com/d/21d2053b3bc85bce

The gist of the algorithm is:

1. sort all the nodes on x, send the first towards x=0, the second towards x = width/(n-1), etc all the way up to x=width for the last point.
2. sort all the nodes on y, send the first towards y=0, the second towards y = height/(n-1), etc all the way up to y=height for the last point.

The first part is an OT on the x direction (or "slice"), and the second an OT in the y direction. (We could separate them into transportX and transportY if we wanted, like forceX and forceY.)

We can put up a similar piece of code to do the same for a disk (or an ellipse), by slicing the data on the angle (atan) and radius^2 dimensions—it's a bit less stable but results in a nice "fill a disk" force.

[Fil]

I've now found a way to properly transport to a disk

[john-guerra]

Hi Fil! At first glance, this looks really cool, I'm moving between countries right now, so i expect to check it by the end of the week

John. From my phone, brevity and all http://johnguerra.co

On Sat, Nov 7, 2020, 10:50 AM Philippe Rivière [email protected] wrote:

I've taken another route completely and came up with a solution using a Sliced Optimal Transport approach.

Test forceTransport at https://observablehq.com/d/21d2053b3bc85bce

The gist of the algorithm is:

1. sort all the nodes on x, send the first towards x=0, the second towards x = width/(n-1), etc all the way up to x=width for the last point.
2. sort all the nodes on y, send the first towards y=0, the second towards y = height/(n-1), etc all the way up to y=height for the last point.

The first part is an OT on the x direction (or "slice"), and the second an OT in the y direction. (We could separate them into transportX and transportY if we wanted, like forceX and forceY.)

We can put up a similar piece of code to do the same for a disk (or an ellipse), by slicing the data on the angle (atan) and radius^2 dimensions—it's a bit less stable but results in a nice "fill a disk" force.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/d3/d3-force/pull/163#issuecomment-723461723, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAJJCS4HV4UC7RZP7YOUKEDSOVUFBANCNFSM4OIQZQKA .

[john-guerra]

This looks really cool @Fil, would love to be able to use it as a part of d3 or as a module. Please let me know if I can help in any way

[Fil]

You can definitely play with the algorithm and see what it does (and doesn't). I don't think it's ready at all for being a module.

[john-guerra]

Ahhhh I forgot that I could test it simply importing from your notebook 😁🤷🏼‍♂️

Here is a test with a sparse network from one of my student's work

https://observablehq.com/d/a98827b7f86dd773

Force transport only cares to move the points if they are beyond the extent, right? That can be positive as it allows for better combination with other forces...

On Tue, Apr 20, 2021 at 12:53 PM Philippe Rivière @.***> wrote:

You can definitely play with the algorithm and see what it does (and doesn't). I don't think it's ready at all for being a module.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/d3/d3-force/pull/163#issuecomment-823558337, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAJJCS4YSCLYOYX7D66QO7DTJXLS7ANCNFSM4OIQZQKA .

--

John Alexis Guerra Gómez https://johnguerra.co

[Fil]

To get a better intuition of the sliced OT algorithm, suppose we are on a unique dimension x. The points are ordered according to their x: 0-1----------2-3-4----5--6-------7

now we want this to be more balanced we'll move them according to their position (x) relative to their expected position (i/n): →0-→1---2←---3←--4-----→5--→6---7←

repeat the procedure on the vertical axis, and you get the rectangular forceTransport.

To get to the disc transport you need to apply this procedure along a "rotating" direction, and the delicate part is in the choice of angles (number and distribution), because taking 1 random direction at each step makes the movement very unstable.

[john-guerra]

Very cool Philippe, thanks for explaining!

On Tue, Apr 20, 2021 at 11:18 PM Philippe Rivière @.***> wrote:

To get a better intuition of the sliced OT algorithm, suppose we are on a unique dimension x. The points are ordered according to their x: 0-1----------2-3-4----5--6-------7

now we want this to be more balanced we'll move them according to their position (x) relative to their expected position (i/n): →0-→1---2←---3←--4-----→5--→6---7←

repeat the procedure on the vertical axis, and you get the rectangular forceTransport.

To get to the disc transport @.***/disc-transport> you need to apply this procedure along a "rotating" direction, and the delicate part is in the choice of angles (number and distribution), because taking 1 random direction at each step makes the movement very unstable.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/d3/d3-force/pull/163#issuecomment-823807686, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAJJCS75X265VXVPFJJ4UTDTJZU47ANCNFSM4OIQZQKA .

--

John Alexis Guerra Gómez https://johnguerra.co