7
$\begingroup$

There is a painting brush tool that can paint a circle area of $1$ unit radius. What is the shortest paint track for painting at least a $100*100$ units rectangle area on wall? How much did the brush moved in total?

Rules:

  • Brush must touch wall only once. (It says that painting should be continues and you have only one shot)
  • Painting can start and finish anywhere.
  • Painting outside the rectangle does not matter. (Actually it is inevitable to paint some of the outer area of rectangle)

Example:

Here's a naive try for a $10*10$ rectangle and the same brush with radius of $1$ unit enter image description here result is $58$ units for $10*10$ rectangle and $(n*m)+2m-2$ for $n*2m$ rectangle

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ Do you need to 'fill' the 4 corners aswell? Round things don't tend to fill rectangles unless you go outside the borders.. $\endgroup$
    – Tim Couwelier
    Oct 7, 2014 at 8:25
  • 1
    $\begingroup$ @TimCouwelier, painting outside the rectangle does not matter. (It is inevitable to paint some of outer area). Thanks $\endgroup$
    – Rafe
    Oct 7, 2014 at 8:31
  • 1
    $\begingroup$ Quick heads up as to why I deleted my post: length of a diagonal was not sqrt(2)/2 x side but sqrt(2) x side, which ruined the calculations.. alot. $\endgroup$
    – Tim Couwelier
    Oct 7, 2014 at 9:11
  • 1
    $\begingroup$ I don't get it, why would any solution be better than the trivial snake solution that Elgert mentioned? It seems like the length of the path is just a function of how much paint you use, so any solution which minimizes wasted paint works $\endgroup$
    – Ben Aaronson
    Oct 7, 2014 at 12:08
  • 1
    $\begingroup$ @Moyli, Exactly! I think Tim thought about sharp tuens that tried to find a spiral path $\endgroup$
    – Rafe
    Oct 7, 2014 at 13:48

4 Answers 4

Reset to default
6
$\begingroup$

The best I can do (so far) is a total track length of 5083.592 (see below).

Update: You can also do away with the final returning curved path in my final solution, which chops off pi/4, so the total length is reduced to 5082.807

enter image description here

Improve this answer
$\endgroup$
5
  • $\begingroup$ Nicely done! best answer for now... but how did you calculate that number? $\endgroup$
    – Rafe
    Oct 8, 2014 at 6:28
  • $\begingroup$ Is it better to do this spiral path instead of going back and forth? $\endgroup$
    – DarioP
    Oct 8, 2014 at 9:36
  • $\begingroup$ Why do you use circular curves of radius one? I would think the two constraints on the path are that it reach the outside corner, and that it reach the vertical/horizontal lines soon enough to avoid leaving gaps at the inside corner. I would think replacing the two curves with straight (but angled) segments would reduce the required distance. $\endgroup$
    – supercat
    Jan 12, 2015 at 23:44
  • $\begingroup$ Unless I'm missing something, that approach should improve the optimal distance to about 5064.3--a noticeable improvement. $\endgroup$
    – supercat
    Jan 13, 2015 at 0:57
  • $\begingroup$ Yes, you might be right. A while after I made my edit i had the feeling that I got it a bit wrong, but haven't got back to update it. $\endgroup$
    – Penguino
    Jan 15, 2015 at 0:16
1
$\begingroup$

I hope this helps you better visualize it

I hi

