2
$\begingroup$

TL;DR: Can anyone point me to a good adaptive path fill algorithm?

Hey there, my name is James, and my daughter built an awesome painting robot with her friends over at Evil Mad Scientist labs, even brought it to the white house, very fun stuff!

Anyways, I'm a web programmer by day, and though it might be fun to try and write some software to get the robot to do some cool stuff, and for some crazy reason I decided to do this using standard web technologies like SVG and JavaScript, and.. it actually works! [see the project at github.com/techninja/robopaint]

But there's a problem: to fill in colors for given shapes, it requires some kind of path filling algorithm using a given size shape to cover every part of the shape internally, not to mention it has to take into account overlapping paths and occlusions.

I have successfully created "fake" fills, by following known paths like spirals and back and forth hatch lines over paths, while detecting occlusion using browser internal functions for detecting what object lies at a given x/y coordinate, but these fill functions fall incredibly short of doing anything other than simply following paths, and can be incredibly inefficient at filling certain paths (like filling borders, letters, or U shaped areas).

The question: I need an adaptive path filling algorithm. I know they're currently being used in similar CNC setups for milling, and similar algorithms are used by the Roomba and 3D printers to figure out coverage in the most efficient way possible. The issue comes in that I don't think any have ever been done in JavaScript, using native SVG paths.

Anyone out there know where I should look? I'm not too afraid to attempt to port something over to JS, or possibly even use it as is for a native Node.JS module. All my work will be sure to go back to the community and become open source as well.

Thanks for the help!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

What you're looking for is a "coverage algorithm". There are a few relevant questions on this site that address this topic:

  1. What's an efficient way to visit every reachable space on a grid with unknown obstacles?
  2. What algorithm should I implement to program a room cleaning robot?
Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the quick reply! Though I think the problem is better represented as "offline" coverage algorithm. I happen to "know" the full path shape as a polygon, less any overlaps/occlusions. And though the "CNC Island Motion Planning" looks right up my alley, though it's behind a paywall. My next option is to look at this, even though it's for 3D motion planning... code.google.com/p/libactp $\endgroup$
    – TechNinja
    Jun 24, 2013 at 20:13
  • $\begingroup$ CNC is absolutely relevant to what you're doing here! That sounds like a good avenue to pursue. $\endgroup$
    – Ian
    Jun 25, 2013 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.