Можно точно представить координаты конструктивных точек?

Ответ 1

Да.

Я настоятельно рекомендую Введение в конструкции, что является хорошим базовым руководством.

В основном вы должны иметь возможность вычислять с конструктивные числа - числа, которые являются либо рациональными, либо формой a + b sqrt (c), где a, b, c были созданы ранее (см. стр. 6 в этом PDF). Это можно сделать с помощью типа алгебраических данных (например, data C = Rational Integer Integer | Root C C C в Haskell, где Root a b c = a + b sqrt (c)). Однако я не знаю, как выполнять тесты с этим представлением.

Возможны два возможных подхода:

• Конструктивные числа - это подмножество алгебраических чисел, поэтому вы можете использовать алгебраические числа. Все алгебраические числа могут быть представлены с использованием многочленов, из которых они являются корнями. Операции вычислимы, поэтому, если вы представляете число a с полиномом p и b с полиномом q (p (a) = q (b) = 0), то можно найти многочлен r такой, что r (a + b ) = 0. Это делается в некоторых CAS, таких как Mathematica, пример. См. Также: Компьютерная теория алгебраических чисел - глава 4

• Используйте тест Tarski и представляйте числа. Он медленный (дважды экспоненциальный или около того), но работает:) Пример: для представления sqrt (2) используйте формулу x ^ 2 - 2 && & x > 0. Вы можете написать уравнения для строк там, проверить, являются ли точки colinear и т.д. См. Набор логических программ, включая тест Tarski

Если вы переходите к вычислимым числам, то равенство, colinearity и т.д. становятся неразрешимыми.

Ответ 2

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

Ответ 3

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

a + b sqrt(c)

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

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

Ответ 4

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

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

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

Ответ 5

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

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

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

Добавление

Обнаружено ссылка Google Книги.

Ответ 6

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

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

Ответ 7

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

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

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

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

Ответ 8

Кажется, вы спрашиваете: "Может ли нормальная математика (целочисленная или плавающая точка), используемая компьютерами, идеально представлять реальные числа без ошибок округления?" И, конечно, ответ на этот вопрос: "Нет". Если вы хотите теоретической корректности, тогда вы столкнетесь с гораздо более сложной проблемой символической манипуляции и кодирования эквивалента выводов, которые выполняются в геометрии. (Короче говоря, я согласен со Стивом Джессопом, выше.)

Ответ 9

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

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

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

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

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