## JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

HermannSW
Posts: 5307
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

I did big cleanup and simplify of "doit()" code, that does determine vertex coordinates of one side vertices of separating circle (orange edges).
And added 2nd parameter for "vtxt()" OpenSCAD module, allowing to not only label vertices with their vertex number.
Finally I added new option "-10" that does determine "vtype" for each vertex when selected (sides 1 and 2, and 0 indicating vertices on separating circle):
(this big diff is best viewed with github split mode)
https://github.com/Hermann-SW/planar_gr ... cf0decc0c8

Code: Select all

``./rjs node.tetra.js graphs/C60.a white.70 -10``
C60.vtype.png
C60.vtype.png (82.52 KiB) Viewed 1009 times
vtype=1 vertices have horizontal angles in 0°..270° range, vtype=2 vertices in 180°..450° range.

The reason for cleanup work was clear.
Adding new "vtype" related option is preparation for next step.
I had no success with single vertex change spring embedders.
Success happened when solving system of linear equations for determining vertex coordinates.

After vertex coordinates have been determined, for vertices of vtype 1 and 2, I will call "tutte.convex_face_coordinates()" again, but this time I will not pass the vertices on separating circle as fixed coordinates, but the vertices of vtype 1 and 2. That will determine new coordinates for vtype=0 vertices (on separating circle), by calling "tutte.convex_face_coordinates()" once. Inspecting the difference then will show whether repeated determination of vtype=1 and vtype=2 vertices, and then of vtype=0 vertices might approach "better" and "better" spring embeddings or not (whatever "better" will be) ...

P.S:
"better" might be more "regular" spring embedding for C60 like football:
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

HermannSW
Posts: 5307
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Two more changes for option "-10":
https://github.com/Hermann-SW/planar_gr ... b63ca53b98
1. show spherical (gray) pentagons
2. show vertices of separating circle (vtype=0) full, vtype 1 or 2 vertices half

(2) makes it easier to spot (changes of) most part of separating circle, even on backside through transparent white sphere surface:

Code: Select all

``./rjs node.tetra.js graphs/C60.a white.70 -10``
C60.vtype.half0.png
C60.vtype.half0.png (80.97 KiB) Viewed 941 times
You can see all 4 red (full) vertices in this view:
• middle
• bottom back near z=10 label
• back near middle between x=-10 and y=10 label
• back right near x=10 label (outside of this screenshot)

(1) for easier comparison of C60 sphere spring embedding to football (black pentagons):
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

HermannSW
Posts: 5307
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

I stumbled over OpenJsCad again, and it looked promising, but I was not able to get it working in browser.
Then I found joostn's working github.io repo:

I forked his deprecated OpenJsCad repo and revived his github.io version in it:

I stripped down index.html to only viewer ...
... showing stored .jscad file only:

Code: Select all

``````<textarea id="code" hidden>
function main() {
var sphere = CSG.sphere({
center: [0, 0, 0],
resolution: 32
});
return sphere.union([sphere.translate([0,0,10]),
sphere.translate([0,10,0]),
sphere.translate([10,0,0])]);
}</textarea>``````
only_viewer.html.png
only_viewer.html.png (25.68 KiB) Viewed 775 times

This only works if opening the .html files locally in browser, otherwise publish on github.io would be needed.

Next steps will be to see, whether this working old deprecated version of OpenJsCad allows to create same output I created with OpenSCAD above:

P.S:
https://openjscad.xyz/ does not work for me, providing valid .jscad input and pressing SHIFT+ENTER to compile results in "processing,", "waiting" and then nothing.
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

HermannSW
Posts: 5307
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

TIL how to use the current github repo correctly, so no need to use my fork at least now:

"git clone" the repo, then cd into packages/web, finally start webserver in that directory:

Code: Select all

``python -m http.server 8000``
Then open this URL:
http://127.0.0.1:8000/demo.html

I don't know how to load files yet, but I copied this example
into editor opening when clicking on 2nd button from top right.

Pressing "SHIFT+ENTER" compiles and shows result:
jscad.local_webserver.jpg (89.93 KiB) Viewed 683 times

The examples have different syntax than the very old version with CSG prefixes.
I stripped down the example above to just a single roundedCylinder that got required:

Code: Select all

``````const { circle, cuboid, roundedCuboid, roundedCylinder, roundedRectangle } = require('@jscad/modeling').primitives
const { rotateX, rotateY, scale, translate } = require('@jscad/modeling').transforms
const { subtract, union } = require('@jscad/modeling').booleans
const { extrudeLinear } = require('@jscad/modeling').extrusions
const { measureBoundingBox } = require('@jscad/modeling').measurements

