What's the most challenging algorithm you've ever faced
-
Treating love like an algorithm might have something to do with it. :laugh:
Real programmers use butterflies
When "true love" is your patient, then, doctor, treatment "primum non nocere" is even more critical. I find it fascinating that the original sigil of the Asclepian healing cult had only onw serpent twining around the staff, not two (as on the Caduceus of Mercury).
«One day it will have to be officially admitted that what we have christened reality is an even greater illusion than the world of dreams.» Salvador Dali
-
true love
«One day it will have to be officially admitted that what we have christened reality is an even greater illusion than the world of dreams.» Salvador Dali
Given these truths: o Time is money. o Money is the root of all evil. o Girls cost time and money. We obtain
time = money
_____
money = V evilgirls = time x money
girls = money x money
_____ _____
girls = V evil x V evilgirls = evil
Robust Services Core | Software Techniques for Lemmings | Articles
The fox knows many things, but the hedgehog knows one big thing. -
... that you can explain the purpose of in one (reasonable) line, say a sentence or two brief ones. Mine is implementing a 2D polygon fill algorithm on a write only display device. I know how in theory - vaguely - to do it, but it's mind bending to attempt in practice, and I say that as someone who writes old-school table based LR parsers. UPDATE: Randor humbled me. There's an easy way to do this. I even knew about it at one point but blanked on it here. I am very grateful, despite feeling a little foolish. My most complicated algo... probably GLR parsing. In terms of ones I haven't solved - there's one that should be simple but I can never get it right -> converting an NFA or DFA state machine into a regular expression.
Real programmers use butterflies
Mine, and I have not completed it after a few years.. :/ :-O Is to do 2D shape (bordered by bezier line) intersection...
A new .NET Serializer All in one Menu-Ribbon Bar Taking over the world since 1371!
-
Given these truths: o Time is money. o Money is the root of all evil. o Girls cost time and money. We obtain
time = money
_____
money = V evilgirls = time x money
girls = money x money
_____ _____
girls = V evil x V evilgirls = evil
Robust Services Core | Software Techniques for Lemmings | Articles
The fox knows many things, but the hedgehog knows one big thing.You forgot the branch cut - a square root has two solutions. This gives us:
time = money
_____
money = ± V evilgirls = time x money
girls = money x money
_____ _____
girls = ± V evil x ± V evilgirls = ± evil
This is closer to the real world, in that: 1. Money may be either positive (credit) or negative (debit) 2. Some girls are good :D
Freedom is the freedom to say that two plus two make four. If that is granted, all else follows. -- 6079 Smith W.
-
... that you can explain the purpose of in one (reasonable) line, say a sentence or two brief ones. Mine is implementing a 2D polygon fill algorithm on a write only display device. I know how in theory - vaguely - to do it, but it's mind bending to attempt in practice, and I say that as someone who writes old-school table based LR parsers. UPDATE: Randor humbled me. There's an easy way to do this. I even knew about it at one point but blanked on it here. I am very grateful, despite feeling a little foolish. My most complicated algo... probably GLR parsing. In terms of ones I haven't solved - there's one that should be simple but I can never get it right -> converting an NFA or DFA state machine into a regular expression.
Real programmers use butterflies
honey the codewitch wrote:
Mine is implementing a 2D polygon fill algorithm
Are you saying that the most complex algorithm you've ever implemented is a depth-first/breadth-first traversal? Or am I misunderstanding something. I glanced through your latest articles but didn't see anything mentioned. I guess the most complicated I've dealt with is noisy sparse signals recovery using Kalman filter[^] variants while I was working at Marine Technologies[^] circa ~2006. Kalman wasn't even the hard part... the underlying Gaussian mixture model[^] was where all the magic really happens. The reason it's considered difficult is because it's an approximation and there is always a better approximation to be found. We had to hire a mathematics professor from Norway as a consultant to help. Math is hard. Best Wishes, -David Delaune
-
honey the codewitch wrote:
Mine is implementing a 2D polygon fill algorithm
Are you saying that the most complex algorithm you've ever implemented is a depth-first/breadth-first traversal? Or am I misunderstanding something. I glanced through your latest articles but didn't see anything mentioned. I guess the most complicated I've dealt with is noisy sparse signals recovery using Kalman filter[^] variants while I was working at Marine Technologies[^] circa ~2006. Kalman wasn't even the hard part... the underlying Gaussian mixture model[^] was where all the magic really happens. The reason it's considered difficult is because it's an approximation and there is always a better approximation to be found. We had to hire a mathematics professor from Norway as a consultant to help. Math is hard. Best Wishes, -David Delaune
It's just not depth first or breadth first traversal - that part is easy. I think you're thinking of a flood fill algorithm, which won't work on a write only device because you need to read the pixel data. It also won't work if you try to draw a filled polygon over existing draws. What I need to do for example: _/\_ \__/ Say that's my poly here /\ I need to go top to bottom, left to right from the beginning of each point of the left line to each point on the right line, across. I also need to sort the points so I can figure out where to start drawing.
Real programmers use butterflies
-
It's just not depth first or breadth first traversal - that part is easy. I think you're thinking of a flood fill algorithm, which won't work on a write only device because you need to read the pixel data. It also won't work if you try to draw a filled polygon over existing draws. What I need to do for example: _/\_ \__/ Say that's my poly here /\ I need to go top to bottom, left to right from the beginning of each point of the left line to each point on the right line, across. I also need to sort the points so I can figure out where to start drawing.
Real programmers use butterflies
-
Hi, A few more questions; 1.) Does your algorithm support polygons with holes[^]? 2.) Did you invent something new or implement an existing algorithm? 3.) Where can I find your work? I'd like to look at it. Best Wishes, -David Delaune
1. Heck no!* 2. I haven't been able to implement the algorithm. It is described at tutorialspoint somewhere but no implementation 3. I'll publish it here when I solve it. Sorry if my OP implied I solved it. I did not mean to. If I had solved it I'd have found something else to get stuck on by now. :laugh: * adding, there's no way to even describe it with my API, except you should be able to approximate any polygon with holes by one without one that loops back on itself - as long as it's filled you won't be able to tell the difference.
Real programmers use butterflies
-
Hi, A few more questions; 1.) Does your algorithm support polygons with holes[^]? 2.) Did you invent something new or implement an existing algorithm? 3.) Where can I find your work? I'd like to look at it. Best Wishes, -David Delaune
I just figured out a much easier way in theory to do it. Just scale the thing smaller and smaller by 1 pixel in any direction and keep redrawing it until you get down to a single point. Unfortunately, in practice this won't work - the way the bresenham line drawing algo works it will leave little holes in the result. *sadface*
Real programmers use butterflies
-
... that you can explain the purpose of in one (reasonable) line, say a sentence or two brief ones. Mine is implementing a 2D polygon fill algorithm on a write only display device. I know how in theory - vaguely - to do it, but it's mind bending to attempt in practice, and I say that as someone who writes old-school table based LR parsers. UPDATE: Randor humbled me. There's an easy way to do this. I even knew about it at one point but blanked on it here. I am very grateful, despite feeling a little foolish. My most complicated algo... probably GLR parsing. In terms of ones I haven't solved - there's one that should be simple but I can never get it right -> converting an NFA or DFA state machine into a regular expression.
Real programmers use butterflies
I was slow to reply because I guess algorithm implies a fairly contained piece of code. So I'd say it was an event dispatcher for telecom state machines. It wasn't so much the algorithm, but the design around it. When you add lots of supplementary services to a basic call, building One Big State Machine creates a Big Ball of Mud. To keep the state machines separate, they run in an event-routing framework that allows state transitions to be announced, overridden, and/or supplemented. Chain of Responsibility plays a role in instantiating the state machines. The algorithm for this was implemented in the state machine base class. I've thought about writing an article about it, but I doubt it would have much value because I haven't heard of another domain that requires this kind of solution.
Robust Services Core | Software Techniques for Lemmings | Articles
The fox knows many things, but the hedgehog knows one big thing. -
I was slow to reply because I guess algorithm implies a fairly contained piece of code. So I'd say it was an event dispatcher for telecom state machines. It wasn't so much the algorithm, but the design around it. When you add lots of supplementary services to a basic call, building One Big State Machine creates a Big Ball of Mud. To keep the state machines separate, they run in an event-routing framework that allows state transitions to be announced, overridden, and/or supplemented. Chain of Responsibility plays a role in instantiating the state machines. The algorithm for this was implemented in the state machine base class. I've thought about writing an article about it, but I doubt it would have much value because I haven't heard of another domain that requires this kind of solution.
Robust Services Core | Software Techniques for Lemmings | Articles
The fox knows many things, but the hedgehog knows one big thing.I could see it in a message passer system like that used in microkernel operating systems.
Real programmers use butterflies
-
I just figured out a much easier way in theory to do it. Just scale the thing smaller and smaller by 1 pixel in any direction and keep redrawing it until you get down to a single point. Unfortunately, in practice this won't work - the way the bresenham line drawing algo works it will leave little holes in the result. *sadface*
Real programmers use butterflies
Well, That doesn't really make any sense. I don't understand the technical issues you are encountering. Drawing, filling and scaling 2D polygons is exceedingly trivial. Based on what you have said I see the following requirements: 1.) You are only supporting simple polygons[^]. 2.) You need to write to the video device in a scanline pattern[^]. 3.) You cannot read pixels. 4.) You have not stated why you can't draw in a frame buffer. But I will assume that you either can't or are unwilling. So I don't think that you can use the Nonzero-rule[^]. But you could use the even–odd rule[^]. Some other things for you to read for scaling your polygons: Dot product[^] Best Wishes, -David Delaune
-
Well, That doesn't really make any sense. I don't understand the technical issues you are encountering. Drawing, filling and scaling 2D polygons is exceedingly trivial. Based on what you have said I see the following requirements: 1.) You are only supporting simple polygons[^]. 2.) You need to write to the video device in a scanline pattern[^]. 3.) You cannot read pixels. 4.) You have not stated why you can't draw in a frame buffer. But I will assume that you either can't or are unwilling. So I don't think that you can use the Nonzero-rule[^]. But you could use the even–odd rule[^]. Some other things for you to read for scaling your polygons: Dot product[^] Best Wishes, -David Delaune
You know I've even read about that technique years ago, and for some reason I completely overlooked it - it went down the memory hole. I'm not entirely sure even-odd will work until I try it, but I'll certainly try it. Thanks in advance, even if it leaves me feeling like a bit of an idiot. I'll take it if it means a solution. :)
Real programmers use butterflies
-
You know I've even read about that technique years ago, and for some reason I completely overlooked it - it went down the memory hole. I'm not entirely sure even-odd will work until I try it, but I'll certainly try it. Thanks in advance, even if it leaves me feeling like a bit of an idiot. I'll take it if it means a solution. :)
Real programmers use butterflies
honey the codewitch wrote:
it leaves me feeling like a bit of an idiot
You are obviously not an idiot, but rather experimenting with geometry and probably never looked here before. Everyone is clueless when they poke around in an unfamiliar topic. Everybody is standing on the shoulders of giants and very rarely do you find a human that generates something new. That's why I wanted to see what you created, I wanted to see if it was something new. Anyway, I forgot to mention why you probably can't use the nonzero-rule. It works by summing the angles which means it would need to use a minimum of 3 rows. The even–odd rule would allow you to cast a single photon (ray of light) across one scanline and simply check for even/odd values. I would recommend testing this stuff on your desktop and get out of that restrained environment during the test development. Good luck, -David Delaune
-
honey the codewitch wrote:
it leaves me feeling like a bit of an idiot
You are obviously not an idiot, but rather experimenting with geometry and probably never looked here before. Everyone is clueless when they poke around in an unfamiliar topic. Everybody is standing on the shoulders of giants and very rarely do you find a human that generates something new. That's why I wanted to see what you created, I wanted to see if it was something new. Anyway, I forgot to mention why you probably can't use the nonzero-rule. It works by summing the angles which means it would need to use a minimum of 3 rows. The even–odd rule would allow you to cast a single photon (ray of light) across one scanline and simply check for even/odd values. I would recommend testing this stuff on your desktop and get out of that restrained environment during the test development. Good luck, -David Delaune
Randor wrote:
I would recommend testing this stuff on your desktop and get out of that restrained environment during the test development.
That's actually part of why I wrote GFX to be runnable anywhere. I didn't want to develop it on a constrained environment. But it has to run on them. My initial GFX library dumped its output solely using printf() and drawing ascii art after converting bitmaps to 16 color grayscale. I used that to test my line drawing algorithms and such. But now that all of that is done and pretty predictable, I find myself going back to the PC to code this thing less and less, either because I'm dealing with things like asynchronous draws which have no support on the PC, or most of what I'm doing works the first time or two after it compiles because i've built the foundation up by now enough that the coding is fairly high level.
Real programmers use butterflies
-
Well, That doesn't really make any sense. I don't understand the technical issues you are encountering. Drawing, filling and scaling 2D polygons is exceedingly trivial. Based on what you have said I see the following requirements: 1.) You are only supporting simple polygons[^]. 2.) You need to write to the video device in a scanline pattern[^]. 3.) You cannot read pixels. 4.) You have not stated why you can't draw in a frame buffer. But I will assume that you either can't or are unwilling. So I don't think that you can use the Nonzero-rule[^]. But you could use the even–odd rule[^]. Some other things for you to read for scaling your polygons: Dot product[^] Best Wishes, -David Delaune
Okay, so I implemented it and what jumps out to me (and I feel like I'm missing something here) is that for me to use even-odd requires a nasty brute force when trying to fill. here's rough C++ psuedocode i just typed to illustrate:
for(int y=0;y
Does that look right to you? It seems heavy handed to me. The wiki entry only shows how to determine if the point is in the polygon though, not how to quickly determine the extents by say, scanline. I feel like there has to be a faster way.
I just figured it out I think.
Real programmers use butterflies
-
Okay, so I implemented it and what jumps out to me (and I feel like I'm missing something here) is that for me to use even-odd requires a nasty brute force when trying to fill. here's rough C++ psuedocode i just typed to illustrate:
for(int y=0;y
Does that look right to you? It seems heavy handed to me. The wiki entry only shows how to determine if the point is in the polygon though, not how to quickly determine the extents by say, scanline. I feel like there has to be a faster way.
I just figured it out I think.
Real programmers use butterflies
Hmmmm, Of course there are faster ways. I would recommend getting your polygon algorithms working first and then move towards optimization. Obviously writing single pixels one at a time will be low performance. Writing sizeof(int) would be faster and SIMD instructions even faster. Same goes for whatever array you are using to store your polygon points. 'sparse' std::bitset would be lowest memory usage but slow as molasses. std::bitset would be low memory but a little bit faster. A huge array of quadword zeros and ones read with SIMD... fast and fat Pick your poison.
-
... that you can explain the purpose of in one (reasonable) line, say a sentence or two brief ones. Mine is implementing a 2D polygon fill algorithm on a write only display device. I know how in theory - vaguely - to do it, but it's mind bending to attempt in practice, and I say that as someone who writes old-school table based LR parsers. UPDATE: Randor humbled me. There's an easy way to do this. I even knew about it at one point but blanked on it here. I am very grateful, despite feeling a little foolish. My most complicated algo... probably GLR parsing. In terms of ones I haven't solved - there's one that should be simple but I can never get it right -> converting an NFA or DFA state machine into a regular expression.
Real programmers use butterflies
Although today it would be quite trivial to do, I reckon that a graphical game of Reversi on a RadioShack TRS80 with only 4K of RAM was my most challenging ever. The computer was pretty much unbeatable on the 'hard' setting.
So old that I did my first coding in octal via switches on a DEC PDP 8
-
Hmmmm, Of course there are faster ways. I would recommend getting your polygon algorithms working first and then move towards optimization. Obviously writing single pixels one at a time will be low performance. Writing sizeof(int) would be faster and SIMD instructions even faster. Same goes for whatever array you are using to store your polygon points. 'sparse' std::bitset would be lowest memory usage but slow as molasses. std::bitset would be low memory but a little bit faster. A huge array of quadword zeros and ones read with SIMD... fast and fat Pick your poison.
I can't use the STL because it's pretty much non-existent on the arduino for anything non-trivial. Part of the reason is due to supporting 8 bit processors and all the constraints that usually come with them. The STL doesn't play well with 8kB of RAM. It's not that it won't work, it's just not really great for that, and if you only have 256kB of nvs program space to work with. Because of that I've had to hand roll things like std::is_same<> :doh: I can't do anything that specifically targets SIMD, because although some of the processors I target do support those instructions, there is no unified way to target it other than to cajole the C++ compiler into generating the right machine code. Frankly, I don't even know what SIMD looks like on, say a 32-bit Tensilica chip but I know it supports it in some form. Same with ARM Cortex CPUs. I'm currently using run lengths so that I draw horizontal scanlines at a time. That cuts down device traffic (often SPI bus traffic), since I can almost always fill a rectangle with a color in less instructions than writing each individual pixel. - horizontal and vertical lines are technically filled rectangles. =) Other than that though, it's still pixel by pixel. What really gets me though, is having to examine each point in the draw destination. I've limited the search by getting a bounding rectangle for the polygon, but all it does is sort the points so it won't deal with "inside out" polygons. I don't rightly care, because that's almost never what you want anyway, and if you did you could just fill the screen before drawing it or something. I can add support for it fairly easily but it seems a waste of time. I'm not worried about scanning the path segments in terms of time or space as I expect paths to be very small in practice. Like less than 30 or so points. You can do more of course, but it's on you because I make you pass in a buffer to use anyway. What I'm concerned about is the brute force check of each pixel in the draw destination to see if it falls within the polygon. That seems ... inelegant to say the least. I got it working less than 10 minutes after you pointed me to it. =)
Real programmers use butterflies
-
Although today it would be quite trivial to do, I reckon that a graphical game of Reversi on a RadioShack TRS80 with only 4K of RAM was my most challenging ever. The computer was pretty much unbeatable on the 'hard' setting.
So old that I did my first coding in octal via switches on a DEC PDP 8
+1 for bringing a game into this instead of code. :laugh:
Real programmers use butterflies
