Целочисленные однородные координаты

Здесь приведён метод точных геометрических расчётов с применением целочисленной арифметики.

Понятие об однородных координатах

Однородные координаты пришли из проективной геометрии. Для примера возьмём двумерное пространство с декартовой системой координат (x y). В однородных координатах такая точка будет иметь вид (kx ky k), то есть произвольной точкой, лежащей на прямой, проходящей через начало координат и точку на плоскости z = 1 с координатами (x y 1).

Что это даёт:

  • возможно представить также бесконечно удалённые точки, или «направления», вида (kcos(t) ksin(t) 0), где t — «азимут» направления;
  • возможно представить также неопределённость в виде координат (0 0 0);
  • и что особенно интересно с точки машинных вычислений, можно представить любые рациональные декартовы координаты посредством целочисленных однородных координат. О них далее.

Рациональные декартовы координаты

Точка с рациональными декартовыми координатами вида (x/u y/v) очень легко перенести на целочисленные однородные. Они будут иметь вид (kxv/НОД(u, v) kyu/НОД(u, v) uv/НОД(u, v)). А если принять k = НОД(u, v), то и вовсе (xv yu uv).

Например, (1/10 5/6) представима как (3 25 30) или (6 50 60).

cifra/celochislennye_odnorodnye_koordinaty.txt · Последние изменения: 2012/02/23 03:41 — vovanium
За исключением случаев, когда указано иное, содержимое этой вики предоставляется на условиях следующей лицензии: CC Attribution 3.0 Unported