Jump to content

  • Log In with Google      Sign In   
  • Create Account

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.

  • You cannot reply to this topic
6 replies to this topic

#1 gretty   Members   -  Reputation: 212

Like
0Likes
Like

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.

 

Add/Insertion Method:

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>()));
		
		vertexDistanceList[index].Value.Add (ele.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.

23iikxx.jpg

 

 

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.


Sponsor:

#2 Bacterius   Crossbones+   -  Reputation: 8944

Like
2Likes
Like

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.


The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis


#3 gretty   Members   -  Reputation: 212

Like
0Likes
Like

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?



#4 gretty   Members   -  Reputation: 212

Like
0Likes
Like

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.



#5 gretty   Members   -  Reputation: 212

Like
0Likes
Like

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.


#6 BedderDanu   Members   -  Reputation: 271

Like
0Likes
Like

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.


#7 Bacterius   Crossbones+   -  Reputation: 8944

Like
0Likes
Like

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.


The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis





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.



PARTNERS