Algorithmically finding the pair of LookVectors in an array of LookVectors that compose the largest angle

So suppose you’re given a set of vectors, in my case each of these are represented by a part’s LookVector, is there a way to find, between each of these LookVectors, what the maximum angle at the intersection of these parts is (assuming it’s less than 180)?

So essentially, I am making a wall placement system and need to know which walls to “extend” to fill a gap, that is fine, however I’ve run into an issue where I’m unsure how to get the pair of parts that is the furthest apart when comparing LookVectors. Currently, I can use :Dot on all possible combinations of parts but this may not be the most efficient way of doing this.

So example 1, the pink parts are the furthest away from each other, which I know visually but don’t know how to tell algorithmically:

So to find the angle between these, I can just do:

math.deg(math.acos(p1.CFrame.LookVector:Dot(p2.CFrame.LookVector)))

to get the “angle” between all of the LookVectors. However, currently to do this, I have to make a nested loop which will iterate through all these parts, and then again through that same table, two loops inside of each other, meaning there’s w^2 possible combinations of angles, then x2 for each of the points defining where the wall starts and ends, where w is the amount of walls at that point, which is okay at first, however it grows exponentially with each wall you add that has a point at this position. I’m also unsure how reliable this is which is another issue. The size of the parts will also be arbitrary so I can’t use magnitude.

There are a few things to note that should (hopefully) make life easier, however:

  • The maximum angle is below 180 (if the angle is 180, we know not to extend this wall), this is not an issue, though, because the dot product accounts only for angles at and less than 180 degrees. I can create a separate case for angles at 0 and 180 degrees though, so that isn’t an issue. The pair of vectors that create the largest angle over 180 degrees should also be the pair of vectors that create the smallest angle under 180 degrees (see white and green partitions:)
  • The vectors will always be a unit vector as, in this case, I’m using RightVectors of the wall models’ pivot points

I also made another post about how the walls’ points are laid out, it’s the same system:

1 Like

Bump again. My theory is that I’d use .Magnitude on each of the vectors and find the combination that have the largest distance between each other but I don’t know if this is the proper way to do it. I also made a stackoverflow post in the meantime as I might get a faster response there idk.

That would work… But still scales badly, I’m not sure if that’s actually a problem here.

But it seems you should be able to do this more efficiently, for example, just calculate all the angles to some basis vector in the same plane. Then order them and voila, where-ever the gap is over 180 degrees, thats the furthest.

You can choose any of the lookvectors as the basis vector, since they are all in the same plane it seems (or this wouldn’t work). Be sure to conserve the sign of the angle.

It would be even easier if you already knew one of the walls, but I guess that’s not the case.

I didn’t test this btw, but it seems to me for example finding a list of angles:
[-5, 0, 5, 70]
(include zero because it’s the original angle you chose as basis)

It would be easy to see that the gap between 70 and 355 (-5) is over 180 and thus must be the solution.

I think table.sort uses quicksort, which is on average O(n log n) but worst case still O(n^2), but using the underlying c library I can’t imagine it matters, you would need a LOT of walls… Just pass it a table and comparison function that conserves reference to the walls while sorting.

Edit: ok didn’t think this through very well. I guess the challenge is in determining the sign of the angle in the plane, after which you can just take the min and max of the resulting list, no ordering required, O(n). But it should be possible using the normal of the plane (by using the same normal for all comparisons).

1 Like

so these are all the checks you have no choice but to do

red circles represents the parts each arrow represents a angle check


so from this image we can see if there are 4 parts then we have to do a total of 6 checks

local parts = ...

local i1 = nil
local i2 = nil
local largestAngle = 0

-- loop from the start to 1 from the end
for i = 1, #parts - 1 do
    -- loop from i + 1 to the end
    for j = i + 1, #parts do
        print("get angle between", parts[i], parts[j])
        local angle = ...
        -- if this new angle is not larger then the one we have found previously then continue to next iteration
        if angle < largestAngle then continue end
        i1 = i
        i2 = j
        largestAngle = angle
    end
end

print("largest angle", parts[i1], parts[i2], largestAngle)

you would need to benchmark magnitude vs dot to see what is faster but i guess there very close

also don’t do math.acos and math.deg until after you have checked all angles

this is how the dot function works so i think its quicker then getting the magnitude

