polyspirallayout.java

经典的货郎担问题解决办法

package com.well.www.user.xanthian.java.layouts;

import java.util.*;

import com.well.www.user.xanthian.java.structures.*;
import com.well.www.user.xanthian.java.tools.*;
import com.well.www.user.xanthian.java.ui.*;

public class PolySpiralLayout
{

/*
** Arbitrarily, use some polygon as our spiraling object.  Even numbers
** of corners are easy, odd numbers are sadistic, because the traveller
** can't just do trips in and trips out along the spiral arms in matched
** pairs.
*/

 final static int CORNERS_IN_POLYGON = 5;

  public static void layout
  (
    double cities[][],
    int cityX,
    int cityY,
    double width,
    double height
  )
  {
    int numCities = cities.length;

    double radius = Math.min ( width, height ) / 2.0D;

    TravellerStatus.setCircumference( radius * 2.0D * Math.PI );

/*
** Arbitrarily, use an eight degree spin per spiral depth increase,
** trying to make it harder for the algorithm to decide between doing
** two arms at once or arm by arm in the outer fringes.  Ten degrees
** seems to lead to attempting to walk two arms at once, five degrees to
** one arm at at time.  Eight degrees is also sadistic, because when,
** for large numbers of cities, the outer part beome more easily
** connectable as rays rather than spiral arms, using eight degrees
** produces 45 of those rays, an odd number, maikng them harder to join
** into a tour.
*/
    final double ANGULAR_INCREASE = 2.0D * Math.PI / 45.0D;

    double polygonAngle = 2.0D * Math.PI / (double) CORNERS_IN_POLYGON;

    double center_x = width / 2.0D;
    double center_y = height / 2.0D;

    int naturalProblemSize =
      (numCities + CORNERS_IN_POLYGON - 1) / CORNERS_IN_POLYGON;

/*
** The spiral gets too crowded going all the way to the center (though it
** sure is pretty); just go 19/20ths of the way instead.
*/

    final int spiralingSize = ( naturalProblemSize * 20 ) / 19;

    int currentCityNumber = 0;

    for ( int i = 0; i < naturalProblemSize; i++ )
    {
      double currentRadius =
        radius
        *
        (double) ( spiralingSize - i )
        /
        (double) spiralingSize;

      for ( int j = 0; j < CORNERS_IN_POLYGON; j++ )
      {
        if ( currentCityNumber < numCities )
        {
          double currentAngle =
            ( ( (double ) j)  * polygonAngle )
            +
            ( ( (double) i ) * ANGULAR_INCREASE );
          cities[currentCityNumber][cityX] =
            center_x + (currentRadius * Math.cos(currentAngle));
          cities[currentCityNumber][cityY] =
            center_y + (currentRadius * Math.sin(currentAngle));
        }
        currentCityNumber++;
      }

    }

    TravellerStatus.setExactSolutionIsKnown( false );
    PerturbLayout.layout( cities, cityX, cityY, width, height );
  }
}