在3D中找到最大数量的共线点 [英] Finding biggest number of collinear points in 3D

问题描述

我承担了一项任务，即必须找到一条直线，该直线穿过给定集合(> 5000)中的最高点.

I was given a task where I have to find a straight line that goes through the most points in a given set (>5000).

我能够通过连接两个点并检查所有其他点是否共线来解决该问题，但这是一种O(N ^ 3)算法.

I was able to solve the problem with connecting 2 points and checking every other point if it is collinear, but that is an O(N^3) algorithm.

我想知道是否有一种方法可以使我的程序比O(N ^ 3)更好地运行.

I would like to know if there is a way to make my program run better than O(N^3).

推荐答案

您可以使用哈希在 O(n ^ 2)中进行操作.

You can do it in O(n^2) by using a hash.

• 每两对点找到由它们定义的线方程 O(n ^ 2)

• 将这些等式放入哈希 O(1)(平均复杂度)中，以便计算每个等式的出现次数.

• put these equations in a hash O(1) (average complexity) in order to count occurrences of each.

遍历所有哈希方程，找到计数最多的 O(n ^ 2).这是您要搜索的行.

go through all hash equations and find the one with the most count O(n ^ 2). This is the line you are searching for.

算法的总时间复杂度: O(n ^ 2)* O(1)+ O(n ^ 2)= O(n ^ 2).

Total time complexity of the alg: O(n^2) * O(1) + O(n^2) = O(n^2).

棘手的一点是，由于浮点精度，同一行看似可以具有2个不同的方程式.您需要找到一个将这一点考虑在内的哈希函数.

The tricky bit is that the same line can seemingly have 2 different equations due to floating point precision. You need to find a hash function that takes this into account.

另一种方法是:

• 将等式放入向量 O(n ^ 2)
• 对向量进行排序 O(n ^ 2 log(n ^ 2)= O(n ^ 2 log n)
• 然后最终找到等式的最长序列 O(n ^ 2).

这将最终复杂度为 O(n ^ 2 log n).

这篇关于在3D中找到最大数量的共线点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！