mesh or graph diagram with nodes and connections

Apologies in advance if this is too broad or to vague a question.

I generate a set of randomised points, let say in 2D space so (x, y).

I want to write code to make lines between points such that I get a graph like the image, but without lines crossing each other as the green dashed lines shown do.

I want to be able to limit the number of points coming into any given node to a maximum number, so at point B the purple line would not be created if the max limit is 9 and the existing lines in image have already been constructed by the algorithm.

I will then animate the points and keep testing that no lines overlap, if so I remove lines until no lines crossing. Also need to define regions in the mesh.

Checking a radius around each point will not necessarily be enough to solve this problem as that doesn't prevent lines crossing or too many lines to a single node or point. Ideally I regularly generate points/nodes with only 3 lines coming into it like point C. Or even exclusively.

Also, as I animate points, I want to test that lines do not become to adjacent to each other as the blue lines from point D when I move it (see second image). Should I test for close to parallel vectors that share points or what?

enter image description here

  • 1
    $\begingroup$ For a static of points, the Delauney triangulation is a well-studied algorithmic approach. If your nodes are moving around, they are apt to become collinear in places, collapsing triangles accordingly. There are a variety of options, including the introduction of points that artificially are fixed (while the real points around them do move). I'm not clear what application you have in mind, but I can give a reference for the static case. $\endgroup$ – hardmath Jul 23 '18 at 16:05
  • $\begingroup$ it's just decorative, animation of a background image for a video/event banners on video screens. I've done random walk kind of things where new points get generated at random distance and direction from last drawn point, but this is taking it up a notch. I just started reading some of the graph text books listed in another question and realise that math is way beyond my comprehension. haven't studied maths since secondary school (did double math and good results but left it behind and only ever really used very elementary geometry for 3D drawing since). $\endgroup$ – wide_eyed_pupil Jul 23 '18 at 16:25
  • $\begingroup$ having watch the video, the images from @3:00 mark to 3:40 are right on what I was thinking about. Delaunay does seem to be a "nice" way to do it. Various algorithms at en.wikibooks.org/wiki/Trigonometry/For_Enthusiasts/… and elsewhere. I'm thinking I might have to cheat a bit to get "nicer" triangles, seems that average number of edges is 6 per node. Basic matrix math I can do, even computationally but might be getting out of my depth on this… thinking of ways I can fake it with predefined meshes/graphs and randomly animate points & lines within prescribed limits. $\endgroup$ – wide_eyed_pupil Jul 23 '18 at 19:06
  • $\begingroup$ @hardmath what happened to the video URL? $\endgroup$ – wide_eyed_pupil Sep 4 '18 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.