5.81. 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.81.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.81.1. Intersection between line-segments
- 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 .
- See also
- Keywords
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 one 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.81.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.81.2. Initial and final graph of the constraint
(a) (b)