rj-action-library/Runtime/Math/Geometry/Path2.cs

using System.Collections;
using System.Collections.Generic;
using Godot;

namespace Rokojori
{

  

  public enum PointInPathResult
  {
    INSIDE,
    OUTSIDE,
    ERROR
  }

  

  public class Path2
  {
    float POINT_TO_CLOSE_DISTANCE = 0.0001f;
    float ANGLE_TO_SIMILAR_TRESHOLD = 0.00001f / 180f;
    int NUM_POINT_IN_PATH_TEST_RETRIES = 5;

    List<Vector2> _points = new List<Vector2>();

    public List<Vector2> points => _points;
    

    public Path2( List<Vector2> points )
    {
      this._points = points;
    }

    public override string ToString()
    {    
      return "Rokojori.Path2 with " + points.Count + " points" ; 
    }


    public Path2( Vector2[] points )
    {
      this._points = new List<Vector2>( points );
    }

    public void ApplyTransform( Transform2D transform2D )
    {
      for ( int i = 0; i < _points.Count; i++ )
      {
        _points[ i ] = transform2D * _points[ i ]; 
      }      
    }

    public void MirrorX( float offset = 0 )
    {
      for ( int i = 0; i < _points.Count; i++ )
      {
        var p = _points[ i ];
        p.X -= offset;
        p.X = - _points[ i ].X;
        p.X += offset;

        _points[ i ] = p;
      } 
    }

    public int numPoints => _points.Count;
    public bool empty => _points.Count == 0;

    public bool cacheProperties = true;
    
    Vector2? min;
    Vector2? max;
    bool? clockwise;

    public void ClearCachedProperties()
    {
      min = null;
      max = null;
      clockwise = null;
    }

    public void SetWindingDirection( bool clockwise )
    {
      if ( isClockwise == clockwise )
      {
        return;
      }

      _points.Reverse();

      this.clockwise = clockwise;
    }

    public bool isClockwise
    {
      get 
      {      
      
        if ( cacheProperties )
        {
          if ( clockwise == null )
          {
            clockwise = Geometry2D.IsPolygonClockwise( points.ToArray() );
          }

          return (bool) clockwise;
        }

        return Geometry2D.IsPolygonClockwise( points.ToArray() );

      }
    }

    public Shape2 ToShape2()
    {
      var s = new Shape2();
      s.paths = new List<Path2>();
      s.paths.Add( this );
      return s;
    }


    public Vector2 leftTop
    {
      get 
      {
        if ( cacheProperties && min != null )
        {
          return (Vector2) min;
        }
        
        var _min = _points[ 0 ];
        
        for ( int i = 1; i < _points.Count; i++ )
        {
          var point = _points[ i ];
          _min.X = Mathf.Min( point.X, _min.X );
          _min.Y = Mathf.Min( point.Y, _min.Y );
        } 

        min = _min;

        return (Vector2) min;

      }
    }

    public Vector2 rightBottom
    {
      get 
      {

         if ( cacheProperties && max != null )
        {
          return (Vector2) max;
        }

        var _max = _points[ 0 ];
        
        for ( int i = 1; i < _points.Count; i++ )
        {
          var point = _points[ i ];
          _max.X = Mathf.Max( point.X, _max.X );
          _max.Y = Mathf.Max( point.Y, _max.Y );
        }

        max = _max;
        
        return (Vector2) max;

      }
    }

    public Vector2 center => ( leftTop + rightBottom ) / 2;

    public void AddToNavigationPolygon( NavigationPolygon polygon )
    { 
      var convexPolygons = Geometry2D.DecomposePolygonInConvex( points.ToArray() );

      for ( int i = 0; i < convexPolygons.Count; i++ )
      {
        var vertices = convexPolygons[ i ];
        polygon.SetVertices( vertices );
        polygon.AddPolygon( CreateIndices( vertices.Length ) );
      }
      
    }

    public static int[] CreateIndices( int amount )
    {
      var indices = new int[ amount ];

      for ( int i = 0; i < amount; i++ )
      {
        indices[ i ] = i;
      }

      return indices;
    } 

