5.95. crossing
| DESCRIPTION | LINKS | GRAPH |
- Origin
Inspired by [CormenLeisersonRivest90].
- Constraint
- Arguments
- Restrictions
- Purpose
is the number of line segments intersections between the line segments defined by the collection. Each line segment is defined by the coordinates and of its two extremities.
- Example
-
FigureΒ 5.95.1 provides a picture of the example with the corresponding four line segments of the collection. The constraint holds since its first argument is set to 3, which is actually the number of line segments intersections.
Figure 5.95.1. Illustration of the Example slot: intersection, in red, between the four line segments , , and ()
- Typical
- Symmetries
Items of are permutable.
Attributes of are permutable w.r.t. permutation (permutation applied to all items).
One and the same constant can be added to the and attributes of all items of .
One and the same constant can be added to the and attributes of all items of .
- Arg. properties
Functional dependency: determined by .
- See also
- Keywords
constraint arguments: pure functional dependency.
final graph structure: acyclic, no loop.
geometry: geometrical constraint, line segments intersection.
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
-
- Graph property(ies)
-
- Graph class
-
- Graph model
Each line segment is described by the and coordinates of its two extremities. In the arc generator we use the restriction in order to generate a single arc for each pair of segments. This is required, since otherwise we would count more than once a given line segments intersection.
PartsΒ (A) andΒ (B) of FigureΒ 5.95.2 respectively show the initial and final graph associated with the Example slot. Since we use the graph property, the arcs of the final graph are stressed in bold. An arc constraint expresses the fact the two line segments intersect. It is taken fromΒ [CormenLeisersonRivest90]. Each arc of the final graph corresponds to a line segments intersection.
Figure 5.95.2. Initial and final graph of the constraint
(a) (b)