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.

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.

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?

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.

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?

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.