Edge intersections: Drawing graphs with minimal edge intersections

The last bit of code we need to make our initial fully randomized algorithm for minimal-crossing embeddings is the method that checks if two edges intersect.

In this section we’ll start discussing the variant for straight-line drawings; since edges are drawn as segments, it’s easier to check if they intersect.

Then we’ll move to Bezier curves, briefly explaining how they work, the subset of curves we’ll allow, and how to check for intersections for elements of this subset.

1. Straight-line segments

Let’s start with the intersection between two segments. After all, we have also said that we decided to focus on straight-line drawings, so we’ll devote more space to discussing this case.

An initial strategy to cheaply screen pairs that are not intersecting is shown in fig­ure 15.16. If we draw a box, parallel to the axes, around each of the two segments, then obviously the two segments can’t cross if the boxes do not intersect. In turn, the two boxes can’t intersect if the projections of the two segments over the Cartesian axes don’t intersect on both the x and y axes.

This condition, having the projected segments not intersecting, is sufficient, but not necessary for establishing that two segments do not cross. Figure 15.16 (B) shows how there can be segments whose boxes intersect, but that don’t cross.

So, we have an asymmetric situation:

• If we find out that the projections of the segments do not intersect over one of the two axes, we can conclude that the segments do not intersect.
• Otherwise, we can’t make any assumptions, and we need to further investigate.

We can do that in many ways, for instance, by verifying that the extremes of a segment fall on the opposite sides of the line passing through the other segment, as shown in figure 15.17.

Figure 15.17 Segment intersection: if bounding boxes have a non-null intersection, the discriminant becomes whether or not the vertices of segment CD (or HG) are on opposite sides of the line passing through the segment AB (EF), and vice versa

This, however, requires a bit too much fiddling with edge cases (for instance, parallel segments), so I prefer a different, more elegant, method I recently discovered.

The gist of it is shown in figure 15.18. It doesn’t involve bounding boxes; rather, we want to find the intersection point of the lines passing through the segments and then check that it lies within both segments. There are, actually, three possible cases:

• The intersection of the two lines, point P, lie outside of both segments.
• P lies inside one of the two segments, but not both.
• P lies within both segments.

The third case is the only one where we have an intersection.

How do we find P? Well, first, more precisely, we will use vectors and semi-lines rather than just lines.

We define vectors v=BA=(B_x-A_x,B_y-A_y) and w=DC=(D_x-C_x,D_y-C_y). These vectors start from the second point in the segment and end at the first one. Now, remember that vectors can be trans­lated seamlessly, so, for instance, we can move the v so that it starts where w ends, or vice versa, and compute their sum or product. For instance, considering the vector u that is shown in figure 15.19 (A) (and that we’ll define in a few lines), we show it sharing point A with v out of convenience, so that it’s apparent how the two vectors are orthogonal.

Assuming that vectors v and w aren’t parallel (which we can easily check by taking their cross product), the lines passing through them will cross at one point P, that might or might not lie inside the segments. Either way, there must be two real num­bers, h and g, such that the scaled vectors h*v and g*w, when their start point is set to B and D respectively, both end exactly at point P, as shown in figure 15.19 (B).

In other words, the coordinates of point P can be expressed in terms of both vectors, and the following equation must hold:

B + h*v = D + g*w

Notice that B and D can also be considered vectors: in particular, the vectors that go from the origin to those two points.

We had mentioned we would define a new vector u. Well, now is the time to consider it:

u = (-v_y,v_x) = (A_y-B_y,B_x-A_x)

This vector has a special property; its dot product with vector v is zero:

UV = vu = VxVy – VyVx = 0

Going back to equation (1), we can multiply both sides by u, which is not null (as long as A and B are distinct points, which we assume as a hypothesis, because distinct vertices can’t be assigned to the same point). Doing so we get

 B·u + h*v·u = D·u + g*w·u ⇒ B·u = D·u + g*w·u

As such we eliminate the unknown h and solve the equation for g:

Similarly, we can define vector z = (-w_y,w_x), such that zw = 0, and derive a formula for h:

All that’s left is reasoning about the meaning of these two solutions. Looking at figure 15.19, can you tell which one, between h and g is, for this example, larger than 1?

If you notice, in this particular example vector, BP is smaller than vector BA, and as such, h must have a value between 0 and 1. The scalar g must be larger than 1, because vector DP is longer than DC.

For the former situation, clearly P is within the segment BA, while for the latter, it’s clearly outside DC.

When either value is 0 or 1, it means that P coincides with one of the segment’s end­points. If both h and g are equal to either 0 or 1, then we have an edge case where the two segments have a vertex in common. These two edge cases are shown in figure 15.20.

In conclusion, if we assume that all 4 vertices are distinct, then the two segments inter­sect if and only if both 0≤h≤1 and 0≤g≤1 (but only at most one of them is either 0 or 1).

Listing 15.8 shows the code to compute the scaling coefficient (either of h or g; which one depends on the order of the points we pass) for one segment with respect to the other.

