Hash Distance & Angle To Produce Unique Value

Question

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.

Answer 1

The question you ask is ill posed: the problem is you are trying to map from a fundamentally 2 dimensional data set (positions on the screen) to a 1 dimensional data structure (your list). Binary search does not work in two dimensions, regardless of the mapping or hash. This is because for any potential hash, we can find points that are nearby in space but arbitrarily far away in the ordering. There exist ways to hash points using space filling curves so that nearby points tend to be near each other, but this isn't strong enough for what you need. Further, even with these solutions, binary search won't do what you need.

Thousands of points should be no problem for a properly written search loop to just linearly scan through all the possibilities, especially because your application does this at most once per frame. (You wouldn't want this if it was used for sight of many AI agents, for example.) If your points change every frame, then the fastest solution is to just a linear scan, because the cost of building any data structure will be at least what it costs to do the brute force search, and you will only use the structure once.

If you have a very large number of points (100,000+), then what you need is a proper space partitioning data structure, specifically a grid or a quadtree. These data structures are very well covered elsewhere. Basically rather than a list, you would store your points in one of these structures, and then make your queries using the nearest neighbor lookup function from that data structure.