6
\$\begingroup\$

Are there any algorithms to find out which cells in a 2D grid lie inside/is part of a slice of a circle - a pie slice shaped region?

Essentially, as per image below, I need to list out all the green cell coordinates.

enter image description here

At the moment, I am ray casting (using DDA based line interpolation) from the starting red cell, and sweeping across the area in with (arbitrarily chosen) small fixed angle increments, casting multiple rays; but this does not guarantee all cells will be covered.

Are there any approaches to this problem?

\$\endgroup\$
  • \$\begingroup\$ You don't need to use an arbitrary number of angle increments. Instead, divide the total angle by the number of pixels between the two outer arc points, then use that step value. You'll have lots of duplicate hits on the inner portions of the sector, but guaranteed just enough for the outer arc. \$\endgroup\$ – Tim Holt Dec 8 '15 at 20:06
4
\$\begingroup\$

If it helps I have a similar image from helping someone with this problem a long time ago. It better illustrates the constraints (you can ignore the near plane since your example doesn't have one):

enter image description here

As you can see you're trying to figure out which corners are inside of the region. You have to make sure they're within the circle which is a distance check. Say our camera is at cameraPosition represented by an (x, y) vector then for each point you're checking just do:

if ((point.x - cameraPosition.x) * (point.x - cameraPosition.x) + (point.y - cameraPosition.y) * (point.y - cameraPosition.y) < radius * radius)

Then you need to figure out if the points are inside of the two lines (3 in my example image, but we'll just use the two long lines). To do this you can use a dot product test. Generate your two vector using (cos(angle), sin(angle)) or however best works for you. Then for the left and right ray find it's left hand normal. (y, -x) or (-y, x) depending on your coordinate system. Then for each point we'll take the dot product between the (point - cameraPosition) and the normal. This will tell us which side of the ray our point is on. If it's on the wrong side we can discard it.

normalLeftX = -sin(angle1)
normalLeftY = cos(angle1)
normalRightX = sin(angle2)
normalRightY = -cos(angle2)
pointRayX = point.x - cameraPosition.x;
pointRayY = point.y - cameraPosition.y;
if (pointRayX * normalLeftX + pointRayY * normalLeftY > 0 &&
    pointRayX * normalRightX + pointRayY * normalRightY > 0)

(You might have to flip the normals between (y, -x) and (-y, x) if I made a mistake).

Combining all 3 checks will test if the point is inside. When a point is inside that means all 4 adjacent tiles are inside. (I'll let someone else expand it to code if they want).

I will point out that this algorithm is very closely related to an optimal vector processing algorithm for triangle rasterization. It would be completely overkill but you can use it if you have to test large amounts of tiles.

https://software.intel.com/en-us/articles/rasterization-on-larrabee

\$\endgroup\$
  • \$\begingroup\$ Nice. I think I got the gist of it now. Thanks a bunch. \$\endgroup\$ – Benzi Dec 9 '15 at 5:23
0
\$\begingroup\$

Your best bet is looking around for "Roguelike Vision Algorithms." This result seems to have a goodly collection, discussing existing methods--including raycasting--and then suggesting the author's own method. His algorithm contains more code than I am willing to copy-paste to this answer, but involves treating cells as walls with beveled edges and using some manner of raycasting:

enter image description here

Whether or not you are interested in "shadow casting" (that is, if a cell inside the cone is prevents areas behind it from being "visible") will likely play a large part in determining which method suits your needs.

\$\endgroup\$
  • \$\begingroup\$ "Roguelike Vision Algorithms" - the keywords I didn't know about... Thanks, I'll have a look around. \$\endgroup\$ – Benzi Dec 8 '15 at 18:08
  • \$\begingroup\$ Glad to help out. Its not a subject I know anything about, but I do have a bit of Google-Fu. ;) \$\endgroup\$ – Draco18s Dec 8 '15 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.