title: How to efficiently find tiles of 2d grid that lay inside a circle sector keeping their relative position information?
body: <p>I have a 2d grid and a circle with <strong>constant</strong> radius. I know the center of a circle, its radius, vectors(or angles, have both) that define a sector, sector always has <strong>constant</strong> amount of degrees between start and end, but start and end can change their positions on the circle.</p>
  
  <p>On every update I need to load data from tiles inside this sector into 1d array of <strong>constant</strong> size in such a way that it keeps relative position information</p>
  
  <p>(if for current start,end and radius of sqrt(2)*1.0(tile diag), there is 40% of tile on the left(CCW), 100% in the middle and 40% on the right(CW), I need NULL, INFO, NULL inside my array, and if 80% on the left 100% in the middle and 0% on the right then INFO, INFO, NULL).</p>
  
  <p>Tile counts as inside if its center point is inside, I guess. I don't need % accuracy.</p>
  
  <p>My best idea for finding tiles that lay inside sector right now is on every update to iterate over all tiles inside a square region with (2*radius + 1) side and check their center points using this function from <a href="https://stackoverflow.com/a/13675772/1952982">here</a> copy/paste(changed function to bool and added var types):</p>
  
  <pre><code>bool areClockwise(Vec2d v1, Vec2d v2) {
    return -v1.x*v2.y + v1.y*v2.x &gt; 0;
  }
  bool isWithinRadius(Vec2d v, float radiusSquared) {
    return v.x*v.x + v.y*v.y &lt;= radiusSquared;
  }
  bool isInsideSector(Vec2d point, Vec2d center, Vec2d sectorStart, Vec2d sectorEnd, float radiusSquared) {
    Vec2d relPoint = point - center;
  
    return !areClockwise(sectorStart, relPoint) &amp;&amp;
           areClockwise(sectorEnd, relPoint) &amp;&amp;
           isWithinRadius(relPoint, radiusSquared);
  }
  </code></pre>
  
  <p>And I'm not sure yet, how to calculate size of my data array with info,null,info etc. Or how to fill it like first go tiles inside a circle of radius 1, then between 1 and 2, then between 2 and 3 etc and how to calculate maximum number of tiles in each of these "rows". Well, it doesn't need to be in this order I think, but it must be the same order every time.</p>
  
  <p><a href="https://i.stack.imgur.com/PTCn0.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/PTCn0.png" alt="enter image description here"></a></p>