function main() {
return roundedCylinder({ height: 12, radius: 3, roundRadius: 1, segments: 18 })
}
module.exports = { main }``````
You can see the result online by clicking on this (share) URL:

[I really like share links, built them into my GraphvizFiddle as well, 2225 bytes long sample URL here]

The feature I really really have to find out is how to zoom in and out, without a mouse with wheel ...

P.S:
Clicking on help button top right leads to User Guide, API Reference, forums, ...:

P.P.S:
Just learned how to zoom without mouse wheel on the laptop I have with me:
The view can be rotated, zoomed in or out, and moved by using the mouse buttons. (Or fingers if using a tablet or mobile phone.)
I remembered that my laptop has a touch display (I never used that) and zooming with 2 fingers works as it does on smartphone.
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

HermannSW
Posts: 5307
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

I tried to build the basic constructs for planar graph sphere embedding.
"vertex()" was easy (JSCAD does work on radians, unlike OpenSCAD which works on degrees):

Code: Select all

``````function map_3D(c,sc) {
}
...
function vertex(_v, c, half=false) {
p = coords[_v]
v = map_3D(p,sc)
return colorize(c, sphere({radius: 0.5, center: v}))
}``````
and as next step I implemented "edge()" as well, as step before "edge2()" great circle arc (round) edges:

Code: Select all

``````function edge(_v,_w) {
v = map_3D(coords[_v],sc)
w = map_3D(coords[_w],sc)
d = [0,0,0]
x = [0,0,0]
subtract(d,w,v)
scale(w,x,0.5)
return colorize([0,0,1,1],
translate(w,
rotate([0,Math.acos(d[2]/length(d)),Math.atan2(d[1],d[0])],
cylinder({ radius: 0.1, height: length(d)}))))
}``````

Unlike OpenSCAD, JSCAD alpha values less than 1 do change appearance, but stuff behind does not shine through. Also the spheres look different:
JSCAD.vertex_edge.js.png (104.47 KiB) Viewed 601 times

Here you can inspect
https://stamm-wilbrandt.de/en/forum/JSC ... ex_edge.js

P.S:
I hope to add a 3D toggle to planar graph playground in browser soon ...
https://hermann-sw.github.io/planar_graph_playground/

P.P.S:
The question is, whether JSCAD will be performant enough to present gray spherical polygons (lots of triangles, complex) as here in bowser, with acceptable rotation refreshes:
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

HermannSW
Posts: 5307
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

One step further, "edge2()" (great circle arc) rounded edges now work in JSCAD as well:
JSCAD.vertex_edge2.js.png (67.28 KiB) Viewed 521 times

Hand edited file for C20 fullerene embedding onto sphere:
https://stamm-wilbrandt.de/en/forum/JSC ... x_edge2.js

You can view, zoom, rotate live in your browser:

Porting "edge2()" from OpenSCAD to JSCAD was not that difficult, besides a bit of juggling with degree/radian angles the same spherical calculations ...

Code: Select all

