AnimasiConvHull.java

package fjr.convhull;

import java.awt.Point;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;

import javafx.application.Application;
import javafx.application.Platform;
import javafx.scene.Group;
import javafx.scene.Scene;
import javafx.scene.canvas.Canvas;
import javafx.scene.canvas.GraphicsContext;
import javafx.scene.paint.Color;
import javafx.stage.Stage;

/*
 * animasi covex hull monotone chain... 
 * @auhor: Moh Fajar
 */

public class AnimasiConvHull extends Application {

	int width_ = 400;
	int height_ = 400;
	Canvas canvas;
	GraphicsContext gc;

	@Override
	public void start(Stage stage) throws Exception {

		Group root = new Group();
		canvas = new Canvas(width_ - 30, height_ - 30);
		gc = canvas.getGraphicsContext2D();
		canvas.setTranslateX(15);
		canvas.setTranslateY(15);

		root.getChildren().add(canvas);

		createRandomDot();
		draw(gc, null, null, null, null);
		stage.setScene(new Scene(root, width_, height_));
		stage.show();
		stage.setTitle("convex hull");

		convexHull();
	}

	ArrayList<Point> listPoint;

	public void createRandomDot() {
		listPoint = new ArrayList<Point>();
		int width = ((int) canvas.getWidth()) - 35;
		int height = ((int) canvas.getHeight()) - 35;
		for (int i = 0; i < 30; i++) {
			int c = ((int) (Math.random() * (width)));
			int d = ((int) (Math.random() * (height)));
			if (c + 35 < width)
				c += 35;
			if (d + 35 < height)
				d += 35;
			Point p = new Point(c, d);
			listPoint.add(p);
		}
	}

	final int sleepTime = 200;
	public void convexHull() {
		Collections.sort(listPoint, new Comparator<Point>() {
			public int compare(Point o1, Point o2) {
				return (new Double(o1.getX())).compareTo(new Double(o2.getX()));
			}
		});

		final ArrayList<Point> listUpper = new ArrayList<Point>();
		final ArrayList<Point> listLower = new ArrayList<Point>();
		new Thread(new Runnable() {
			public void run() {
				for (int i = 0; i < listPoint.size(); i++) {
					while (listUpper.size() >= 2
							&& !rightTurn(listUpper.get(listUpper.size() - 2),
									listUpper.get(listUpper.size() - 1),
									listPoint.get(i))) {
						Platform.runLater(new Runnable() {
							public void run() {
								draw(gc, listUpper, Color.YELLOW, null, null);
							}
						});
						try {
							Thread.sleep(sleepTime);
						} catch (Exception e) {
						}
						listUpper.remove(listUpper.size() - 1);
							Platform.runLater(new Runnable() {
								public void run() {
									draw(gc, listUpper, Color.YELLOW, null, null);
								}
							});
						try {
							Thread.sleep(sleepTime);
						} catch (Exception e) {
						}
					}
					listUpper.add(listPoint.get(i));
					Platform.runLater(new Runnable() {
						public void run() {
							draw(gc, listUpper, Color.YELLOW, null, null );
						}
					});
					try {
						Thread.sleep(sleepTime);
					} catch (Exception e) {
					}
				}
				for (int i = listPoint.size()- 1; i >= 0; i--) {
					while (listLower.size() >= 2
							&& !rightTurn(listLower.get(listLower.size() - 2),
									listLower.get(listLower.size() - 1),
									listPoint.get(i))) {
						Platform.runLater(new Runnable() {
							public void run() {
								draw(gc, listUpper, Color.YELLOW, listLower, Color.MAGENTA);
							}
						});
						try {
							Thread.sleep(sleepTime);
						} catch (Exception e) {
						}
						listLower.remove(listLower.size() - 1);
							Platform.runLater(new Runnable() {
								public void run() {
									draw(gc, listUpper, Color.YELLOW, listLower, Color.MAGENTA);
								}
							});
							try {
								Thread.sleep(sleepTime);
							} catch (Exception e) {
							}
					}
					listLower.add(listPoint.get(i));
					Platform.runLater(new Runnable() {
						public void run() {
							draw(gc, listUpper, Color.YELLOW, listLower, Color.MAGENTA);
						}
					});
					try {
						Thread.sleep(sleepTime);
					} catch (Exception e) {
					}
				}
			}
		}).start();
	}

	public void drawConvexHull(GraphicsContext gc, Color color,
			ArrayList<Point> list) {
		gc.setStroke(color);
		gc.beginPath();
		gc.setLineWidth(2);
		double x = list.get(0).getX();
		double y = list.get(0).getY();
		gc.moveTo(x, y);
		gc.stroke();
		for (int i = 0; i < list.size(); i++) {
			x = list.get(i).getX();
			y = list.get(i).getY();
			gc.lineTo(x, y);
			gc.stroke();
		}
	}
	
	private boolean rightTurn(Point a, Point b, Point c) {
		return (b.getX() - a.getX()) * (c.getY() - a.getY())
				- (b.getY() - a.getY()) * (c.getX() - a.getX()) > 0;
	}

	public void draw(GraphicsContext gc, ArrayList<Point> list,
			Color color, ArrayList<Point> secondList, Color c) {
		gc.setFill(Color.WHITE);
		gc.fillRect(0, 0, canvas.getWidth(), canvas.getHeight());
		gc.setStroke(Color.BLACK);
		gc.strokeRect(0, 0, canvas.getWidth(), canvas.getHeight());
		gc.setFill(Color.RED);
		for (int i = 0; i < listPoint.size(); i++) {
			gc.fillOval(listPoint.get(i).x -2.5, listPoint.get(i).y-2.5, 5, 5);
		}
		if (list != null) {
			drawConvexHull(gc, color, list);
		}
		if(secondList != null){
			drawConvexHull(gc, c, secondList);
		}
		
	}

	public static void main(String[] args) {
		launch(args);
	}

}