Point ret = new Point(bounds.x + rand.nextInt(bounds.width),                              bounds.y + rand.nextInt(bounds.height));        if(new Ellipse2D.Double(bounds.x, bounds.y, bounds.width, bounds.height).contains(ret)) return ret;      }    }    debug("UNKNOWN CONT TYPE");    return null;  }  //find the point on the continent border with the given angle to center.  //we do this by a binary search for the border  private Point getPointOnContinentBorder(Point center, double theta, Rectangle border, int contType) {    if(!border.contains(center)) debug("border doesn't contain center!");    if(contType == CONT_RECT || contType == CONT_ELLIPSE) {      RectangularShape rs = null;      if(contType == CONT_RECT) {        rs = border;      } else if(contType == CONT_ELLIPSE) {        rs = new Ellipse2D.Double(border.x, border.y, border.width, border.height);      }      int radius = 1000;      Point ret = null;      int movement = 500;      for(int i = 0; i < 20; i += 1) {        ret = new Point((int)(center.x + radius*Math.cos(theta)), (int)(center.y + radius*Math.sin(theta)));        if(rs.contains(ret)) {          radius += movement;        } else {          radius -= movement;        }        movement /= 2;      }      return ret;    }    debug("GPOCB: unkown cont type");    return null;  }  //connect up the continents so that any country can reach any other country.  //the algorithm is to make the shortest valid connection at each step until  //all continents are reacheable. we return a Vector of lines that should be  //drawn representing the connections we made  private Vector makeConnectionsBetweenContinents(              int[] contIndices, Point[] contCenters, Rectangle[] contBounds, int numContinents) {    //an array saying whether there is a direct connection between any two continents    boolean[][] contsConnected = new boolean[numContinents][numContinents];    for(int i = 0; i < numContinents; i += 1) {      for(int j = 0; j < numContinents; j += 1) {        contsConnected[i][j] = false;      }    }    Vector lines = new Vector();    //connect continents until they are all connected    while(!allContsReachableFrom(0, contsConnected, numContinents)) {      double shortestGap = 10000;      int contA = -1;      int contB = -1;      for(int i = 0; i < numContinents; i += 1) {        for(int j = 0; j < numContinents; j += 1) {          if(!contsConnected[i][j] && contsConnectable(i, j, contBounds, contCenters, numContinents)) {            double gap = dist(contCenters[i], contCenters[j]);            if(gap < shortestGap) {              shortestGap = gap;              contA = i;              contB = j;            }          }        }      }      contsConnected[contA][contB] = true;      contsConnected[contB][contA] = true;      lines.add(connectContinents(contA, contB, contIndices));    }    for(int i = 0; i < numContinents; i += 1) {      int connectedConts = 0;      for(int j = 0; j < numContinents; j += 1) {        if(contsConnected[i][j]) connectedConts += 1;      }      debug("connectedConts[" + i + "] = " + connectedConts);      if(connectedConts == 2) { //dead end        double shortestGap = 10000;        int contB = -1;        for(int j = 0; j < numContinents; j += 1) {          if(!contsConnected[i][j] && contsConnectable(i, j, contBounds, contCenters, numContinents)) {            double gap = dist(contCenters[i], contCenters[j]);            if(gap < shortestGap) {              shortestGap = gap;              contB = j;            }          }        }        debug("XXXXXXXXXXXX");        if(contB != -1) {          lines.add(connectContinents(i, contB, contIndices));          contsConnected[i][contB] = true;          contsConnected[contB][i] = true;        }      }    }    return lines;  }  //can we connect contA and contB? no if the resulting line would cross another continent  private boolean contsConnectable(int contA , int contB, Rectangle[] contBounds, Point[] contCenters, int numContinents) {    Line2D.Double l = new Line2D.Double(contCenters[contA], contCenters[contB]);    for(int i = 0; i < numContinents; i += 1) {      if(i != contA && i != contB) {        if(l.intersects(contBounds[i])) return false;      }    }    return true;  }  //can all continents be reached from start?  private boolean allContsReachableFrom(int start, boolean[][] contsConnected, int numContinents) {    boolean[] reachedAlready = new boolean[numContinents];    for(int i = 0; i < numContinents; i += 1) {      reachedAlready[i] = false;    }    reachedAlready[start] = true;    int numReached = 1;    for(int i = 0; i < numContinents; i += 1) {      if(contsConnected[start][i] && i != start) {        reachedAlready = whichContsReachableFrom(i, contsConnected, reachedAlready, numContinents);      }    }    for(int i = 0; i < numContinents; i += 1) {      if(!reachedAlready[i]) return false;    }    return true;  }  //which continents can be reached from start?  private boolean[] whichContsReachableFrom(               int start, boolean[][] contsConnected, boolean[] reachedAlready, int numContinents) {    int numReached = 1;    reachedAlready[start] = true;    for(int i = 0; i < numContinents; i += 1) {      if(contsConnected[start][i] && !reachedAlready[i]) {        reachedAlready = whichContsReachableFrom(i, contsConnected, reachedAlready, numContinents);      }    }    return reachedAlready;  }  //connect cont1 and cont2, adding the connection to the connections Vector  //and returning the line to draw on the board  private Line2D.Double connectContinents(int cont1, int cont2, int[] contIndices) {    int bestPolygon1 = -1;    int bestPolygon2 = -1;    double bestLength = 10000;    for(int j = contIndices[cont1]; j < contIndices[cont1+1]; j += 1) {      for(int k = contIndices[cont2]; k < contIndices[cont2+1]; k += 1) {        Point a = polygonCenter((Polygon)countryPolygons.get(j));        Point b = polygonCenter((Polygon)countryPolygons.get(k));        double dist = dist(a, b);        if(dist < bestLength) {          bestLength = dist;          bestPolygon1 = j;          bestPolygon2 = k;        }      }    }    ((Vector)connections.get(bestPolygon1)).add(new Integer(bestPolygon2));    ((Vector)connections.get(bestPolygon2)).add(new Integer(bestPolygon1));    return drawLineBetween((Polygon)countryPolygons.get(bestPolygon1),                           (Polygon)countryPolygons.get(bestPolygon2));  }  //write the xml representation of a country polygon  private void writePolygon(PrintWriter out, Polygon p) {    out.write("<polygon>");    for(int i = 0; i < p.npoints; i += 1) {      out.write("" + p.xpoints[i] + "," + p.ypoints[i] + " ");    }    out.write("</polygon>\n");  }  //write the xml representation of a country's adjoining list  private void writeConnections(PrintWriter out, Vector conns) {    out.write("<adjoining>");    for(int i = 0; i < conns.size()-1; i += 1) {      out.write("" + (Integer)conns.get(i) + ",");    }    if(conns.size() > 0) out.write("" + (Integer)conns.get(conns.size()-1));    out.write("</adjoining>\n");  }  //write the xml representation of a line  private void writeLine(PrintWriter out, Line2D.Double l) {    out.write("<line><position>" + (int)l.x1 + "," + (int)l.y1 + " " +                                   (int)l.x2 + "," + (int)l.y2 + "</position></line>\n");  }  //distance between two points  private double dist(Point a, Point b) {    return Math.sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));  }  //find the center of gravity of a polygon  private Point polygonCenter(Polygon p) {    double x = 0;    double y = 0;    for(int i = 0; i < p.npoints; i += 1) {      x += p.xpoints[i];      y += p.ypoints[i];    }    x /= p.npoints;    y /= p.npoints;    return new Point((int)x, (int)y);  }  //draw a line between the polygons with endpoints on their perimeters  //we do this through a binary search for their boundaries  private Line2D.Double drawLineBetween(Polygon a, Polygon b) {    Point ca = polygonCenter(a);    Point cb = polygonCenter(b);    double theta = Math.atan2(ca.y - cb.y, ca.x - cb.x);    double radius = dist(ca, cb);    double movement = radius/2;    for(int i = 0; i < 20; i += 1) {      ca = new Point((int)(cb.x + radius*Math.cos(theta)), (int)(cb.y + radius*Math.sin(theta)));      if(a.contains(ca)) {        radius -= movement;      } else {        radius += movement;      }      movement /= 2;    }    radius += 5; //make sure the line isn't detached    ca = new Point((int)(cb.x + radius*Math.cos(theta)), (int)(cb.y + radius*Math.sin(theta)));    theta += Math.PI;    radius = dist(ca, cb);    movement = radius/2;    for(int i = 0; i < 20; i += 1) {      cb = new Point((int)(ca.x + radius*Math.cos(theta)), (int)(ca.y + radius*Math.sin(theta)));      if(b.contains(cb)) {        radius -= movement;      } else {        radius += movement;      }      movement /= 2;    }    radius += 5; //make sure the line isn't detached    cb = new Point((int)(ca.x + radius*Math.cos(theta)), (int)(ca.y + radius*Math.sin(theta)));    return new Line2D.Double(ca, cb);  }  //interface function. should be true on release  public boolean canCache() {    return true;  }  public String description() {    return "Makes maps consisting of island continents.";  }  //user size choices  static final String CHOICE_NORMAL = "IslandInfinity - Hawaii";  static final String CHOICE_BIG = "IslandInfinity - normal";  static final String CHOICE_HUGE = "IslandInfinity - big";  static final String CHOICE_REALLYHUGE = "IslandInfinity - huge";  public java.util.List getChoices() {    Vector v = new Vector();    v.add(CHOICE_NORMAL);    v.add(CHOICE_BIG);    v.add(CHOICE_HUGE);    v.add(CHOICE_REALLYHUGE);    return v;  }  //interface function; unused  public String message(String message, Object data) {    return "";  }  public String name() {    return "IslandInfinity";  }  public float version() {    return 1.0f;  }  private void debug(String s) {//    System.out.println(":" + s);  }}