Convex Polygon

This example neatly demonstrates matrix manipulation, and how to access particular elements of a matrix. Furthermore, the problem and solution can be examined graphically.

Consider a polygon: imagine the vertices are represented by Cartesian co-ordinates (x1,y1), (x2,y2) etc, and these points are connected to produce a (closed) polygon. Suppose we next take any of the polygon co-ordinates, and travel around the polygon (in either direction) and return to our starting point. The polygon is said to be convex if we travel either continuously clockwise, or continuously anti-clockwise. If a polygon fails this test, it is said to be not convex.

The following are examples of convex and not-convex polygons:

The above polygons are represented by the respective co-ordinates: 

and 

where the last data points are the same as the first, to allow the plots to 'join up'.

By considering the vertices, it can be shown that the polygon is convex if all the vertices are either positive or negative. The mathematical formula to establish the sign of the vertices is:

(x2 - x1).(y3 - y2) - (y2 - y1).(x3 - x1)

where (x1,y1),(x2,y2), and (x3,y3) are the first three co-ordinates of the polygon. (At this stage, just three connected points would represent a triangle, which one instinctively thinks of as being convex). Once these points are evaluated in the above formula, the sign of the result is noted. The sign of the next co-ordinate is considered: (x2,y2),(x3,y3),and (x4,y4). If the sign is the same, the points thus far form a convex polygon. As we proceed around the co-ordinates, should the sign change, the polygon is no longer convex. As we are dealing with a closed polygon, the data points (x_n+1,y_n+1) and (x_n+2,y_n+2) are represented by (x1,y1) and (x2,y2) respectively.

By entering the above co-ordinates as a matrix, it is possible to plot these points. To join them up, when in the 2-D plot window, select options/display/points/connect. To join up the loop, we need to add the first set of co-ordinates to the bottom of the matrix.

To test the sign of the first co-ordinate, a routine could be written thus:

Here, r1 is the name of the routine,  a is the matrix of points, and n is the increment. In the above example of a convex polygon:

r1(a, 1)

-5

which is negative. Repeating for the next two points:

r1(a, 2)

-2

and

r1(a, 3)

-4

All are negative so far - hence a convex polygon (so far!). To establish the sign of the last two points, we need to modify the r1 routine. At the point n-1:

and at the point n:

When r2 and r3 are simplified for (n-1) and (n):

r2(a, 4) = -4

r3(a, 5) = -4

Again, all the same sign (negative). Hence, the polygon is convex.

To automate this routine, the following code could be used. While there may be more efficient ways of coding the routine, it is intended to be as readable as possible:

Hence, 

rout(a)

convex

This is entered in the Derive Entry line as:(we recommend you copy and paste)

rout(a, n, x1, x2, x3, y1, y2, y3, ans, rotation) := PROG(n := 2, x1 := a™n™1, x2 := a™(n + 1)™1, x3 := a™(n + 2)™1, y1 := a™n™2, y2 := a™(n + 1)™2, y3 := a™(n + 2)™2, ans := (x2 - x1)·(y3 - y2) - (y2 - y1)·(x3 - x1), rotation := SIGN((a™2™1 - a™1™1)·(a™3™2 - a™2™2) - (a™2™2 - a™1™2)·(a™3™1 - a™1™1)), LOOP(IF(n > DIM(a) - 3, exit), IF(rotation·ans < 0, RETURN "not convex"), n :+ 1), n :+ 1, x3 := a™1™1, y3 := a™1™2, IF(rotation·ans < 0, RETURN "not convex"), n :+ 1, x2 := a™1™1, x3 := a™2™1, y2 := a™1™2, y3 := a™2™2, IF(rotation·ans < 0, RETURN "not convex"), RETURN "convex")

Hint: if you are viewing the above code via a computer that does NOT have Derive 5 installed, the great many down-arrow symbols may appear as 'trademark' symbols:  " ™ " . Don't worry; when pasted into Derive, these trademark symbols automatically change back to the down-arrow!