Search code examples
javaalgorithmscalecurvepoints

How to Scale a Curve Line made up of points?

What is the best algorithm for scaling a curve line made up of points? For example:

Curve line (A):
o               
 o             
  o            o o   
   o         o     o     o o
    o       o       o   o   o
     o     o         o o     o
       o o

If Curve Line (A) is scaled "Smaller" by 5% then it looks like this.

Output:

o
 o        o o
  o      o    o   o o
   o    o      o o   o
    o o

If Curve Line (A) is scaled "Bigger" by 10% then it looks like this.

o               
 o             
  o                
   o               
    o                o o    
     o             o     o      o o    
      o           o       o   o     o
       o         o         o o       o
        o       o
         o     o
           o o

I just want to know the algorithm, concept or the idea on how to solve it but to make it more clearer here are some java codes I want to achieved.

class CurveLine
{
    public static ArrayList<float[]> getScaledCurveLine
    (float[][] curveLine, float percentage, bool enlarged)
    {
         ArrayList<float[]> scaledCurveLine = new ArrayList<float[]>();
         /*
               Some Algorithm for Scaling Curve Line
         */
         return scaledCurveLine; //new set of points
    }

    public static void main (string args[])
    {
         float [][] curveLine = new float[20][2]; //set of points
         curveLine[0][0] = 0; //x1
         curveLine[0][1] = 5; //y1
         curveLine[1][0] = 1; //x2
         //and so on..

         ArrayList<float[]> largerCurveLine = getScaledCurveLine(curveLine, 20, true);
         ArrayList<float[]> smallerCurveLine = getScaledCurveLine(curveLine, 20, false);
    }
}

I read some algorithm such as "Nearest Neighbor Interpolation" in scaling points but I'm not sure if I'm on the right path :(.

I badly need to know how to do it guys :( thanks in advance.

Solution

  • If I get your question right You basically want resize your polyline (curve) without changing the point density.

    1. approximate/fit curve to match your polyline

      If you got many points than you should do this piecewise (using 4 point cubics for example). In case you got some original polyline data you could remember the original polyline as curve for any further resampling to avoid fitting on each resize.

      for more info see How can i produce multi point linear interpolation?

      The polynomial degree of the curve used depends on what continuity you need. For basic graphic stuff 4 point cubics are enough. But if you need that also higher derivates are smooth than you need to use higher degrees.

    2. multiply all curve control points by scale

      in case you are using curve defined by vectors multiply them too ... If you want to do more complex transformations or rescale differently in each axis than you should apply this step after sampling in bullet #3. Because those transformations will produced different results if done on control points and on the curve points itself.

    3. sample new polyline

      so simply iterate over your curve by the new point density (parameter step) and use produced points as your new polyline.

      In case you are applying transformation #2 in this step the parameter step will be affected by the scale too.

      In case of piecewise curves with parameter t=<0,1> you need to start with t for next curve with value from the last one. so once the t crosses 1.0 you are moving to next curve and should start with t-1.0 parameter start value.

      If you want more precise density than you need to find point on curve that is exact distance from the last one instead of constant parameter increment.

    Here is a quick sketch of what I had in mind by all this:

    sketch