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

21–30 of 50 posts

Re: The Beauty of Bresenham's Algorithm

#21

Post by textminer »

6ren wrote: post #20
FredBrach wrote: post #8

By the way, I had a teacher (J.P Reveilès) who had invented the theoretically fastest drawline algorithm ever: he simply figure out that, for a line, there is a pixel pattern which repeat itself (unless the variation is a transcendental number http://en.wikipedia.org/wiki/Transcendental_number ) so you only have to compute that pattern once and copy/paste it. If I remember well, for example, a line which has a variat…

Wouldn't the exception be for lines whose slope is irrational? (i.e. that can't be represented by a ratio of integers), so the repeating pattern is analogous to the repeating pattern in a decimal representation of a rational number.

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

Re: The Beauty of Bresenham's Algorithm

#22

Post by pvarangot »

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 meters but also about no block in that trajectory, all those cells you now suppose are free and the one you suppose is not are the result of Bressenham's Algorithm)

Re: The Beauty of Bresenham's Algorithm

#23

Post by mjcohenw »

textminer wrote: post #21
6ren wrote: post #20

Earlier quoted context omitted.

Wouldn't the exception be for lines whose slope is irrational? (i.e. that can't be represented by a ratio of integers), so the repeating pattern is analogous to the repeating pattern in a decimal representation of a rational number.

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.

Re: The Beauty of Bresenham's Algorithm

#26

Post by jejones3141 »

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".

Any compiler/interpreter worth its salt will notice when an expression being tested in a conditional is constant and generate code that doesn't actually test it at run time. for (;;) is arguably more "idiomatic" C, though.

Re: The Beauty of Bresenham's Algorithm

#27

Post by [deleted] »

6ren wrote: post #20
FredBrach wrote: post #8

By the way, I had a teacher (J.P Reveilès) who had invented the theoretically fastest drawline algorithm ever: he simply figure out that, for a line, there is a pixel pattern which repeat itself (unless the variation is a transcendental number http://en.wikipedia.org/wiki/Transcendental_number ) so you only have to compute that pattern once and copy/paste it. If I remember well, for example, a line which has a variat…

Wouldn't the exception be for lines whose slope is irrational? (i.e. that can't be represented by a ratio of integers), so the repeating pattern is analogous to the repeating pattern in a decimal representation of a rational number.

[deleted]

Re: The Beauty of Bresenham's Algorithm

#28

Post by [deleted] »

textminer wrote: post #21
6ren wrote: post #20

Earlier quoted context omitted.

Wouldn't the exception be for lines whose slope is irrational? (i.e. that can't be represented by a ratio of integers), so the repeating pattern is analogous to the repeating pattern in a decimal representation of a rational number.

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

[deleted]
Post reply on HN