3 ms·
I wrote something similar in Apple ][+ Basic. It had a cool optimization: it would scan 16 points around the boundary of each 64x64 pixel block, and if they wer
by tlb 12y ago
I wrote something similar in Apple ][+ Basic. It had a cool optimization: it would scan 16 points around the boundary of each 64x64 pixel block, and if they were all-black (in the set) or all-white, it would assume the rest of the block was the same and finish quickly. My dot-matrix printer had something like 2000 pixels of width and limited-only-by-patience height, so the printouts were amazingly detailed.
I wish I'd had similarly inclined peers at the time. We could have totally geeked out. But I was the only one I knew.
- ska 12y agoEdit: the wording "assumed" led me to interpret that you didn't know about this mathematical property, but perhaps you did! You almost hit upon a real property of the set, namely that if you can find a closed contour of the interior, all the enclosed points are in the set... A common variant of your approach, then, was to quad tree the area of interest and evaluate the boundary of each square, if it was consistent you just fill in the block, otherwise subdivide. This is a massive speed up for locations like the canonical initial view with large areas of the set shown... ... Of course the problem with this is you are sampling discretely, so inferring that the boundary is closed because a sampling of it is doesn't really work. Your filling in of the white blocks like this is particularly problematic, as that can easily cut off "children" in the set. You can do this sort of approach properly, but it is a bit more complicated.