View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# Hash Distance & Angle To Produce Unique Value

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

6 replies to this topic

### #1gretty  Members

Posted 20 July 2014 - 11:50 PM

Hello

I have many vertices drawn on my Unity3d C# application window (thousands). I am attempting to come up with a fast way to detect which vertex has been clicked.

My idea is to use a sorted list. The list will be ordered by a vector/vertices distance to (0,0,0):

List <KeyValuePair<double, GameObject>> vectorMap = new List <KeyValuePair<double, GameObject>>();


I use a binary search to order, search and add to the list.

public void recordElementVertices(Element ele) {
// Element is a Sub-Class of GameObject

foreach (Vector3d v in ele.WorldVertices) {
double distFromZero = Vector3d.Distance(Vector3d.zero, v);

int index = -1;
if (Algorithms.LowerBounds(vertexDistanceList, distFromZero, out index, DEF_PRECISION) != Algorithms.SearchResult.FOUND_TARGET)
vertexDistanceList.Insert(index, new KeyValuePair<double, List<GameObject>>(distFromZero, new List<GameObject>()));

}
}


Hit Test (Search) Method:

public List<GameObject> hits(Vector3d mousePos) {

int 	index 			= -1;
double 	distFromZero 	= Vector3d.Distance(Vector3d.zero, mousePos);

// Binary search will search for an exact hit or find the closest vertex to the mouse pos
if (Algorithms.BinarySearch(vertexDistanceList, distFromZero, out index, DEF_PRECISION) == Algorithms.SearchResult.FAIL || index < 0)
return null;

return vertexDistanceList[index].Value; // return all game objects that occupies that vector position
}


This all works nicely and is fast but there is a major flaw. The algorithm doesn't take into account the vertices angle from (0,0,0). So 2 points that are the exact same distance from (0,0,0) but have different angles will be considered the same vertex when they are not.

For example; these 2 points lie 5 metres from (0,0,0) but have different angles. My algorithm will consider these 2 points as occupying the same place in space when they are in a completely different position.

Do you have any suggestions how I can hash a distance and angle to produce a unique result that describes that point in space? Some simple like doing Distance ^ Angle could produce a unique result but they would also produce huge numbers. A restriction is that my list sorting algorithm requires that two points close to each other should produce a hash that is similar in order to find points close to the mouse position. Hope that makes sense.

I've heard about Locatily Sensitve Hashing but it looks like implementing this algorithm would be very tricky.

Any advice would be greatly appreciated.

Edited by gretty, 21 July 2014 - 12:04 AM.

### #2Bacterius  Members

Posted 21 July 2014 - 12:47 AM

What about multiplying the distance and the angle, suitably quantized, and handling angle wraparound properly? Should work, I think, and it takes into account the fact that spacing between angles gets larger as distance increases (if you don't want that, take the square root of the distance instead). Otherwise, you could just convert the distance + angle to an actual 2D point and go from there, it might be easier.

“If I understand the standard right it is legal and safe to do this but the resulting value could be anything.”

### #3gretty  Members

Posted 21 July 2014 - 12:50 AM

What about multiplying the distance and the angle, suitably quantized, and handling angle wraparound properly?

Thanks for your reply. What do you mean by 'suitably quantized, and handling angle wraparound properly'?

If I multiply the angle and distance isn't that going to cause the same collisions? Like for a point with distance = 5 and angle = 10 resolves to 50 and a point with distance = 10 and angle = 5 also resolves to 50?

### #4gretty  Members

Posted 21 July 2014 - 12:55 AM

you could just convert the distance + angle to an actual 2D point and go from there, it might be easier.

Wow, never though of that! A list of Vector2 where x = distance and y = angle may just work!! Thanks!

I can also do operator comparisions on Vector2's such as 'if v1 < v2' so that works nicely.

### #5gretty  Members

Posted 21 July 2014 - 04:54 PM

Ok, after implementing the advice given to use Vector2's as keys I've got one last query/problem:

How should I go about handling angle wraparound?

For example; given the 2 points (DISTANCE, ANGLE):  A(100, 10) and B(100, 350). These 2 points are close by but will not be considered by operator comparision (<=, <, >=, >) to be close by.

Any ideas how I could handle this?

Edited by gretty, 21 July 2014 - 04:55 PM.

### #6BedderDanu  Members

Posted 21 July 2014 - 06:30 PM

check if angles are close for both (A%360, B%360) and (A%360, B%360 - 360)?

If either are close, then the angle is close.

Edit:

for hashing, use your closeness algorithm to find the closest angle to (1, 0 deg), either θ%360, or θ%360 - 360. Always hash that angle, not the one your are directly given in the function? That might just push the problem out to 180 though.

Above, A would convert to (100, 10) before hashing. B would convert to (100, -10). A hypothetical (95, 725) would then convert to (95, 5) before hashing.

Edited by BedderDanu, 21 July 2014 - 06:36 PM.

### #7Bacterius  Members

Posted 23 July 2014 - 03:56 AM

you could just convert the distance + angle to an actual 2D point and go from there, it might be easier.

Wow, never though of that! A list of Vector2 where x = distance and y = angle may just work!! Thanks!

I can also do operator comparisions on Vector2's such as 'if v1 < v2' so that works nicely.

What I meant was convert them to (x, y) points using e.g. (distance * cos(angle), distance * sin(angle)).. not as efficient, but perhaps a bit easier to work with than a distance + angle representation.

“If I understand the standard right it is legal and safe to do this but the resulting value could be anything.”

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.