Dresden Algorithmics Channel: Module 8

The monograph [1] gives an interesting compact notation for the area A of a polygon where the P_i ; i = 1(1)n are given by their Cartesian coordinates (x_i, y_i) (Fig. 1, see also [2, 3]).

Fig. 1:

Polygon
(a) convex, (b) concave (not convex)

In usual notation we have

	(1)
.	(2)

The determinant representation Equ. (2) is now compressed into

(3)

the actual computation of the area A is done by repeated application of the Sarrus rule for the second order determinant as shown in Equ. (3) (Sarrus generalization). Thus Equ. (1) can be immediately obtained from Equ. (3).

Obviously, for n=3 and n=4 Equ. (3) can formally be seen as determinant representations, which are reduced to the coordinate parts:

	(4)
	(5)

In Module 2 and Module 5 we have already applied and discussed the cylinder notation of Equ. (3) for n=4 and n=3 resp. We shall now generalize and explore this approach further.
Evidently, the final column (identical to the first column of the rectangular scheme)

(6)

is added in order to generate the last two summands in Equ. (1).
Thus, this column can be dropped when

one thinks the columns 1,2,3,..,n to be transferred to a cylinder which is divided into n equally-sized segments (see Fig. 2(a)),

the summands (x_iy_i+1- x_i+1y_i) and (x_ny₁ - x₁y_n) resp. are sequentially read by a moving road head (see Fig. 2(b))

and added up in an accumulator, which finally reveals A(P₁,P₂,P₃,...,P_n).

(a)

The read head´s direction of move,
the data cylinder is fixed

(b)

Fig. 2:

(a) The cylinder representation of Equ. (6),

(b) corresponding read head

From now on we write for the formal cylinder notation of Equ. (6) the following:

(7)

It is based on the idea shown in Fig. 2.
Thus we obtain for Equ. (3)

(8)

8.1.

Verify Equ. (1) using Equ. (2) and Equ. (4) for the convex and concave polygon (see Fig. 1).

8.2.

Examine the relationship of Equ. (1) with the Pick´s theorem [5,6,7]:

The polygon in Fig. 3 has only vertices with integer coordinates (lattice points of the square lattice)

(x_i, y_i)

(9)

In this case the computation of the area A simplifies significantly compared with Equ. (1)

(10)

where

B is the number of lattice points on the boundary of the polygon,
I is the number of lattice points found inside the polygon.

Fig. 3: A polygon in an integer coordinate system (square lattice), Pick´s theorem

B=8, I=21, A=24

8.3.

We consider a noncrossed polygon according to Fig. 1 where the vertices P_i; i=1(1)n are given by their Cartesian coordinates (x_i, y_i).

Using the cylinder notation Equ. (8) formulate a criterion which allows for all P_k to compute from the coordinates (x₁, y₁), (x₂, y₂), (x₃, y₃), ..., (x_n, y_n):
The noncrossed polygon P₁P₂P₃..P_n has at P_k a convex corner.

concave

8.4.

We consider a crossed polygon (Fig. 4) where the vertices P_i; i=1(1)n are given by their Cartesian coordinates (x_i, y_i).

Fig. 4: A crossed polygon

Using the cylinder notation construct a simple filter algorithm which extracts all four-point constellations (see Fig. 5) of a crossed polygon given by their coordinates (ref. Module 2, ex. 2.5).