identifying a Horizontal line in Scan Line Filling

Question

3.00/5 (1 vote)

See more:

Hey I am trying to render some fonts on the screen. Actually I have done that.
Now what I am trying is to fill the characters i.e. fill the bounded regions.

The only thing I have is a 2-d buffer which stores information for each pixel i.e. it is set if the pixel is to be illuminated otherwise it contains '0'.

I cant think of a logic to fill the bounded regions using this.
This is what I tried but it failed as it cant recognize the horizontal lines.

for(int p=0 ; p<401 ; ++p){
            for(int q=0 ; q<401 ; ++q){
                if( buffer[p][q] == 1 ){
                    ++q ;
                    while (buffer[p][q] == 0){
                          buffer[p][q]  = 1 ;
                          ++q ;
                    }
                }
            }
        }

Posted 15-Jul-11 1:37am

Member 8086596

Updated 15-Jul-11 2:20am

v2

Add a Solution

Comments

R. Erasmus 15-Jul-11 9:53am

This piece of code is prone to having bugs....
incrementing q will cause array out of bounds exception when q = 400 if buffer size contains 401 elements.
Loop is also way to complex... Its better to use functions that devides the program up into simpler segments. Its a testing nightmare.

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CPallini · Answer 1 · 2011-07-15T01:44:00

Solution 1

Why don't you have a look at Flood Fill algorithm[^] at Wikipedia?

Posted 15-Jul-11 1:44am

CPallini

Comments

Espen Harlinn 15-Jul-11 8:13am

Right :)

Member 8086596 15-Jul-11 8:17am

That's entirely different thing i guess. I don't have any idea about the behaviour of the edges or you can say the bounded regions. I only have the pixel info in the 2-d buffer , but for standard flood fill algorithm i need to know the coordinates of corners.

CPallini 15-Jul-11 8:23am

I guess your guess is wrong. Please read carefully the linked page.

Member 8086596 15-Jul-11 8:28am

Suppose i have rendered "ABC" on the canvas. Firstly i dont have start node to start with , secondly, even if I get the start node by scanning the buffer[][] that would become very inefficient in case the text is lenghty coz i have to find the start node for each and every character.

CPallini 15-Jul-11 8:34am

Could you please post one (or more) image(s)?

Member 8086596 15-Jul-11 8:37am

Sorry I am new to this forums world . How am I supposed to post images?

CPallini 15-Jul-11 8:44am

You may upload the image (on a free image hosting service) and then post the link here.
BTW cannot you use different colors for the initiali printout of the characters (I mean, for instance, given "AKA", 'A'<->1, 'K'<->2, 'A'<->3 , this way internal pixels are bounded by external pixels having the same value)?

Member 8086596 15-Jul-11 8:55am

I can do that I guess. But hows that gonna help ? I still will have to find the Start node for each character.
Actually I am rendering the fonts from SVG file on the mobile device. So i have to make it as efficient as possible. So I am looking for the way in which i can fill all the bounded regions by just scanning the buffer[][] once.

CPallini 15-Jul-11 9:00am

It helps because, otherwise, you cannot recognize horizontal lines (if I got you: you cannot distingush 'inside' from 'outside'. Having different colors helps: a blank pixel between a 1-pixel and a 2-pixel is 'outside').

Member 8086596 15-Jul-11 9:26am

here is the image
http://www.freeimagehosting.net/image.php?fcfe295ea5.png

I need to fill the "BOTS".

Member 8086596 15-Jul-11 8:56am

I dont have access to the image now. Will do that later.

John R. Shaw · Answer 2 · 2011-07-15T06:23:00

Search for "fill polygon" or "scanline fill algorithm".

It is a scan-line problem. If you can draw the font outline, then you can also store the points in a Y/X sorted list. If you did not draw the outline, then you can scan it to create the list.

[y1][x1], [y1][x2], [y1][x3], [y1][x4], ...
[y2][x1], [y2][x2], [y2][x3], [y2][x4]...
...

x1 => far left
x2 => first right
x3 => next left
x4 => next right
...

[y1][x1] line to [y1][x2] no line [y1][x3] line to [y1][x4]

I just wrote the following - so it has not been tested. But it should give you an idea of how a scan-line fill works.

struct MyPoint {
	int x, y;
};
// Fill horizontal lines between points in given point list
// - does not draw on outline (border)
void FillBetweens(MyPoint* list, size_t list_size)
{
	// assumes list is sorted from top to bottom and left to right
	int current_y = 0;
	for (size_t i=0; i<list_size-1; ++i)
	{
		if( list[i].y != current_y )
			current_y = list[i].y; // or ++current_y (depends on your choices)
		if( list[i+1].y == current_y )
		{
			// your horizontal line drawing function (y,x1,x2)
			// - assumes drawing between end points
			draw_betweens(list[i].y, list[i].x, list[i+1].x);
			++i;
		}
		// else we skip single point lines
	}
}