From: hollasch@kpc.com (Steve Hollasch)
Subject: Re: wierd polygons (was Re: Determining if a polygon is convex)
Organization: Kubota Pacific Computer, Inc.
Date: Thu, 15 Oct 1992 03:35:28 GMT

fred@kpc.com (Fred Fisher) writes:
> Does anyone know a nice quick way to determine if a polygon is convex?

zhu@sgi.com (Benjamin Zhu) writes:
| (1) Throw away vertex ordering, and compute the convex hull of
|     these vertices. If the computed convex hull is identical to the
|     original polygon, the old polygon is convex. Otherwise, not!

hollasch@kpc.com (Steve Hollasch) writes:
>                                                 0 _____ 3
>                                                   \   /
>                                                    \ /
>     This fails for a bow-tie polygon, i.e.:         X
>                                                    / \
>                                                   /   \
>                                                 2 ~~~~~ 1

bouma@cs.purdue.EDU (William J. Bouma) writes:
|    This is true, but it is only useful in theory.  I have written a lot of
|    code to manipulate polygons and have never seen a polygon like this.  If
|    my code ever produced a polygon like this I would either shoot it, or
|    have it insert two new points where the X is.  Does anyone really use
|    (allow) polygons where the edges cross?  For what reason?
| 
|    As far as I am concerned, taking the convex hull is a practical and fast
|    solution to the given problem.  It annoys me when theoreticians bring
|    up these degenerate cases that never arise in practice to claim that an
|    algorithm doesn't work.  If my code avoids those cases, then it does
|    not fail for them.
| 
|    If the original poster was asking a theoretical question, never mind.

    I assure you Fred & I are asking a practical, not a theoretical
question.  Allow me to annoy you further.

    In computer graphics, the fabulous world of modeling is often separate
from the dirty world of rendering.  As a modeler, I have control over the
type of polygons I generate, and with little additional effort can USUALLY
generate nice, simple polygons (not self-intersecting, ordered vertices,
etc.)

    Writing a renderer is a very different subject, though.  In PEX, you can
provide polygons that are convex, concave, self-intersecting, or unknown.
OpenGL doesn't officially include such beasts, but it provides a software
library to handle them.  Yes, these things actually exist.  Yes, robust and
complete rendering libraries should be able to handle, or at not choke on
these sorts of polygons.

    I'm surprised that you seem to believe that a simple bow-tie polygon
would never arise in a real-world situation.  Let me share one.  Some of
the code I've worked with models torii with a quadrilateral tesselation.
All of these quadrilaterals should be nice and behaved, right?  Well, when
the user specifies a torus so fat that it intersects itself, you get
bow-tie polygons at the intersection "dimples".  I happened to _like_ the
look of the Doubly-Dimpled-Ball (tm), and would hate to have had the
rendering code limit the modeling code.  You may argue that a self-
intersecting torus is too "theoretical", but there's nothing magical about
it, and any decent rendering library should be able to display it.

    Would you propose outlawing reflection and mirror transformations
also?

______________________________________________________________________________
Steve Hollasch                                   Kubota Pacific Computer, Inc.
hollasch@kpc.com                                 Santa Clara, California
Newsgroups: comp.graphics