Как вы можете преобразовать набор чисел в основном целые?
Небольшое количество фона: я работаю над конвертером, который связывает между создателем карты (Плиточный) что выводит в XML, и движок (Angel2D) что вводит таблицы lua. Большая часть этого проста
Тем не менее, Tiled выводит в пиксельных смещениях (целые числа абсолютных значений), в то время как Angel2D вводит единицы OpenGL (с плавающей точкой относительных значений); необходим коэффициент преобразования между этими двумя (например, 32px = 1gu). Поскольку единицы OpenGL являются абстрактными, и камера может увеличивать или уменьшать масштаб, если объекты слишком малы или велики, фактический коэффициент преобразования не важен; Я мог бы использовать случайное число, и пользователю просто нужно было увеличивать или уменьшать масштаб.
Но было бы лучше, если бы коэффициент преобразования был выбран таким, чтобы большинство выводимых чисел были маленькими и целыми (или дробями маленьких целых чисел), потому что это облегчает работу с ними (и весь смысл модулей OpenGL в том, что они легко работать с).
Как я могу найти такой коэффициент пересчета надежно?
Моя первая попытка состояла в том, чтобы использовать наименьшее заданное число; это приводило к отсутствию дробей ниже 1, но часто приводило к множеству десятичных разрядов, где факторы не совпадали.
Затем я попробовал режим последовательности, который приводит к наибольшему числу возможных 1, но часто приводит к очень длинным плавающим эффектам для фоновых изображений.
Мой нынешний подход дает GCD всей последовательности, которая, когда она работает, прекрасно работает, но может быть легко сбита с курса одним плохим яблоком.
Обратите внимание, что хотя я мог бы просто передать числа, которые мне даны, или выбрать какой-то фиксированный коэффициент, или использовать одно из преобразований, указанных выше, я ищу способ надежного масштабирования этого списка целых чисел до небольших целых чисел или простые дроби, потому что это, скорее всего, не удивительно для конечного пользователя; это не разовое обращение.
Конечные пользователи, как правило, используют 1.0 в качестве своей «базы» для манипуляций (потому что это просто и очевидно), поэтому было бы более разумно, чтобы размеры сущностей группировались вокруг этого.
Решение
Как насчет «наибольшего числа, которое составляет несколько процентов от значений».
Таким образом, GCD — это «наибольшее число, которое составляет коэффициент 100%» от значений.
Вы можете выбрать наибольшее число, которое составляет, скажем, 60% значений. Я не знаю, технический ли это термин, но это своего рода «грубый GCD, если не точный GCD».
Возможно, вам придется сделать след и ошибку, чтобы найти его (возможно, бинарный поиск). Но вы также можете рассмотреть выборку. То есть если у вас есть миллион точек данных, просто выберите 100 или 1000 случайным образом, чтобы найти число, которое делится равномерно на ваш целевой процент от набора выборок, и этого может быть достаточно.
какая-то грязная псевдо C.
/** return percent of values in sampleset for which x is a factor */
double percentIsFactorOf(x, sampleset) {
int factorCount = 0;
for (sample : sampleset)
if (sample%x == 0) factorCount++;
return (double)factorCount/sampleset.size;
}
/** find largest value which is a factor of goalPercentage of sampleset */
double findGoodEnoughCommonFactor(sampleset, goalPercentage) {
// slow n^2 alogrithm here - add binary search, sampling, or something smarter to improve if you like
int start = max(sampleset);
while (percentIsFactorOf(start, sampleset)< goalPercent)
start--;
}
Другие решения
Понятия не имею, о чем вы говорите с «единицами GL».
На самом абстрактном уровне у GL нет единицы. Координаты вершин изначально находятся в объектном пространстве и проходят через полдюжины пользовательских преобразований, прежде чем они в конечном итоге выдают координаты (оконное пространство) с известными единицами (пикселями).
Вы абсолютно правы, что даже в окне-пространстве координаты все еще не являются целыми числами. Вы бы не хотели этого на самом деле, иначе треугольники прыгали бы повсюду и, как правило, не походили бы на треугольники, если бы их позиции вершин были привязаны к целочисленным пиксельным координатам.
Вместо этого GL добавляет субпиксельную точность в микс. Координаты по-прежнему в конечном итоге квантуются до целочисленных значений, но каждое целое может охватывать 1/256го пикселя с заданной 8-битной точностью до субпикселя. Тестирование покрытия пикселей выполняется на уровне подпикселей, как вы можете видеть здесь:
http://i.msdn.microsoft.com/dynimg/IC520311.png
GL никогда не пытается найти какой-либо коэффициент преобразования, который вы обсуждаете, он просто разбивает пространство чисел для координат пикселей на фиксированное деление на целое и дробное … фиксированная точка другими словами. Вы могли бы рассмотреть возможность сделать то же самое.
Если вы вводите в N ^ 2 (двухмерное пространство над полем натуральных чисел, то есть неотрицательных целых чисел), и вам необходимо вывести в R ^ 2 (двухмерное пространство над полем действительных чисел, которое в данном случае будет представлен / аппроксимирован поплавком).
Забудьте о масштабировании на минуту, и пусть выход будет того же масштаба, что и вход. Первый шаг — понять, что вы входная координата. <0, 0> не представляет <0, 0> на выходе, это представляет <0,5f, 0,5f>, центр пикселя. Точно так же вход <2, 3> становится <2,5, 3,5>. В общем, преобразование может быть выполнено так:
float x_prime = (float)x + 0.5f;
float y_prime = (float)y + 0.5f;
Далее, вы, вероятно, хотите выбрать коэффициент масштабирования, как вы уже упоминали. Я всегда считал полезным выбрать какой-то реальный юнит, обычно метров. Таким образом, вы можете рассуждать о других физических аспектах того, что вы пытаетесь смоделировать, потому что у них есть единицы измерения; то есть скорости, ускорения теперь могут быть в метрах в секунду или в метрах в секунду в квадрате. Сколько метров в высоту или ширину вы делаете? Сколько метров это пиксель? Выберите то, что имеет смысл, и тогда ваша формула станет такой:
float x_prime = ((float)x + 0.5f) * (float)units_per_pixel;
float y_prime = ((float)y + 0.5f) * (float)units_per_pixel;
Возможно, вы не хотите, чтобы все ваши выходные координаты были в положительном квадранте; то есть вы можете захотеть, чтобы источник находился в центре объекта. Если вы это сделаете, вы, вероятно, захотите, чтобы поле вашей исходной системы координат включало отрицательные целые числа или предоставляло некоторое смещение относительно истинного центра. Допустим, вы указываете смещение пикселя к истинному центру. Ваше обращение тогда становится таким:
float x_prime = ((float)x + 0.5f - (float)x_offset) * (float)units_per_pixel;
float y_prime = ((float)y + 0.5f - (float)y_offset) * (float)units_per_pixel;
Отбрасывая вашу справочную информацию, я понимаю, что основная проблема, которую вы пытаетесь решить, заключается в следующем:
Дано конечное число (положительных) целых чисел {x_1, … x_N} найти некоторое (рациональное) число f такое, что все x_i / f являются «хорошими».
Если вы настаиваете на «хорошем» значении целое и как можно меньше, то f = GCD — (математически) точный ответ на этот вопрос. Нет ничего лучше, если GCD равен 1, не повезло.
Если предполагается, что «хороший» означает рациональное с небольшим числителем и знаменателем, вопрос становится более интересным, и в зависимости от того, что означает «маленький», найдите свой компромисс между небольшим абсолютным значением (f = max) и небольшим знаменателем (f = GCD) , Обратите внимание, однако, что маленький числитель / знаменатель не означает маленькое представление с плавающей запятой, например 1/3 = 0,333333 … в основании 10.
Если вы хотите коротко плавающие точки, убедитесь, что f является степенью вашей базы, т. е. 10 или 2, в зависимости от того, должны ли числа выглядеть короткими для пользователя или на самом деле иметь разумное машинное представление. Это то, что используется для научное представительство с плавающей запятой, что может быть лучшим ответом на вопрос о том, как сделать десятичные числа красивыми в первую очередь.
Вы можете переработать код, который вы, вероятно, в настоящее время используете для нормализации вектора, нормализовать значения так, чтобы они соответствовали макс. значение 1; например:
формула для 3d нормализации вектора отлично работает здесь
Сначала получите длину:
|a| = sqrt((ax * ax) + (ay * ay) + (az * az))
Затем вам нужно будет разделить значения каждого компонента на длину:
x = ax/|a|
y = ay/|a|
z = az/|a|
Теперь все x, y, z значения будут попадать в максимумы от -1 до 1, так же, как базовая система координат OpenGL.
Я знаю, что это не генерирует систему целых чисел, которую вы хотели бы, однако это дает меньший, более унифицированный вид диапазона.
Скажем, вы хотите ограничить диапазон только целыми числами, просто используйте функцию, подобную следующей, которая возьмет нормализованное значение и преобразует его в значение диапазона только для int:
#include <algorithm> // this allows the use of std::min
int maxVal = 256
unsigned char convertToSpread(float floatValueToConvert){
return (unsigned char) (std::min((maxVal-1), (int) (floatValueToConvert * maxVal)));
}
Выше будет распространять ваши значения от 0 до 255, просто увеличить значение maxVal к тому, что вам нужно, и измените unsigned char к типу данных, который соответствует вашим потребностям.
Так что если вы хотите 1024 значения, просто измените maxVal до 1024 и unsigned char toбез знака int`
Надеюсь, это поможет, однако, дайте мне знать, если вам нужна дополнительная информация, и я могу уточнить 🙂