What is a good way to iterate over all the points on and within an arc wedge, given a known center point, start angle, end angle, radius, and grid spacing?
Context: The lighting system for my engine blends arcs into an opaque mask (thus creating areas of visible "light" where you can see through the mask). These lights are defined by the center point of the circle they'd be on, the starting and ending angles of the arc (say, 0 and pi/2), and the radius of the imaginary circle the arc would be on.
The equation for converting a given coordinate from world coords to the coords of the underlying detection system is:
result = (int)(input+1)*100
I could brute-force this easily enough by iterating over angles and then over lines at angle from center to radius, but that would be really inefficient and wouldn't necessarily hit every grid point on the wedge (Unless the iteration over angles was really tight, and that would make it even less efficient).
Coordinates on a wedge
Is there a particular order you want to go over the points in the wedge? If not, you could just do this:
- Start with two lists of points: open and visited. The visited list is initially empty, while the open list starts off with one element: the center point.
- If the open list is empty, stop. Otherwise take a point on the open list P.
- Put P on the visited list.
- Examine the points in the 4 cardinal directions from P (according to the grid spacing) except for those on the visited list.
- Add any of these points which are inside the wedge to the open list. Go back to step 2.
An efficient way could be to split it in a few parts, trace edges and fill scanlines, and use bresenham to trace the circle edge.
It's kind of like a triangle(or a few) with a funky edge.
It's kind of like a triangle(or a few) with a funky edge.
Author
I'm not actually coding this bit myself, someone working with me is (I posted the problem in an attempt to help him out). They managed to get a solution working. Their approach basically works out to splitting a circle into its quadrants (obviously, for a wedge that only occupies a couple wedges, less processing is done), iterating over the X values within that quadrant, then iterating over the potential Y values in that column. The result is a gaurantee of hitting all grid elements, and the code doesn't strike me as being too horrifically inefficient (though I'm sure we'll want to go in and tighten it up).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
