Set intersection

As explained in Advanced Algorithms and Data Structures

An edge intersection is a geometric point or region at which two drawn graph edges meet away from their permitted common endpoint.

To count crossings in a graph drawing, first decide when two drawn edges intersect. For straight-line edges, the relevant event is a meeting away from a permitted common endpoint. A shared endpoint alone is not a crossing. This distinction lets an embedding count edge intersections without counting ordinary connections between edges. section 15.4.1 section 16.1.1

For two straight-line segments, test intersection in stages:

• Optionally compare their axis-aligned bounding boxes. If their projections are disjoint on either axis, the segments cannot intersect; overlapping boxes do not prove that they do. section 15.4.1
• Find where the lines through the segments meet. Express that point using a scaling factor for each segment; it lies on both segments only when both factors are between 0 and 1, inclusive. section 15.4.1
• Exclude a meeting where both factors identify endpoints. The displayed scaling-factor calculation divides by a vector dot product, so an implementation must handle a zero denominator separately rather than divide by it. section 15.4.1

Figure 15.18 Checking whether the point of intersection of the two lines falls within both segments

The diagram separates a meeting of the extended lines from a meeting that falls within both finite segments. section 15.4.1

An orthogonal polyline edge needs a different count: compare its constituent horizontal and vertical segments using their endpoint coordinates. Two such edges can meet more than once, unlike the single-intersection cases considered for straight-line edges. section 15.4.2

Counting crossings in a candidate drawing

Place each vertex at a distinct point in a rectangle, reject a placement if a vertex lies on a nonincident edge, then test each unordered pair of edges and increment a crossing count when the edge-intersection test succeeds. Repeating this for random valid placements lets you retain the drawing with the lowest count. With m edges, the pair scan makes O(m²) intersection tests per valid placement. section 16.1.1

Crossing count is also a cost function, but it changes abruptly as vertices move. In a four-vertex complete-graph example, moving one vertex horizontally changes the cost from 1 to 0 when it enters a triangular region; positions that put a vertex on another edge are invalid. Thus counting crossings is straightforward, while using the count to guide an optimization algorithm can be problematic. section 16.2.1

How Advanced Algorithms and Data Structures covers it

How deep it goes

Develops a bounding-box rejection test and a vector-based segment test, but does not specify zero-denominator handling.

Examples

Uses segment diagrams, a pairwise crossing-count routine, orthogonal polylines, and complete-graph cost plots.

What it assumes

Assumes Cartesian coordinates and graph vertices and edges; introduces the vector scaling test while stating drawing constraints explicitly.

What you can do after

Build it from scratch to count straight-line edge crossings and compare valid candidate embeddings.

How it connects

Connects segment intersection to bounding boxes, graph embeddings, polylines, random sampling, and cost functions.

liveBookmanning.com

Read Advanced Algorithms and Data Structures on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Geometry for ProgrammersA geometric or set operation whose result consists of elements shared by the combined objects.
• 

  liveBookmanning.com
  Julia as a Second LanguageSet intersection is the operation that produces the elements shared by two or more sets.
• 

  liveBookmanning.com
  Python How-ToSet intersection is the operation that produces the elements common to two sets or set-compatible collections.
• 

  liveBookmanning.com
  Secrets of the JavaScript Ninja, Second EditionA set operation that produces a set containing the elements common to the operand sets.

Compare how 5 books explain set intersection →

Related concepts

• setuses · A set is a collection of unique elements in which membership is determined by whether an element is present, not by duplicate occurrences.
• set operationkind of · A set operation combines, compares, or transforms sets according to the membership of their elements.
• set differencecontrasts with · Set difference is the set of elements that belong to one set but not to another.
• inner joinequivalent to · An inner join is a relational operation that returns combinations of rows only when the join condition matches records in both input relations.

This explainer was generated by Manning's knowledge graph from the text of Advanced Algorithms and Data Structures. The section links point to the parts of the book it draws on.