J2ME上任意多边形填充算法

http://www.docin.com/p-160437612.html

JMicroPolygon is a project to provide polygon drawing and filling facilities for J2ME (MIDP 1.0 and 2.0) without relying on extension APIs.

http://sourceforge.net/projects/jmicropolygon/

package com.cvte.game.game;



import java.util.Stack;

import javax.microedition.lcdui.Graphics;


public class PolygonGraphics {
	public static void drawPolygon(Graphics g, int[] xPoints, int[] yPoints) {
		int max = xPoints.length - 1;
		for (int i = 0; i < max; ++i)
			g.drawLine(xPoints[i], yPoints[i], xPoints[(i + 1)], yPoints[(i + 1)]);

		g.drawLine(xPoints[max], yPoints[max], xPoints[0], yPoints[0]);
	}

	public static void fillPolygon(Graphics g, int[] xPoints, int[] yPoints) {
		Stack stack = new Stack();
		fillPolygon(g, xPoints, yPoints, stack);
		while (!(stack.isEmpty()))
			fillPolygon(g, (int[])stack.pop(), (int[])stack.pop(), stack);
	}

	private static void fillPolygon(Graphics g, int[] xPoints, int[] yPoints, Stack stack) {
		while (xPoints.length > 2) {
			int a = GeomUtils.indexOfLeast(xPoints);

			int b = (a + 1) % xPoints.length;

			int c = (a > 0) ? a - 1 : xPoints.length - 1;

			int leastInternalIndex = -1;
			boolean leastInternalSet = false;

			if (xPoints.length > 3) {
				for (int i = 0; i < xPoints.length; ++i) {
					if ((i != a) && (i != b) && (i != c)
							&& (GeomUtils.withinBounds(xPoints[i], yPoints[i], xPoints[a], yPoints[a], xPoints[b], yPoints[b], xPoints[c], yPoints[c]))
							&& (((!(leastInternalSet)) || (xPoints[i] < xPoints[leastInternalIndex])))) {
						leastInternalIndex = i;
						leastInternalSet = true;
					}
				}
			}

			if (!(leastInternalSet)) {
				g.fillTriangle(xPoints[a], yPoints[a], xPoints[b], yPoints[b], xPoints[c], yPoints[c]);
				int[][] trimmed = GeomUtils.trimEar(xPoints, yPoints, a);
				xPoints = trimmed[0];
				yPoints = trimmed[1];
			}
			else {
				int[][][] split = GeomUtils.split(xPoints, yPoints, a, leastInternalIndex);
				int[][] poly1 = split[0];
				int[][] poly2 = split[1];

				stack.push(poly2[1]);
				stack.push(poly2[0]);
				stack.push(poly1[1]);
				stack.push(poly1[0]);
				return;
			}
		}
	}
}

package com.cvte.game.game;


public abstract class GeomUtils {
	static boolean withinBounds(int px, int py, int ax, int ay, int bx, int by, int cx, int cy) {
		if ((px < min(ax, bx, cx)) || (px > max(ax, bx, cx)) || (py < min(ay, by, cy)) || (py > max(ay, by, cy)))
			return false;

		boolean sameabc = sameSide(px, py, ax, ay, bx, by, cx, cy);
		boolean samebac = sameSide(px, py, bx, by, ax, ay, cx, cy);
		boolean samecab = sameSide(px, py, cx, cy, ax, ay, bx, by);
		return ((sameabc) && (samebac) && (samecab));
	}

	static int[][][] split(int[] xPoints, int[] yPoints, int aIndex, int bIndex) {
		int firstLen;
		int index;
		if (bIndex < aIndex)
			firstLen = xPoints.length - aIndex + bIndex + 1;
		else
			firstLen = bIndex - aIndex + 1;

		int secondLen = xPoints.length - firstLen + 2;
		int[][] first = new int[2][firstLen];
		int[][] second = new int[2][secondLen];
		for (int i = 0; i < firstLen; ++i) {
			index = (aIndex + i) % xPoints.length;
			first[0][i] = xPoints[index];
			first[1][i] = yPoints[index];
		}
		for (int i = 0; i < secondLen; ++i) {
			index = (bIndex + i) % xPoints.length;
			second[0][i] = xPoints[index];
			second[1][i] = yPoints[index];
		}
		int[][][] result = new int[2][][];
		result[0] = first;
		result[1] = second;
		return result;
	}

	static int[][] trimEar(int[] xPoints, int[] yPoints, int earIndex) {
		int[] newXPoints = new int[xPoints.length - 1];
		int[] newYPoints = new int[yPoints.length - 1];
		int[][] newPoly = new int[2][];
		newPoly[0] = newXPoints;
		newPoly[1] = newYPoints;
		int p = 0;
		for (int i = 0; i < xPoints.length; ++i)
			if (i != earIndex) {
				newXPoints[p] = xPoints[i];
				newYPoints[p] = yPoints[i];
				++p;
			}

		return newPoly;
	}

	static int indexOfLeast(int[] elements) {
		int index = 0;
		int least = elements[0];
		for (int i = 1; i < elements.length; ++i)
			if (elements[i] < least) {
				index = i;
				least = elements[i];
			}

		return index;
	}

	private static boolean sameSide(int p1x, int p1y, int p2x, int p2y, int l1x, int l1y, int l2x, int l2y) {
		long lhs = (p1x - l1x) * (l2y - l1y) - (l2x - l1x) * (p1y - l1y);
		long rhs = (p2x - l1x) * (l2y - l1y) - (l2x - l1x) * (p2y - l1y);
		long product = lhs * rhs;
		boolean result = product >= 7930382294286598144L;
		return result;
	}

	private static int min(int a, int b, int c) {
		return Math.min(Math.min(a, b), c);
	}

	private static int max(int a, int b, int c) {
		return Math.max(Math.max(a, b), c);
	}
}

J2ME中绘制和填充多边形