RedBlue Intersection Detection Algorithms, With Applications to Motion Planning and Collision Detection Classic Reprint

Excerpt from Red-Blue Intersection Detection Algorithms, With Applications to Motion Planning and Collision Detection

In this section, we give an efficient algorithm for the case when the red arcs in F are non-intersecting line segments which form the boundary of a simple polygon 13 (see figure 1) or, more generally, non~intersecting Jordan arcs whose union is the boundary of a simply-connected region. Let a(i) denote the arrangement of I (i.e. The planar map induced by these arcs; its vertices are the intersection points of the arcs and their endpoints, its edges are maximal connected subsets of the arcs which do not contain any vertex, and its faces are maximal connected subsets of the plane which do not contain any vertex or edge). Let 2 denote any fixed point on 613. The following Lemma is a simple but a key observation which allows us to obtain an efficient algorithm.

Lemma Let f be the face of a(i) containing the point 2. Then 63 and I intersect if and only if and 68 intersect.

About the Publisher

Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com

This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.