c++ - How to efficiently find tiles of 2d grid that lay inside a circle sector keeping their relative position information? -

i have 2d grid , circle constant radius. know center of circle, radius, vectors(or angles, have both) define sector, sector has constant amount of degrees between start , end, start , end can change positions on circle.

on every update need load data tiles inside sector 1d array of constant size in such way keeps relative position information

(if current start,end , radius of sqrt(2)*1.0(tile diag), there 40% of tile on left(ccw), 100% in middle , 40% on right(cw), need null, info, null inside array, , if 80% on left 100% in middle , 0% on right info, info, null).

tile counts inside if center point inside, guess. don't need % accuracy.

my best idea finding tiles lay inside sector right on every update iterate on tiles inside square region (2*radius + 1) side , check center points using function here copy/paste(changed function bool , added var types):

bool areclockwise(vec2d v1, vec2d v2) {   return -v1.x*v2.y + v1.y*v2.x > 0; } bool iswithinradius(vec2d v, float radiussquared) {   return v.x*v.x + v.y*v.y <= radiussquared; } bool isinsidesector(vec2d point, vec2d center, vec2d sectorstart, vec2d sectorend, float radiussquared) {   vec2d relpoint = point - center;    return !areclockwise(sectorstart, relpoint) &&          areclockwise(sectorend, relpoint) &&          iswithinradius(relpoint, radiussquared); } 

and i'm not sure yet, how calculate size of data array info,null,info etc. or how fill first go tiles inside circle of radius 1, between 1 , 2, between 2 , 3 etc , how calculate maximum number of tiles in each of these "rows". well, doesn't need in order think, must same order every time.

to find tiles inside sector, follow e.g. get every pixel of arc/sector suggested vittorio romeo. or stick approach. because in opinion far more difficult part “in such way keeps relative position information” requirement mention. performance cost outweight cost naive enumeration of affected pixels.

for relative position assignment, i'd start standard position arc, center @ origin , first ray along positive x axis. in situation place many tile positions maximally expect covered. or more precisely: many want have entries in 1d array. don't have place them in grid-like fashion, can use points on concentric circles or whatever fancy. apply coordinate transformation actual tile positions, transforming them standard position , comparing them standard positions. you'll end matrix of distances, or perhaps squared distances if prefer those.

now apply hungarian method find optimal (i.e. least sum of (squared) distances) match between standard positions , actual positions. tells place tiles in 1d array. since hungarian method o(n³), cost of tile enumeration o(n) , of pairwise distance computation o(n²) small comparison, @ least asymptotically. let's hope number n of covered tiles doesn't large approach feasible.