title: Out of an array of arbitrary unit vectors, what is the most efficient method of finding the two vectors that have the largest angle?
body: <p>So I'm attempting to make a wall system like the Sims. While it is 3D, it can be simplified to 2D (think a bird's eye view). A wall is defined by two points: a starting point an an ending point and the walls themselves have directions and can be simplified to unit vectors. Walls are also made with rectangular prisms, each of these prisms start at one point and end at another. So, bearing this in mind, sometimes walls have to be extended, otherwise there will be a small gap in the convex corner of the wall</p>
  <p><a href="https://i.stack.imgur.com/OpTpC.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/OpTpC.png" alt="1" /></a></p>
  <p>if one of the points is shared between the walls. Any number of walls can be placed in a single position, so all of this in mind, a grid point's data could contain something like this (using Lua), each table represents a vector2, using a table for ease of visualization, this code won't actually work:</p>
  <pre class="lang-lua prettyprint-override"><code>local gridPoint = {
    {x = 1, y = 0},
    {x = 0.7071, y = 0.7071},
    {x = 0, y = 1},
    {x = 0.7071, y = -0.7071},
  }
  </code></pre>
  <p>Here's a visual of what the points might look like, where the intersection is the grid point and the walls are the vectors extending from the intersection, assuming each of the vectors have a length of 1 (excuse my terrible drawing skills). Since dot products flip when greater than 180 degrees, the largest angle would always be &lt;=180.</p>
  <p><a href="https://i.stack.imgur.com/qJ0OR.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/qJ0OR.png" alt="2" /></a></p>
  <p>So now, to get the angle between any two of points, we can just do <code>math.deg(math.acos(v1:dot(v2)))</code> to get the angle between these two points in degrees, where <code>v1</code> is vector 1, <code>v2</code> is vector 2, and dot is a function that returns the dot product of <code>v1</code> and <code>v2</code>.</p>
  <p>So up to this point, everything is fine. The issue is that I have to create two loops which goes through every single combination of possible dot products which I'm not sure is the best method of finding the largest angle, this is <code>#gridPoint^2</code> possible combinations which is fine at lower numbers, but this number of possible combination increases exponentially with each new wall.</p>
  <p>Is there an easier way of doing this?</p>