/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Catalano.Math.Geometry;

import Catalano.Core.FloatPoint;
import Catalano.Core.IntPoint;
import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author Diego
 */
public final class PointsCloud {

    private PointsCloud() {}
    
    /**
     * Shift cloud by adding specified value to all points in the collection.
     * @param cloud Collection of points to shift their coordinates.
     * @param shift Point to shift by.
     */
    public static void Shift( ArrayList cloud, IntPoint shift ){
        for ( int i = 0, n = cloud.size(); i < n; i++ ){
            IntPoint p = cloud.get(i);
            p.Add(shift);
            cloud.set(i, p);
        }
    }
    
    /**
     * Get bounding rectangle of the specified list of points.
     * @param cloud Collection of points to get bounding rectangle for.
     * @return Bounding rectangle.
     */
    public static List GetBoundingRectangle( List cloud){
        
        List bound = new ArrayList();
        
        int minX = Integer.MAX_VALUE;
        int maxX = Integer.MIN_VALUE;
        int minY = Integer.MAX_VALUE;
        int maxY = Integer.MIN_VALUE;

        for ( IntPoint pt : cloud )
        {
            int x = pt.x;
            int y = pt.y;

            // check X coordinate
            if ( x < minX )
                minX = x;
            if ( x > maxX )
                maxX = x;

            // check Y coordinate
            if ( y < minY )
                minY = y;
            if ( y > maxY )
                maxY = y;
        }

        if ( minX > maxX ) // if no point appeared to set either minX or maxX
            throw new IllegalArgumentException( "List of points can not be empty." );

        IntPoint min = new IntPoint( minX, minY );
        IntPoint max = new IntPoint( maxX, maxY );
        
        bound.add(min);
        bound.add(max);
        
        return bound;
    }
    
    public static FloatPoint GetCenterOfGravity( ArrayList cloud ){
        int numberOfPoints = 0;
        float xSum = 0, ySum = 0;

        for ( IntPoint pt : cloud )
        {
            xSum += pt.x;
            ySum += pt.y;
            numberOfPoints++;
        }

        xSum /= numberOfPoints;
        ySum /= numberOfPoints;

        return new FloatPoint( xSum, ySum );
    }
    
    public static FurthestPoint GetFurthestPoint( List cloud, IntPoint referencePoint ){
        FurthestPoint furthestPoint = new FurthestPoint();
        float maxDistance = -1;

        int rx = referencePoint.x;
        int ry = referencePoint.y;

        for ( IntPoint point : cloud )
        {
            int dx = rx - point.x;
            int dy = ry - point.y;
            // we are not calculating square root for finding "real" distance,
            // since it is really not important for finding furthest point
            float distance = dx * dx + dy * dy;

            if ( distance > maxDistance )
            {
                maxDistance = distance;
                furthestPoint.x = point.x;
                furthestPoint.y = point.y;
                furthestPoint.distance = maxDistance;
            }
        }

        return furthestPoint;
    }
    
    public static FurthestPoint[] GetFurthestPointsFromLine( List cloud, IntPoint linePoint1, IntPoint linePoint2 ){
        
        FurthestPoint[] furthest = new FurthestPoint[2];
        furthest[0] = new FurthestPoint(linePoint1);
        furthest[1] = new FurthestPoint(linePoint2);
        
        double distance1 = 0;
        double distance2 = 0;

        if ( linePoint2.x != linePoint1.x ){
            // line's equation y(x) = k * x + b
            float k = (float) ( linePoint2.y - linePoint1.y ) / ( linePoint2.x - linePoint1.x );
            float b = linePoint1.y - k * linePoint1.x;

            float div = (float) Math.sqrt( k * k + 1 );
            double distance = 0;

            for ( IntPoint point : cloud ){
                distance = ( k * (double)point.x + b - (double)point.y ) / div;

                if ( distance > distance1 ){
                    distance1 = distance;
                    furthest[0] = new FurthestPoint(point, (float)distance);
                }
                if ( distance < distance2 ){
                    distance2 = distance;
                    furthest[1] = new FurthestPoint(point, (float)distance);
                }
            }
        }
        else{
            int lineX = linePoint1.x;
            float distance = 0;

            for ( IntPoint point : cloud ){
                distance = lineX - point.x;

                if ( distance > distance1 ){
                    distance1 = distance;
                    furthest[0] = new FurthestPoint(point, distance);
                }
                if ( distance < distance2 ){
                    distance2 = distance;
                    furthest[1] = new FurthestPoint(point, distance);
                }
            }
        }

        //distance2 = -distance2;
        furthest[1].distance = (float)-distance2;
        
        return furthest;
    }
    