We reuse this coefficient in listing 15.9, where we check the intersection between two graph edges.

2. Polylines

In our examples in chapter 15 we have drawn a few flowcharts by using polylines for edges, and specifically a subset of all polylines where the only segments allowed are parallel to the Cartesian axes. In this configuration, checking for intersections becomes somewhat easier, because while it’s true that for each edge we need to con­sider the segments composing it, checking the intersections of two segments that can either be vertical or horizontal becomes much easier and boils down to checking their endings’ coordinates.

One important difference with this representation is that the number of intersec­tions between two edges is not just 0 or 1 anymore; they can intersect multiple times— one more reason to prefer other styles over polylines.

3. Bezier curves

An interesting and flexible alternative to polylines is provided by Bezier curves. These curves are a valuable solution because they can be drawn with a variable degree of pre­cision, depending on the computational resources available. Bezier curves have a beautiful mathematical formula and are both flexible and precise. Going into the details of how they work is beyond the scope of this book, but we’ll try to give a quick introduction that should be enough to get you started. To the interested reader that would like to delve into this topic, we have two freely available online resources:

• Sederberg, Thomas W. “Computer aided geometric design” (2012).
• “A Primer on Bezier Curves”, https://pomax.github.io/bezierinfo/.

Let’s start building our intuition with the geometric definition of Bezier curves, shown in figure 15.21 for a quadratic curve.

A quadratic curve requires three points: two endpoints (S and E in figure 15.21) and a control point (C₁). First, we have to draw the two segments between the end­points and C₁. Then we need to choose two points on those segments, under the con­straint that if the point on SC₁ (call it A) is such that SA/SC=t, then B, the endpoint on EC₁, must satisfy EB/EC₁=(1-t). These two points, A and B, will be the endpoints of another segment, AB, on which we choose a point P_t such that AP_t/AB=t.

If t==0, then P_t==A, while when t==1 then P_t==B. The collection of all these points P_t, for all values of t between 0 and 1, makes a quadratic Bezier curve between A and B.

Notice how the segment A_tB_t is always tangent to the curve.

For cubic Bezier curves the procedure becomes a bit more involved, as shown in fig­ure 15.22. There are two control points, C and C₂, and we first have to draw the seg­ments C₁C₂ and select a point C_t on this segment. We’ll have to note the ratio between the two subsegments created by this point, t=C₁C_t/C₁C₂.

Then we select two points A_t and B_t on the segments between the endpoints and the closest control point, such that SA_t/SC₁=t and C₂B_t/C₂E=t.

Finally, for the three points A_t, B_t and C_t, we need to go through the same steps we performed for a quadratic curve, and select a point P_t.

Technically a Bezier curve is an iterative linear interpolation. When we select points A_t, B_t, (and C_t) we apply linear interpolation (varying the ratio t), and likewise we can do this for the segments between the generated points.

So, if we start with two segments (quadratic curve), we can apply linear interpola­tion twice to find the curve’s points. With three initial segments (cubic curve), we pick three points, which in turn define two new segments, and so on; we thus apply linear interpolation three times.

Following this definition, even a straight-line segment can be expressed as a Bezier curve. It has no control points and just 1 segment, so we apply linear interpolation once.

In this edge case, it’s easy to see that the generic point P_t is given by the vectorial equation:

We won’t derive it for a quadratic curve, but here is how it will look:

In general, for a Bezier curve with n-2 control points, we can express its generic point as

using the conventions: S=Q₀, E=Q_n and C_i=Q_i ∀ i=1,. .,n-1.

4. Intersections between quadratic Bezier curves

In our examples, we are only going to use a subset of the set of Bezier curves—symmet­ric quadratic Bezier curves where the control point lies at exactly the same distance between the two endpoints. This way, we can simplify the way we reason about the curve and the way we look for intersections.

Looking at figure 15.23, we can see a few interesting facts:

• The curve is always going to be a section of a parabola.
• We can store point C by using a single real value (the distance from the line passing through the endpoints).
• The tangent to the curve that’s parallel to segment SE is exactly halfway between the same segment and point C.

We’ll see later why the third point is especially important for us.

First, we need to give a brief overview of the methods that can be used to check intersections between Bezier curves:

• Bezier subdivision is a method based on convex hull—For a Bezier curve with n-2 control points, its convex hull is the polygon with n sides whose vertices are the endpoints and control points. Figure 15.24 illustrates how it’s possible to compute the intersection of two curves by comparing their convex hulls.

If they do not overlap, the curves do not intersect; otherwise, the curves are each split in half and the two halves of one curve are checked for overlap against the two halves of the other curve. This step can be iterated until either there is no overlap between any pair of sections, or the curves are split into sections so small that they can be approxi­mated with segments (within a certain acceptable error). Then, we can just use the algorithm in section 15.4.1 to check that no pairs of segments intersect.

• Bezier clipping—For generic Bezier curves, this is the most efficient method, but also the most complicated. We won’t get into the details for this one.

