По поводу вашего алгоритма. Он может вернуть как вектор вдоль большей, так и меньшей высоты. К тому же количество точек по разные стороны от прямой может отличаться, что может привести к довольно большим погрешностям.
Я бы сделал примерно следующее. Буду описывать без формул, их уже сами выбирайте для достижения результата.
- Начертить прямоугольник, стороны которого лежат вдоль осей координат и проходят минимум через одну точку. То есть получится что то вроде описанного вокруг точек прямоугольника с двумя сторонами паралельными оси Х и двумя - оси У.

- Точки, которые лежат на сторонах получившегося прямоугольника, будут вершинами нового четырехугольника. Если есть стороны, на которых более одной точки, то строим все четырехугольники, которые удастся (с условием, что на одной стороне прямоугольника из пункта 1 только одна вершина нового). После этого из получившихся четырехугольников выбираем единственный, модуль разницы длин диагоналей которого будет наименьшим, а средняя величина любых двух противоположных углов будет как можно ближе к 90 градусам.

- В получившемся четырехугольнике из каждой его вершины строим перпендикуляры к двум сторонам, не входящим в эту вершину. У нас получается 8 точек пересечения получившихся перпендикуляров со прямыми, проходящими через стороны четырехугольника (по 2 возле каждой вершины).

- Между двумя точками возле каждой вершины, получившимися в предыдущем пункте, проводим отрезки.
- На центрах этих отрезков ставим точки.

- Эти точки будут вершинами итогового четырехугольника. Далее вы знаете.

ЗЫ Если слишком сложно, могу картиночки нарисовать, но очень не хочется. Читайте алгоритм и рисуйте картиночки сами, на бумаге станет яснее.
ЗЫЫ Картиночки добавил. Как видите, получившийся прямоугольник находится не точно в том месте, где вы бы его провели и, возможно, отличается размером, но вам же не это важно. Главное, сохранено направление и пропорции, чего вполне достаточно для получения желаемого результата.
Однако, если нужно не только направление вектора, но и его размер, вы можете из итогового прямоугольника сделать вписанный и описанный прямоугольники (не вращая итоговый, а просто изменяя размер и положение). Далее соединить их ближайшие друг к другу вершины отрезками и построить прямоугольник через центры этих отрезков. Но, насколько я понимаю, этого не требуется.
ЗЫЫЫ Формулы, которые вам понадобятся, вполне простые из начальных курсов геометрии.
ЗЫЫЫЫ Данное решение основано на интуиции и его верность мне сейчас доказывать не хочется.