Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.milw.wisc.edu!lll-winken!uunet!mcvax!unido!uklirb!incas!mdoerr
From: mdoerr@incas.UUCP (Michael Doerr)
Newsgroups: comp.graphics
Subject: Computational geometry
Message-ID: <2053@incas.UUCP>
Date: 27 Apr 89 13:38:01 GMT
Organization: University of Kaiserslautern, W-Germany
Lines: 49


Although I've followed nearly all of the Point-In-Polygon and similiar
geometry-related discussions on comp.graphics I've never seen the
following subject discussed before:
	How does one determine _reliabely_ (!!!) the winding sense (clockwise
	or counter-clockwise) of the sides of an arbitrary polygon?
	By arbitrary polygon I mean the interior of a closed region of
	the plane that is defined by a circular list of vertices that
	are connected by straight line segments. The lines may touch or
	(partially) overlap, but mutual intersections are not allowed.
	Additionally one vertex may be shared by more than two line segments.
	That is, polygons may be convex or concave, but not self-overlapping.

I've come up with the following algorithm and would like to know whether
it is correct:
	1. Select an arbitrary vertex of the polgon.
	   Tranlate the polygon so that this vertex is placed into
	   the origin (0, 0).
	   Set SUM = 0.
	2. FOR each pair of vertices along the sides of the polygon DO
	   a)	Compute the ANGLE that is subtended by each side with
		respect to the reference vertex (selected in step 1).
		This usually involves an expensive arctan operation.
	   b)	Compute SUM = SUM + ANGLE
	3. IF SUM > 0 THEN   winding sense of polygon boundary is CCW
	   IF SUM < 0 THEN   winding sense of polygon boundary is CW
	   IF SUM == 0 THEN  polygon is in some way degenerate (?????)

I hope someone can answer the following questions:
	1. Does the above stated algorithm really compute
	   the correct winding sense?
	2. If question 1 has to be answered with NO:
		Please send me references, hints, programs, etc.
		for a working algorithm.
	3. If questions 1 can be answered with YES:
		How could the algorithm be improved, so that less
		expensive operations are required?
	4. In which way is the polygon degenerate, if SUM == 0?
	5. Can this algorithm also be applied or extended
	   to self-overlapping polygons?

Many thanks in advance, Michael.


Michael "The Turtle" Doerr			%% /-------\ %%
CS Department (FB Informatik)			  %  o   o  %
University of Kaiserslautern			-{ o   o   o }==O
D-6750 Kaiserslautern (West Germany)		  %  o   o  %
uucp: ...!uunet!unido!incas!mdoerr		%% \-------/ %%