Browse Prior Art Database

Region-of-Interest Edge Iterator for Geometrical Computation

IP.com Disclosure Number: IPCOM000106515D
Original Publication Date: 1993-Nov-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 8 page(s) / 236K

Publishing Venue

IBM

Related People

Clark Jr, K: AUTHOR [+4]

Abstract

Many geometric computations iterate over one or more sets of bounding edges of shapes, doing a kernel computation on a single edge or pair of edges. For example, the following pseudo-code determines whether two polygons cross each other:

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 15% of the total text.

Region-of-Interest Edge Iterator for Geometrical Computation

      Many geometric computations iterate over one or more sets of
bounding edges of shapes, doing a kernel computation  on a single
edge or pair of edges.  For example, the following pseudo-code
determines whether two polygons cross each other:

Boolean doPolygonsCross ( Polygon poly1, Polygon poly2 ) {
  foreach (Point pt1 in poly1)
    foreach (Point pt2 in poly2)
      if ( doEdgesCross(pt1, pt1.next, pt2, pt2.next) ) return TRUE;
  return FALSE;

      These kinds of programs can often be speeded up by skipping the
kernel computation (here, "doEdgesCross") for edges (edge pairs,
etc.) that lie outside a region of interest (ROI).  For example:

Boolean doPolygonsCross ( Polygon poly1, Polygon poly2 ) {
  foreach (Point pt1 in poly1)
    foreach (Point pt2 in poly2)
      if ( disjoint(shadow(pt1,pt1.next),shadow(pt2,pt2.next) )
        if ( doEdgesCross(pt1, pt1.next, pt2, pt2.next) ) return
TRUE;
  return FALSE;
// NOTE:  shadow(ptA,ptB) the Least Enclosing Rectangle of the two
// points.  disjoint(LER1,LER2) returns TRUE iff the LER's don't
touch

In this case, the simpler functions "shadow" and "disjoint" can
screen out most of the calls to the more complicated function
"doEdgesCross".  This technique, known in the literature as a "boxing
check" or "Region-of-interest check", can be made more efficient by
using the Least Enclosing Rectangles of the Polygons:

Boolean doPolygonsCross ( Polygon poly1, Polygon poly2 ) {
  Shadow s1 = shadow(poly1);
  Shadow s2 = shadow(poly2);
  if (disjoint(s1,s2)) return FALSE;
  foreach (Point pt1 in poly1) {
    Shadow es1 = shadow(pt1,pt1.next);
    if ( disjoint(es1,s2) )
      continue;  // skip the inner loop
    foreach (Point pt2 in poly2)
      if ( disjoint(es1,shadow(pt2,pt2.next) )
        if ( doEdgesCross(pt1, pt1.next, pt2, pt2.next) ) return
TRUE;
    }
  return FALSE;
}

Almost all computation can be skipped if the two Polygons' shadows
are disjoint.  If not, the inner loop can be skipped for all (outer
loop) edges of poly1  whose Shadow is disjoint from poly2's.  Note,
               poly1                                poly2's
               poly1                                poly2's
               poly1                                poly2's
               _____                                _______
however, that we get an improvement in efficiency with some loss of
clarity, since the details of manipulating the shadows now pervade
the program.  Further improvements can be obtained by observing that
many of the tests involved in computing and comparing shadows are
redundant, since the program above takes no advantage of the fact
that on each iteration of both the inner...