Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


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.

  • You cannot reply to this topic
3 replies to this topic

#1 medevilenemy   Members   -  Reputation: 326

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.

Sponsor:

#2 RulerOfNothing   Members   -  Reputation: 1164

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.


#3 Olof Hedman   Crossbones+   -  Reputation: 2947

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.


#4 medevilenemy   Members   -  Reputation: 326

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.



PARTNERS