Java-Gaming.org    
Featured games (91)
games approved by the League of Dukes
Games in Showcase (577)
games submitted by our members
Games in WIP (498)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Point Indexing  (Read 868 times)
0 Members and 1 Guest are viewing this topic.
Offline westloar

Junior Member





« Posted 2013-01-12 17:43:36 »

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
Offline theagentd
« Reply #1 - Posted 2013-01-12 18:13:18 »

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

Myomyomyo.
Offline Best Username Ever

Junior Member





« Reply #2 - Posted 2013-01-12 18:18:15 »

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!
Legends of Yore - The Casual Retro Roguelike
Offline westloar

Junior Member





« Reply #3 - Posted 2013-01-12 20:16:04 »

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.
Offline Danny02
« Reply #4 - Posted 2013-01-12 20:25:18 »

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.
Offline Best Username Ever

Junior Member





« Reply #5 - Posted 2013-01-12 21:33:26 »

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.

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:

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.
Offline Roquen
« Reply #6 - Posted 2013-01-12 21:35:26 »

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?
Offline westloar

Junior Member





« Reply #7 - Posted 2013-01-13 02:28:56 »

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.
Offline Best Username Ever

Junior Member





« Reply #8 - Posted 2013-01-13 02:45:02 »

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?
Offline Roquen
« Reply #9 - Posted 2013-01-13 10:27:18 »

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.
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

xsi3rr4x (18 views)
2014-04-15 18:08:23

BurntPizza (15 views)
2014-04-15 03:46:01

UprightPath (28 views)
2014-04-14 17:39:50

UprightPath (13 views)
2014-04-14 17:35:47

Porlus (29 views)
2014-04-14 15:48:38

tom_mai78101 (54 views)
2014-04-10 04:04:31

BurntPizza (111 views)
2014-04-08 23:06:04

tom_mai78101 (212 views)
2014-04-05 13:34:39

trollwarrior1 (181 views)
2014-04-04 12:06:45

CJLetsGame (187 views)
2014-04-01 02:16:10
List of Learning Resources
by Longarmx
2014-04-08 03:14:44

Good Examples
by matheus23
2014-04-05 13:51:37

Good Examples
by Grunnt
2014-04-03 15:48:46

Good Examples
by Grunnt
2014-04-03 15:48:37

Good Examples
by matheus23
2014-04-01 18:40:51

Good Examples
by matheus23
2014-04-01 18:40:34

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:22:30

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:05:20
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!