From: rcskb@minyos.xx.rmit.oz.au (Kendall Bennett)
Newsgroups: comp.graphics
Subject: Re: Simple Convexity Working Group (preliminary report)
Date: 9 Nov 1992 01:58:44 GMT
Organization: RMIT Computer Centre
NNTP-Posting-Host: minyos.xx.rmit.oz.au

Kenneth.Sloan@freudsys.nl.mugnet.org (Kenneth Sloan) writes:

>Organization: CIS, University of Alabama at Birmingham

>>...A polygon is either 
>>convex, or non-convex.

>Is the following polygon "convex"?

>0 0
>1 0
>1 1
>0 0 
>1 0
>1 1

In my books it definitately is. It is not simple, but it is convex. Why
would you ever need to handle this sort of poly except in dicussions about
whether they are convex or not?

>>... Mathematical definitions of convex polygons abound,

>Please supply a pointer to an unambiguous, complete, authoritative
>definition.  Definitions of convex sets abound.  Polygons (as we have
>been treating them) , on the other hand, are *boundaries* - not the
>interior.  The *path* of the boundary curve counts just as much as the
>set of points enclosed by the boundary.

Polygons are generally used to model the set of points contained within
the polygon boundary. How do you think you get the definition of which 
pixels to draw for self intersecting polygons? Convex sets are bounded
by convex polygons. In the paper that I mentione by Chazelle and Dobkin,
a good defintion of a convex polygon is given. Obviously not complete
and authoritative, since you would naturally find some counter example
which no-one would ever see in practice.

>>so why the need to say that it is convex and SIMPLE? If it is convex, it
>>MUST be simple.

>Oh really?  See the polygon above.  Is it "convex"?  Is it simple?  How
>about this one:

Ok, so it may be non-simple but still convex as in the above example.

>0 0
>2 0
>1 2
>1 1
>1 2

>Is it convex?  Is it concave?  Is it simple?

It is concave. It is also simple in my books. It has two co-incident edges
in it bounding an empty set of points, but if your traces it's border
it is concave (ie: non-convex, you could scan convert this poly with a 
general polygon scan conversion routine).

>> If it is not convex, then it must be concave.

>Why is it necessary to bring in the concept of "concave"?  We started
>with "convex", and "simple", and constructed two classes: "convex and
>simple" and "not convex or not simple".  Why do you need "concave"?

You don't. But why can't you simply say convex or not convex?

>By the way...we're still waiting for your code.

Yeah well, it is all hot air at the moment. I haven't had time to work
on it, and I don't know when I will. Choose a winner without me :-)

+------------------------------------------+-------------------------------+
| Kendall Bennett                          | Internet:                     |
| RMIT Advanced Computer Graphics Centre   | kjb@citri.edu.au              |
| CITRI Building, 723 Swanston Street      | rcskb@minyos.xx.rmit.oz.au    |
| Carlton Victoria 3053 AUSTRALIA.         |                               | 
+------------------------------------------+-------------------------------+
| CoSysop (Bossman), PC Connection Australia:               +61 3 688 0909 |
+--------------------------------------------------------------------------+