• Create Account

## Coordinates on a wedge

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

3 replies to this topic

### #1medevilenemy  Members

361
Like
0Likes
Like

Posted 20 September 2012 - 06:40 PM

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

Edited by medevilenemy, 20 September 2012 - 06:42 PM.

There was a saying we had in college: Those who walk into the engineering building are never quite the same when they walk out.

### #2RulerOfNothing  Members

1369
Like
0Likes
Like

Posted 21 September 2012 - 07:34 AM

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.

### #3Olof Hedman  Members

5699
Like
0Likes
Like

Posted 21 September 2012 - 07:46 AM

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.

Edited by Olof Hedman, 21 September 2012 - 07:48 AM.

### #4medevilenemy  Members

361
Like
0Likes
Like

Posted 23 September 2012 - 01:46 AM

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

Edited by medevilenemy, 23 September 2012 - 01:47 AM.

There was a saying we had in college: Those who walk into the engineering building are never quite the same when they walk out.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.