local dot = v1.X * v2.X + v1.Y * v2.Y + v1.Z * v2.Z
3 Likes

Agreed that this algorithm is the best way. Sure it’s O(n^2) but

  1. The calculation is really cheap
  2. The number of walls at an intersection is almost certainly always <20 and 400 dot products is still not a lot
  3. If you’re really worried you can cache this info, and then as you create new walls, only iterate over the existing walls once and compare to the cached value.

Small thing though: if you’re calculating dot product, the largest angle would have the smallest (most negative) dot product, so I think the < should be flipped here

2 Likes

I would take advantage of dot products!

its not O(n^2) its O(n*(n-1)/2)

if N = 4 then O = 6
if N = 8 then O = 28

if it was O(n^2) then it would of been

if N = 4 then O = 16
if N = 8 then O = 64

It does track with that equation!

Usually with big O notation though you ignore all but the fastest-growing term in your equation and drop any scalars

So O(n(n-1)/2) == O(0.5n^2 - 0.5n) ~ O(n^2)

The point being that anything with a n^2 term will always outpace something with just an n term, even a very large one

i’m not that fluent with Big O notation but i don’t like the idea of sweeping all them O’s under the rug :stuck_out_tongue:

if we look at some larger numbers for instance if there was 1024 parts

1024 * 1023 / 2 = 523776
1024 * 1024 = 1048576

that’s a delta of 524800 operations

1 Like

It’s a good point but keep in mind that O(n) is a subclass of O(n^2), that’s why it’s fine to sweep under the rug. Plus scaling is not everything, a long O(n) algorithm may be slower than a fast O(n^2) in practice, if n stays within a reasonable range, because we also sweep constant multipliers to the number of operations under the rug. Btw I think my suggestion is O(n) (or better ;P) and also really fast.

i don’t see how your O(n) suggestion gets all the angles between all the parts but only the angles between 1 selected part

Well, because all the angles are in the same plane, you can do addition and substraction with them. For example, if I know the angle between A and B is 45 degrees, and the angle between A and C is -70 degrees, you can tell the angle between B and C (-115 degrees).

But, you need the signed angle (knowing if it’s plus or minus, in the defined plane). You can get that by defining a normal for the plane (there is a choice of up=up or down=up), and as long as you stick with that normal and compute all angles from the chosen vector relative to that normal (using the ‘right hand rule’), the resulting list of signed angles should easily tell you the furthest-apart vectors.

The actual formula is well explained in the answers in the link I gave.

Could you give some example code because I can’t 100% see it

Yeah I’m thinking this is the best method as well. I made this question and the answers are basically the same, both using essentially the same method. I’ll benchmark both magnitude and dot and send an update. Thanks everyone for the responses! I’ll send an update with my findings.

Also the stack overflow question if anyone’s interested

I forgot to post a response oops, but @5uphi, if you were interested, here are my findings for 216 parts:

Dot (not a Vector3 function) is just return v1.X * v2.X + v1.Z * v2.Z, I ignored the Y axis because it’s always 0 in my case. Dot (a Vector3 function) is vector1:Dot(vector2). Magnitude is just (vec1 - vec2).Magnitude. Magnitude func is return math.sqrt(v.X^2 + v.Z^2), and finally, MagnitudePow func is return (v.X^2 + v.Z^2)^(1/2).

  02:13:50.806  largest angle Part Part 1.0000006712969167  -  Server - Script:42
  02:13:50.806  Dot (not a Vector3 function) took 0.007598899999720743  -  Server - Script:43
  02:13:53.823  largest angle Part Part 1.0000007152557373  -  Server - Script:65
  02:13:53.823  Dot (a Vector3 function) took 0.008139900000969646  -  Server - Script:66
  02:13:56.838  largest distance Part Part 1.0000007152557373  -  Server - Script:88
  02:13:56.838  Magnitude took 0.007537600000432576  -  Server - Script:89
  02:13:59.855  largest distance Part Part 1.0000007152557373  -  Server - Script:111
  02:13:59.855  Magnitude func took 0.007618199999342323  -  Server - Script:112
  02:14:02.871  largest distance Part Part 1.0000007152557373  -  Server - Script:134
  02:14:02.871  MagnitudePow func took 0.007634800000232644  -  Server - Script:135

