Point Indexing

[westloar]

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.

OR

b) Just running the algorithm on all points

[theagentd]

You could use a grid data structure to only test points that are in the vicinity of the half-circle.

[Best Username Ever]

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.

1   2   3   4

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

Games published by our own members! Check 'em out!

[westloar]

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:

1   2   3   4   5   6   7   8   9   10   11   12

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.

[Danny02]

1   2   3   4   5   6   7   8   9   10

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.

[Best Username Ever]

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?

Option A:

Iterate through each point
- 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.

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:

1   2   3   4   5   6   7   8   9   10   11   12

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.

Radians are totally irrelevant and your algorithm must have a typo because it does not do anything useful.

[Roquen]

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?

[westloar]

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.

[Best Username Ever]

Just get it working. What is 10 or 20 of something like that compared to resources measured in terms of mega-units or giga-units?

[Roquen]

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.