    public static IntPoint GetFurthestPointFromLine( ArrayList cloud, IntPoint linePoint1, IntPoint linePoint2){
        IntPoint furthestPoint = linePoint1;
        float distance = 0;

        if ( linePoint2.x != linePoint1.x ){
            // line's equation y(x) = k * x + b
            float k = (float) ( linePoint2.y - linePoint1.y ) / ( linePoint2.x - linePoint1.x );
            float b = linePoint1.y - k * linePoint1.x;

            float div = (float) Math.sqrt( k * k + 1 );
            float pointDistance = 0;

            for ( IntPoint point : cloud ){
                pointDistance = Math.abs( ( k * point.x + b - point.y ) / div );

                if ( pointDistance > distance ){
                    distance = pointDistance;
                    furthestPoint = point;
                }
            }
        }
        else{
            int lineX = linePoint1.x;
            float pointDistance = 0;

            for ( IntPoint point : cloud ){
                distance = Math.abs( lineX - point.x );

                if ( pointDistance > distance ){
                    distance = pointDistance;
                    furthestPoint = point;
                }
            }
        }
        return furthestPoint;
    }
    
    private static float quadrilateralRelativeDistortionLimit = 0.1f;
    
    public static float getQuadrilateralRelativeDistortionLimit(){
        return quadrilateralRelativeDistortionLimit;
    }
    
    public static void setQuadrilateralRelativeDistortionLimit(float value){
        quadrilateralRelativeDistortionLimit = Math.max( 0.0f, Math.min( 0.25f, value ) );
    }
    
