title: Efficient Algorithm to obtain Points in a Circle around a Center
body: <h2>Problem</h2>
  
  <p>I want to get all pixels that are within a circle of a given radius about a given point, where points can only have <strong>integer coordinates</strong>, i.e. pixels in a canvas.</p>
  
  <p><a href="https://i.stack.imgur.com/zNvUF.png" rel="noreferrer"><img src="https://i.stack.imgur.com/zNvUF.png" alt="Illustration"></a></p>
  
  <p>So I want to obtain all points in the yellow area given <code>(x, y)</code> and <code>r</code>.</p>
  
  <h2>Approaches</h2>
  
  <p>The most efficient way I can think of is to loop through a square around <code>(x, y)</code> and check the <em>Euclidean distance</em> for each point:</p>
  
  <pre class="lang-cpp prettyprint-override"><code>for (int px = x - r; px &lt;= x + r; px++) {
    for (int py = y - r; py &lt;= y + r; py++) {
      int dx = x - px, dy = y - py;
  
      if (dx * dx + dy * dy &lt;= r * r) {
        // Point is part of the circle.
      }
    }
  }
  </code></pre>
  
  <p>However, this means that this algorithm will check <code>(r * 2)^2 * (4 - pi) / 4</code> pixels that are not part of the circle. <code>dx * dx + dy * dy &lt;= r * r</code>, which seems rather expensive, is called redundantly almost <code>1 / 4</code> of the time.</p>
  
  <p>Integrating something like what was <a href="https://stackoverflow.com/a/7227057/6509751">proposed here</a> might enhance performance:</p>
  
  <pre class="lang-cpp prettyprint-override"><code>for (int px = x - r; px &lt;= x + r; px++) {
    for (int py = y - r; py &lt;= y + r; py++) {
      int dx = abs(x - px), dy = abs(y - py);
  
      if (dx + dy &lt;= r || (!(dx &gt; r || dy &gt; r) &amp;&amp; (dx * dx + dy * dy &lt;= r * r))) {
        // Point is part of the circle.
      }
    }
  }
  </code></pre>
  
  <p>However as the author themselves pointed out, this is likely not going to be faster when most of the points are going to be inside of the circle (especially because of <code>abs</code>), which <code>pi / 4</code> are in this case.</p>
  
  <hr>
  
  <p>I was not able to find any resources on this question. I am looking specifically for a solution in C++ and not something <a href="https://stackoverflow.com/q/36358188/6509751">in SQL</a>. </p>