Next: 5.4 Point/curve intersection Up: 5. Intersection Problems Previous: 5.2.3 Classification by number Contents Index

5.3 Point/point intersection

Point/point intersection problems reduce to checking the Euclidean distance between two points ${\bf r}_1$ and ${\bf r}_2$ , i.e.

$\displaystyle \vert \mathbf{r}_1 - \mathbf{r}_2 \vert < \varepsilon\;,$

(5.1)

where $\varepsilon$ represents the maximum allowable tolerance. Choice of tolerances in a geometric modeler is a difficult open question [309]. For example it may cause incidence intransitivity. Figure 5.5 gives an example of three points ${\bf r}_1$ , ${\bf r}_2$ and ${\bf r}_3$ where $\mathbf{r}_1 = \mathbf{r}_2$ since $\vert\mathbf{r}_1 - \mathbf{r}_2\vert < \varepsilon$ , $\mathbf{r}_2 = \mathbf{r}_3$ since $\vert\mathbf{r}_2 -\mathbf{r}_3\vert < \varepsilon$ , but $\mathbf{r}_1 \neq \mathbf{r}_3$ , since $\vert\mathbf{r}_1 -\mathbf{r}_3\vert > \varepsilon$ . When points are represented procedurally or via implicit algebraic equations, P/P intersection can be typically reduced to comparison of intervals which contain such isolated points. In Hu et al. [180,181] interval point equality is defined in an alternate manner: if the intervals representing the points intersect, assuming these intervals are very small, then the points are considered coincident and a new interval point (the minimal rectangular box with faces parallel to the coordinate planes) is used to replace the two coincident points. With this construction, incidence transitivity is guaranteed in the context of interval solid modeling but at the cost of reduced resolution (accuracy).

**Figure 5.5:** Intersection of points within a tolerance is intransitive
$\begin{figure}\centerline{ \psfig{figure=fig/intransitivity.eps,height=2.0in} }\end{figure}$

Next: 5.4 Point/curve intersection Up: 5. Intersection Problems Previous: 5.2.3 Classification by number Contents Index

December 2009