I have the algorithm for determining whether a specific point is within the area of a semi-circle, but which is the more efficient way of determining whether multiple points lay within that area:
a) Running through each of the points and discounting those that couldn’t possibly be within the circle i.e. are much further away from the origin of the circle than the length of radius or diameter. Then creating an index or array of the points that could be within the circle and running the algorithm.
Option b is like writing an entire page of writing and then going back to add punctuation. Kind of pointless on a CPU. Your algorithm should be one line of code.
// Well three lines to save typing
double dx = x1 - x2;
double dy = y1 - y2;
if(dx * rx + dy * ry >= 0 && dx * dx + dy * dy <= rx * rx + ry * ry) { /* Do something */ }
Ask if you need an explanation of the vector math.
The code you posted is essentially my algorithm, I don’t think I explained with enough clarity in my first post.
The question I was asking is should I filter the points that definitely could not be within the semi-circle i.e. have a distance from the origin of the circle bigger than it’s radius and then run the algorithm on the points that could be in the circle.
OR
Is it more efficient to just iterate through all points with the algorithm?
Also I realise that the better method would be to use radians (I don’t understand these yet), but would the following work to determine whether a point within the circle is in the top semicircle or bottom semicircle:
A = Answer
P = Point (x,y)
C = Circle Origin (x,y)
P = (P - C)
C = (C - C)
A = (C - P)
If A is -ve then P lies within the top half of the circle.
If A is +ve then P lies within the bottom half of the circle.
This is obviously not in Java, it is more of a mental exercise.
vec2 normal;//normal of the line which halfs your circle, pointing in the direction of the half you are interesting in
vec2 center;//center of the circle
float radiusSquare;//square of the radius(radius²)
boolean isInsideHalfCircle(Vec2 point)
{
vec2 dir = point - center;//vector from center to point
return dir.dot(normal) > 0 && dir.dot(dir) <= radiusSquare;//dir.dot(dir) is the length of dir squared
}
remember that if you have a logical and(&&), if the first argument is false the second isn’t even evaluated because the hole equation is already false.
If the point is not within the radius, go to the next point
If you get to this point, add it to a temporary list
Iterate through each point in the list
If the point is not in the right half of the circle, go to the next point
If you get to this point in the loop, add it to the final loop.
Option B:
Iterate through each point
If the point is not within the radius, go to the next point
If the point is not in the right half of the circle, go to the next point
Add point to the final list if you get to this point
You are basically asking if its faster to filter through a list of points once, then filter it again. Or filter it once and go directly to the result. In order to filter over something, you have iterate over every element. For option A, you do N elements on the first pass and M elements on the second. For option B you test N elements and do a second test on the M elements that pass the first test. The difference is you don’t have to waste time copying data to a new array, doing M extra loop tests, and waiting for the CPU to cache extra memory when inserting into the temporary list or starting back at the beginning of the list in the second loop.
[quote]Also I realise that the better method would be to use radians (I don’t understand these yet), but would the following work to determine whether a point within the circle is in the top semicircle or bottom semicircle:
A = Answer
P = Point (x,y)
C = Circle Origin (x,y)
P = (P - C)
C = (C - C)
A = (C - P)
If A is -ve then P lies within the top half of the circle.
If A is +ve then P lies within the bottom half of the circle.
This is obviously not in Java, it is more of a mental exercise.
[/quote]
Radians are totally irrelevant and your algorithm must have a typo because it does not do anything useful.
There’s not enough information to answer the question. semi-circle = half circle? Are they arbitrarily or fixed oriented? Are the points fixed/dynamic or mixed? What’s the maximum number of these queries per frame? What’s a guess on the number of points (total) and max inside a query? Can you say anything about the distribution of queries and/or points?
Essentially the pc swings a sword in 180 degree arc infront of himself and I want to check which enemy mobs i.e. the points are in said arc.
I would imagine there could be 10 - 20 mobs on the screen at a time.
I’m not so hot with my maths so wasn’t sure if I would have to do some calculations based ona circle and then work out if the mobs were in the top half of the circle i.e. within the sword swing or if there is maths that allows you to just work with semicircles.
I figured that you would have to at some level query all the points on screen to discover if they were in the circle, so the max points in a query would be the same as the number of points on screen.
The max number of queries per frame is like to be very small as it will be limited by the amouint of times the pc can swing, possibly 1 a second or less.
Any efficiency gains from something like this should be secondary…a result of knowing what entities are close to one another, which is useful for all proximity queries. The problem itself isn’t worth spending any time attempting to make it fast…just make it work and feel good.
When you know nearby objects, then the above listed is near optimal…check on side of directed line and inside radius squared. As a brain exercise only, then the ordering will make a difference but not worthwhile in this case.
