Draw Orthogonal Polygons (original) (raw)

Draw Orthogonal Polygons

URI:	http://herbert.gandraxa.com/herbert/dop.asp
Link template:	Draw Orthogonal Polygons
Link symbols:	On current page | On this site	On external site	Wikipedia article	ZIP archive	PDF	E-Mail

Article

Organization

Home » Articles» Draw Orthogonal Polygons

Scope

This article describes, how a simple orthogonal polygon expressed as a list of vertex coordinates can be efficiently drawn into a bounding rectangular area such, that the interior of the polygon is given a distinct value unequal 0 and the exterior a value of 0 (or vice-versa).

Using the binary values 1 and 0 is most useful to obtain an area mask for a given polygon. Several such area masks can then easily be tested against each other in a variety of ways to determine polygon unions, polygon intersections etc.

Note, however, that the method described here is not restricted to binary values: one of the values in fact can be any value unequal to 0, which makes the method interesting also for other purposes, like e.g. drawing the polygon's content in any RGB color directly onto a black canvas (i.e. a part of the screen, assuming that the bounding rectangle consists of an initially black area, which in RGB is represented with 0).

Author

Herbert Glarner

Published

2007-Jan-16

External Links

Terms

The Canvas

We define the needed terms by setting up an example, which will accompany us through the whole rest of the article.

Assume, that we are given a bounding rectangle of an arbitrary 12 x 12 subareas (e.g. pixels on a screen, bits in words), into which our polygon shall be drawn.

The abscissa (x axis) of the bounding rectangle runs from the left to the right as usual in Cartesian coordinate systems, but the ordinate (y axis) runs from the top to the bottom (rather than the usual bottom up) to better reflect typical computer screens.

Because we will need to clearly distinguish between upper and lower, and left and right, resp., it is advantageous to enumerate the vertical and horizontal lines in between the subareas (represented by the white squares in fig. 1), not the squares themselves in between two such line pairs. The 13 lines on each axis are enumerated from 0...12 as follows:

Fig. 1: The canvas

For the rest of the article is valid, that white squares represent the value unequal 0, indicating that such are part of the polygon. Accordingly, black squares shall signify 0 and thus "not part of the polygon".

The Polygon

Now assume, that we are given a simple orthogonal icosagon (20-gon) with a list of vertices, given in "screen" coordinates as defined above.

Because we need to know, which side needs to be treated as the inside of the polygon (and accordingly which one as its outside), we must define a direction in which we want to traverse the polygon's vertices.

Arbitrarily, we define to list the vertices in a clockwise direction, with the implication, that the interior of the polygon lies on the right side of the edges as we travel around the polygon.

This is the list with the vertex coordinates for our example:

Coordinates are given in x/y notation.

As per agreement we want to render the polygon's interior in white (signifying the non zero value) and its outside in black (the zero value). Therefore this is how our polygon eventually must look like:

Fig. 2: The desired result

The intent of this article is to show, how this result can be obtained by processing each vertex just once, without the need to compare opposite bounds in a time-consuming way.

The Algorithm

Preprocessing

The presented algorithm will set the subareas (pixels, flags, in the examples rendered as squares) of the outside area of the polygon to 0, leaving the interior as it was before.

This implies, that an initial preprocessing task must be performed to obtain a completely "painted" canvas in the dimensions of the bounding rectangle, i.e. the whole bounding rectangle must initially be set with the non zero value. Compare with fig. 1: the canvas is white, which is the "interior" color.

Omitting this preprocessing step will result in the complement of the desired result, i.e. white and black areas are reversed (which can be useful, depending on your application).

Processing

For each vertex, we consider the edge pair consisting of the edge which leads to it (approaching edge) and the one moving away from it (receding edge). (This means, that although we process only the 20 given vertices, ultimately we need to consider 20 adjacent edge pairs, and thus a total of 21 edges: the first vertex' approaching edge also is the last vertex' receding edge.)

Assuming, that coordinates are only given at points at which the direction changes (there is no reason to mark a vertex anywhere else along an edge), the two edges at the vertex can only form an angle of either 90° or then of 270° (else it would not be an orthogonal one). This has the notion of a corner, which term we will use from now on whenever we mean two consecutive edges meeting at a vertex. There are as many corners as there are vertices: in our example there are 20.

What we primarily are interested in, is the direction of each of the corners. Let's have a look at the first corner.

First corner? This requires some elaboration. Which one is the first corner, the one consisiting of the first vertex? Well, it does not matter, which corner we declare to be the first, as long as we process them all. However, in an actual implementation it turns out to be advantageous if we declare the corner around the second vertex to be the first corner. This is because we need to find the direction of the approaching edge, which for the corner including the first vertex originates at the last vertex of the polygon. This last vertex usually still is out of scope, and depending on implementation, possibly will not be known before having processed the whole vertex list. This is not the case for the second vertex, though: for it, the approaching edge originates at the very first vertex, which is known right from the beginning.

Throughout all following examples, we will mark corners by coloring the two involved edges red. Note, that an arrowhead at the end of the receding edge marks the direction in which we travel (clockwise, as defined above). For the first corner, see fig. 3, we speak of a "right/down"-corner (or RD corner for short), because the approaching (first) edge goes to the right and the receding (second) edge goes downwards.

