[comp.graphics] Polygon identification method needed

rustcat@csli.STANFORD.EDU (Vallury Prabhakar) (01/21/89)

Hello, 

  The problem is as follows:

  Given a set of end-points of lines, I wish to identify/reconstruct all
  the polygons formed by these lines.  The available information is:

  (1) All these lines belong to 1 or more polygons.
  (2) The polygons may share common edges, vertices or be disjoint.
  (3) There are no partially overlapping polygons.  Only connected ones. 
      [This is only to avoid ambiguity in interpretation.]
  (4) A polygon may however be completely inside another without sharing
      any edges.  [A "hole"]
  (5) Polygons may be convex or concave.
  (6) A polygon may be defined by the sequence of its bounding edges.

I would be very grateful if somebody could either suggest some references
or a solution to the above.  Thank you.

						-- Vallury Prabhakar
						-- rustcat@csli.stanford.edu