StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>How about <a href="http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm" rel="nofollow noreferrer">Bresenham's</a> Line algorithm? After some setup, it's pure integer math, and can be adapted to draw a polygon by simple iteration of starting points along the polygon edges.</p> <p>comments followup:</p> <p>I'll try to draw this in ASCII, but it'll probably look like crud. Bresenham's can be used to draw a filled polygon by picking a starting edge, and iteratively moving a bresenham line across the canvas parallel to that point.</p> <p>Let's say you've got some points like this:</p> <pre><code>*(1) *(3) *(2) *(4) </code></pre> <p>These are numbered in left-right sort priority, so you pick the left-most starting point (1) and decide if you want to go vertically (start 1,2) or horizontally (1,3). That'd probably depend on how your DSP does its display, but let's go with vertical.</p> <p>So... You use the 1-2 line as your starting bresenham line. You calculate the starting points of your fill lines by using lines 1-3 and 2-4 as your start/end points. Start a bresenham calculation for each, and draw another Bresenham between those two points. Kinda like:</p> <pre><code>1.1 -> 2.1, then 1.2 -> 2.2, then 1.3 -> 2.3 </code></pre> <p>etc... until you reach the end of either of those lines. In this case, that'd be when the lower starting point reaches (4). At that point, you start iterating up the 4,3 line, until you reach point 3 with both starting points, and you're done.</p> <pre><code>*------- \\\\\\\\ * \\\\\\\\ *-----\\ ------- * </code></pre> <p>Where the dashes are the starting points you calculated along 1-3 and 2-4, and the slashes are the fill lines.</p> <p>Of course, this only works if the points are properly sorted, and you've got a convex polygon. If it's concave, you'll have to be very careful to not let your fill lines cross over the border, or do some pre-processing and subdivide the original poly into two or more convex ones.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload