My Papers

This page assembles the various brief papers and algorithms I’ve sketched out over the years on this blog. Some of these papers may be of use to you; I don’t know.

I’ve taken the liberty to surface those papers here for future reference.

Generating LR(1) grammars

This paper (in PDF form available on GitHub) provides a detailed description of the algorithms used to generate an LR parser. This covers concepts from the basic power-set construction algorithm to building LR(0), SLR, LALR and LR(1) grammars. The concepts should be at a level that a beginning Computer Science student should be able to understand and hopefully apply to their own parser-generator system, if they so wish.

Constructing a cyclic polygon given the edge lengths.

So I have a problem: given the length of the edges L = {l0, l1, … lN} of an N-sided irregular polygon with N > 3, I need to construct the values for the radius R and the angles A = {a0, a1, … aN} such that the points P = { R, ai } form a closed polygon with the lengths given.

I searched through the internet and found all sorts of articles on the subject, but a day of searching and I was unable to find a way that I could construct the values R and A. I’m sure it’s out there, but I figured it’d be a good exercise to do it myself.

Finding the boundary of a one-bit-per-pixel monochrome blob

Recently I’ve had need to develop an algorithm which can find the boundary of a 1-bit per pixel monochrome blob. (In my case, each pixel had a color quality which could be converted to a single-bit ‘true’/’false’ test, rather than a literal monochrome image, but essentially the problem set is the same.)

In this post I intend to describe the algorithm I used.

Goodbye Far Clipping Plane.

This paper discusses a minor variation to the perspective transformation matrix in computer graphics which permits one to dispense with the far clipping plane, yet maintain a high degree of numeric accuracy no matter how far away an object moves. (Theoretically one could even use this to render objects at the infinite plane; the plane of objects whose homogeneous coordinates are represented as (x,y,z,0).)

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s