10
$\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?

Improve this question
$\endgroup$
3
  • $\begingroup$ Lines or line segments? $\endgroup$
    – Mokosha
    Commented Nov 29, 2015 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
    Commented Nov 29, 2015 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
    Commented Nov 29, 2015 at 23:36

1 Answer 1

Reset to default
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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