Coding Away

In the last few years I found myself in need to render a font outlined to increase readability or to comply with UI requirements.
In both cases I had a non-outlined font, I had no choice of picking a different one, and I had to render it outlined.

To give you example, I had to render a font like this:

Outlined, like this:

If you are not too concerned about rendering speed (in my case, it wasn’t an issue), the trick I used to accomplish this is astonishingly simple, and very effective. You just need to render the font 5 times in different positions; 4 times with the color of the outline, and one time with the color of the body of the text.

Assuming that you want the body of the text starting at position (x,y) on the screen, the algorithm is:

A) Select the outline color.
1) Draw the text at (x+1,y)
2) Draw the text at (x-1,y)
3) Draw the text at (x,y+1)
4) Draw the text at (x,y-1)
B) Select the font body color
5) Draw the text at (x,y)

Here is an example of the results you get after each draw, numbered as in the above steps. In the example the color of the outline is BLACK, and the color of the body of the text is RED. I also added a background with a color similar to color of the body of the text, to show how outlining can increase readability in cases where you don’t know what the color of the background is (like in cases where the background could be any image).

To make it even clearer for you I did the same thing but this time I rendered the body of the text in gray after each steps 1,2,3 and 4. This way it becomes very clear how the outline is constructed, with each draw, around the body of the text:

In Java, a very simple example of a method that does exactly what described looks like:

public void drawTextOutlined(Graphics g,
                            String text,
                            int x, int y,
                            Color cOutline,
                            Color cBody) {
   g.setColor(cOutline);
   g.drawString(text, x+1, y);
   g.drawString(text, x-1, y);
   g.drawString(text, x, y+1);
   g.drawString(text, x, y-1);
   g.setColor(cBody);
   g.drawString(text, x, y);
}

Variations:

This method of outlining can be used with pretty much anything that you can render in a given color; it doesn’t have to be only text. In some cases it can even be expanded to images. It’s somewhat of a long story, but if anybody cares I can post about that as well.

There are also many variations based on the same concept. For example you can draw the outline rendering the text in the outline color at positions (x+1,y+1) (x+1,y-1) (x-1,y+1) (x-1,y-1) with similar results. You can also try drawing the outline with only two renderings of the text in the outline color, at positions (x+1,y+1) (x-1,y-1) or (x-1,y-1) (x+1,y+1), saving two text renderings and obtaining OK results in most cases.

I prefer the variations presented here, which gave me the best results in the situations I had, but feel free to experiment. There are cases where different variations might give you better results.

Hope you’ll find this helpful.

I’d like to share some numbers that I gathered during a little experiment I just ran regarding the effectiveness of on-line advertisement targeted to the Software Developer’s community compared to other niches. This article obviously doesn’t represent an exhaustive research. It is just the report of one single experiment that provides very interesting results.

As you can probably imagine, on the Internet there is a great deal of traffic generated by developers and geeks surfing for information or cool stuff. That’s not hard to believe considering how much time developers spend in front of a connected computer, and given that the Internet is possibly the only “book” they really need (well, a book full of amazing errors and faulty opinions, but still a pretty good book if you know what to look for).

Anyway, I have several Blogs that I maintain, this one being the last one I opened. To pay my hosting bills I usually put some light Google Adsense ads which is usually just enough to pay for the hosting expenses. I do not care of making money with ads, but I like the idea of not having to pay for providing a service to my readers. AdSense allows me to at least Blog without having to pay for it but still choose a domain name and retain full control on the site, configuration, software, etc.

To verify something that I really already knew, I ran a little side-by-side experiment using two articles that I was going to publish anyway. One I published on this Blog a couple of days ago, and one published on a different Blog with a very different type of readership.

The article on this Blog was about an algorithm to find loops in a linked list. The topic is obviously targeted to software developers. It gained some interest in the active on-line development community and ended up on the main page of programming.reddit.com for a couple of days, receiving about 3,000 hits / day, most of them being unique visitors. On the article I placed a small Google ad at the very beginning.

The other article was on a completely different subject: dream interpretation and sleep patterns. Yeah, I have many interests in different areas The ”dreams” article also featured a Google ad placed in the exact same area as the linked list one. I guess people like to sleep because it received very much interest and traffic. It was positively reviewed and linked by a very well known MD offering on-line health advice, and received just about ~3,500 hits / day, most of them from unique visitors.

