Java-Gaming.org Hi !
 Featured games (84) games approved by the League of Dukes Games in Showcase (565) Games in Android Showcase (151) games submitted by our members Games in WIP (606) 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 1295 times) 0 Members and 1 Guest are viewing this topic.
westloar

Junior Devvie

 « Posted 2013-01-12 16: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
theagentd

« JGO Bitwise Duke »

Medals: 410
Projects: 2
Exp: 8 years

 « Reply #1 - Posted 2013-01-12 17:13:18 »

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

Myomyomyo.
Best Username Ever

Junior Devvie

 « Reply #2 - Posted 2013-01-12 17: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 typingdouble 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

Junior Devvie

 « Reply #3 - Posted 2013-01-12 19: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 = AnswerP = 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
 « Reply #4 - Posted 2013-01-12 19: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 invec2 center;//center of the circlefloat 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

Junior Devvie

 « Reply #5 - Posted 2013-01-12 20: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 = AnswerP = 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
 « Reply #6 - Posted 2013-01-12 20: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?
westloar

Junior Devvie

 « Reply #7 - Posted 2013-01-13 01: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.
Best Username Ever

Junior Devvie

 « Reply #8 - Posted 2013-01-13 01: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?
Roquen
 « Reply #9 - Posted 2013-01-13 09: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.

 ags1 (21 views) 2015-03-31 10:55:12 theagentd (13 views) 2015-03-27 23:08:20 wxwsk8er (54 views) 2015-03-20 15:39:46 Fairy Tailz (47 views) 2015-03-15 21:52:20 Olo (29 views) 2015-03-13 17:51:59 Olo (32 views) 2015-03-13 17:50:51 Olo (39 views) 2015-03-13 17:50:16 Olo (44 views) 2015-03-13 17:47:07 ClaasJG (60 views) 2015-03-10 11:36:42 ClaasJG (43 views) 2015-03-10 11:33:01
 BurntPizza 21x LiquidNitrogen 21x basil_ 19x KevinWorkman 18x EgonOlsen 17x theagentd 16x Roquen 16x wessles 11x Varkas 11x 65K 11x Riven 11x Rayvolution 9x phu004 8x SHC 8x princec 8x Ashedragon 8x
 How to: JGO Wikiby Mac702015-02-17 20:56:162D Dynamic Lighting2015-01-01 20:25:42How do I start Java Game Development?by gouessej2014-12-27 19:41:21Resources for WIP gamesby kpars2014-12-18 10:26:14Understanding relations between setOrigin, setScale and setPosition in libGdx2014-10-09 22:35:00Definite guide to supporting multiple device resolutions on Android (2014)2014-10-02 22:36:02List of Learning Resources2014-08-16 10:40:00List of Learning Resources2014-08-05 19:33:27
 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