**
Converting the
line algorithm to only follow edges.
**

void DrawEdge(int x1, int y1, int x2, int y2) { int mn, md; int x_move, y_move; int x_position, y_position; int balance; md = x2 - x1; // Find md. if (md < 0) // If it is negative, { md = -md; // Make mn positive. x_move = -1; // Make x move in a negative direction. } else // else { x_move = 1; // Make x move in a positive direction. } mn = y2 - y1; // Find mn. if (mn < 0) // If it is negative, { mn = -mn; // Make mn positive. y_move = -1; // Make y move in a negative direction. } else { y_move = 1; // Make y move in a positive direction. } // ======================= NEW CODE ======================= if (mn == 0) { // The line is flat, so only one edge point exists. DrawPointAt(x2, y2); // Draw the point. return; } x_step = (md/mn) * x_move; // Find the x value always to step by. md = (md % mn); // Find the new slope for finding the singular // x movements. // ======================================================== x_position = x1; // Set the starting x position. y_position = y1; // Set the starting y position. if (mn < md) // If the x grows faster than y. { balance = md; // Set the balance as positive md. } else // Else { balance = -(mn); // Set the balance as negative mn. } mn = 2 * mn; // Double mn and md which is the equivalent md = 2 * md; // of halving balance. // While not at the last x and y position, go... while ((x_position != x2) || (y_position != y2)) { DrawPointAt(x_position, y_position); // Draw the point. // ======================= NEW CODE ======================= x_position = x_position + x_step; // Always step by this amount. y_position = y_position + y_move; // Always move forward y. balance = balance + md; // Balance x with y. // ======================================================== // =================== CODE REMOVED HERE ================== // ======================================================== // Putting this here insures x gets a chance to move each time. if (balance >= 0) // If the balance leans toward y... { balance = balance - mn; // Balance y with x. x_position = x_position + x_move; // Move x in the correct direction. } } DrawPointAt(x_position, y_position); // Draw the last point. }

**
The edge structure (to make things easier).
**

// The structure to hold edge information. struct EdgeInfo { long balance; // The balance value. long mn; // The x balancing factor. long md; // The y balancing factor. long x_step; // The amount x moves every step down or up y. long x_move; // The amount x moves every time it needs to rebalance. long y_move; // The amount y moves down (usually 1 for drawing polygon). long x_start; // The x position the edge starts at. long y_start; // The y position the edge starts at. long height; // The height of the edge. };

**
Storing points.
**

typedef double real; struct Point { real x, y; } struct Polygon { Point points[20]; Point *start; Point *end; };

**
Setting up the edge structure.
**

void next_edge(int offset, Point *end, Point *start, Point *&points, EdgeInfo &edge) { Point *points_temp; long y_end, x_end; // Save the initial point position. points_temp = points; // Get the y coordinate that will be started at. edge.y_start = (long)points->y; if (points->y < 0.0) edge.y_start--; // Find the position where the height changes. for (edge.height = 0; edge.height == 0; ) { // Get the x coordinate that will be started at. edge.x_start = (long)points->x; if (points->x < 0.0) edge.x_start--; // Move to the next point. points += offset; // Loop if the point went beyond the bounds of the point array. if (points < start) points = end; else if (points > end) points = start; // Make sure this is not looping endlessly. if (points == points_temp) { edge.height = 0; return; } y_end = (int)points->y; if (points->y < 0.0) y_end--; edge.height = edge.y_start - y_end; } // Find md (the slope's denominator). x_end = (int)points->x; if (points->x < 0.0) x_end--; edge.md = x_end - edge.x_start; if (edge.md > 0) // If it is positive, { edge.x_move = 1; // Make x move in a positive direction. } else // else { edge.md = -edge.md; // Make md positive. edge.x_move = -1; // Make x move in a negative direction. } // Find mn (the slope's numerator). edge.mn = y_end - edge.y_start; if (edge.mn > 0) // If it is positive, { edge.y_move = 1; // Make y move in a positive direction. } else // else { edge.mn = -edge.mn; // Make mn positive. edge.y_move = -1; // Make y move in a negative direction. } // Find out the minimum x_step per move in y. edge.x_step = (edge.md/edge.mn) * edge.x_move; edge.md = (edge.md % edge.mn); // Make the denominator reflect the change. if (edge.mn < edge.md) // If the x grows faster than y, { edge.balance = edge.md; // Set the balance as positive md. } else // Else, { edge.balance = -(edge.mn); // Set the balance as negative mn. } edge.mn = 2 * edge.mn; // Double mn and md which is the equivalent edge.md = 2 * edge.md; // of halving balance. }

**
Specifics of drawing the polygon.
**

**
Finally drawing the polygon.
**

void draw_polygon(const Polygon &polygon, unsigned char *screen, const long &screen_height, const long &screen_width, unsigned char color) { int i; real highest_y; Point *start, *end; Point *left, *right; EdgeInfo ledge, redge; // Get the beginning and end of the point array for later reference. start = polygon.start; end = polygon.end; // Find the highest point and set the left and right point to start at it. for (right = start, highest_y = start->y; right <= end; right++) { if (right->y >= highest_y) { left = right; highest_y = right->y; } } right = left; // Choose the highest point. left += 1; if (left->y == highest_y) { right = left; } else { right -= 1; left = right; } // *** Find the initial slopes and destinations. *** // First do the left edge. next_edge(-1, end, start, left, ledge); // Second do the right edge. next_edge(1, end, start, right, redge); // Go until there is no height to go on the left (or right) side. while (ledge.height > 0) { // Set the pixels. for (i = ledge.x_start; i < redge.x_start; i++) { DrawPointAt(i, ledge.y_start); // Draw the point. } // Move down one y. ledge.y_start += ledge.y_move; redge.y_start += redge.y_move; ledge.balance += ledge.md; // Balance x with y since we moved down one. redge.balance += redge.md; // Balance x with y since we moved down one. // *** Update the left edge. *** // First move the point in the x direction. ledge.x_start += ledge.x_step; if (ledge.balance >= 0) // If the balance leans toward y ... { ledge.balance -= ledge.mn; // Balance y with x. ledge.x_start += ledge.x_move; // Move x in the correct direction. } // Check to see if we are starting a new edge. if (--ledge.height <= 0) { // Moving to a new edge. next_edge(-1, end, start, left, ledge); } // *** Update the right edge. *** // First move the point in the x direction. redge.x_start += redge.x_step; if (redge.balance >= 0) // If the balance leans toward y ... { redge.balance -= redge.mn; // Balance y with x. redge.x_start += redge.x_move; // Move x in the correct direction. } // Check to see if we are starting a new edge. if (--redge.height <= 0) { // Moving to a new edge. next_edge(1, end, start, right, redge); } } }

**
Improvements to drawing the polygon.
**

void next_edge(int offset, Point *end, Point *start, Point *&points, EdgeInfo &edge) { Point *points_temp; long y_end, x_end; // Save the initial point position. points_temp = points; // Get the y coordinate that will be started at. edge.y_start = (long)points->y; if (points->y < 0.0) edge.y_start--; // Find the position where the height changes. for (edge.height = 0; edge.height == 0; ) { // Get the x coordinate that will be started at. edge.x_start = (long)points->x; if (points->x < 0.0) edge.x_start--; // Move to the next point. points += offset; // Loop if the point went beyond the bounds of the point array. if (points < start) points = end; else if (points > end) points = start; // Make sure this is not looping endlessly. if (points == points_temp) { edge.height = 0; return; } y_end = (int)points->y; if (points->y < 0.0) y_end--; edge.height = edge.y_start - y_end; } // Find md (the slope's denominator). x_end = (int)points->x; if (points->x < 0.0) x_end--; edge.md = ((int)points->x) - edge.x_start; if (edge.md > 0) // If it is positive, { edge.x_move = 1; // Make x move in a positive direction. } else // else { edge.md = -edge.md; // Make md positive. edge.x_move = -1; // Make x move in a negative direction. } // Find mn (the slope's numerator). edge.mn = y_end - edge.y_start; if (edge.mn > 0) // If it is positive, { edge.y_move = 1; // Make y move in a positive direction. } else // else { edge.mn = -edge.mn; // Make mn positive. edge.y_move = -1; // Make y move in a negative direction. } // Find out the minimum x_step per move in y. edge.x_step = (edge.md/edge.mn) * edge.x_move; edge.md = (edge.md % edge.mn); // Make the denominator reflect the change. // ======================= CODE CHANGED ======================= // The y position changes faster than the x, so set the balance as a // portion of mn. // Set the balance as a portion of negative mn. if (edge.y_start >= 0) edge.balance = -((edge.y_start*edge.md)%edge.mn); else edge.balance = -(edge.mn - ((edge.y_start*edge.md)%edge.mn)); // ============================================================ }

**
Problems with imperfect polygons.
**

** Special thanks to: **

(My Home Page) - (My Personal Page) - (My Computer Science Page) - (My Resume)