``````function edge2(_p1,_p2,_e) {
p1 = coords[_p1]
p2 = coords[_p2]
// al/la/ph: alpha/lambda/phi | lxy/sxy: delta lambda_xy/sigma_xy
l12 = la2 - la1
ph1 = degToRad(90 - p1[1])
ph2 = degToRad(90 - p2[1])
al1 = Math.atan2(Math.cos(ph2)*Math.sin(l12), Math.cos(ph1)*Math.sin(ph2)-Math.sin(ph1)*Math.cos(ph2)*Math.cos(l12))
// delta sigma_12
// https://en.wikipedia.org/wiki/Great-circle_distance#Formulae
s12 = Math.acos(Math.sin(ph1)*Math.sin(ph2)+Math.cos(ph1)*Math.cos(ph2)*Math.cos(l12))``````
... and then the JSCAD way of concatenating rotations, extrudeRotate(), ...:

Code: Select all

``````    return rotate([0,0,la1],
rotate([0,-ph1,0],
extrudeRotate({segments: 32, angle: s12},
}``````

Next step (JSCAD spherical triangle and spherical polygon) will decide whether the effort sofar was worth it, or whether it becomes too slow for browser ...
viewtopic.php?t=333342&start=50#p2023738
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

HermannSW
Posts: 5307
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

I learned how to use JSCAD params and added look_inside boolean toggle, that allows to "look inside" the white sphere:
https://stamm-wilbrandt.de/en/forum/JSC ... .params.js
x.anim.gif
x.anim.gif (101.45 KiB) Viewed 471 times
The inside vertex sphere halves can be seen only because now sphere with radius reduced by 0.1 got subtracted:

Code: Select all

``````...
,colorize([1,1,1,1],
subtract(
sphere({radius: sc, segments: params.wsegments})
,sphere({radius: sc-0.1, segments: params.wsegments})
,cube({size: params.look_inside?sc:0.01, center: [sc/2,-sc/2,sc/2]})
)
)
...``````

First I used 180 segments as I did with generating OpenSCAD, but that took way to loooong. After reducing to 30 segments the response was OK. 2nd param white_segments allows to play with view and response time, eg. 2 seconds in Chrome developer tools console for 30 segments:

Code: Select all

``total time for design regeneration 2009 13``
You can play live with new JSCAD.vertex_edge2.params.js in browser:
If enabling "Instant Update", any change of a param updates the view.

Now that I learned about JSCAD "subtract()" ("difference()" in OpenSCAD) #segments time issues, it will be interesting whether when doing "subtract()" for a spherical triangle with convex hull of 6 points, JSCAD design regeneration performance will suffer or not ...
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

HermannSW
Posts: 5307
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Made progress with porting sphere embedding OpenSCAD modules to JSCAD, now spherical triangle and spherical polygon work as well in JSCAD. Design regeneration time (can be seen in browser console) for C20 with one gray pentagon is below 3 seconds (on Intel i7 Linux Chrome, will test with 64bit Raspberry Pi OS in 2 weeks). Details in this posting:
JSCAD.spherical_polygon.js.png (98.57 KiB) Viewed 267 times

Clicking on "Enable Auoto-zoom" and "Enable Auto-rotate" results in nice animation ...
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

HermannSW
Posts: 5307
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Done with porting "vtxt()" and "half=true" for "vertex()" optional 3rd argument, details in this posting:

Link for browser view:
JSCAD.vertex_half.js.png (65.71 KiB) Viewed 188 times
Next step is to enable "node.tetra.js" to output either OpenSCAD (x.scad), or JSCAD (scad.js) output.
For JSCAD output, openjscad.xyz does not allow for "data:" scheme URIs:
So open either local webserver demo.html (eg. "http://127.0.0.1:8000/demo.html") or "https://openjscad.xyz" in browser, click on edit symbol top right and copy in the file you are working on. Then press CTRL+ENTER for refreshing view and continue working on changes.
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

HermannSW
Posts: 5307
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

For evaluation whether 12 gray pentagons of a fullerene (12*3*2=72 "sp_tria2()" calls, and 12 "subtract()"s with 6 point "hull()"s) has acceptable performance with JSCAD in browser, I enhanced JSCAD file a lot, with many added parameters:

You can directly play with it clicking here:

I first open Chrome browser console, then tick "Enable Auto-zoom" and "Instant Update", and finally deselect "no pentagons". This is the result:
JSCAD.C20_params.js.png (111.4 KiB) Viewed 126 times
Because "look_inside" is selected, 3 of the 12 pentagons do not show the gray spherical pentagons. On Intel i7 design regeneration takes less than 5 seconds only.

Next, deselecting "surface of sphere" results in view without white sphere surface:
JSCAD.C20_params.js.2.png (97.47 KiB) Viewed 126 times
Here you can see the inner spherical pentagons, which are hidden by white sphere normally.

Finally deselecting "look_inside" shows all 12 gray pentagons, with still less than 5 seconds of design regeneration:
JSCAD.C20_params.js.3.png (94.53 KiB) Viewed 126 times

This all works now because of carefully chosen values for gray_points (24) and gray segments (30). With current code the previous values of (40/40) for both from OpenSCAD mean 82/40 for gray points/segments. With those values design regeneration is in 25 seconds area.

Since all fullerenes have exactly 12 pentagons, JSCAD output is useful for performant browser view (will have to test with 64bit Raspberry Pi OS when back home). After design regeneration, rotation in browser is super fast.
https://hermann-sw.github.io/planar_graph_playground
https://stamm-wilbrandt.de/en#raspcatbt
https://github.com/Hermann-SW/memrun
https://github.com/Hermann-SW/Raspberry_v1_camera_global_external_shutter
https://stamm-wilbrandt.de/en/Raspberry_camera.html

HermannSW
Posts: 5307
Joined: Fri Jul 22, 2016 9:09 pm
Location: Eberbach, Germany

### Re: JavaScript graph library, for embedding and drawing planar graphs in 2D and/or sphere surface

Instead of not displaying 3 pentagons, I subtracted cube in case of look_inside selected from each pentagon:
https://stamm-wilbrandt.de/en/forum/JSC ... arams_b.js

I tested to color the pentagons with different than grey as well, for planar embedding face 6-coloring on sphere:

I found no satisfying way to capture video of JSCAD Auto-rotate, so I just shot a smartphone video and posted one rotation on youtube: