Mercury13

UPD. Переписал с нуля.
r <= z/x < r + 1
l <= z/y < l + 1

Тогда y/x = z/x : z/y > r / (l+1)
С другой стороны: y/x < z/x : z/y < (r+1)/l

Пока вижу диапазон [r / (l+1)]; [(r+1)/l]
Второе — минус один, если точное целое: приблизиться-то можно, а достичь нельзя. Сымитируем это таким образом…
[r / (l+1)]; [r/l]

Покажем, что границы достижимы (например, первая). Она затрагивает два неравенства.
z/x < r + 1
z/y >= l
Подбором x, y и z можно довести второе до равенства и сколь угодно сильно приблизить первое.

UPD2. Пусть r = [z/x] = 10, l = [z/y] = 3
Тогда [y/x] будет в пределах от [10/4] = 2 до [10/3] = 3. А Если без целой части — то от 2,5 до 3 2/3.
z = 100.000, x=10.000, y=25.001, y/x = 2,5001
z = 100.000, x = 9091, y=33.333, y/x ≈ 3,66659

1. Надо указывать не только то, что все точки первой фигуры внутри второй, но и то, что все точки второй фигуры снаружи первой.
2. Даже примитивный алгоритм даёт скорость O(mn). Сколько у вас примерно точек?
3. Можно воспользоваться эвристиками. Если охватывающий прямоугольник 1-й фигуры целиком во 2-й — ДА. Если вылезает из охватывающего прямоугольника 2-й — НЕТ.
4. Можно поступить так. Отсортируем все точки той фигуры, которую проверяем на точки, по X-координате. Также отсортируем все отрезки той фигуры, которую проверяем на отрезки, по X-координате левой точки. Указатель отрезков ставим в начало перечня отрезков. Заводим список активных отрезков. Проходимся по всем точкам, поступая так…
• Для всех отрезков в списке активных: если точка вышла из [X1, X2) — исключить из списка!
• Смотрим на тот отрезок, что под указателем. Если X точки >= X1 — идём по фигуре дальше; если заодно X < X2 и Y выше отрезка (X1,X2 — (Y1,Y2) — включаем отрезок в список.
При определённом устройстве списка (куча по X2) имеем O(n log n). И если меньшая фигура имеет сложность примерно как у большей (т.е. не логарифм) — имеем выигрыш.

Как я понял, твоя матрица 3×3 — это однородные координаты в 2D? Я бы поступил так.
1. Убедиться, что элементы 3-1 и 3-2 нули (иначе — это не аффинное преобразование).
2. Элемент 3-3 превратить в единицу, соответственно увеличив остальные (на что — читай, что такое однородные координаты).
3. Элементы 1-3 и 2-3 — перенос. Отрежем их, получается матрица 2×2.
4. То, что осталось, должно быть вида (c, s), (-s, c). Если с какой-то погрешностью это не так и 2-норма строк не единица (тоже с какой-то погрешностью) — это не поворот (т.е. может быть масштабирование или наклон). Остаётся взять atan2(c, s) — получается угол.