What is an arrangement?

2D: n lines in a plane

  vertices (0D, intersection of 2 lines)
  edges (1D, piece of a line)
  faces (2D, subregions of the plane)

example of arrangement in 2D with straight lines

Complexity of the subdivision: O(n²) (O(n²) vertices, O(n²) edges, O(n²) faces)

3D: n planes in a volume

  vertices (0D, intersection of 3 planes) 
  edges (1D, piece of the intersection of 2 planes)
  faces (2D, piece of one of the input planes)
  cells (3D, subregions of the volume)

etc. for higher dimensions... Complexity O(n^d)
NOTE: We are dealing with "simple" arrangements. No more than 2 lines intersect at any point, and no two lines are parallel.

What do we use arrangements for?

  Find the convex hull of a set of points:
      make an arrangement from their duals (lines) 
      and find the cell with sign assignment 
      (+, +, +, + ... )

  Linear Programming
      many dimensional arrangements of hyperplanes

  Visibility 
      an application of 3D arrangements 
      (more on this later)

  Robot motion planning
      an application of arrangements with curves 

robot which has 2 degrees of freedom, angle & length in an environment with obstacles



the arrangement induced by the gray boundaries and red & blue obstacles

How do we build it?

lines in 2D (or planes in 3D):

  plane sweep algorithm  O(n2 log n)
  incremental algorithm  O(n2)

incremental algorithm adds each of n lines, one at a time, n work required per line: O(n²)

zone theorem provide an upper bound of O(n) for each line inserted into the arrangement

curves in 2D:

The complexity of an arrangement of n curves is greater than that of an arrangement of n lines. If the degree of the curves is bounded, then the upper bound of the complexity of the arrangement can be computed.

examples of curves that don't cross, curves that cross multiple times, and a curve that self-intersects

Better idea... make an approximation with a quadtree

For each node in the tree, determine for each curve in the arrangement whether:

  a) curve intersects node
  b) node is completely on left side of curve
  c) node is completely on right side of curve

When do we split a node?

  When the sign assignments are not all
  homogeneous (at least one of the curves 
  intersects the node).

How do we determine if a curve intersects a given node?

  We could use root-finding to determine exactly 
  if the curve intersects the node, OR

  Assuming we can find bounding box for the curve,

  If a bounding box of the curve doesn't intersect 
  the node, then the curve also doesn't intersect 
  the node.

EXAMPLE: A bounding box of the bezier curve is the convex hull of its control points.

Bezier curve with 4 control points:

   P1  P2  P3  P4
   Q(t)  =  (1-t)3P1 + 3t(1-t)2P2 + 3t2(1-t)P3 + t3P4

Can be split into 2 new Bezier curves:

   P1      (1/2)(P1+P2)  Q(0.5)-(1/6)Q'(0.5)  Q(0.5)
 Q(0.5)  Q(0.5)+(1/6)Q'(0.5)  (1/2)(P3+P4)      P4

successive subdivision of the curve quickly leads to a chain of minimal area bounding boxes

How do we determine which side of the curve a node of the tree is on?
(once we have determined it doesn't intersect any of the curves)

   For a closed curve,

   From any point on a face, we shoot a ray to 
   infinity.  If the ray crosses the curve an 
   even number of times, we say we are on the 
   LEFT side of the curve.

a curve with some rays - the red rays are on the RIGHT side, the blue rays are on the LEFT side

Another neat trick: Locate where the curves intersect

We can also zero in on the intersections of these curves. If we keep splitting the tree until there is either at most 1 curve through the tree node, or we have reached some specified minimum node dimension, then only the area around intersections of 2 (or more) curves will be divided most finely.



example of an arrangement of curved lines with curve intersections highlighted.

DEMO!

What about curved surfaces in 3D?

Same ideas as above apply for finding cells. Just use an octree.

References