I have got a set of points and I need to find the plane that would contain the maximum number of these points. Is there a simple way to do this, without trying out all permutations?
Update:
I am giving an illustration below:
The red dots are the points that exist in 3d space. There can be several planes like A, B, C, D that would contain 3 or more of these points. However, the plane A contains the maximum number of them. I need to find this plane (or to be more precise, the points on this plane).
Update2: I am giving below the code I had tried earlier. This coincides with the approach suggested by @hatinacat2000 and looks to be the best available option:
import bpy
from mathutils import Vector
from itertools import combinations
def main():
o = bpy.context.object
# Take sample test points from Bezier curves
# (you need to create curves having coplanar points
# by subdividing 2d segments for example)
bps = [bp for s in o.data.splines for bp in s.bezier_points]
loc = [bp.co.copy().freeze() for bp in bps]
l = list(combinations(loc, 3))
# Map of {normal vector: 3 point combination for that normal}
# Normal rounded to 3 decimal places
normalsCos = [[Vector((round(((c[1] - c[0]).cross((c[2] - c[0])).normalized())[i], 3) \
for i in range(0,3))).freeze(), c] for c in l]
normals = [n[0] for n in normalsCos]
# Map of {count: normal}
nmap = {normals.count(n): n for n in normals}
maxCnt = max(nmap.keys())
normal = nmap[maxCnt]
coTriplets = []
for nc in normalsCos:
if(nc[0] == normal):
coTriplets.append(nc[1])
# These are the required points
planeCos = set([c for t in coTriplets for c in t])
# And the remaining points...
remainder = set(loc) - planeCos
Update3: Please see the answer from @lemon. It has got a huge performance improvement over this code (this is more of a POC), and also considers parallel planes.