Intersections

The Intersections class detects intersections between graph items, including edge crossings and overlaps of all sorts. Detecting intersections can be valuable in many scenarios, for example:

• Run a layout algorithm if any items are intersecting
• Reroute edges that intersect other items, excluding source and target node (see Example Code)
• Place labels which are overlapping other items

Using the Intersections algorithm shows the basic usage of the algorithm.

// create the intersection algorithm and let it consider all item types
const algorithm = new Intersections({
  consideredItemTypes: IntersectionItemTypes.ALL
})

// run the  algorithm
const result = algorithm.run(graph)

// examine each intersection (pair of intersecting graph items)
for (const intersection of result.intersections) {
  const item1 = intersection.item1
  const item2 = intersection.item2
  // ...
  // do something
  // ...
}

Rerouting of intersecting edges demonstrates how to find edges that intersect with nodes and reroute them using the EdgeRouter.

// prepare routing algorithm for re-routing edges
const edgeRouter = new EdgeRouter({
  scope: 'route-affected-edges'
})

const routerData = new EdgeRouterData()
// run the  algorithm with default settings
const result = new Intersections().run(graph)

// if an edge is involved in an intersection with a node, mark the edge for re-routing
// Note: intersections with the edge's source or target node are not detected here, since
// the edges are by default not part of Intersections.independentItems
for (const intersection of result.intersections) {
  if (intersection.item1 instanceof IEdge && intersection.item2 instanceof INode) {
    routerData.affectedEdges.items.add(intersection.item1)
  } else if (intersection.item2 instanceof IEdge && intersection.item1 instanceof INode) {
    routerData.affectedEdges.items.add(intersection.item2)
  }
}

// apply the router to re-route the edges for which a node-edge intersection was detected
graph.applyLayout(edgeRouter, routerData)

The Intersection detection demo showcases a generic application to detect and highlight intersections among graph items.

Considered Item Types

The algorithm considers nodes, edges, node labels and edge labels. If any two items geometrically intersect, then this intersection will be detected and returned as an instance of class Intersection. More about the result is described below, in the section Working with the Result.

The scope of the algorithm can be restricted to specific items via the following options.

consideredItemTypes

Specifies the graph item types that are taken into account. The enum values can be combined to specify that, for example, edges and edge labels are included.

affectedItems

Defines a set of specific graph items that must be part of any intersection. Other intersections are discarded.

More generally, the graph can also be reduced to a subset of nodes and/or edges via properties subgraphNodes and subgraphEdges. In that case ignored items are really not in the graph during the algorithm execution. Therefore, intersections of affected items with those ignored ones are not found.

The intersection algorithm does not explicitly consider the graph items of type IBend, IPort and IStripe. Ports and bends are implicitly taken into account since each edge segment is considered. However, they are never returned as the involved items in an Intersection instance.

Working with the Result

The algorithm yields a IntersectionsResult object.

intersectionCount

The number of intersections that have been found.

intersections

The collection of Intersection instances that have been found.

Each Intersection represents a pair of two graph items that intersect with each other.

The property intersectionPoints yields the specific points that geometrically describe the intersection.

• A single point, if the items only touch in that exact point. This is most likely the case for edge-edge crossings.
• Two points, meaning the items overlap in all points on the line formed by the two points.
• More than two points, meaning there is an overlapping area. The points are sorted to form a convex polygon.

Multi-Segment Intersections

As described above, an Intersection instance always describes the intersection of exactly two graph items. When it comes to edges, it can be that several segments of the edge overlap with the same other graph item (e.g. a node). In that case, multiple Intersection instances are returned. In the example shown below, the edge intersects node "C" twice, once with a vertical and once with a horizontal segment. This means that the algorithm returns two Intersection objects.

Independent Items

The property independentItems allows to specify which graph item types are treated independently of their owning element. Intersections between dependent items are by default not included. Only if an item type is declared as being independent, then those intersections are included.

The dependencies are:

• Labels depend on their owner (e.g. node for node labels).
• Edges depend on their source and target node.
• Nodes depend on their ancestor nodes for grouped graphs.

For example, let us look at the node with node label and edge with edge label dependencies. By default, the labels overlapping with their owning item is not found as an intersection. If declaring node and edge labels as being independent, then the intersections will be found, see the figures in Independent Items Example and the code snippet in Independent node and edge labels.

// create and run Intersections algorithm
// configured to treat node and edge labels as independent items
const result = new Intersections({
  independentItems: GraphItemTypes.NODE_LABEL | GraphItemTypes.EDGE_LABEL
}).run(graph)

Considering the Actual Item Geometry

By default, the algorithm uses the actual item geometry defined by the visualization (styles) of the graph items to determine whether items intersect.

• For nodes, the IShapeGeometry is queried from the node’s lookup and its outline is used to test for intersections.
• For edges, the IPathGeometry is queried from the lookup and its path is then used for intersection calculations.

When disabling this feature via property considerItemGeometry, the calculations are instead based on simplified rectangular bounds for nodes and line segments for edges, disregarding the actual visualization of the items.

This plays an important role when nodes have a shape other than a simple rectangular one, since the simplified bounds may intersect while the actual visualization might not show an intersection.