[comp.graphics] Polygon-related questions

stolfi@jumbo.dec.com (Jorge Stolfi) (07/14/88)

Vallury Prabhakar writes:
>
>   I have a given set of points some of which form the vertices of
>   a polygon while the rest are "interior" to the polygon.  I would
>   like to be able to determine which of these points form the vertices
>   of the polygon, and the others which are internal.

Roger Crawfis writes:
>
>   I have a bunch of 3D scattered data points and want to form a
>   solid 'blob' around them.

Here are some references for the convex hull of n points in 2 and
3 dimensions:

    A: {F. P. <Preparata> and I. M. <Shamos>}
    T: {Computational geometry: An introduction}
    P: {[Book] Springer Verlag, NY (1985).}

    A: {R. <Sedgewick>}
    T: {Algorithms: Chapter 25}
    P: {[Book] Addison-Wesley (1983).}

    A: {E. W. <Dijkstra>}
    T: {A discipline of programming: Chapter 24}
    P: {[Book] Prentice-Hall (19??).}
    
    A: {F. P. <Preparata> and S. J. <Hong>}
    T: {Convex hulls of finite sets of points in two and three dimensions.}
    P: {Comm. ACM Vol. 20 No. 2 (Feb. 1977), 87--93}
    C: {$O(n\log n)$ worst-case algorithms based on divide-and-conquer.}

    A: {R. L. <Graham>}
    T: {An efficient algorithm for determining the convex hull of a
    finite planar set.}
    P: {Information Processing Letters Vol. 1, 132--133 (1972)}
    C: {An $O(n\log n)$ algorithm based on polar sorting.}

    A: {W. F. <Eddy>}
    T: {A new convex hull algorithm for planar sets.}
    P: {ACM TOMS vol. 3 (1977) 398--403.}
    C: {A simple $O(n)$ expected-time algorithm.}

    A: {P. J. <Green> and B. W. <Silverman>}
    T: {Constructing the convex hull of a set of points in the plane.}
    P: {The Computer Jounal Vol. 22 No. 3 (date??), 262--266}
    C: {Practical notes on implementing Eddy's algorithm. Benchmarks.}

    A: {R. A. <Jarvis>}
    T: {On the identification of the convex hull of a finite set of points in
    the plane.}
    P: {Information Processing Letters Vol. 2, 18--21 (1973)}
    C: {A simple $O(n h)$ algorithm ($h={}$size of convex hull).}

    A: {A. M. <Andrew>}
    T: {Another efficient algorithm for convex hulls in two dimensions.}
    P: {Information Processing Letters Vol. 9 No. 5 (Dec. 1979) 216--219.}

    A: {L. J. <Guibas> and J. <Stolfi>}
    T: {Primitives for the manipulation of general subdivisions and the
    computation of Voronoi diagrams.}
    P: {ACM Transactions on Graphics Vol. 4 No. 2 (April 1985),
    74--123.}
    C: {Data structure for representing the hull.}
    
    A: {S. G. <Akl> and T. <Toussaint>}
    T: {A fast convex hull algorithm.}
    P: {Information Processing Letters Vol. 7 No. 5 (Aug. 1978), 219--222.}

    A: {J. L. <Bentley>, M. G. <Faust>, and F. P. <Preparata>}
    T: {Approximate algorithms for convex hulls.}
    P: {Comm. ACM Vol. 25, 64--68 (1982)}
    C: {Approximate algorithms, in linear time.}

    A: {D. G. <KirkPatrick> and R. <Seidel>}
    T: {The ultimate planar convex hull algorithm?}
    P: {SIAM J. On Computing vol. 15 (1986), 287-299.}
    C: {An $O(n \log h)$ algorithm.}

    A: {D. <Avis>, H. <ElGindy>, and R. <Seidel>}
    T: {Simple on-line algorithms for convex polygons.}
    P: {In "Computatonal Geometry", ed. by G. T. <Toussaint>, 
    North-Holland, Amsterdam (1985), 23--42.}
    C: {Updates the convex hull of $n$ points in the plane after adding
    a new point, in $O(\log n)$ time (no deletions?).}

    A: {R. L. <Graham> and F. F. <Yao>}
    T: {Finding the convex hull of a simple polygon.}
    P: {Journal of Algorithms Vol. 4 (1983), 324--331. }
    C: {$O(n)$ if the points are vertices of a polygon, in order.}

    A: {A. <Maus>}
    T: {Delaunay triangulation and the convex hull of $n$ points in expected
    linear time.}
    P: {BIT Vol. 24 (1984), 151--163.}

    A: {E. <Soisalon-Soininen>}
    T: {On computing approximate convex hulls.}
    P: {Information processing letters Vol. 16 (1983), 121--126.}
    
    A: {G. <Swart>}
    T: {Finding the convex hull facet by facet.}
    P: {Journal of Algorithms Vol. 6 (1985), 17--48.}

    A: {S. <Hertel>}
    T: {An almost trivial convex hull algorithm for a presorted point set
    in the plane.}
    P: {Technical report A 83/08, FB 10, Univ. of Saarland (1983).}

Jim Lewis writes:
>
>   Why don't you try adapting one of the standard convex hull
>   algorithms to 3-D?  For example, with 3 axes you will usually
>   be able to find 6 unique extremal points (max/min coordinate values
>   for each axis); these points are guaranteed to lie on the hull,
>   and you can discard any points interior to the solid defined by
>   the extremal points.  Now rotate the axes a bit, recompute the
>   extremal points among those not on the current hull, and discard
>   any points inside the new solid.  Continue until you account for
>   all the points.  I don't know how that might compare asymptotically
>   to the optimal algorithm, but at least it's guaranteed to work,
>   even for pathological cases.

I don't think anything this simple is going to work in 3D.  If on
each pass you keep the extremal points that you found in the previous
passes, then there is no bound on the number of passes you must make
to classify all points.  If on the other hand you put the previous
extremal points aside, then on the next pass you may incorrectly
classify interior points as extremal.

Besides, what do you mean by "rotate the axes a bit"?  Around what, and
by how much?  You seem to be thinking of Eddy's algorithm for 2D; but
in that algorithm each pass looks for the extremal points in the
directions perpendicular to the edges of the hull found in the previous
pass.  In 3D, you should do the same for all directions perpendicular
to faces of the previous hull, so you must know what those faces are.
Indeed, all 3D convex hull algorithms that I know must keep track of
the hull's combinatorial structure (edges, vertices, and faces).  

Hope this helps,

                Jorge Stolfi @ DEC Systems Research Center
                stolfi@src.dec.com, ...!decwrl!stolfi

crawfis@lll-lcc.aRpA (Roger A. Crawfis) (07/14/88)

I appollogize for my misprint in the original posting, but what I 
meant to say is:  What if we do not want the convex region, but 
rather want to get some sort of concave polygon (or polyhedron) from
the points?  My feeling is that this will be ill-defined.

For example, if we had the 2D scattered data points:

        x                             x


        x    0   0     0      x   0 0     x


               x                       x

where I will call the x's exterior points and the 0's interior points.

The blob we are looking for consists of the x's.  However note that in
this case there are 2 such blobs, one with the middle x (on the 2nd line)
connected with the top and one with it connected with the bottom (a third
could also be with the middle point connected to both the top and the
bottom, but in 3D I want a solid non-disjoint blob).  Now the convex hull
can probably be applied to sections of this at a time, but what sections?
This also leads to some sort of partitioning problem as I mentioned 
earlier.  Any more ideas?

Roger A. Crawfis
Lawrence Livermore National Lab