3

I have a 2d grid and a circle with constant radius. I know the center of a circle, its radius, vectors(or angles, have both) that define a sector, sector always has constant amount of degrees between start and end, but start and end can change their positions on the circle.

On every update I need to load data from tiles inside this sector into 1d array of constant size in such a way that it keeps relative position information

(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).

Tile counts as inside if its center point is inside, I guess. I don't need % accuracy.

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 here copy/paste(changed function to bool and 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 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.

enter image description here

Community
  • 1
  • 1
userqwerty1
  • 887
  • 2
  • 9
  • 23
  • simple math, for checking is full inside the circle check if all tile points are within the range of the circle radiour, for check collision check if at least one point is whithin the radious – Netwave Jan 07 '16 at 17:34
  • Relevant question: [Get every pixel of an arc/sector](http://stackoverflow.com/questions/33422777/get-every-pixel-of-an-arc-sector) – Vittorio Romeo Jan 07 '16 at 17:43
  • Can you store the location of the squares in polar co-ordinates? – Fantastic Mr Fox Jan 07 '16 at 18:26
  • @Ben I sure can convert them into polar. But what's the difference then, between converting all points into polar coo system and running code above and computing square distance to each tile center on every update? – userqwerty1 Jan 07 '16 at 18:50
  • I didn't understand this “1d array of constant size in such a way that it keeps relative position information” part, nor the parenthesized paragraph after that. What exactly does relative position information mean here? How can a tile that is 100% in the middle (between the two rays?) still be 40% left (outside the sector) and 40% right? What do the `NULL` values signify? Data you don't have to load? So is the 1d array sized to contain the sector or to contain the whole grid? – MvG Jan 07 '16 at 19:23
  • @MvG I'm terribly sorry for this. Let me try to express my thoughts again. Here's picture with what I meant with 40/100/40 http://i.imgur.com/IcNnDQE.png tiles with red dots are inside sector and others outside for simplicity. I need to check only one point - center, and not 4. And 1d array. Well, color info will be fed to neural network, so I need constant size array of tiles inside sector but depending on rotation of the sector one time it can be 10 tiles inside and another less or more because ray can go like on the left of the picture on both sides, and all those tiles are not included. – userqwerty1 Jan 07 '16 at 20:23
  • Still trying to understand the 40/100/40. Take 3 tiles which are consecutive neighbours in the 8-neighbourhood of the center. Then the example ray covers 40% of the first, 100% of the second, 40% of the third and 0% of the other 5 surrounding tiles. Is that what you meant? Is the center of the circle located at a tile center, as it is here in the question, or not neccessarily so, as it is in your example picture from the comment? The neural network aspect helps clarify your requirements a lot. So you essentially want the array positions to move with the sector, as much as possible, right? – MvG Jan 07 '16 at 20:44
  • @MvG I'm making a vision sensor for a grid :) And yes, that's what I meant by 40/100/40, if radius small only 8 neighbours can be included and sector cuts like in picture. I'm making brute force approach in python right now to show what I mean when I said that at one time it can be 10 and another less or more. No, center of the circle is arbitrary, my creatures live above grid and can move freely in real values. – userqwerty1 Jan 07 '16 at 21:05
  • @MvG Here's brute force approach showing that number of tiles inside changes during rotation http://www.codeskulptor.org/#user41_A1NkXd92Jx_64.py //need to press triangle to run//edited. – userqwerty1 Jan 07 '16 at 21:33

1 Answers1

1

To find all tiles inside the sector, follow e.g. Get every pixel of an arc/sector as suggested by Vittorio Romeo. Or stick with your approach. Because in my opinion the far more difficult part is this “in such a way that it keeps relative position information” requirement you mention. The performance cost for that will likely outweight the cost for a naive enumeration of all affected pixels.

For the relative position assignment, I'd start with a standard position for the arc, say with the center at the origin and the first ray along the positive x axis. In that situation you place as many tile positions as you maximally expect to be covered. Or more precisely: as many as you want to have entries in your 1d array. You don't have to place them in a grid-like fashion, but can use points on concentric circles or whatever you fancy. Now you apply a coordinate transformation to your actual tile positions, transforming them to the standard position and comparing them to the standard positions. You'll end up with a matrix of distances, or perhaps squared distances if you prefer those.

Now you apply the hungarian method to find an optimal (i.e. least sum of (squared) distances) match between standard positions and actual positions. That tells you where to place the tiles in your 1d array. Since the hungarian method is O(n³), the cost of tile enumeration which is O(n) and that of pairwise distance computation which is O(n²) are small by comparison, at least asymptotically. Let's hope the number n of covered tiles doesn't get too large for this approach to be feasible.

Community
  • 1
  • 1
MvG
  • 57,380
  • 22
  • 148
  • 276