Improve this answer
$\endgroup$
7
  • $\begingroup$ How are you going to fill the gaps shown in this picture: i.imgur.com/6OFDVuo.png $\endgroup$
    – Moyli
    Oct 7, 2014 at 13:02
  • $\begingroup$ wow great - i think thats better than the old 'written' answer! i thought about your path and i find it more and more attractive! (i'll have to check length and compare again, but i like it!!) $\endgroup$
    – Martin Frank
    Oct 7, 2014 at 13:32
  • $\begingroup$ @Moyli that was the same what i was thinking!! but honestly i really like this picture as a base of conversation! $\endgroup$
    – Martin Frank
    Oct 7, 2014 at 13:36
  • $\begingroup$ @Moyli Just move the paint brush up until the gap is gone, then again repeat the diagonal movement inwards $\endgroup$
    – Ben Aaronson
    Oct 7, 2014 at 13:36
  • $\begingroup$ I thought about that. The only problem this method has is that if you start with a diagonal move second line will not cover that easily. $\endgroup$
    – Rafe
    Oct 7, 2014 at 13:44
1
$\begingroup$

A solution much better than Penguino's "spiral" can be achieved by starting with Penguino's zig-zag (the one with length 5098) but adjusting it slightly. Looking at the first place the line comes toward the left from the right, it extends all the way to (0,3) and then (0,5) for the purpose of being within one unit of (0,2) and (0,6), but for any x and y in the range (0,1) such that x²+y²≤1, those points could be reached by having the line extend to (1+x,1), (x,2+y), (x,6-y), and (1+x,5) before returning to the right. Penguino's zig-zag is a special case for x=0,y=1 but x=0.6 y=0.8 yields a much better result (assuming the right side is treated similarly, it will reduce the amount of x excursion per row by 1.2, but adds only 0.8 worth of y excursion, with about half of that being on shallow diagonals). The net effect is a total length under 5060.5--a noticeable savings.

The slight tweak used for the above number entails starting at (x,2-y), then moving to (x,y), and going to (1+x,1) and all subsequent points in normal fashion. Note that things must be drawn in that order to avoid leaving an unpainted area on the top. Note also that using slightly different coordinates could improve things a bit, but further improvements are apt to be fairly slight.

Improve this answer
$\endgroup$
-1
$\begingroup$

if you draw a circle you will be NEVER able to fill the rectangle...

if you FILL circles you might need w/2 x h/2 filled circles (even filled circles) on the first run and then need (w-1)/2 x (h-1)/2 filled circles (odd filled circles) to fill the gaps between... you can 'cut' pathes when you draw a even line and then switch to an odd line...

lenght of even line = 100; length of odd line = 99; path to switch from odd to even (and back) = Math.Squrt(2) (i'll say it's 1.4 for terms of easier use)...

so you have 100 x 100 + 99 x 99 + 99*1.4 = 10'000 + 9801 + 138.6 = 19939.6 (having rounding erros)

enter image description here

BLACK  = even circles
RED    = odd circles
PURPLE = rectangle
GREEN  = path

i can't proof that this path would be shorter:

enter image description here

update:

ok ok, after learning that that paint tool sprays continously i show another path...

enter image description here

Draw a cross (starts NorthWest -> SouthEast -> SouthWest -> NorthEast) on step back and then make the loop into the center

Improve this answer
$\endgroup$
20
  • $\begingroup$ The question says "circle area," not circle. Elgert's solution is 50 x 100 + 49 x 2 = 5098 so almost 4 times shorter. $\endgroup$
    – Moyli
    Oct 7, 2014 at 11:07
  • $\begingroup$ you describe the amount of circled areas - noth the length of the path... $\endgroup$
    – Martin Frank
    Oct 7, 2014 at 11:15
  • 1
    $\begingroup$ grml - i put so much effort into this hahahaa.... ok ok, thanks for clearing THAT out ^^$ $\endgroup$
    – Martin Frank
    Oct 7, 2014 at 11:45
  • 2
    $\begingroup$ Don't think the spiral answer works either. Assume the first three lengths to be 98 98 98, then you'll 'bump into' the lines you already had and the next series will be 96 96 96, then 94 94 94 etc etc. In total you'll end up with 3 times the sum of (2;4;6;..;90;92;94;96;98), or 7350, plus the length of the cross, which undoubtedly puts you over the previously mentioned value of 5098. $\endgroup$
    – Tim Couwelier
    Oct 7, 2014 at 12:07
  • 2
    $\begingroup$ You're both wrong, actually. It's 98, 98, 98, 96, 96, 94, 94, ... to a total of 4998 (plus or minus a couple units -- I can't tell off the top of my head how the spiral ends.) You can see the idea in this 10x10 square where the pattern is 8, 8, 8, 6, 6, 4, 4, 2, 2: i.imgur.com/ISBhYOw.png $\endgroup$
    – Moyli
    Oct 7, 2014 at 17:43

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.