Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Beauty of Bresenham's Algorithm

free.pages.at

Post reply on HN
Print view View original

31–40 of 50 posts

Re: The Beauty of Bresenham's Algorithm

#31

Post by ThePherocity »

biot wrote: post #17
barbs wrote: post #5

Why do people write non-conditional loops as "for(;;)" instead of "while(1)"?

According to the C99 standard [0], an omitted optional expression-2 in a for loop is replaced by a non-zero constant. Thus, for(;;) is equivalent to for(;1;) which is effectively equivalent to while(1) as there are no other declarations or expressions. And, for those who are counting, it also saves a character. [0] http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf (See 6.8.5.3)

Why would anyone wreck legibility to save a character?

Re: The Beauty of Bresenham's Algorithm

#33

Post by FredBrach »

mjcohenw wrote: post #23
textminer wrote: post #21

Earlier quoted context omitted.

How does a computer distinguish an irrational number from a good, (necessarily rational) floating-point approximation of one?

The algorithm only works with points with integer coordinates, so the slope is always rational.

I think you have the last words because line drawing algorithms become irrelevant if you use a Floating Point Unit.

just:

{ x++ and y+=slope } or { y++ and x+= 1./slope }

Then slopes are always rational in line drawing algorithms.

Re: The Beauty of Bresenham's Algorithm

#34

Post by WalterBright »

nitrogen wrote: post #7
barbs wrote: post #5

Why do people write non-conditional loops as "for(;;)" instead of "while(1)"?

Because while(1) still has a condition that is checked on every loop iteration when optimizations are disabled. for(;;) can be read as "forever".

That issue disappeared before the 1980's. Check your compiler.

Re: The Beauty of Bresenham's Algorithm

#35

Post by Jimmie »

ThePherocity wrote: post #31
biot wrote: post #17

Earlier quoted context omitted.

According to the C99 standard [0], an omitted optional expression-2 in a for loop is replaced by a non-zero constant. Thus, for(;;) is equivalent to for(;1;) which is effectively equivalent to while(1) as there are no other declarations or expressions. And, for those who are counting, it also saves a character. [0] http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf (See 6.8.5.3)

Why would anyone wreck legibility to save a character?

Ahhh, the ole' semicolon debate.

Re: The Beauty of Bresenham's Algorithm

#36

Post by maximz »

pvarangot wrote: post #22

About a week ago I came to know Bresenham's Algorithm is also important in mobile robotics. Basically, you model your map using a grid, after firing a sensor such as a LIDAR or sonar and finding something blocks its cone of sight you use Bresenham's to see what cells in your map the new reading provides information about. (i.e. something bouncing 2 meters from where your robot is not only tells you about a block at 2…

Could you please elaborate on how this works or point to some resources on this application of the algorithm (if you know of any)?

Re: The Beauty of Bresenham's Algorithm

#37

Post by spitfire »

I remember implementing this in ask! Fun times.

it's very funny how this sort of stuff comes back at opportune times to magically solve really hard problems for you with a single pass. Sort of like having Knuth on your bookshelf.

Re: The Beauty of Bresenham's Algorithm

#38

Post by dbaupp »

ThePherocity wrote: post #31
biot wrote: post #17

Earlier quoted context omitted.

According to the C99 standard [0], an omitted optional expression-2 in a for loop is replaced by a non-zero constant. Thus, for(;;) is equivalent to for(;1;) which is effectively equivalent to while(1) as there are no other declarations or expressions. And, for those who are counting, it also saves a character. [0] http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf (See 6.8.5.3)

Why would anyone wreck legibility to save a character?

I don't think it wrecks legibility, since it's a C idiom. People reasonably experienced in C will read "for (;;)" as an infinite loop just as well as "while(1)". That said, it might be a little confusing for beginners (or others who don't use C very regularly).

Re: The Beauty of Bresenham's Algorithm

#39

Post by dbaupp »

FredBrach wrote: post #11
nitrogen wrote: post #7

Earlier quoted context omitted.

Because while(1) still has a condition that is checked on every loop iteration when optimizations are disabled. for(;;) can be read as "forever".

I do doubt that even for a for(;;), a jmp (x86) is use instead of a conditional jump like jz.

Compilers are smart! For common things like this, they will easily optimise away any conditional jumps.

Re: The Beauty of Bresenham's Algorithm

#40

Post by Schwolop »

maximz wrote: post #36
pvarangot wrote: post #22

About a week ago I came to know Bresenham's Algorithm is also important in mobile robotics. Basically, you model your map using a grid, after firing a sensor such as a LIDAR or sonar and finding something blocks its cone of sight you use Bresenham's to see what cells in your map the new reading provides information about. (i.e. something bouncing 2 meters from where your robot is not only tells you about a block at 2…

Could you please elaborate on how this works or point to some resources on this application of the algorithm (if you know of any)?

Essentially it's ray-tracing but in a grid. Bresenham's algorithm let's you do the ray-tracing efficiently.

This is done because a LIDAR/sonar/whatever scanning range sensor returns the angle and range to a reflective object. In most cases, there's an implicit additional piece of information - namely that there's nothing in between the sensor and the object, since the EM radiation was able to get there and back. Bresenham's algorithm is used to tell you the grid cells in which you can assume free space.

Post reply on HN