If you’re in the scenario where your vectors’ Y axes can vary, you will have to factor that in, but since I’m using only LookVectors,the Y axes will always be 0 so I was able to leave those calculations out since they would just be performing operations on 0 which would be zero.

For a more readable table from fastest to slowest:

Method Time
(v1 - v2).Magnitude 0.007537600000432576
dot(v1,v2) 0.007598899999720743
magnitude(v1 - v2) 0.007618199999342323
magnitudePow(v1 - v2) 0.007634800000232644
v1:Dot(v2) 0.008139900000969646

Thanks for sharing because I was interested and the results are kinda strange

I don’t understand how Roblox’s dot function is the slowest o well good to know (v1- v2).Magnitude is fast because I use it a lot

But 0.007 seconds for 216 parts is not that bad the differences are very small we could just ignore it

1 Like

@5uphi @7z99 @nicemike40 Ok so I finally got some time to work out a small demo script.

It’s a good exercise so you may want to try it yourself before looking at it.

I’ll put the full script below, just copy paste the whole thing into a script in workspace and press play.

The only important bit is the function calculateAngles(). It takes a random vector from your list of lookvectors, and then computes the signed angles of all vectors in the list relative to your randomly chosen one. You could just take the first one instead of a random one, they are randomly initiated in makeVectors() anyway, but just to prove it’s in no way due to order.

		local angle = math.acos(myVector:Dot(randomVector))
		local cross = myVector:Cross(randomVector)
		if normal:Dot(cross) < 0 then
			angle = -angle
		end

I just implemented that calculation from the answer I linked earlier. Just like in your previous solution, there are other strategies possible, they may be faster, but it’s not very important I think. The important thing is this fixes the scaling, it’s now O(n).

In this example, we only have stuff in the horizontal plane, so I just manually define the normal vector as [0,1,0]. It’s not hard to compute the normal vector from 2 vectors, as long as they are not exactly aligned. The normal vector is the vector orthogonal to the plane, and since all the vectors are in the same plane, this should work. Just always re-use the same normal vector. (In the rare case that all vectors are aligned, any of them are the furthest apart).

Using the normal, we can compute the sign of the angle (the unsigned angle is computed as you did before). After that, we can just go through the list and find the lowest and highest angle. The maximum angle is 180 degrees, and so this should always work. It should also work for non-horizontal vectors, but you will have to compute the normal. I thought the example would be more clear this way.

Technically, since I take the unit vector of a random vector, it would crash if the random vector were [0,0,0] but it’s virtually impossible and just a demo script.

Anyway here is the full code… it’s very hastily written - please don’t judge X)

local myVectors = {}
local rng = Random.new()
local arrowLength = 10
local origin = Vector3.new(0,5,0)
local allArrows = Instance.new("Model")

local function makeVectors(amount)
	for i=1, amount do
		local x = rng:NextNumber()
		local z = rng:NextNumber()*2-1
		local myVector = Vector3.new(x, 0, z)
		myVector = myVector.Unit
		table.insert(myVectors, {Vector = myVector})
	end
end

local function makeArrow()
	local arrow = Instance.new("Model")
	local mainPart = Instance.new("Part")
	mainPart.Size = Vector3.new(0.05,0.05, arrowLength)
	
	local leftHead = Instance.new("WedgePart")
	leftHead.Size = Vector3.new(.05, .25, .5)
	leftHead.CFrame = CFrame.new(-0.125,0, -arrowLength/2-.25) * CFrame.Angles(0, 0, math.pi/2)
	local rightHead = Instance.new("WedgePart")
	rightHead.Size = Vector3.new(.05, .25, .5)
	rightHead.CFrame = CFrame.new(0.125,0, -arrowLength/2-.25) * CFrame.Angles(math.pi, math.pi, math.pi/2)
	
	for i, myPart in {mainPart, leftHead, rightHead} do
		myPart.Anchored = true
		myPart.Color = Color3.new(0.737255, 0.219608, 0.152941)
		myPart.Parent = arrow
	end
	
	arrow.PrimaryPart = mainPart
	return arrow
end

local arrowTemplate = makeArrow()
--arrowTemplate.Parent = game.Workspace

