Координаты конструируемых точек могут быть представлены точно?

Я думаю, что это было бы возможно только в том случае, если бы вы использовали символическое представление, вместо того, чтобы пытаться напрямую представлять значения координат - так что у вас будет чтобы не пытаться преобразовать значения вроде sqrt (2) в какой-либо числовой формат. Вы будете иметь дело с иррациональными числами, которые не могут быть конечно представимы в двоичной системе, десятичная или любая другая позиционная запись.

Чтобы немного расширить ответ Джима Льюиса , если вы хотите оперировать точками, которые можно построить из целых чисел с помощью точной арифметики, вам нужно будет уметь работают с представлениями формы:

a + b sqrt(c)

где a, b и c либо рациональные числа, либо представления в форме, данной выше. В Википедии есть довольно приличная статья о том, какие точки можно построить.

Ответить на вопрос о точном равенстве (необходимом для установления колинеарности) с такими представлениями - довольно сложная задача.

Если оси сетки имеют целочисленные значения, то ответ довольно прост: точки либо точно коллинеарны, либо нет.

Обычно, однако, работают с действительными числами (ну, с плавающей точкой), а затем рисует на экране округленные значения, которые существуют в целочисленном пространстве. В этом случае у вас нет другого выбора, кроме как выбрать допуск и использовать его для определения колинеарности. Держите его маленьким, и пользователи никогда не заметят разницы.

You seem to be asking, in effect, "Can the normal mathematics (integer or floating point) used by computers be made to represent real numbers perfectly, with no rounding errors?" And, of course, the answer to that is "No." If you want theoretical correctness, then you will be stuck with the much harder problem of symbolic manipulation and coding up the equivalent of the inferences that are done in geometry. (In short, I'm agreeing with Steve Jessop, above.)

В общем, конструируемые точки могут иметь произвольно сложную символьную форму, поэтому вы должны использовать символьное представление для их точной работы. Как отметил Стивен Кэнон выше, вам часто нужны числа вида a + b * sqrt (c), где a и b рациональные, а c - целое число. Все числа этой формы образуют замкнутое множество относительно арифметических операций. Я написал несколько классов C ++ (см .rational_radical1.h) для работы с этими числами, если это все, что вам нужно.

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

Чтобы пойти еще дальше, вы можете построить квадратный корень из любого заданного числа, так что вы потенциально можете иметь вложенные квадратные корни. Здесь представления должны быть древовидными структурами для работы с корневой иерархией. Хотя это сложно реализовать, в принципе ничто не мешает вам работать с этими представлениями. Я не уверен, какие дополнительные числа можно построить, но после определенного момента ваше символическое представление будет достаточно выразительным, чтобы обрабатывать очень большие классы чисел.

Приложение

Нашел эту ссылку на Google Книги .

представления должны быть древовидными структурами для работы с корневой иерархией. Хотя это сложно реализовать, в принципе ничто не мешает вам работать с этими представлениями. Я не уверен, какие дополнительные числа можно построить, но после определенного момента ваше символическое представление будет достаточно выразительным, чтобы обрабатывать очень большие классы чисел.

Приложение

Нашел эту ссылку на Google Книги .

представления должны быть древовидными структурами для работы с корневой иерархией. Хотя это сложно реализовать, в принципе ничто не мешает вам работать с этими представлениями. Я не уверен, какие дополнительные числа можно построить, но после определенного момента ваше символическое представление будет достаточно выразительным, чтобы обрабатывать очень большие классы чисел.

Приложение

Нашел эту ссылку на Google Книги .

Я бы рекомендовал no, чтобы попытаться сделать его совершенно точным.

Первая причина - это то, о чем вы здесь спрашиваете, ошибка округления и все такое, что связано с вычислениями с плавающей запятой.

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

Кроме того, с точки зрения удобства использования, проще щелкнуть по соседству с другой точкой (например, в строке) и что интерфейс считайте, что вы щелкаете по самой точке.

Если вы попытаетесь сравнить координаты ваших точек, у вас возникнет проблема. Оставив на мгновение в стороне вопрос о линейности, как насчет того, чтобы просто выяснить, являются ли две точки одинаковыми или нет?

Предположим, что одна задала координаты, а другая представляет собой конструкцию линейки с компасом, начиная с некоторых других координат. ординат, вы хотите с уверенностью определить, находятся ли они в одной точке или нет. В любом случае это теорема евклидовой геометрии, это не то, что вы можете просто измерить. Вы можете доказать, что они не одинаковы, обнаружив некоторую разницу в их координатах (например, вычислив десятичные разряды каждого из них, пока не обнаружите разницу). Но в целом доказать то же самое приближенными методами невозможно. Вычислите сколько угодно десятичных знаков в некоторых расширениях 1 / sqrt (2) и sqrt (2) / 2 , и вы можете доказать, что они очень близки друг к другу, но вы никогда не докажет, что они равны. Для этого нужна алгебра (или геометрия).

Точно так же, чтобы показать, что три точки коллинеарны, вам понадобится программа для доказательства теорем. Представьте точки A, B, C их построениями и попытайтесь доказать теорему «A, B и C коллинеарны». Это очень сложно - ваша программа будет доказывать одни теоремы, а другие - нет. Гораздо проще попросить пользователя предоставить доказательство того, что он коллинеарен, а затем проверить (или опровергнуть) это доказательство, но, вероятно, это не то, что вам нужно.

Для этого нужна алгебра (или геометрия).

Точно так же, чтобы показать, что три точки коллинеарны, вам понадобится программа для доказательства теорем. Представьте точки A, B, C их построениями и попытайтесь доказать теорему «A, B и C коллинеарны». Это очень сложно - ваша программа будет доказывать одни теоремы, а другие - нет. Гораздо проще попросить пользователя предоставить доказательство того, что он коллинеарен, а затем проверить (или опровергнуть) это доказательство, но, вероятно, это не то, что вам нужно.

Для этого нужна алгебра (или геометрия).

Точно так же, чтобы показать, что три точки коллинеарны, вам понадобится программа для доказательства теорем. Представьте точки A, B, C их построениями и попытайтесь доказать теорему «A, B и C коллинеарны». Это очень сложно - ваша программа будет доказывать одни теоремы, а другие - нет. Гораздо проще попросить пользователя предоставить доказательство того, что он коллинеарен, а затем проверить (или опровергнуть) это доказательство, но, вероятно, это не то, что вам нужно.

Некоторые мысли в надежде, что они могут помочь.

Типа конструкций, которые вы ' То, о чем мы говорим, потребует умножения и деления, что означает, что для сохранения точности вам придется использовать рациональные числа, которые, как правило, легко реализовать на основе подходящего типа большого целого числа (т. е. неограниченной величины). (В Common Lisp они встроены, и должны быть другие языки.)

Теперь вам нужно представить квадратные корни из произвольных чисел, и их нужно смешать.

Следовательно, число - это одно из: рациональное число, рациональное число, умноженное на квадратный корень из рационального числа (или, альтернативно, просто квадратный корень из рационального числа), или сумма чисел. Чтобы что-то доказать, вам придется привести эти числа в некую каноническую форму, что, насколько я могу предположить, может быть раздражающим и затратным с точки зрения вычислений.

Это, конечно, означает, что пользователи будут ограничены. к рациональным точкам и не может использовать произвольные вращения, но это, вероятно, не важно.