1
$\begingroup$

I'm trying to make a function that, given floating point coordinates/arguments, returns the area of a shape within a given pixel. The purpose is drawing anti-aliased shapes for a game's UI.

I know how to do rectangles, as it is very simple, but other shapes (ellipses, triangles, non-regular polygons, etc.) are a bit harder.

So, given a set of points for a polygon, if I loop through the shape on a grid with a cell size of 1x1, I want the area of the shape within said cell.

What about circles/ellipsoids?

Picture example: Pixel in Circle

What is the area of the circle within the bounds of the red pixel, given the pixel coordinates, circle coordinates, and circle radius?

Better example: Zoomed Pixel in Circle

What is the area of the white within the non-shaded area, given the four coordinates of the shaded area, coordinate of circle, and radius of circle?

What about with any polygon, regular or irregular, given a list of coordinates, and a coordinate to find the area within?

What I mean by the checking coordinate is, area within given-coordinate-to-check -> given-coordinate-to-check+1

Sorry if my question is confusing!

To restate the question more clearly, what is the area of a square-shaped shaded region on any possible geometric shape?

$\endgroup$
  • 1
    $\begingroup$ "The purpose is drawing anti-aliased shapes for a game's UI." Don't do this yourself! Surely your graphics library/API already provides a way to draw smooth anti-aliased shapes. $\endgroup$ – Rahul Oct 29 '16 at 18:23
  • $\begingroup$ Haha, well it doesn't, surprisingly! $\endgroup$ – user91670 Oct 29 '16 at 18:57
1
$\begingroup$

There are ways to do any shape. However, methods that work for one shape may not work for another. As such, programming this could be hard.

I suggest a Monte Carlo approach. Put points randomly in your square, see how many of them fall within your polygon, and that gives you an approximation of area within your square. The more points the better.

$\endgroup$
  • $\begingroup$ Ohhh, this seems like it could work. Approximation isn't an issue here! $\endgroup$ – user91670 Oct 29 '16 at 18:56
  • $\begingroup$ @user91670: This (random sampling) is an extremely common method, that is used by most raytracers to achieve antialiasing. ($N^2$ random samples produce better (psychovisual) results than $N \times N$ regular samples in a grid.) One very nice speedup is that if you know which surfaces/edges are involved in the calculation for the four points at $(x,y)$, $(x+1,y)$, $(x,y+1)$, $(x+1,y+1)$, it is enough to consider those surfaces/edges in the random samples. $\endgroup$ – Nominal Animal Oct 29 '16 at 19:08

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.