------------------------------------------------- Arithmetic Boundary Checking - Stephen M. Mansour ------------------------------------------------- A point partitions a line into three disjoint subsets: the set of points to its left, the point itself and the set of points to its right. Relational functions produce two results 0 and 1, effectively partitioning a line into only two sub- sets. A technique, known as arithmetic boundary checking, uses arithmetic funct- ions instead of relational and Boolean functions to determine where a point lies in a line or a plane. Relational Functions -------------------- Relational functions ask the question: is the statement true or false? If the statement ⍺<⍵ is true, we have all the information we need, but if it is false, we don't know whether ⍺=⍵ or ⍺>⍵. To get a complete picture, we need to perform a second test. The dynamic function bp performs two tests to produce a Boolean pair: bp←{⊃(⍺<⍵)(⍺>⍵)} ⍝ Boolean pair (2-vector) 2 3 4 bp 3 ⍝ ⍺<⍵←→1 0 ⋄ ⍺=⍵←→0 0 ⋄ ⍺>⍵←→0 1 1 0 0 0 0 1 While this preserves information, there are two problems. First, it seems some- what redundant to do two similar comparisons, and second, we would like a scalar result because it will allow us to work more easily with arrays of data. Signum Difference ----------------- The signum function (×) naturally partitions a line into three disjoint subsets, by producing three results (-1, 0, 1). We can apply signum to the difference between a value and the boundary point to produce the signum difference, which asks a more specific question, i.e. what is the relationship between ⍺ and ⍵? xd←{×⍺-⍵} ⍝ Signum difference 2 3 4 xd 3 ⍝ ⍺<⍵←→¯1 ⋄ ⍺=⍵←→0 ⋄ ⍺>⍵←→1 ¯1 0 1 Notice that bp produces the two-bit binary representation of the ones complement of the result of xd. Alternatively, we could produce the same result as that of xd by subtracting the left bit from the right bit of the ones complement in the function bd listed below : bd←{(⍺>⍵)-(⍺<⍵)} ⍝ Boolean difference 2 3 4 bd 3 ⍝ ⍺<⍵←→¯1 ⋄ ⍺=⍵←→0 ⋄ ⍺>⍵←→1 ¯1 0 1 However, a performance test in Dyalog Version 10 shows that xd runs significant- ly faster than bd: U←1E¯4×500000-?100⍴1E6 V←1E¯4×500000-?100⍴1E6 cmpx 'U xd V' 'U bd V' U xd V 2.2E¯5 0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕ U bd V 3.4E¯5 +52% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕ Intervals --------- An interval is indicated by two distinct points on the real line. The interval includes the interior and may include one or both of the end-points. An interval is open if it excludes the end-points; closed if it includes both of them, and half-open if it includes only one of them. A half-open interval can be open on the left or on the right. The four types of intervals can be described by comb- ining relational functions into the operator rg: rg←{(⍺[0]⍺⍺ ⍵)∧⍺[1]⍵⍵ ⍵} ⍝ Range Operator 1 3 <rg> ⍳5 ⍝ Open Interval: ○-----------○ 0 0 1 0 0 1 3 ≤rg≥ ⍳5 ⍝ Closed Interval: ⍟-----------⍟ 0 1 1 1 0 1 3 <rg≥ ⍳5 ⍝ Half-Open Left: ○-----------⍟ 0 0 1 1 0 1 3 ≤rg> ⍳5 ⍝ Half-Open Right: ⍟-----------○ 0 1 1 0 0 This operator is still limited in that it does not differentiate between an interior point and a boundary (limit) point. Partitions ---------- A pair of distinct points on the real line can define two types of partitions: an interval partition and a range partition. An "interval partition" divides the real line into three disjoint subsets: the interior (between the end-points), the boundary (the two end-points themselves), and the outside (everything else). Outside Bound Interior Bound Outside <----------------|--------------------|-----------------> 1 0 ¯1 0 1 The product of the signum differences between a specified point and each of the boundary points will indicate whether the point falls in the interior, the boundary, or outside. If the point is outside the interval, the differences are both positive, or both negative so their signum product is +1. If the point is on the boundary, one of the differences is zero, thus the product is zero. And if the point is in the interior, the differences have opposite signs, so the signum product is -1. A range partition divides the real line into five disjoint regions: below, lower bound (L.B.), interior, upper bound (U.B.) and above: Below L.B. Interior U.B. Above <----------------|--------------------|-----------------> ¯2 ¯1 0 +1 +2 ┌───────────┬─────────┬─────────┬───────┬───────┐ │ │A←P xd LB│B←P xd UB│xp: A×B│xs: A+B│ ├───────────┼─────────┼─────────┼───────┼───────┤ │Below │ ¯1 │ ¯1 │ 1 │ ¯2 │ ├───────────┼─────────┼─────────┼───────┼───────┤ │Lower bound│ 0 │ ¯1 │ 0 │ ¯1 │ ├───────────┼─────────┼─────────┼───────┼───────┤ │Interior │ 1 │ ¯1 │ ¯1 │ 0 │ ├───────────┼─────────┼─────────┼───────┼───────┤ │Upper bound│ 1 │ 0 │ 0 │ 1 │ ├───────────┼─────────┼─────────┼───────┼───────┤ │Above │ 1 │ 1 │ 1 │ 2 │ └───────────┴─────────┴─────────┴───────┴───────┘ Table 1: Signum Product and Signum Sum The sum of the signum differences will produce five distinct values ranging from -2 to +2 and corresponding to each of the 5 regions in a range partition. xp←{×/×⍵∘.-⍺} ⍝ Signum product 1 3 xp ⍳5 ⍝ produces interval partition 1 0 ¯1 0 1 xs←{+/×⍵∘.-⍺} ⍝ Signum sum 1 3 xs ⍳5 ⍝ produces range partition ¯2 ¯1 0 1 2 Two-Dimensional Region Checking ------------------------------- In a GUI application, you may want to know whether the cursor is within a dialog box. In particular you may want to know whether the cursor is in the interior of the box, on the boundary, or outside the box. ┌───────────────┐ │ Interior(¯1) │ Outside (1) Boundary (0)--→│ │ └───────────────┘ Figure 1: Regions in the plane defined by a rectangle We now extend the concept of arithmetic boundary checking to two dimensions. In the following example, we have six points in various positions relative to a rectangular region in the plane. The coordinates of the upper left and lower right corners of the rectangle are (3,2) and (5,6) respectively. The signum products of the x and y coordinates must be calculated separately. · ∘(2,3) · · · Upper Left --→ (3,2)∘───────────────────────∘(3,5)──┐ · │ │ · │ │ · │ ∘(4,4) │ · │ │ · │ │ · (5,2)∘───────────────────────────────∘(5,6) ←-- Lower Right · · · ∘(6,8) · · ∘(7,6) Figure 2: Points in various positions relative to a rectangle in the plane. If we take the signum product of the x-coordinate with respect to the row coord- inates and the signum product of the y-coordinate with respect to the column co- ordinates, we obtain a ordered pair indicating the position in each direction. The following table shows this for the points in Figure 2. ┌─────┬───────────┬──────┬─────────┬──────────┐ │Point│Description│Row xp│Column xp│Region (⌈)│ ├─────┼───────────┼──────┼─────────┼──────────┤ │(6,8)│Outside │ 1 │ 1 │ 1 │ ├─────┼───────────┼──────┼─────────┼──────────┤ │(5,2)│Corner │ 0 │ 0 │ 0 │ ├─────┼───────────┼──────┼─────────┼──────────┤ │(4,4)│Interior │ ¯1 │ ¯1 │ ¯1 │ ├─────┼───────────┼──────┼─────────┼──────────┤ │(7,6)│Below │ 1 │ 0 │ 1 │ ├─────┼───────────┼──────┼─────────┼──────────┤ │(3,5)│Edge │ ¯1 │ 0 │ 0 │ ├─────┼───────────┼──────┼─────────┼──────────┤ │(2,3)│Above │ 1 │ ¯1 │ 1 │ └─────┴───────────┴──────┴─────────┴──────────┘ Table 2: Various points in the plane with respect to a defined rectangular region. In order to be in the interior, both coordinates of the point must be in the interior of their respective intervals in the x and y directions. If either co- ordinate is outside, then the point itself is outside. Otherwise, the point is on the boundary. In general, the region in which the point resides is the great- er of the partitions in each direction. xm←{-/⊃×⌿×⍺,.-⍉⍵} ⍝ Max Signum b←⊃(3 2)(5 6) ⍝ Upper Left and Lower Right Corners b xm⊃(6 8)(5 2)(4 4)(7 6)(3 5)(2 3) ⍝ Various Points 1 0 ¯1 1 0 1 The left argument of the dynamic function xm is a 2 x 2 matrix containing the coordinates of the upper-left and lower-right corners of a rectangular region. The right argument is a 2-element vector or 2-column matrix containing the co- ordinates of various points in the plane. Sometimes it is necessary to divide the borders of the dialog box into specific regions. For example when the cursor is over an edge, it will resize the window in one direction. If it is over a corner, it will resize the window in two dir- ections. The particular edge or corner selected also determines the position of the resized window. A rectangular region naturally subdivides the x-y plane into 25 regions, 5 in the x direction by 5 in the y direction . The following regions are shown in Figure 3: 1 interior region, four corners, four edges, and 16 outside regions. ┌───────────┬───────────┬───────────┬───────────┬───────────┐ │Outside (8)│Outside (8)│Outside (8)│Outside (8)│Outside (8)│ ├───────────┼───────────┼───────────┼───────────┼───────────┤ │Outside (8)│Upper Left │Upper Edge │Upper Right│Outside (8)│ │ │Corner (¯4)│ (¯3) │Corner (¯2)│ │ ├───────────┼───────────┼───────────┼───────────┼───────────┤ │Outside (8)│Left Edge │Interior │Right Edge │Outside (8)│ │ │ (¯1) │ (0) │ (1) │ │ ├───────────┼───────────┼───────────┼───────────┼───────────┤ │Outside (8)│Lower Left │Bottom Edge│Lower Right│Outside (8)│ │ │Corner (2) │ (3) │Corner (4) │ │ ├───────────┼───────────┼───────────┼───────────┼───────────┤ │Outside (8)│Outside (8)│Outside (8)│Outside (8)│Outside (8)│ └───────────┴───────────┴───────────┴───────────┴───────────┘ Figure 3: 25 Regions defined by a rectangle The signum sum applied to each coordinate generates an ordered pair. If we wish to identify all 25 regions uniquely, we can use base value with a root of 5 to generate the integers -12 to +12 with 0 representing the interior. More likely, we only wish to identify the 9 relevant regions, disregarding the 14 outside regions. We can use base value with a root of 3. This will produce the values -4 to +4 with 0 representing the interior. We will assign the value 8 to the outside regions. We can identify a point in the outside region if the ordered pair of its signum sums contains the value 2 or -2. The function xr generates the appropriate value. xr←{d←⍉⊃+/×⍵,.-⍉⍺ ⋄ ((2∨.=|d)/d)←2 ⋄ 3⊥d} b xr ⊃(2 3)(3 5)(4 4)(5 2)(6 8)(7 6) 8 ¯3 0 2 8 8 Theoretical Considerations and Conclusion ----------------------------------------- Arithmetic boundary checking is based upon the topological properties of the real line and the Euclidean 2-space [1]. The boundaries of an interval or a rectangle correspond to limit points in topology. An open interval corresponds to the interior set, whereas a closed interval corresponds to the union of the boundary set and the interior set. A k-cell is defined as an closed interval on the real line where k=1 or a closed rectangle in the plane, where k=2. [2] While Boolean functions are useful if binary results are adequate, they do not work as well when more information is required. Location on the real line or in the plane can be determined arithmetically without the use of Booleans. The ternary nature of signum is exploited to handle boundary conditions. References ---------- [1] Jerrold Marsden, "Elementary Classical Analysis" W.H.Freeman & Co. 1974, Chapter 2, Topology of, pp 32-44. [2] Walter Rudin, "Principles of Mathematical Analysis, Third Edition", McGraw- Hill 1976, pp. 31-32 . See also: kcell kball Back to: contents Back to: Workspaces