2
\$\begingroup\$

I've an unit in a 2d (integer) grid-based game, which has a bearing. Now I want to display an arc, with a given radius (for instance simulating a 90 degree cone of a sensor with respect to the bearing of the unit, attaching this sensor).

How can I efficently get all points in the 2d grid to draw that 'cone' arc ?

This question actually is about a similar issue but in contrast I want to get all points and not only check if a given point is located in that sector.

\$\endgroup\$
  • \$\begingroup\$ A 2d grid contains an infinite number of points. Do you mean the ones with an integer x and y coordinate? \$\endgroup\$ – Bálint Oct 24 '17 at 19:08
  • \$\begingroup\$ Yes, I have meant integer based \$\endgroup\$ – Marco Oct 24 '17 at 19:43
  • \$\begingroup\$ Do you want to draw just the curved arc line, or do you want to fill it in down to the center, like a pie slice? \$\endgroup\$ – Tim Holt Oct 24 '17 at 23:54
  • \$\begingroup\$ @TimHolt yes, like a pie slice \$\endgroup\$ – Marco Oct 25 '17 at 6:28
2
\$\begingroup\$

To get every point, loop through the points between (px - r; py - r) and (px + r; py + r) where px and py are the player's x and y coordinates and r is the radius of the circle. For each point, do the following:

  1. Given the point (x; y) calculate the distance of this point and the player's position (d = √((x - px)^2 + (y - py)^2)). Save this somewhere because you'll need it.
  2. If d is less than or equal to the radius of the circle, then this point is inside the main circle and you can continue. Otherwise just go to the next point.
  3. Normalize the vector pointing from the player position to the current point using the distance you calculated earlier. The new vector should be ((x - px) / d, (y - py) / d). Then get the dot product of this vector and (1, 0) to get the cosine of the angle between the (It'll be (x - px) / d if you did everything correctly).
  4. The point is inside the cone if the arccosine of the value you get after the dot product is between the angles.

In pseudo code:

getPoint(px, py, angle1, angle2, r) do
    output = empty set

    for each x between px - r and px + r) do
        for each y between py - r and py + r) do
            d = sqrt((px - x)^2 + (py - y)^2)
            if d > r then
                continue
            end

            d = acos((x - px) / d)
            if d >= angle1 and d <= angle2 then
                add (x, y) to output
            end
        end
    end
    return output
end
\$\endgroup\$
2
\$\begingroup\$

If you think of your grid as pixels in an image/raster display, you could use the midpoint circle algorithm for rasterizing circles.

Wikipedia's page for the algorithm has a section on drawing incomplete octants that could do the job.

\$\endgroup\$

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.