1 package org.xpilot.jxpmap; 2 3 import java.awt.*; 4 import java.awt.image.BufferedImage; 5 import java.io.*; 6 import java.util.*; 7 8 public class FindPolygon { 9 10 private static final int ANGLE_0 = 0; 11 private static final int ANGLE_45 = 1; 12 private static final int ANGLE_90 = 2; 13 private static final int ANGLE_135 = 3; 14 private static final int ANGLE_180 = 4; 15 private static final int ANGLE_225 = 5; 16 private static final int ANGLE_270 = 6; 17 private static final int ANGLE_315 = 7; 18 private static final int ANGLE_360 = 8; 19 20 findPolygon(BufferedImage img)21 public static Polygon findPolygon(BufferedImage img) { 22 Point start = findStart(img); 23 if (start == null) return null; 24 ArrayList points = smoothen(img, start, merge(connect(img, start))); 25 Polygon poly = new Polygon(); 26 int h = poly.getBounds().height; 27 for(Iterator i = points.iterator(); i.hasNext();) { 28 int[] p = (int[])i.next(); 29 poly.addPoint(p[0] * 64, (h - p[1]) * 64); 30 } 31 return poly; 32 } 33 findStart(BufferedImage img)34 private static Point findStart(BufferedImage img) { 35 for(int y = 0; y < img.getHeight(); y++) 36 for(int x = 0; x < img.getWidth(); x++) 37 if(fg(img, x, y)) 38 return new Point(x, y); 39 return null; 40 } 41 connect(BufferedImage img, Point start)42 private static ArrayList connect(BufferedImage img, Point start) { 43 int x = start.x; 44 int y = start.y; 45 int dir = 0; 46 int dx[] = { 1, 1, 0, -1, -1, -1, 0, 1 }; 47 int dy[] = { 0, -1, -1, -1, 0, 1, 1, 1 }; 48 ArrayList points = new ArrayList(); 49 do 50 { 51 int dir1 = (dir + 3) % 8; 52 int diri = dir1; 53 do { 54 int x2 = x + dx[diri]; 55 int y2 = y + dy[diri]; 56 if (fg(img, x2, y2)) { 57 dir = diri; 58 x = x2; 59 y = y2; 60 points.add(new Point(dx[diri], dy[diri])); 61 break; 62 } 63 if (--diri < 0) diri += 8; 64 } while(diri != dir1); 65 } while(x != start.x || y != start.y); 66 return points; 67 } 68 merge(ArrayList points)69 private static ArrayList merge(ArrayList points) { 70 ArrayList rv = new ArrayList(); 71 Iterator i = points.iterator(); 72 if(!i.hasNext()) return points; 73 Point p1 = (Point)i.next(); 74 while(i.hasNext()) { 75 Point p2 = (Point)i.next(); 76 if(p1 != null) { 77 if(parallel(p1, p2)) { 78 p1.x += p2.x; 79 p1.y += p2.y; 80 if(!i.hasNext()) rv.add(p1); 81 } else { 82 rv.add(p1); 83 p1 = p2; 84 } 85 } 86 } 87 return rv; 88 } 89 parallel(Point p1, Point p2)90 private static boolean parallel(Point p1, Point p2) { 91 return sign(p1.x) == sign(p2.x) && p1.x * p2.y == p2.x * p1.y; 92 } 93 infnorm(Point p)94 private static int infnorm(Point p) { 95 return Math.max(Math.abs(p.x), Math.abs(p.y)); 96 } 97 smoothen( BufferedImage img, Point start, ArrayList points)98 private static ArrayList smoothen( 99 BufferedImage img, Point start, ArrayList points) { 100 ArrayList list = new ArrayList(); 101 int x = start.x; 102 int y = start.y; 103 list.add(new int[] { x, y, 0 }); 104 for(int i = 0; i < points.size(); i++) { 105 Point p1 = (Point)points.get(i); 106 Point p2 = (Point)points.get((i + 1) % points.size()); 107 Point p3 = (Point)points.get((i + 2) % points.size()); 108 x += p1.x; 109 y += p1.y; 110 if (infnorm(p1) > 1) { 111 if (infnorm(p2) == 1 && infnorm(p3) > 1) { 112 int d1 = dir(p1); 113 int d3 = dir(p3); 114 if ((d1 + 2) % 8 == d3) { 115 if (p1.x != 0) x += sign(p1.x); 116 if (p1.y != 0) y += sign(p1.y); 117 if (p3.x != 0) p3.x += sign(p3.x); 118 if (p3.y != 0) p3.y += sign(p3.y); 119 i++; 120 list.add(new int[] { x, y, 1 }); 121 continue; 122 } 123 } else if (infnorm(p2) > 1) { 124 int d1 = dir(p1); 125 int d2 = dir(p2); 126 if ((d1 + 1) % 8 == d2) { 127 list.add(new int[] { x, y, 1 }); 128 continue; 129 } 130 } 131 } 132 list.add(new int[] { x, y, 0 }); 133 } 134 135 Point max = new Point(img.getWidth() - 1, img.getHeight() - 1); 136 for(Iterator i = list.iterator(); i.hasNext();) { 137 int p[] = (int[])i.next(); 138 int rm = 0; 139 if (p[2] == 0) { 140 if (p[0] == 0 || !fg(img, p[0] - 1, p[1])) rm++; 141 if (p[0] == max.x || !fg(img, p[0] + 1, p[1])) rm++; 142 if (p[1] == 0 || !fg(img, p[0], p[1] - 1)) rm++; 143 if (p[1] == max.y || !fg(img, p[0], p[1] + 1)) rm++; 144 } 145 if(rm == 1) i.remove(); 146 } 147 148 return list; 149 } 150 dir(Point p)151 private static int dir(Point p) { 152 int x = p.x <= 0 ? (p.x != 0 ? -1 : 0) : 1; 153 int y = p.y <= 0 ? (p.y != 0 ? 1 : 0) : -1; 154 if (x == 0 && y == 1) return ANGLE_90; 155 if (x == 0 && y == -1) return ANGLE_270; 156 if (x == 1 && y == 0) return ANGLE_0; 157 if (x == 1 && y == 1) return ANGLE_45; 158 if (x == 1 && y == -1) return ANGLE_315; 159 if (x == -1 && y == 0) return ANGLE_180; 160 if (x == -1 && y == 1) return ANGLE_135; 161 if (x == -1 && y == -1) return ANGLE_225; 162 throw new IllegalArgumentException(p.toString()); 163 } 164 sign(int i)165 private static int sign(int i) { 166 return i < 0 ? -1 : 1; 167 } 168 fg(BufferedImage img, int x, int y)169 private static boolean fg(BufferedImage img, int x, int y) { 170 if (x < 0 || x >= img.getWidth()) 171 return false; 172 if (y < 0 || y >= img.getHeight()) 173 return false; 174 return (img.getRGB(x, y) & 0xffffff) != 0; 175 } 176 } 177