9
$\begingroup$

I have to connect point pairs without intersection. Let's say I have two given points that I connect with a segment of a curve. Then again two new endpoints are selected and these new points have to be connected as well however without intersecting previously drawn curves and so on for any number of given point pairs.

What is the easiest way of finding and drawing these segments of curves?

$\endgroup$
  • $\begingroup$ Lines or line segments? $\endgroup$ – Mokosha Nov 29 '15 at 18:33
  • $\begingroup$ It is only important, that the two new points are connected, therefore segments of curves are also OK. Question edited. $\endgroup$ – user36552 Nov 29 '15 at 22:33
  • 2
    $\begingroup$ You might look into path-finding algorithms for this. Use existing segments as obstacles and find a path between the two new endpoints. Maybe apply some smoothing to the resulting path to make it a nicer-looking curve. $\endgroup$ – Nathan Reed Nov 29 '15 at 23:36
6
$\begingroup$

The general problem is called graph drawing and is not an easy problem.

The graphs that can be drawn on the plane without crossings are called planar, but not all graphs are planar: the typical graphs that are not planar are the complete graph on $5$ vertices $K_5$ and the complete bipartite graph on 6 vertices $K_{3,3}$, famous because of the three utilities problem.

You may want to try Graphviz - Graph Visualization Software to produce nice drawings.

See also

Szirmay-Kalos, László, Dynamic layout algorithm to display general graphs, in Graphics Gems IV, 1994. code

Rosati, Claudio, A simple connection algorithm for 2-d drawing, Graphics Gems III, 1992, code.

$\endgroup$
  • $\begingroup$ Other tools include yEd (Free to use but no free licese), gephi... this is a NP Hard problem. $\endgroup$ – joojaa Nov 30 '15 at 3:45

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.