    public static Path2 AsXZFrom( Curve3D curve3D, bool closed, int resolution = 20 )
    {
      var points = new List<Vector2>();

      var numPoints = resolution;

      var normalizer = 1f / resolution;

      for ( int i = 0; i < numPoints; i++ )
      {
        points.Add( Math2D.XZ( curve3D.Samplef( i * normalizer ) ) );
      }

      if ( closed )
      {
        points.Add( points[ 0 ] );
      }

      return new Path2( points );
    }

    public static Path2 AsXZFrom( Curve3 curve3, bool closed, int resolution = 20 )
    {
      var points = new List<Vector2>();

      var numPoints = resolution;

      var normalizer = 1f / resolution;

      for ( int i = 0; i < numPoints; i++ )
      {
        points.Add( Math2D.XZ( curve3.PositionAt( i * normalizer ) ) );
      }

      if ( closed )
      {
        points.Add( points[ 0 ] );
      }

      return new Path2( points );
    }

    public bool PointInPath( Vector2 p, bool fast = true, bool checkBoundingBox = true )
    {
      if ( fast )
      {
        return PointInPathFast( p, checkBoundingBox );
      }
      else
      {
        return PointInPathReliable( p, checkBoundingBox );
      }
    }

    public bool PointInPathFast( Vector2 point, bool checkBoundingBox = true )
    { 
      var min = this.leftTop;
      var max = this.rightBottom;

      if ( checkBoundingBox )
      {        
        if ( ! Box2.ContainsPoint( min, max, point ) )
        {
          return false;
        }
      }

      return CheckPointInPathFast( point, max + new Vector2( 122.133544f, 129.45423f ) );
    }

    public Path2 Clone()
    {     
      return new Path2( new List<Vector2>( _points ) );
    }

    public bool PointInPathReliable( Vector2 point, bool checkBoundingBox = true )
    {
      var min = this.leftTop;
      var max = this.rightBottom;

      if ( checkBoundingBox )
      {        
        if ( ! Box2.ContainsPoint( min, max, point ) )
        {
          return false;
        }

      }

      var endPoint = max + new Vector2( 0.1234235f, 0.4211322f );     
      var result = CheckPointInPath( point, endPoint );

      if ( PointInPathResult.ERROR != result )
      { 
        return PointInPathResult.INSIDE == result;
      }
      
      var rightTop = new Vector2( max.X, min.Y );
      endPoint = rightTop + new Vector2( 0.03234235f, -0.90211322f );   
      result = CheckPointInPath( point, endPoint );
      
      if ( PointInPathResult.ERROR != result )
      {
        return PointInPathResult.INSIDE == result;
      }
      
      var centerTop = new Vector2( ( min.X + max.X ) * 0.5f , min.Y );
      endPoint = centerTop + new Vector2( 0.013234235f, -0.90211322f );   
      result = CheckPointInPath( point, endPoint );
      
      if ( PointInPathResult.ERROR != result )
      {
        return PointInPathResult.INSIDE == result;
      }
     
      var rightMiddle = new Vector2( max.X , ( min.Y + max.Y ) * 0.5f);
      endPoint = rightMiddle + new Vector2( 0.013234235f, 0.00211322f );   
      result = CheckPointInPath( point, endPoint );      

      if ( PointInPathResult.ERROR != result )
      {
        return PointInPathResult.INSIDE == result;
      }

      endPoint = leftTop + new Vector2( -0.01053535f, -0.41005465f );   
      result = CheckPointInPath( point, endPoint );

      if ( PointInPathResult.ERROR != result )
      {
        return PointInPathResult.INSIDE == result;
      }

      for ( int i = 0; i < NUM_POINT_IN_PATH_TEST_RETRIES; i++ )
      {
        var randomX = GodotRandom.Get().Next();
        var randomY = GodotRandom.Get().Next();

        var randomPoint = max + new Vector2( randomX, randomY );     
        result = CheckPointInPath( point, endPoint );

        if ( PointInPathResult.ERROR != result )
        {
          return PointInPathResult.INSIDE == result;
        }
      } 

      return false; 
    }