• Interval subdivision—This is similar to Bezier clipping, but it adapts better to our stricter requirements. The difference is that in this case, we first find the vertical and horizontal tangents to the curve. By splitting the curve, making sure that the points where its tangent is parallel to one of the axes are at the extremes of each segment, we guarantee that in each segment the curve is monotone (because a function can change its trend only in such points), and that for each value point on the x axes, there is only one point belonging to the curve in each one of these sections. Figure 15.25 illustrates how it works for a generic Bezier curve. In turn, we can use these properties to further split the curve by halving each segment along the x axis and computing the exact point on the curve. This point will be one of the corners of each section’s bounding box, and we can easily compare the bounding boxes of two curves. They will all be parallel to the Cartesian axis, so we just need to check a few inequalities to find out if they intersect.

Applying the interval subdivision method to symmetric quadratic Bezier curves is even simpler, because these curves have at most two points where its tangent is parallel to one of the axes. Moreover, we can easily compute an initial, coarse-grained bounding box for each of these curves. As shown in figure 15.26, they all lie within the rectangle delimited by the line passing through its endpoints, the parallel to the former tangent to the apex of the curve (at distance d/2 from segment SE, as we have previously men­tioned), and the perpendicular lines to SE passing to those endpoints.

Therefore, we can informally define the algorithm to check for intersection of two symmetric quadratic Bezier curves as the following steps:

• Compute the bounding boxes of the two curves, as shown in figure 15.26 (A).
• If the bounding boxes do not intersect, return 0; if they do, continue.
• Compute the vertical and horizontal tangents to each curve, and use them to split the curve into two or three sections (depending on if they have both tan­gents or just one).
• Recursively
  •  For each of the sections of curve  C₁ check which sections in curve C₂ it overlaps.
  •  If no two sections overlap, return 0.
  • Otherwise, return the sum of the intersections for the remote calls among the overlapping pairs:
    • For each pair of overlapping sections.
    • Split each of the overlapping sections in half.
    • If the sections are small enough to be approximated with segments, com­pute the segments’ intersection.
    • Otherwise, recursively check the four sections resulting from the split.

If we compare this algorithm to the one in section 15.4.1 for segment intersection, the main difference that stands out is that this algorithm is recursive (or equivalently iter­ative), while for segments we only need to perform a constant number of operations.

This means that if we use curves instead of segments, computing the edge crossing at each iteration of an optimization algorithm is going to be much more expensive.

Moreover, with quadratic curves we already have four possible intersections for each pair of edges, and for cubic curves it’s obviously even worse: we have more parameters to optimize, and each change can make a greater difference.

That’s why we are focusing on straight-line drawings. One should really double­check the requirements and discuss the benefits and costs, before deciding to embark on the more challenging enterprise of curve-line embeddings.

5. Vertex-vertex and edge-vertex intersections

So far, we have delayed the discussion about validating an embedding by checking that no pair of vertices share the same position, and that no edge crosses a vertex.

There are many ways to draw edges, as we have seen, but there are also many ways to draw vertices: they can be punctiform, they can be drawn as circles, but they can also be drawn as squares, octagons, or any kind of polygon, really. Depending on these choices, we’ll need a different algorithm.

Here, we’ll assume that vertices are drawn with circles (punctiform vertices being an edge-case, a circle with a radius close to zero), and edges are drawn with segments. This will give you the tools to handle the simplest solution and a basis to build more complex ones, if needed.

For vertices, in particular, if you choose to use squares or regular polygons, you can always consider the circumscribed circle or minimum bounding circle of the polygon and change the constraints considering these circles instead of the actual shape of the vertices.

Using circles makes our lives a lot easier; it allows us to just check the distance between two vertices (between their centers) or between a vertex and an edge.

For two vertices, the algorithm is trivial: we just need to check that the distance between their centers is larger than the sum of their radii. Figure 15.27 shows why.

To make sure an edge doesn’t overlap with a vertex (which is not an endpoint for the edge), we need to make sure that the distance between the edge and the vertex is larger than the vertex’s radius.

In turn, when edges are drawn with straight­line segments, this forces us to check three dis­tances. If the distances between the two seg­ment’s endpoints (S, E in figure 15.28) and the vertex’s center (let’s call it C) are smaller than the vertex radius, then we certainly have an inter­section. Even if these distances are larger, though, the vertex could intersect the edge somewhere in the middle, so we need to check the distance between the line passing through the segment and the vertex’s center, and that the point of minimum distance between the vertex and the line falls inside the segment.

To find the point-to-segment distance, we can use the following formula (which we won’t derive here):

And finally, to check if the intersection between the line passing through the segment and the line of minimum distance to a vertex (a line perpendicular to the segment passing through a vertex) falls within or outside a segment, we can use the same algo­rithm we developed for segment intersection, using points S and E on one side, and v and P_v (or u and P_u) on the other side. We just need to check that the multiplicator factor is between 0 and 1.

Source: Rocca Marcello La (2021), Advanced Algorithms and Data Structures, Manning Publications (2021)