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 nodes (see Example Code).
• Place labels that overlap 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 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()

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.scope.edges.items.add(intersection.item1)
  } else if (
    intersection.item2 instanceof IEdge &&
    intersection.item1 instanceof INode
  ) {
    routerData.scope.edges.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 using 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 using properties subgraphNodes and subgraphEdges. In that case, ignored items are not present 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 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 returns a IntersectionsResult object.

intersectionCount

The number of intersections that were found.

intersections

The collection of Intersection instances that were found.

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

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

• A single point indicates that the items only touch at that exact point. This is most likely the case for edge-edge crossings.
• Two points mean that the items overlap in all points on the line formed by the two points.
• More than two points indicate 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, several segments of the edge can 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 you to specify which graph item types are treated independently of their owning element. By default, intersections between dependent items are not included in the analysis. Only if an item type is declared as being independent will those intersections be included.

The dependencies are:

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

For example, consider nodes with node labels and edges with edge labels. By default, intersections of labels with their owning item are not found. If you declare node and edge labels as being independent, these 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 obtained from the node’s lookup, and its outline is used to test for intersections.
• For edges, the IPathGeometry is obtained 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.