    public static List FindQuadrilateralCorners( List cloud ) {
        // quadrilateral's corners
        List corners = new ArrayList( );

        // get bounding rectangle of the points list
        IntPoint minXY, maxXY;
        List bounds = PointsCloud.GetBoundingRectangle( cloud );
        minXY = bounds.get(0);
        maxXY = bounds.get(1);
        // get cloud's size
        IntPoint cloudSize = IntPoint.Subtract(maxXY, minXY);
        // calculate center point
        cloudSize.Divide(2);
        minXY.Add(cloudSize);
        IntPoint center = minXY;
        // acceptable deviation limit
        float distortionLimit = quadrilateralRelativeDistortionLimit * ( cloudSize.x + cloudSize.y ) / 2;

        // get the furthest point from (0,0)
        IntPoint point1 = PointsCloud.GetFurthestPoint( cloud, center ).toIntPoint();
        // get the furthest point from the first point
        IntPoint point2 = PointsCloud.GetFurthestPoint( cloud, point1 ).toIntPoint();

        corners.add( point1 );
        corners.add( point2 );

        // get two furthest points from line
        IntPoint point3, point4;
        float distance3, distance4;

        FurthestPoint[] fur = PointsCloud.GetFurthestPointsFromLine(cloud, point1, point2 );
        
        point3 = fur[0].toIntPoint();
        distance3 = fur[0].distance;
        
        point4 = fur[1].toIntPoint();
        distance4 = fur[1].distance;

        // ideally points 1 and 2 form a diagonal of the
        // quadrilateral area, and points 3 and 4 form another diagonal

        // but if one of the points (3 or 4) is very close to the line
        // connecting points 1 and 2, then it is one the same line ...
        // which means corner was not found.
        // in this case we deal with a trapezoid or triangle, where
        // (1-2) line is one of it sides.

        // another interesting case is when both points (3) and (4) are
        // very close the (1-2) line. in this case we may have just a flat
        // quadrilateral.

        if (
             ( ( distance3 >= distortionLimit ) && ( distance4 >= distortionLimit ) ) ||

             ( ( distance3 < distortionLimit ) && ( distance3 != 0 ) &&
               ( distance4 < distortionLimit ) && ( distance4 != 0 ) ) )
        {
            // don't add one of the corners, if the point is already in the corners list
            // (this may happen when both #3 and #4 points are very close to the line
            // connecting #1 and #2)
            if ( !corners.contains( point3 ) )
            {
                corners.add( point3 );
            }
            if ( !corners.contains( point4 ) )
            {
                corners.add( point4 );
            }
        }
        else
        {
            // it seems that we deal with kind of trapezoid,
            // where point 1 and 2 are on the same edge

            IntPoint tempPoint = ( distance3 > distance4 ) ? point3 : point4;

            // try to find 3rd point
            fur = PointsCloud.GetFurthestPointsFromLine( cloud, point1, tempPoint );
            
            point3 = fur[0].toIntPoint();
            distance3 = fur[0].distance;
            point4 = fur[1].toIntPoint();
            distance4 = fur[1].distance;

            boolean thirdPointIsFound = false;

            if ( ( distance3 >= distortionLimit ) && ( distance4 >= distortionLimit ) )
            {
                if ( point4.DistanceTo( point2 ) > point3.DistanceTo( point2 ) )
                    point3 = point4;

                thirdPointIsFound = true;
            }
            else
            {
                fur = PointsCloud.GetFurthestPointsFromLine( cloud, point2, tempPoint );
                
                point3 = fur[0].toIntPoint();
                distance3 = fur[0].distance;
                point4 = fur[1].toIntPoint();
                distance4 = fur[1].distance;

                if ( ( distance3 >= distortionLimit ) && ( distance4 >= distortionLimit ) )
                {
                    if ( point4.DistanceTo( point1 ) > point3.DistanceTo( point1 ) )
                        point3 = point4;

                    thirdPointIsFound = true;
                }
            }

            if ( !thirdPointIsFound )
            {
                // failed to find 3rd edge point, which is away enough from the temp point.
                // this means that the clound looks more like triangle
                corners.add( tempPoint );
            }
            else
            {
                corners.add( point3 );

                // try to find 4th point
                float tempDistance;

                fur = PointsCloud.GetFurthestPointsFromLine( cloud, point1, point3 );
                
                tempPoint = fur[0].toIntPoint();
                tempDistance = fur[0].distance;
                point4 = fur[1].toIntPoint();
                distance4 = fur[1].distance;

                if ( ( distance4 >= distortionLimit ) && ( tempDistance >= distortionLimit ) )
                {
                    if ( tempPoint.DistanceTo( point2 ) > point4.DistanceTo( point2 ) )
                        point4 = tempPoint;
                }
                else
                {
                    fur = PointsCloud.GetFurthestPointsFromLine( cloud, point2, point3 );
                        
                    tempPoint = fur[0].toIntPoint();
                    tempDistance = fur[0].distance;
                    point4 = fur[1].toIntPoint();
                    distance4 = fur[1].distance;

                    if ( ( tempPoint.DistanceTo( point1 ) > point4.DistanceTo( point1 ) ) &&
                         ( tempPoint != point2 ) && ( tempPoint != point3 ) )
                    {
                        point4 = tempPoint;
                    }
                }

                if ( ( point4 != point1 ) && ( point4 != point2 ) && ( point4 != point3 ) )
                    corners.add( point4 );
            }
        }

        // put the point with lowest X as the first
        for ( int i = 1, n = corners.size(); i < n; i++ )
        {
            if ( ( corners.get(i).x < corners.get(0).x ) ||
                 ( ( corners.get(i).x == corners.get(0).x ) && ( corners.get(i).y < corners.get(0).y ) ) )
            {
                IntPoint temp = corners.get(i);
                corners.set(i, corners.get(0));
                corners.set(0, temp);
            }
        }


        // sort other points in counter clockwise order
        float k1 = ( corners.get(1).x != corners.get(0).x ) ?
            ( (float) ( corners.get(1).y - corners.get(0).y ) / ( corners.get(1).x - corners.get(0).x ) ) :
            ( ( corners.get(1).y > corners.get(0).y ) ? Float.POSITIVE_INFINITY : Float.NEGATIVE_INFINITY );

        float k2 = ( corners.get(2).x != corners.get(0).x ) ?
            ( (float) ( corners.get(2).y - corners.get(0).y ) / ( corners.get(2).x - corners.get(0).x ) ) :
            ( ( corners.get(2).y > corners.get(0).y ) ? Float.POSITIVE_INFINITY : Float.NEGATIVE_INFINITY );

        if ( k2 < k1 )
        {
            IntPoint temp = corners.get(1);
            corners.set(1, corners.get(2));
            corners.set(2, temp);

            float tk = k1;
            k1 = k2;
            k2 = tk;
        }

        if ( corners.size() == 4 )
        {
            float k3 = ( corners.get(3).x != corners.get(0).x ) ?
                ( (float) ( corners.get(3).y - corners.get(0).y ) / ( corners.get(3).x - corners.get(0).x ) ) :
                ( ( corners.get(3).y > corners.get(0).y ) ? Float.POSITIVE_INFINITY : Float.NEGATIVE_INFINITY );

            if ( k3 < k1 )
            {
                IntPoint temp = corners.get(1);
                corners.set(1, corners.get(3));
                corners.set(3, temp);

                float tk = k1;
                k1 = k3;
                k3 = tk;
            }
            if ( k3 < k2 )
            {
                IntPoint temp = corners.get(2);
                corners.set(2, corners.get(3));
                corners.set(3, temp);

                float tk = k2;
                k2 = k3;
                k3 = tk;
            }
        }

        return corners;
    }
        
    public static class FurthestPoint{
        public int x;
        public int y;
        public float distance;

        public FurthestPoint() {}

        public FurthestPoint(int x, int y, float distance) {
            this.x = x;
            this.y = y;
            this.distance = distance;
        }
        
        public FurthestPoint(IntPoint p){
            this.x = p.x;
            this.y = p.y;
        }
        
        public FurthestPoint(IntPoint p, float distance){
            this.x = p.x;
            this.y = p.y;
            this.distance = distance;
        }
        
        public IntPoint toIntPoint(){
            return new IntPoint(x,y);
        }
    }
}
 

Ads help maintain this website.