Java-Gaming.org
 Featured games (81) games approved by the League of Dukes Games in Showcase (497) Games in Android Showcase (114) games submitted by our members Games in WIP (563) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Point Indexing  (Read 1041 times) 0 Members and 1 Guest are viewing this topic.
westloar

Junior Member

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

Junior Member

 « 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.
westloar

Junior Member

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

Junior Member

 « 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 Member

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

Junior Member

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

 Add your game by posting it in the WIP section, or publish it in Showcase. The first screenshot will be displayed as a thumbnail.
 BurntPizza (16 views) 2014-09-19 03:14:18 Dwinin (34 views) 2014-09-12 09:08:26 Norakomi (61 views) 2014-09-10 13:57:51 TehJavaDev (84 views) 2014-09-10 06:39:09 Tekkerue (42 views) 2014-09-09 02:24:56 mitcheeb (64 views) 2014-09-08 06:06:29 BurntPizza (47 views) 2014-09-07 01:13:42 Longarmx (35 views) 2014-09-07 01:12:14 Longarmx (39 views) 2014-09-07 01:11:22 Longarmx (36 views) 2014-09-07 01:10:19
 BurntPizza 38x Riven 18x Rayvolution 17x princec 17x basil_ 16x ags1 16x KevinWorkman 15x kevglass 12x LiquidNitrogen 11x nsigma 11x theagentd 11x HeroesGraveDev 9x The Lion King 7x SHC 6x Gibbo3771 6x cylab 6x
 List of Learning Resources2014-08-16 10:40:00List of Learning Resources2014-08-05 19:33:27Resources for WIP games2014-08-01 16:20:17Resources for WIP games2014-08-01 16:19:50List of Learning Resources2014-07-31 16:29:50List of Learning Resources2014-07-31 16:26:06List of Learning Resources2014-07-31 11:54:12HotSpot Optionsby dleskov2014-07-08 01:59:08
 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