Fig. 3: An RD corner

How many distinctive corners are there? Well, the approaching edge can point to any of the 4 possible directions left, right, top and down, and so can the receding edge.

However, because a corner has an angle of either a 90° or 270° angle, not all 4 x 4 combinations are possible: in fact, only 8 combinations are possible, because for either one of the 4 possible approaching edges, only 2 "continuations" are possible (the other two possibilities would mean "continue into the same direction", and "go back into the direction where we came from", both resulting in a degenerated corner, i.e. a straight line).

It should come as no surprise, that our icosagon contains corners in all possible combinations. The following table shows a specimen of each. The two-letters-abbreviation above the figure identify the directions of the two edges (where R=Right, L=Left, D=Down, and U=Up).

Note, that if we just looked at the directed edges, we can distinguish 4 clockwise corners and 4 counterclockwise corners: although they involve the same edges and meet at the same vertex location, their direction is different and consequently they are named differently.

RD corner	DL corner	LU corner	UR corner
Clockwise corner
UL corner	RU corner	DR corner	LD corner
Corresponding counterclockwise corner

Fig. 4: All possible corners

Corners being positionally identical with the exception of the direction belong to a different set and therefore also must be treated different. Therefore it is surprising, that the same is not the case for corner pairs which involve the same directional edges (because they indeed look different). Despite the apparent difference, it is irrelevant in what order the edges appear (i.e. if a particular edge is approaching or receding): For example is a DR corner treated absolutely like an RD corner when processed.

Therefore, we in fact only have to consider 4 distinct corner types, identifiable by the corner's constituting edges. Just mark, say in a bitfield, which two edges belong to the corner, and mark them as to the left, to the right, upwards or downwards. Thus, 4 bits suffice to tell which 2 of the 4 possible edges are involved.

Notice, that in fact two bits would be enough, because either a left or a right edge must be present, as well as must either an upward or downward edge. Such, we could define horizontal instead of to the left and to the right, and accordingly vertical instead of upward or downward. Then we only would need to define, what 0 and 1 mean, and could go along with two bits. However, for sake of simplicity we will continue to use the more explicit 4 values without the burden of an imposed definition.

To easily point out involved edges, let's assume, those 4 bits are in a dedicated position within a word. Somewhat arbitrarily we define that order to be L, R, U and D from the most significant to the least significant bit, as follows:

Fig. 5: One bit per edge

Whenever we refer to a corner, the two not appearing edges will be greyed out, e.g.:

Fig. 6: Greyed out positions

Recall, that it does not matter which edge appears first. Above figure means either "first to the left, then downward", or "first downward, then to the left".

These are some examples of the possible 4 groups:

Present edges	Clockwise	Counterclockwise

Fig. 7: The 4 corner groups

Once we have determined, which of the 4 cases is applicable for the corner actually being processed, we proceed by identifying the four quadrants within the bounding rectangle.

The quadrants are defined by extending the two involved edges, in such a way, that the involved vertex at the given coordinate separates the whole surrounding rectangle into 2 x 2 halves.

As an example on how to identify the 4 quadrants, consider the 6th corner with the coordinates 8/5:

Fig. 8: Identifying quadrants

One of these quadrants is now manipulated by XORing it: this means, if a subarea (pixel) currently has the value 0 (represented by a black square), it is replaced with our non zero value (represented by a white square); but if it already has that non zero value, then it is replaced with a 0.

Remains only to set out the rule, which quadrant needs to be treated that way. Here it is:

The manipulated quadrant is in that half, which is opposite of the receding edge. Of the two quadrants in that half, choose the one which is adjacent to the approaching edge.

For our example with the 6th corner this translates this way: the receding edge points to the right, thus the quadrant in question must be to the left; and because the approaching edge is in the lower half, our candidate must be the lower left quadrant:

Fig. 9: Choosing the correct quadrant

Notice, how the involved (directed) edges just need to be negated in order to directly obtain the affected quadrant:

Involved edges
Affected quadrant after negation
Read result as:	Upper right	Upper left	Lower right	Lower left

Fig. 10: Negating quadrants

Notabene, that the black squares in fig. 9 (and in the following quadrant figures) does not imply, that all subareas within the bounding rectangle are converted from 1 to 0. It rather means, that the actual content of each affected subarea (black square) is XORed with our non zero value, writing back the result of the operation as the subarea's new content. Such, depending on what was present before the operation, each individual subarea within the quadrant is "set" or "cleared" individually.

Well, that's all what there is about it. Applying this technique for each corner leaves us with the desired result. This is shown in the next section, step by step for all 20 corners.

Example

Step	Involved Corner	Flags	XOR Quadrant	Result
Preprocessing
Corner 1
Corner 2
Corner 3
Corner 4
Corner 5
Corner 6
Corner 7
Corner 8
Corner 9
Corner 10
Corner 11
Corner 12
Corner 13
Corner 14
Corner 15
Corner 16
Corner 17
Corner 18
Corner 19
Corner 20

Fig. 11: Step-by-step simulation for the example polygon

After having processed the last corner, we are left with the desired representation as initially defined in fig. 2.