-------------------------------------------------
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, "Priciples of Mathematical Analysis, Third Edition", McGraw-
    Hill 1976, pp. 31-32 .

See also: kcell kball

Back to: contents

Back to: Workspaces