    public bool CheckPointInPathFast( Vector2 point, Vector2 endPoint )
    {
      var pointLine = new Line2( point, endPoint );

      var iterationLine = new Line2();
            
      var intersections = 0;

      for ( int i = 0; i < _points.Count; i++ )
      {
        var start = _points[ i ];

        var nextIndex = ( i == _points.Count - 1 ) ? 0 : ( i + 1 );
        var end   = _points[ nextIndex ];     
        

        iterationLine.start = start;        
        iterationLine.end   = end;

        var intersects = pointLine.IntersectsWith( iterationLine );

        if ( intersects )
        {
          intersections ++;
        }
        
      }

      
      return intersections % 2 != 0;
    }

    public List<Vector3> AsTriangleFan( bool close = false )
    {
      var list = new List<Vector3>();

      var c = center;
      var end = close ? points.Count : ( points.Count - 1 );

      for ( int i = 0; i < end; i++ )
      {
        var n = ( i + 1 ) % points.Count; 

        var v0 = points[ i ];
        var v1 = points[ n ];
        var v2 = center;

        list.Add( Math3D.XYasXZ( v0 ) );
        list.Add( Math3D.XYasXZ( v1 ) );
        list.Add( Math3D.XYasXZ( v2 ) );

      }

      return list;
    }
    
    public void Reverse()
    {
      _points.Reverse();
      ClearCachedProperties();
    }

    public void PositionJitter( float max, Vector2 scale, Vector2 offset, RandomEngine random = null )
    {
      if ( random == null )
      {
        random = GodotRandom.Get();
      }

      for ( int i = 0; i < _points.Count; i++ )
      {
        _points[ i ] = Noise.PerlinOffset( _points[ i ], max, scale, offset, random );
      }
    }


    public string ToSVGPath()
    {
      var pathCommands = new List<string>();

      pathCommands.Add( "M " + SVGPathCommand.SVGCoordinate( points[ 0 ] ) );

      for ( int i = 1; i < points.Count; i++ )
      {
        pathCommands.Add( "L " + SVGPathCommand.SVGCoordinate( points[ i ] ) );
      }

      return Lists.Join( pathCommands, " ");
    }

    public MeshGeometry CreateMeshGeometry()
    {
      var geometry = new MeshGeometry();
      geometry.Initialize();
      
      var convexShapes = Convex2.PathToConvexList( this );

      for ( int i = 0; i < convexShapes.Count; i++ )
      {
        geometry.AddConvex2( convexShapes[ i ] );
      }

      return geometry;
    }

    PointInPathResult CheckPointInPath( Vector2 point, Vector2 endPoint )
    {
      var pointLine = new Line2( point, endPoint );
      var pointAngle = pointLine.angle;
      var pointAngle2 = pointLine.reverseAngle;

      var iterationLine = new Line2();
      
      var intersections = 0;

      for ( int i = 0; i < _points.Count; i++ )
      {
        var start = _points[ i ];

        if ( pointLine.DistanceToPoint( start ) < POINT_TO_CLOSE_DISTANCE )
        {
          return PointInPathResult.ERROR;
        } 

        var nextIndex = ( i == _points.Count - 1 ) ? 0 : ( i + 1 );
        var end   = _points[ nextIndex ];     
        

        iterationLine.start = _points[ i ];        
        iterationLine.end = _points[ nextIndex ];

        var iterationAngle = iterationLine.angle;
        var angleDifference = AbsoluteDeltaAngleFromRadiansToDegrees( pointAngle, iterationAngle );

        if ( angleDifference < ANGLE_TO_SIMILAR_TRESHOLD )
        {
          return PointInPathResult.ERROR;
        } 

        angleDifference = AbsoluteDeltaAngleFromRadiansToDegrees( pointAngle2, iterationAngle );

        if ( angleDifference < ANGLE_TO_SIMILAR_TRESHOLD )
        {
          return PointInPathResult.ERROR;
        } 


        var intersects = pointLine.IntersectsWith( iterationLine );

        if ( intersects )
        {
          intersections ++;
        }
        
      }

      if ( intersections % 2 != 0 )
      {
        return PointInPathResult.INSIDE;
      }

      return PointInPathResult.OUTSIDE;

    }

