Defining a logical predicate

What is the value of the previous representation? As a simple example, we can define a logical predicate that serves as a collision detector. Recall from Section 2.4.1 that a predicate is a Boolean-valued function. Let $\phi$ be a predicate defined as $\phi : {\cal W}\rightarrow \{$TRUE$,\;$FALSE$\}$, which returns TRUE for a point in ${\cal W}$ that lies in ${\cal O}$, and FALSE otherwise. For a line given by $f(x,y)=0$, let $e(x,y)$ denote a logical predicate that returns TRUE if $f(x,y) \leq 0$, and FALSE otherwise.

A predicate that corresponds to a convex polygonal region is represented by a logical conjunction,

$$\alpha (x,y) = e_1(x,y) \wedge e_2(x,y) \wedge \cdots \wedge e_m(x,y) .$$ (3.5)

The predicate $\alpha (x,y)$ returns TRUE if the point $(x,y)$ lies in the convex polygonal region, and FALSE otherwise. An obstacle region that consists of $n$ convex polygons is represented by a logical disjunction of conjuncts,

$$\phi (x,y) = \alpha _1(x,y) \vee \alpha _2(x,y) \vee \cdots \vee \alpha _n(x,y) .$$ (3.6)

Although more efficient methods exist, $\phi$ can check whether a point $(x,y)$ lies in ${\cal O}$ in time $O(n)$, in which $n$ is the number of primitives that appear in the representation of ${\cal O}$ (each primitive is evaluated in constant time).

Note the convenient connection between a logical predicate representation and a set-theoretic representation. Using the logical predicate, the unions and intersections of the set-theoretic representation are replaced by logical ORs and ANDs. It is well known from Boolean algebra that any complicated logical sentence can be reduced to a logical disjunction of conjunctions (this is often called ``sum of products'' in computer engineering). This is equivalent to our previous statement that ${\cal O}$ can always be represented as a union of intersections of primitives.