linear algebra - Efficient algorithm to find max points on a line given a collection of Vector3 points?

Question

I am trying to figure out an efficient algorithm to detect the most points on the same line given a collection of N Vector3 points. This is a 3D version of this problem: https://www.geeksforgeeks.org/count-maximum-points-on-same-line/

My original hunch was to iterate through the entire graph of points, and since there are no explicit edges in this plot of points, they are all neighbors of each other. From there we iteratively build all possible lines out of the nodes, terminating early if there are no more neighbors left to check for linearity, or the node we check is not on the same line as the one we are currently building.

So for example, if I have the following collection of points:

A B C D

E F

The max points on a line would be 4 (for A B C D). Second place would be ABC, or BCD, with 3 points. Third place would be any two points on the map (which is the bare minimum amount of points on a line anyway, so the answer should always be 2 or above).

We initialize an integer for currentMaxPointsInLine at 0.

Starting at A, I would check all of its neighbors (B through F) From there, I would iteratively check each line's next neighbor, making sure to keep track of which nodes have been visited on this current line. We check for linearity using the dot product between the two ends of the existing line, and the vector from the tail of the existing line to the neighbor. For example, if we are evaluating ABC, and checking neighbor D, we take the normalized vectors of AC and CD, and if the dot product is 1, we know it belongs on the same line.

I feel like the algorithm I have is overly complex and expensive, because you are checking all paths on an undirected graph where all nodes are neighbors of one another, and only terminating a path search once there are either no neighbors left to check, or the neighbor does not lie on the same line.

Is there a more efficient or elegant way to approach this algorithm?

question from:https://stackoverflow.com/questions/65896474/efficient-algorithm-to-find-max-points-on-a-line-given-a-collection-of-vector3-p

Answer 1

Waitting for answers