local function displayVectors()
	for i, vectorInfo in myVectors do
		local myVector = vectorInfo["Vector"]
		local arrow = arrowTemplate:Clone()
		local myCF = CFrame.new(myVector*arrowLength/2 + origin, myVector*(arrowLength+1) + origin)
		arrow:SetPrimaryPartCFrame(myCF)
		
		arrow.Parent = allArrows
		vectorInfo["Arrow"] = arrow
	end
	allArrows.Parent = game.Workspace
end

local function calculateAngles()
	local randomIndex = rng:NextInteger(1, #myVectors)
	local randomVectorInfo = myVectors[randomIndex]
	local randomVector = randomVectorInfo["Vector"]
	local normal = Vector3.new(0,1,0)
	
	for i, vectorInfo in myVectors do
		local myVector = vectorInfo["Vector"]
		local angle = math.acos(myVector:Dot(randomVector))
		local cross = myVector:Cross(randomVector)
		if normal:Dot(cross) < 0 then
			angle = -angle
		end
		vectorInfo["Angle"] = angle
	end
end

local function findFurthest()
	local lowest = nil
	local lowestIndex = nil
	local highest = nil
	local highestIndex = nil
	
	for i, vectorInfo in myVectors do
		local myAngle = vectorInfo["Angle"]
		if (not lowest) or (myAngle < lowest) then
			lowest = myAngle
			lowestIndex = i
		end
		if (not highest) or (myAngle > highest) then
			highest = myAngle
			highestIndex = i
		end
	end
	return myVectors[lowestIndex], myVectors[highestIndex]
end

local function colorArrows(infoTable)
	for i, info in infoTable do
		local arrow = info["Arrow"]
		for i, myPart in arrow:GetChildren() do
			myPart.Color = Color3.new(0, 1, 0.498039)
		end
	end	
end

makeVectors(29)
displayVectors()
calculateAngles()

local lowestInfo, highestInfo = findFurthest()
colorArrows({lowestInfo, highestInfo})
1 Like

cool i see it now yes your correct here are some images that i used to see it working

the green vector is the randomly selected vector

i have not tested this code but i think it works
i removed some things for instance normal:Dot(cross) as i believe just checking the Y axis is all we need to do also for the angle i’m using magnitude if the benchmarks above are correct then that would be the quickest way

local parts = ...
local vector = parts[1].CFrame.LookVector
local lowestIndex = nil
local highestIndex = nil
local lowestMagnitude = math.huge
local highestMagnitude = -math.huge

for i, part in ipairs(parts) do
    local partVector = part.CFrame.LookVector
    local magnitude = (vector - partVector).Magnitude
    local cross = partVector.X * vector.Z - partVector.Z * vector.X
    if cross < 0 then magnitude = -magnitude end
    if magnitude < lowestMagnitude then
        lowestMagnitude = magnitude
        lowestIndex = i
    end
    if magnitude > highestMagnitude then
        highestMagnitude = magnitude
        highestIndex = i
    end
end

print(parts[lowestIndex], parts[highestIndex])

The only problem with this is that it gets angles that are greater then 180 degrees and I don’t think Cody wanted that

1 Like

That’s clever. It’s slightly less intuitive but unless the plane is vertical it should work, yes.

The only purpose is to compare the normal of the plane to the ‘normal’ (cross product) of the two vectors you are comparing. If they point in the same direction, the angle is positive, if they point in the opposite direction, the angle is negative.

For the magnitude, you don’t really need to take the square root for these purposes, I guess, if you really wanna microoptimize X) but then we can also remove the crossproduct and just take
v1.X*v2.Z - v1.Z*v2.X

Anyway, at some point all these tricks will start holding you back, as it becomes non-intuitive when you come back to edit the code months later. Often it’s better to have very slightly slower code that is much more readable and understandable. If the code is not very intensively used, these nanoseconds don’t really add up to anything. Type of scaling however, can quickly eat a lot of resources unneccessarily, so it’s more important.

Do you have any idea how we can change this so it only go up to 180 degrees instead of 360 degrees?

Iv been thinking but cant think of a good method

Yer because we crossing on a flat plain the cross will always be 0,1,0 or 0,-1,0

Also if you look at the benchmarks above

(v1 - v2).Magnitude

Was faster then

v1.X * v2.X + v1.Z * v2.Z

If Cody’s benchmarks where correct I never personally benchmarked it