Re: Editor advice Needed.

Bernd Kreimeier (Bernd.Kreimeier@NeRo.Uni-Bonn.DE)
Thu, 20 Jun 1996 18:45:45 +0200 (MET DST)

Date: Thu, 20 Jun 1996 18:45:45 +0200 (MET DST)
From: Bernd Kreimeier <Bernd.Kreimeier@NeRo.Uni-Bonn.DE>
Subject: Re: Editor advice Needed.

> From:
> but I Have Looked for this information (Graphics Gems, Book Store)
> and I can not find a working solution.

Not in the Gems?

> The problem is that I can not get the points into a clockwise
> ordering.

I am not sure I understand. Does your algorithm just emit a bunch
of vertices in no particular order? If you just need to determine
whether the polygon is CW or CCW, see
FAQ maintained by Joseph O'Rourke (recommended):

Section 2. 2D Polygon Computations
Subject 2.07: How do I find the orientation of a simple polygon?

Compute the signed area (Subject 2.01). The orientation is
counter-clockwise if this area is positive.

A slightly faster method is based on the observation that it isn't
necessary to compute the area. One can find the lowest, rightmost
point of the polygon, and then take the cross product of the edges
fore and aft of it. [ ...]Code for this is available at (2K).
Subject 2.01: How do I find the area of a polygon?

The signed area can be computed in linear time by a simple sum.
The key formula is this:

If the coordinates of vertex v_i are x_i and y_i,
twice the area of a polygon is given by

2 A( P ) = sum_{i=0}^{n-1} (x_i y_{i+1} - y_i x_{i+1}).

Reference: [O' Rourke] pp. 18-27; [Gems I] Rokne, pp. 5-6.

To find the area of a planar polygon not in the x-y plane, use:

2 A(P) = abs(N . (sum_{i=0}^{n-1} (v_i x v_{i+1})))

where N is a unit vector normal to the plane. The `.' represents the
dot product operator, the `x' represents the cross product operator,
and abs() is the absolute value function.

[Gems II] pp. 170-171.

Perhaps you will find some valuable hints in the QuakeEd sources, see
SetBrush.h/m, on the Source oberview page at

> Does anyone know a solution that will take into account
> concave polygons?

The algorithms quoted above will. However, there cannot be concave
polygons on a Brush. A Brush is a convex polyhedron, and each facet
has to be a convex polygon by definition. Brush-brush intersection
is a different issue.

hope this helps