The lucky part was to receive a very similar amount of traffic on two completely different articles. In both cases the traffic started abruptly due to a link, and in both cases the article featured a very similar ad size and placement. To be noted that the coloring of the Blogs, the contrast between article and ad and everything else are also very similar.

How much do you think each ad campaign generated with traffic of about 3,000 hits/day?
Take a quick guess!

The article about dream interpretation and sleep patterns generated about $10.00, with a click ratio of about ~3.5%.

Are you ready? The article on linked lists generated 1 single click (yes, ONE), which is the equivalent of a few cents, or pretty much 0% click ratio.

I knew that as a group we (developers) are pretty difficult customers, but I didn’t think it was that bad! If you are a developer, you may find these results obvious. However, I ensure you that most people, especially marketing and business folks, do not understand developer’s psychology very much.

My suggestion for the reader is: if you are really thinking of generating revenue with on-line ad campaigns targeted to developers, do some research! You may change your mind In fact, I almost guarantee that you will.

One of the challenges that from time to time you may find is a program that has to deal with a linked list having a loop.

While this is not a very common situation, it can happen, desired or not, as result of a bug, the particular usage of the linked list in the program or corrupted data.

A classic example of such situation caused maliciously by viruses, is the case of directory loops in the old DOS. As in many other OSs, in DOS directories where nodes of a tree; each node, or directory, had a pointer to each of its sub-directories. A single path such as “C:\a\b\c\d\e” could be seen as a linked list a->b->c->d->e. This is not uncommon, but one thing was particularly bad in DOS 3.1. Nothing in the system was able to deal with directory loops, no even the most advanced utilities.

If you took a disk editor and connected a directory, say “e”, with anything on an upper level, say “b”, you’d cause serious issues. No utility at the time was able to catch such an issue, which was guaranteed to crash any directory crawling program, including CHKDSK. You could keep re-entering the loop ending up with a path like “C:\a\b\c\d\e\b\c\d\e\b\c\d\e”. Some old viruses took advantage of this weakness to create all sort of troubles.

Anyhow, how do you write an algorithm to find out if a list has a loop? Usually people tend to go for a solution like traversing the list, marking each node as they go and, if they found an already marked node, than there is a loop. That solution works, but once you are done you have to clear that mark on all the marked nodes. In some cases this might not be desirable or even possible.

I’d like to present a small cleaver algorithm that detects loops in a list without having to alter the list in any way. I like to call this algorithm “The Rabbit and The Turtle Algorithm”, but I wonder if it has another name (does it?)

The idea is simple: you use two runners (pointers) to traverse the list. One moves one step at the time (turtle), and one moves two steps at the time (rabbit). The two keep running until the rabbit finds the end of the list, or until the rabbit passes the turtle. If the rabbit arrives at the end of the list, there is obviously no loop. If the rabbit passes the turtle, than there is a loop.

Simple, isn’t it? Here a simple implementation in Java:

// ListNode is the type of a node.
// head is a ListNode, head of the list.
// If node is of type ListNode, node.next is
// the pointer to the next element in the list.

01: public boolean hasLoop() {
02:
03:    if ((head == null) ||
04:        (head.next == null)) return false;
05:
06:    ListNode lnT = head;        // Turtle
07:    ListNode lnR = head.next; // Rabbit
08:
09:    while ( true ) {
10:       if ( lnT == lnR )
               return true;
11:       if ( (lnR = lnR.next) == null )
               return false;
12:       lnT = lnT.next;
13:       if ( lnT == lnR )
               return true;
14:       if ( (lnR = lnR.next) == null )
               return false;
15:    }
16 }

Lines 03-04 deal with the cases of (1) an empty list and (2) a list with only one node. In either case there is no loop for sure.
Lines 06-07: talk about injustice! The rabbit starts in front of the turtle already.
Line 10: checks if the rabbit encountered the turtle. If it did, we found a loop.
Line 11: Moves the rabbit forward one step. If the rabbit reached the end of the list, no loop exists.
Line 12: Moves the turtle forward.
Line 13: If the rabbit found the turtle, we have a loop!
Line 14: Moves the rabbit an extra step forward. If the rabbit reached the end of the list, no loop exists.
Line 09: Repeats until one of the conditions above is satisfied.

Hope this is useful.