c# - plano - distancia dirigida de un punto a una recta

¿Arreglo de punto matemático en c#?

Question

Me preguntaba si alguien aquí sabe de algún buen recurso para matemática de punto fijo en c #? He visto cosas como esta ( http://2ddev.72dpiarmy.com/viewtopic.php?id=156 ) y esto ( ¿Cuál es la mejor manera de hacer cálculos matemáticos de punto fijo? ), Y varias discusiones sobre si decimales es realmente un punto fijo o, en realidad, un punto flotante (actualización: los respondedores han confirmado que definitivamente es el punto flotante), pero no he visto una biblioteca sólida de C # para cosas como calcular el coseno y el seno.

Mis necesidades son simples: necesito los operadores básicos, además de coseno, seno, arctan2, PI ... Creo que eso es todo. Tal vez sqrt. Estoy programando un juego de estrategia en tiempo real 2D, que tengo en gran medida trabajando, pero el movimiento de la unidad al usar matemáticas de coma flotante (dobles) tiene imprecisiones muy pequeñas en el tiempo (10-30 minutos) en varias máquinas, lo que lleva a desyncs. Actualmente, solo se encuentra entre un sistema operativo de 32 bits y un sistema operativo de 64 bits, todas las máquinas de 32 bits parecen estar sincronizadas sin problemas, que es lo que me hace pensar que se trata de un problema de coma flotante.

Me di cuenta de esto como un posible problema desde el principio, y así he limitado el uso de matemáticas de posición no entera tanto como sea posible, pero para un movimiento diagonal suave a diferentes velocidades estoy calculando el ángulo entre los puntos en radianes, luego obteniendo los componentes xey del movimiento con sin y cos. Ese es el problema principal. También estoy haciendo algunos cálculos para las intersecciones del segmento de línea, intersecciones de línea-círculo, intersecciones círculo-rect, etc., que también probablemente necesiten pasar de punto flotante a punto fijo para evitar problemas entre máquinas.

Si hay algo de código abierto en Java o VB u otro lenguaje comparable, probablemente podría convertir el código para mis usos. La principal prioridad para mí es la precisión, aunque me gustaría tener la menor pérdida de velocidad posible sobre el rendimiento actual. Este asunto de matemática de punto fijo es muy nuevo para mí, y me sorprende la poca información práctica que hay sobre él en Google, la mayoría de las cosas parecen ser teoría o archivos densos de encabezado C ++.

Cualquier cosa que puedas hacer para apuntarme en la dirección correcta es muy apreciada; si puedo hacer que esto funcione, planeo abrir las funciones matemáticas que armé para que haya un recurso para otros programadores de C #.

ACTUALIZACIÓN: Definitivamente podría hacer que una tabla de búsqueda de coseno / seno funcione para mis propósitos, pero no creo que eso funcione para arctan2, ya que necesitaría generar una tabla con aproximadamente 64,000x64,000 entradas (yikes). Si conoce alguna explicación programática de formas eficientes de calcular cosas como arctan2, sería increíble. Mis antecedentes matemáticos están bien, pero las fórmulas avanzadas y la notación matemática tradicional son muy difíciles de traducir en código.

Answer 1

Además de los enteros escalados, hay algunas bibliotecas numéricas de precisión arbitraria que generalmente incluyen un tipo "BigRational", y el punto fijo es solo una potencia fija de diez denominador.

Answer 2

