<p>The general problem is called <a href="https://en.wikipedia.org/wiki/Graph_drawing" rel="noreferrer">graph drawing</a> and is not an easy problem.</p>
<p>The graphs that can be drawn on the plane without crossings are called <a href="https://en.wikipedia.org/wiki/Planar_graph" rel="noreferrer">planar</a>, but not all graphs are planar: the typical graphs that are not planar are the complete graph on <span class="math-container">$5$</span> vertices <span class="math-container">$K_5$</span> and the complete bipartite graph on 6 vertices <span class="math-container">$K_{3,3}$</span>, famous because of the <a href="https://en.wikipedia.org/wiki/Three_utilities_problem" rel="noreferrer">three utilities problem</a>.</p>
<p>You may want to try <a href="http://www.graphviz.org/" rel="noreferrer">Graphviz - Graph Visualization Software</a> to produce nice drawings.</p>
<p>See also</p>
<blockquote>
<p>Szirmay-Kalos, László, <a href="http://www.iit.bme.hu/%7Eszirmay/lsgraph.ps.gz" rel="noreferrer">Dynamic layout algorithm to display general graphs</a>, in <em>Graphics Gems IV</em>, 1994. <a href="http://www.realtimerendering.com/resources/GraphicsGems/gemsiv/graph_layout/" rel="noreferrer">code</a></p>
<p>Rosati, Claudio, A simple connection algorithm for 2-d drawing, <em>Graphics Gems III</em>, 1992, <a href="http://www.realtimerendering.com/resources/GraphicsGems/gemsiii/con2d.c" rel="noreferrer">code</a>.</p>
</blockquote>

CC BY-SA 3.0
2015-11-30T03:45:31.187Z
Other tools include yEd (Free to use but no free licese), gephi... this is a NP Hard problem.
joojaa
CC BY-SA 3.0
2015-11-30T00:51:28.830Z
2015-11-30T03:58:02.933Z
2020-06-18T08:32:12.800Z
lhf
<p>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.</p>

<p>What is the easiest way of finding and drawing these segments of curves?</p>

CC BY-SA 3.0
2015-11-29T18:33:25.253Z
Lines or line segments?
Mokosha
CC BY-SA 3.0
2015-11-29T22:33:43.360Z
It is only important, that the two new points are connected, therefore segments of curves are also OK. Question edited.
user36552
CC BY-SA 3.0
2015-11-29T23:36:38.467Z
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.
Nathan Reed
<algorithm>
Strategy for connecting 2 points without intersecting previously drawn segments of curves
user36552
# Strategy for connecting 2 points without intersecting previously drawn segments of curves

(Asked by: username_0 on 2015-11-29)

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?

**Tags:** algorithm

> **Comments:**
> **username_1**: Lines or line segments?  
> **username_0**: It is only important, that the two new points are connected, therefore segments of curves are also OK. Question edited.  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_3 on 2015-11-30. Score: 6

The general problem is called [graph drawing](https://en.wikipedia.org/wiki/Graph_drawing) and is not an easy problem.

The graphs that can be drawn on the plane without crossings are called [planar](https://en.wikipedia.org/wiki/Planar_graph), 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](https://en.wikipedia.org/wiki/Three_utilities_problem).

You may want to try [Graphviz - Graph Visualization Software](http://www.graphviz.org/) to produce nice drawings.

See also

> Szirmay-Kalos, László, [Dynamic layout algorithm to display general graphs](http://www.iit.bme.hu/%7Eszirmay/lsgraph.ps.gz), in *Graphics Gems IV*, 1994. [code](http://www.realtimerendering.com/resources/GraphicsGems/gemsiv/graph_layout/)
>
> Rosati, Claudio, A simple connection algorithm for 2-d drawing, *Graphics Gems III*, 1992, [code](http://www.realtimerendering.com/resources/GraphicsGems/gemsiii/con2d.c).

> **Comments:**
> **username_4**: Other tools include yEd (Free to use but no free licese), gephi... this is a NP Hard problem.  

---

