<p>If the contour exists in a loop <em>entirely inside one of your coarse cells</em> — or has some thin protrusion that passes between the corner points, at least — then it will be missed entirely; it will look just like empty space in that cell. This puts a limit on how large your initial grid can be: it must be fine enough that at least one point lies within and one point outside the contour.</p>
<p>Now, if you know that <em>there must be at least one loop within a region</em> then you can sample finer until you find it. But then you've given up on “plot any implicit curve”, because you need to know where to look.</p>
<p>This doesn't mean there isn't any point in multiple resolutions. Once a grid of a certain resolution has found the features of the shape (as many as are coarse enough for it to notice), you can sample more finely to get <em>more smoothly curved</em> lines/surfaces.</p>

CC BY-SA 4.0
2023-05-06T05:32:36.317Z
2023-05-06T05:32:36.317Z
Kevin Reid
<p>So I just saw a video on <a href="https://youtu.be/6oMZb3yP_H8" rel="nofollow noreferrer">Marching Squares</a> by reducible, and I thought of a straightforward optimisation, but I couldn't find anything about it online. Basically here's the idea -<br />
Start with a fairly large grid size, sample the points, this forms a very rough image, but what we do now is only for the cells which the contour passes through, we further divide them into more cells recursively (make the grid smaller but only inside those cells) and sample more points until a set recursion depth. For example turning a single cell into 4 different cells only require you to sample an additional 5 points
This should give us a much sharper image without having to sample too many points, most of which give us no information.</p>
<p>This came pretty naturally to me so I refuse to believe that no one else has thought of this, so is there any particular reason why I wasn't able to find anything about it?
(Maybe it has some fault I don't see, or maybe there's a better optimisation, or maybe it just has a different name I don't know)</p>

CC BY-SA 4.0
2024-10-25T16:49:10.553Z
See [Quadtree Algorithms for Contouring Functions of Two Variables](https://doi.org/10.1093/comjnl/33.5.402) by K. G. Suffern
lhf
<2d-graphics><optimisation>
Recursive sampling in Marching Squares
TanejaTj
# Recursive sampling in Marching Squares

(Asked by: username_0 on 2023-05-05)

So I just saw a video on [Marching Squares](https://youtu.be/6oMZb3yP_H8) by reducible, and I thought of a straightforward optimisation, but I couldn't find anything about it online. Basically here's the idea -  
Start with a fairly large grid size, sample the points, this forms a very rough image, but what we do now is only for the cells which the contour passes through, we further divide them into more cells recursively (make the grid smaller but only inside those cells) and sample more points until a set recursion depth. For example turning a single cell into 4 different cells only require you to sample an additional 5 points
This should give us a much sharper image without having to sample too many points, most of which give us no information.

This came pretty naturally to me so I refuse to believe that no one else has thought of this, so is there any particular reason why I wasn't able to find anything about it?
(Maybe it has some fault I don't see, or maybe there's a better optimisation, or maybe it just has a different name I don't know)

**Tags:** 2d-graphics, optimisation

> **Comments:**
> **username_1**: See [Quadtree Algorithms for Contouring Functions of Two Variables](https://doi.org/10.1093/comjnl/33.5.402) by K. G. Suffern  

---

## 1 answers

### Answer by username_2 on 2023-05-06. Score: 1

If the contour exists in a loop *entirely inside one of your coarse cells* — or has some thin protrusion that passes between the corner points, at least — then it will be missed entirely; it will look just like empty space in that cell. This puts a limit on how large your initial grid can be: it must be fine enough that at least one point lies within and one point outside the contour.

Now, if you know that *there must be at least one loop within a region* then you can sample finer until you find it. But then you've given up on “plot any implicit curve”, because you need to know where to look.

This doesn't mean there isn't any point in multiple resolutions. Once a grid of a certain resolution has found the features of the shape (as many as are coarse enough for it to notice), you can sample more finely to get *more smoothly curved* lines/surfaces.


---