Creé una estructura de punto fijo similar. Obtienes un golpe de rendimiento usando new () porque pone datos en el montón incluso aunque estés usando una estructura. Ver Google (C # Heap (ing) Vs Stack (ing) en .NET: Parte I) el verdadero poder de usar struct es la capacidad de no usar nuevos y pasar de valor a la pila. Mi ejemplo a continuación hace lo siguiente en la pila. 1. [resultado int] en la pila 2. [a int] en la pila 3. [b int] en la pila 4. [*] operador en la pila 5. el resultado del valor devolvió los costos no asignados.

    public static Num operator *(Num a, Num b)
    {
        Num result;
        result.NumValue = a.NumValue * b.NumValue;
        return result;
    }

Answer 3

Implementé un tipo de punto fijo Q31.32 en C #. Realiza todas las operaciones aritméticas básicas, sqrt, sin, cos, tan, y está bien cubierto por pruebas unitarias. Puede encontrarlo here , el tipo interesante es Fix64. :

Tenga en cuenta que la biblioteca también incluye los tipos Fix32, Fix16 y Fix8, pero esos fueron principalmente para la experimentación y no son tan completos ni están libres de errores.

Answer 4

Sé que este hilo es un poco viejo, pero para el registro aquí hay un enlace a un proyecto que implementa matemáticas de punto fijo en C #: http://www.isquaredsoftware.com/XrossOneGDIPlus.php

Answer 5

Use enteros de 64 bits en, por ejemplo, escala 1/1000. Puede agregar y restar normalmente. Cuando necesite multiplicar, multiplique números enteros y luego divida por 1000. Cuando necesite sqrt, sin, cos, etc., conviértalo en doble largo, divida por 1000, sqrt, multiplique por 1000, conviértalo en entero. Las diferencias entre las máquinas no deberían importar entonces.

Puede usar otra escala para divisiones más rápidas, por ejemplo 1024 como x/1024 == x >> 10 .

Answer 6

Ok, esto es lo que se me ocurrió para una estructura de punto fijo, basada en el enlace de mi pregunta original, pero también incluye algunas correcciones de cómo se manejaba la división y la multiplicación, y lógica agregada para módulos, comparaciones, turnos, etc. :

public struct FInt
{
    public long RawValue;
    public const int SHIFT_AMOUNT = 12; //12 is 4096

    public const long One = 1 << SHIFT_AMOUNT;
    public const int OneI = 1 << SHIFT_AMOUNT;
    public static FInt OneF = FInt.Create( 1, true );

    #region Constructors
    public static FInt Create( long StartingRawValue, bool UseMultiple )
    {
        FInt fInt;
        fInt.RawValue = StartingRawValue;
        if ( UseMultiple )
            fInt.RawValue = fInt.RawValue << SHIFT_AMOUNT;
        return fInt;
    }
    public static FInt Create( double DoubleValue )
    {
        FInt fInt;
        DoubleValue *= (double)One;
        fInt.RawValue = (int)Math.Round( DoubleValue );
        return fInt;
    }
    #endregion

    public int IntValue
    {
        get { return (int)( this.RawValue >> SHIFT_AMOUNT ); }
    }

    public int ToInt()
    {
        return (int)( this.RawValue >> SHIFT_AMOUNT );
    }

    public double ToDouble()
    {
        return (double)this.RawValue / (double)One;
    }

    public FInt Inverse
    {
        get { return FInt.Create( -this.RawValue, false ); }
    }

    #region FromParts
    /// <summary>
    /// Create a fixed-int number from parts.  For example, to create 1.5 pass in 1 and 500.
    /// </summary>
    /// <param name="PreDecimal">The number above the decimal.  For 1.5, this would be 1.</param>
    /// <param name="PostDecimal">The number below the decimal, to three digits.  
    /// For 1.5, this would be 500. For 1.005, this would be 5.</param>
    /// <returns>A fixed-int representation of the number parts</returns>
    public static FInt FromParts( int PreDecimal, int PostDecimal )
    {
        FInt f = FInt.Create( PreDecimal, true );
        if ( PostDecimal != 0 )
            f.RawValue += ( FInt.Create( PostDecimal ) / 1000 ).RawValue;

        return f;
    }
    #endregion

    #region *
    public static FInt operator *( FInt one, FInt other )
    {
        FInt fInt;
        fInt.RawValue = ( one.RawValue * other.RawValue ) >> SHIFT_AMOUNT;
        return fInt;
    }

    public static FInt operator *( FInt one, int multi )
    {
        return one * (FInt)multi;
    }

    public static FInt operator *( int multi, FInt one )
    {
        return one * (FInt)multi;
    }
    #endregion

    #region /
    public static FInt operator /( FInt one, FInt other )
    {
        FInt fInt;
        fInt.RawValue = ( one.RawValue << SHIFT_AMOUNT ) / ( other.RawValue );
        return fInt;
    }

    public static FInt operator /( FInt one, int divisor )
    {
        return one / (FInt)divisor;
    }

    public static FInt operator /( int divisor, FInt one )
    {
        return (FInt)divisor / one;
    }
    #endregion

    #region %
    public static FInt operator %( FInt one, FInt other )
    {
        FInt fInt;
        fInt.RawValue = ( one.RawValue ) % ( other.RawValue );
        return fInt;
    }

    public static FInt operator %( FInt one, int divisor )
    {
        return one % (FInt)divisor;
    }

    public static FInt operator %( int divisor, FInt one )
    {
        return (FInt)divisor % one;
    }
    #endregion

    #region +
    public static FInt operator +( FInt one, FInt other )
    {
        FInt fInt;
        fInt.RawValue = one.RawValue + other.RawValue;
        return fInt;
    }

    public static FInt operator +( FInt one, int other )
    {
        return one + (FInt)other;
    }

    public static FInt operator +( int other, FInt one )
    {
        return one + (FInt)other;
    }
    #endregion

    #region -
    public static FInt operator -( FInt one, FInt other )
    {
        FInt fInt;
        fInt.RawValue = one.RawValue - other.RawValue;
        return fInt;
    }

    public static FInt operator -( FInt one, int other )
    {
        return one - (FInt)other;
    }

    public static FInt operator -( int other, FInt one )
    {
        return (FInt)other - one;
    }
    #endregion

    #region ==
    public static bool operator ==( FInt one, FInt other )
    {
        return one.RawValue == other.RawValue;
    }

    public static bool operator ==( FInt one, int other )
    {
        return one == (FInt)other;
    }

    public static bool operator ==( int other, FInt one )
    {
        return (FInt)other == one;
    }
    #endregion

    #region !=
    public static bool operator !=( FInt one, FInt other )
    {
        return one.RawValue != other.RawValue;
    }

    public static bool operator !=( FInt one, int other )
    {
        return one != (FInt)other;
    }

    public static bool operator !=( int other, FInt one )
    {
        return (FInt)other != one;
    }
    #endregion

    #region >=
    public static bool operator >=( FInt one, FInt other )
    {
        return one.RawValue >= other.RawValue;
    }

    public static bool operator >=( FInt one, int other )
    {
        return one >= (FInt)other;
    }

    public static bool operator >=( int other, FInt one )
    {
        return (FInt)other >= one;
    }
    #endregion

    #region <=
    public static bool operator <=( FInt one, FInt other )
    {
        return one.RawValue <= other.RawValue;
    }

    public static bool operator <=( FInt one, int other )
    {
        return one <= (FInt)other;
    }

    public static bool operator <=( int other, FInt one )
    {
        return (FInt)other <= one;
    }
    #endregion

    #region >
    public static bool operator >( FInt one, FInt other )
    {
        return one.RawValue > other.RawValue;
    }

    public static bool operator >( FInt one, int other )
    {
        return one > (FInt)other;
    }

    public static bool operator >( int other, FInt one )
    {
        return (FInt)other > one;
    }
    #endregion

    #region <
    public static bool operator <( FInt one, FInt other )
    {
        return one.RawValue < other.RawValue;
    }

    public static bool operator <( FInt one, int other )
    {
        return one < (FInt)other;
    }

    public static bool operator <( int other, FInt one )
    {
        return (FInt)other < one;
    }
    #endregion

    public static explicit operator int( FInt src )
    {
        return (int)( src.RawValue >> SHIFT_AMOUNT );
    }

    public static explicit operator FInt( int src )
    {
        return FInt.Create( src, true );
    }

    public static explicit operator FInt( long src )
    {
        return FInt.Create( src, true );
    }

    public static explicit operator FInt( ulong src )
    {
        return FInt.Create( (long)src, true );
    }

    public static FInt operator <<( FInt one, int Amount )
    {
        return FInt.Create( one.RawValue << Amount, false );
    }

    public static FInt operator >>( FInt one, int Amount )
    {
        return FInt.Create( one.RawValue >> Amount, false );
    }

    public override bool Equals( object obj )
    {
        if ( obj is FInt )
            return ( (FInt)obj ).RawValue == this.RawValue;
        else
            return false;
    }

    public override int GetHashCode()
    {
        return RawValue.GetHashCode();
    }

    public override string ToString()
    {
        return this.RawValue.ToString();
    }
}

public struct FPoint
{
    public FInt X;
    public FInt Y;

    public static FPoint Create( FInt X, FInt Y )
    {
        FPoint fp;
        fp.X = X;
        fp.Y = Y;
        return fp;
    }

    public static FPoint FromPoint( Point p )
    {
        FPoint f;
        f.X = (FInt)p.X;
        f.Y = (FInt)p.Y;
        return f;
    }

    public static Point ToPoint( FPoint f )
    {
        return new Point( f.X.IntValue, f.Y.IntValue );
    }

    #region Vector Operations
    public static FPoint VectorAdd( FPoint F1, FPoint F2 )
    {
        FPoint result;
        result.X = F1.X + F2.X;
        result.Y = F1.Y + F2.Y;
        return result;
    }

    public static FPoint VectorSubtract( FPoint F1, FPoint F2 )
    {
        FPoint result;
        result.X = F1.X - F2.X;
        result.Y = F1.Y - F2.Y;
        return result;
    }

    public static FPoint VectorDivide( FPoint F1, int Divisor )
    {
        FPoint result;
        result.X = F1.X / Divisor;
        result.Y = F1.Y / Divisor;
        return result;
    }
    #endregion
}

En base a los comentarios de ShuggyCoUk, veo que esto está en formato Q12. Eso es razonablemente preciso para mis propósitos. Por supuesto, aparte de las correcciones de errores, ya tenía este formato básico antes de hacer mi pregunta. Lo que estaba buscando eran formas de calcular Sqrt, Atan2, Sin y Cos en C # usando una estructura como esta. No hay otras cosas que conozca en C # que manejen esto, pero en Java logré encontrar la biblioteca MathFP de Onno Hommes. Es una licencia de software de fuente liberal, así que he convertido algunas de sus funciones para mis propósitos en C # (con una corrección para atan2, creo). Disfrutar:

    #region PI, DoublePI
    public static FInt PI = FInt.Create( 12868, false ); //PI x 2^12
    public static FInt TwoPIF = PI * 2; //radian equivalent of 260 degrees
    public static FInt PIOver180F = PI / (FInt)180; //PI / 180
    #endregion

    #region Sqrt
    public static FInt Sqrt( FInt f, int NumberOfIterations )
    {
        if ( f.RawValue < 0 ) //NaN in Math.Sqrt
            throw new ArithmeticException( "Input Error" );
        if ( f.RawValue == 0 )
            return (FInt)0;
        FInt k = f + FInt.OneF >> 1;
        for ( int i = 0; i < NumberOfIterations; i++ )
            k = ( k + ( f / k ) ) >> 1;

        if ( k.RawValue < 0 )
            throw new ArithmeticException( "Overflow" );
        else
            return k;
    }

    public static FInt Sqrt( FInt f )
    {
        byte numberOfIterations = 8;
        if ( f.RawValue > 0x64000 )
            numberOfIterations = 12;
        if ( f.RawValue > 0x3e8000 )
            numberOfIterations = 16;
        return Sqrt( f, numberOfIterations );
    }
    #endregion

    #region Sin
    public static FInt Sin( FInt i )
    {
        FInt j = (FInt)0;
        for ( ; i < 0; i += FInt.Create( 25736, false ) ) ;
        if ( i > FInt.Create( 25736, false ) )
            i %= FInt.Create( 25736, false );
        FInt k = ( i * FInt.Create( 10, false ) ) / FInt.Create( 714, false );
        if ( i != 0 && i != FInt.Create( 6434, false ) && i != FInt.Create( 12868, false ) && 
            i != FInt.Create( 19302, false ) && i != FInt.Create( 25736, false ) )
            j = ( i * FInt.Create( 100, false ) ) / FInt.Create( 714, false ) - k * FInt.Create( 10, false );
        if ( k <= FInt.Create( 90, false ) )
            return sin_lookup( k, j );
        if ( k <= FInt.Create( 180, false ) )
            return sin_lookup( FInt.Create( 180, false ) - k, j );
        if ( k <= FInt.Create( 270, false ) )
            return sin_lookup( k - FInt.Create( 180, false ), j ).Inverse;
        else
            return sin_lookup( FInt.Create( 360, false ) - k, j ).Inverse;
    }

    private static FInt sin_lookup( FInt i, FInt j )
    {
        if ( j > 0 && j < FInt.Create( 10, false ) && i < FInt.Create( 90, false ) )
            return FInt.Create( SIN_TABLE[i.RawValue], false ) + 
                ( ( FInt.Create( SIN_TABLE[i.RawValue + 1], false ) - FInt.Create( SIN_TABLE[i.RawValue], false ) ) / 
                FInt.Create( 10, false ) ) * j;
        else
            return FInt.Create( SIN_TABLE[i.RawValue], false );
    }

    private static int[] SIN_TABLE = {
        0, 71, 142, 214, 285, 357, 428, 499, 570, 641, 
        711, 781, 851, 921, 990, 1060, 1128, 1197, 1265, 1333, 
        1400, 1468, 1534, 1600, 1665, 1730, 1795, 1859, 1922, 1985, 
        2048, 2109, 2170, 2230, 2290, 2349, 2407, 2464, 2521, 2577, 
        2632, 2686, 2740, 2793, 2845, 2896, 2946, 2995, 3043, 3091, 
        3137, 3183, 3227, 3271, 3313, 3355, 3395, 3434, 3473, 3510, 
        3547, 3582, 3616, 3649, 3681, 3712, 3741, 3770, 3797, 3823, 
        3849, 3872, 3895, 3917, 3937, 3956, 3974, 3991, 4006, 4020, 
        4033, 4045, 4056, 4065, 4073, 4080, 4086, 4090, 4093, 4095, 
        4096
    };
    #endregion

    private static FInt mul( FInt F1, FInt F2 )
    {
        return F1 * F2;
    }

    #region Cos, Tan, Asin
    public static FInt Cos( FInt i )
    {
        return Sin( i + FInt.Create( 6435, false ) );
    }

    public static FInt Tan( FInt i )
    {
        return Sin( i ) / Cos( i );
    }

    public static FInt Asin( FInt F )
    {
        bool isNegative = F < 0;
        F = Abs( F );

        if ( F > FInt.OneF )
            throw new ArithmeticException( "Bad Asin Input:" + F.ToDouble() );

        FInt f1 = mul( mul( mul( mul( FInt.Create( 145103 >> FInt.SHIFT_AMOUNT, false ), F ) -
            FInt.Create( 599880 >> FInt.SHIFT_AMOUNT, false ), F ) +
            FInt.Create( 1420468 >> FInt.SHIFT_AMOUNT, false ), F ) -
            FInt.Create( 3592413 >> FInt.SHIFT_AMOUNT, false ), F ) +
            FInt.Create( 26353447 >> FInt.SHIFT_AMOUNT, false );
        FInt f2 = PI / FInt.Create( 2, true ) - ( Sqrt( FInt.OneF - F ) * f1 );

        return isNegative ? f2.Inverse : f2;
    }
    #endregion

    #region ATan, ATan2
    public static FInt Atan( FInt F )
    {
        return Asin( F / Sqrt( FInt.OneF + ( F * F ) ) );
    }

    public static FInt Atan2( FInt F1, FInt F2 )
    {
        if ( F2.RawValue == 0 && F1.RawValue == 0 )
            return (FInt)0;

        FInt result = (FInt)0;
        if ( F2 > 0 )
            result = Atan( F1 / F2 );
        else if ( F2 < 0 )
        {
            if ( F1 >= 0 )
                result = ( PI - Atan( Abs( F1 / F2 ) ) );
            else
                result = ( PI - Atan( Abs( F1 / F2 ) ) ).Inverse;
        }
        else
            result = ( F1 >= 0 ? PI : PI.Inverse ) / FInt.Create( 2, true );

        return result;
    }
    #endregion

    #region Abs
    public static FInt Abs( FInt F )
    {
        if ( F < 0 )
            return F.Inverse;
        else
            return F;
    }
    #endregion

Hay una serie de otras funciones en la biblioteca MathFP del Dr. Hommes, pero estaban más allá de lo que necesitaba, por lo que no me he tomado el tiempo para traducirlas a C # (ese proceso se hizo más difícil por el hecho de que estaba usando un largo, y estoy usando la estructura FInt, que hace que las reglas de conversión sean un poco difíciles de ver de inmediato).

La precisión de estas funciones, ya que están codificadas aquí, es más que suficiente para mis propósitos, pero si necesita más, puede aumentar la CANTIDAD DE CAMBIOS en FInt. Solo tenga en cuenta que si lo hace, las constantes de las funciones del Dr. Hommes deberán dividirse por 4096 y luego multiplicarse por lo que requiera su nueva CANTIDAD DE CAMBIO. Es probable que encuentre algunos errores si lo hace y no tiene cuidado, así que asegúrese de ejecutar comprobaciones en las funciones matemáticas integradas para asegurarse de que los resultados no se disienten ajustando una constante incorrectamente.

Hasta ahora, esta lógica FInt parece tan rápida, si no quizás un poco más rápida, que las funciones equivalentes incorporadas en .net. Eso obviamente variaría según la máquina, ya que el coprocesador fp determinaría eso, así que no he ejecutado puntos de referencia específicos. Pero están integrados en mi juego ahora, y he visto una ligera disminución en la utilización del procesador en comparación con la anterior (esto es en un Q6600 de cuatro núcleos, aproximadamente una caída del 1% en el uso en promedio).

Gracias de nuevo a todos los que comentaron por su ayuda. Nadie me señaló directamente lo que estaba buscando, pero me diste algunas pistas que me ayudaron a encontrarlo en Google. Espero que este código resulte útil para otra persona, ya que no parece haber nada comparable en C # publicado públicamente.