    public static Path2 Circle( Vector2 center, float radius = 1, int resolution = 36 )
    {
      var points = new List<Vector2>();

      for ( int i = 0; i < resolution; i++ )
      {
        var t = i / ( float ) ( resolution );
        var phase = t * Mathf.Pi * 2;
        var x = Mathf.Cos( phase ) * radius;
        var y = Mathf.Sin( phase ) * radius;

        points.Add( new Vector2( x, y ) + center );
      }

      return new Path2( points );
    }
    

    public static float AbsoluteDeltaAngleFromRadiansToDegrees( float rA, float rB )
    {
      var dA = Mathf.RadToDeg( rA );
      var dB = Mathf.RadToDeg( rB );

      return MathX.AbsoluteDeltaAngle( dA, dB );
    }


    public static Shape2 Union( Path2 a, Path2 b )
    {
      var paths = Geometry2D.MergePolygons( a._points.ToArray(), b._points.ToArray() );

      var s = new Shape2();

      for ( int i = 0; i < paths.Count; i++ )
      {
        s.paths.Add( new Path2( paths[ i ] ) );
      }

      return s;
    }

    const double DefaultClipperLibraryScale = 10e8;

    public static Path2 ToLinearXZPath( Path3D path3D )
    {
      var curve = path3D.Curve;

      var points = new List<Vector2>();

      for ( int i = 0; i < curve.PointCount; i++ )
      {
        var point = path3D.ToGlobal( curve.GetPointPosition( i ) );

        points.Add( Math2D.XZ( point ) );
      }

      return new Path2( points );

    }

    public static List<ClipperLib.IntPoint> ToClipperPath( Path2 path, double scale = Path2.DefaultClipperLibraryScale )
    {
      return Lists.Map( 
        path.points, p => 
        {
          var x = p.X * scale;
          var y = p.Y * scale;

          return new ClipperLib.IntPoint( x, y );
        }
      );
    }

    public static Path2 FromClipperPath( List<ClipperLib.IntPoint> clipperPath, double scale = Path2.DefaultClipperLibraryScale )
    {
      var points = Lists.Map( 
        clipperPath, p => 
        {
          var x = p.X / scale;
          var y = p.Y / scale;

          return new Vector2( (float)x, (float)y );
        }
      );

      return new Path2( points );
    }

    public static Shape2 Boolean( Path2 a, Path2 b, Geometry2D.PolyBooleanOperation booleanOperation, bool simplify = true )
    {
      // RJLog.Log( "Using Clipper Library" );

      var clipperPathA = ToClipperPath( a );
      var clipperPathB = ToClipperPath( b );

      var resultPaths = new List<List<ClipperLib.IntPoint>>();

      var type = ClipperLib.ClipType.ctUnion;

      if ( Geometry2D.PolyBooleanOperation.Difference == booleanOperation )
      {
        type = ClipperLib.ClipType.ctDifference;
      }
      else if ( Geometry2D.PolyBooleanOperation.Intersection == booleanOperation )
      {
        type = ClipperLib.ClipType.ctIntersection;
      }
      else if ( Geometry2D.PolyBooleanOperation.Xor == booleanOperation )
      {
        type = ClipperLib.ClipType.ctXor;
      }

			var clipper = new ClipperLib.Clipper();
			clipper.AddPath( clipperPathA, ClipperLib.PolyType.ptSubject, true); 
			clipper.AddPath( clipperPathB, ClipperLib.PolyType.ptClip, true); 
			clipper.Execute( type, resultPaths );

      if ( simplify )
      {
        resultPaths = ClipperLib.Clipper.SimplifyPolygons( resultPaths );
      }
      

      var s = new Shape2();

      resultPaths.ForEach(
        ( r ) =>
        {
          s.paths.Add( FromClipperPath( r ) );
        }
      );

      return s;
    }


  } 
}