Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.awt.Color;
- import java.awt.Font;
- import java.util.ArrayList;
- import java.util.List;
- import algoanim.animalscript.AnimalCircleGenerator;
- import algoanim.animalscript.AnimalPointGenerator;
- import algoanim.animalscript.AnimalPolylineGenerator;
- import algoanim.animalscript.AnimalRectGenerator;
- import algoanim.animalscript.AnimalScript;
- import algoanim.animalscript.AnimalTextGenerator;
- import algoanim.animalscript.AnimalTriangleGenerator;
- import algoanim.primitives.Circle;
- import algoanim.primitives.Point;
- import algoanim.primitives.Polyline;
- import algoanim.primitives.Rect;
- import algoanim.primitives.SourceCode;
- import algoanim.primitives.Text;
- import algoanim.primitives.Triangle;
- import algoanim.primitives.generators.Language;
- import algoanim.properties.AnimationPropertiesKeys;
- import algoanim.properties.CircleProperties;
- import algoanim.properties.PointProperties;
- import algoanim.properties.PolylineProperties;
- import algoanim.properties.RectProperties;
- import algoanim.properties.SourceCodeProperties;
- import algoanim.properties.TextProperties;
- import algoanim.properties.TriangleProperties;
- import algoanim.util.Coordinates;
- import algoanim.util.Node;
- import algoanim.util.TicksTiming;
- import algoanim.util.Timing;
- import auxiliary.Vector2f;
- public class SAT {
- public static final Color LINE_DEFAULT_COLOR = Color.BLACK;
- public static final Color VECTOR_DEFAULT_COLOR = Color.BLACK;
- Language lang;
- Text text;
- Point point;
- Circle circle;
- Polyline line;
- Polyline edge;
- Polyline vector;
- Polyline separatingAxis;
- Triangle triangle;
- // temp
- Polyline[] vectors = new Polyline[3];
- SourceCode sc;
- Timing timing;
- // might need these properties
- TextProperties textProps;
- RectProperties rectProps;
- PointProperties pointProps;
- CircleProperties circleProps;
- PolylineProperties lineProps;
- PolylineProperties vectorProps;
- TriangleProperties triangleProps;
- int x = 40;
- int y = 140;
- int startY;
- int offsetY = 20;
- String vertexName;
- String neighbor1Name;
- String neighbor2Name;
- List<Text> textList = new ArrayList<>();
- public void init() {
- lang = new AnimalScript("Separating Axis Theorem (Circle-Triangle)", "Bekir Oezkara", 640, 480);
- lang.setStepMode(true);
- timing = new TicksTiming(200);
- textProps = new TextProperties();
- textProps.set(AnimationPropertiesKeys.COLOR_PROPERTY, Color.BLACK);
- textProps.set(AnimationPropertiesKeys.FONT_PROPERTY, new Font("Monospaced", Font.PLAIN, 12));
- rectProps = new RectProperties();
- rectProps.set(AnimationPropertiesKeys.COLOR_PROPERTY, Color.DARK_GRAY);
- rectProps.set(AnimationPropertiesKeys.FILLED_PROPERTY, true);
- rectProps.set(AnimationPropertiesKeys.FILL_PROPERTY, Color.LIGHT_GRAY);
- rectProps.set(AnimationPropertiesKeys.DEPTH_PROPERTY, 2);
- pointProps = new PointProperties();
- pointProps.set(AnimationPropertiesKeys.COLOR_PROPERTY, Color.CYAN);
- circleProps = new CircleProperties();
- // circleProps.set(AnimationPropertiesKeys.COLOR_PROPERTY, Color.RED);
- circleProps.set(AnimationPropertiesKeys.FILL_PROPERTY, Color.WHITE);
- lineProps = new PolylineProperties();
- lineProps.set(AnimationPropertiesKeys.COLOR_PROPERTY, LINE_DEFAULT_COLOR);
- vectorProps = new PolylineProperties();
- vectorProps.set(AnimationPropertiesKeys.COLOR_PROPERTY, VECTOR_DEFAULT_COLOR);
- vectorProps.set(AnimationPropertiesKeys.FWARROW_PROPERTY, true);
- triangleProps = new TriangleProperties();
- // triangleProps.set(AnimationPropertiesKeys.COLOR_PROPERTY, Color.GREEN);
- triangleProps.set(AnimationPropertiesKeys.FILL_PROPERTY, Color.WHITE);
- makeHeader();
- makeSideBox();
- drawCoordSystem();
- }
- public boolean hasSA(auxiliary.Circle circle, auxiliary.Triangle triangle) {
- makeCircle(circle.center.x, circle.center.y, circle.radius);
- makeTriangle(triangle.A, triangle.B, triangle.C);
- lang.nextStep();
- startY = getY(circle, triangle);
- y = startY;
- x = 910;
- startY = 160;
- y = startY;
- // vertices
- vertexName = "A";
- neighbor1Name = "B";
- neighbor2Name = "C";
- point = makePoint((int)triangle.A.x, (int)triangle.A.y);
- textAndStep("Vertex A");
- boolean separatedByVertexA = isVertexSA(circle, triangle, triangle.A);
- point.hide();
- clearText();
- y = startY;
- vertexName = "B";
- neighbor1Name = "A";
- neighbor2Name = "C";
- point = makePoint((int)triangle.B.x, (int)triangle.B.y);
- textAndStep("Vertex B");
- boolean separatedByVertexB = isVertexSA(circle, triangle, triangle.B);
- point.hide();
- clearText();
- y = startY;
- vertexName = "C";
- neighbor1Name = "A";
- neighbor2Name = "B";
- point = makePoint((int)triangle.C.x, (int)triangle.C.y);
- textAndStep("Vertex C");
- boolean separatedByVertexC = isVertexSA(circle, triangle, triangle.C);
- point.hide();
- clearText();
- y = startY;
- // edges
- edge = makeLine(triangle.A, triangle.B, false);
- edge.changeColor("", Color.PINK, null, null);
- textAndStep("Edge from A to B");
- boolean separatedByEdgeAB = isEdgeSA(circle, triangle, triangle.edgeAB, triangle.A, triangle.B, triangle.C);
- edge.hide();
- clearText();
- y = startY;
- edge = makeLine(triangle.A, triangle.C, false);
- edge.changeColor("", Color.PINK, null, null);
- textAndStep("Edge from A to C");
- boolean separatedByEdgeAC = isEdgeSA(circle, triangle, triangle.edgeAC, triangle.A, triangle.C, triangle.B);
- edge.changeColor("", Color.BLACK, null, null);
- clearText();
- y = startY;
- edge = makeLine(triangle.B, triangle.C, false);
- edge.changeColor("", Color.PINK, null, null);
- textAndStep("Edge from B to C");
- boolean separatedByEdgeBC = isEdgeSA(circle, triangle, triangle.edgeBC, triangle.B, triangle.C, triangle.A);
- edge.hide();
- clearText();
- y = startY;
- boolean result = separatedByVertexA || separatedByVertexB || separatedByVertexC || separatedByEdgeAB || separatedByEdgeAC || separatedByEdgeBC;
- if(result) {
- separatingAxis.changeColor("", Color.GREEN, null, null);
- separatingAxis.show();
- }
- textAndStep("we found separating axis = " + result);
- return result;
- }
- /**
- *
- * @param circle
- * @param triangle
- * @param vertex
- * @return
- */
- private boolean isVertexSA(auxiliary.Circle circle, auxiliary.Triangle triangle, Vector2f vertex) {
- line = makeLine(circle.center.x, circle.center.y, circle.center.x + circle.radius, circle.center.y, false);
- textAndStep("radius = " + circle.radius);
- line.hide();
- float distToCenter = vertex.dist(circle.center);
- line = makeLine(vertex, circle.center, false);
- textAndStep("distance to center = " + distToCenter);
- line.hide();
- Vector2f vertexToCenter = circle.center.sub(vertex);
- vectors[0] = makeLine(vertex, circle.center, true);
- textAndStep("vector from vertex to center = " + vertexToCenter);
- Vector2f vertexToNeighbor1;
- Vector2f vertexToNeighbor2;
- if(vertex == triangle.A) {
- vertexToNeighbor1 = triangle.B.sub(vertex); // AB
- vertexToNeighbor2 = triangle.C.sub(vertex); // AC
- neighbor1Name = "B";
- neighbor2Name = "C";
- vectors[1] = makeLine(vertex, triangle.B, true);
- vectors[2] = makeLine(vertex, triangle.C, true);
- }
- else if(vertex == triangle.B) {
- vertexToNeighbor1 = triangle.A.sub(vertex); // BA
- vertexToNeighbor2 = triangle.C.sub(vertex); // BC
- neighbor1Name = "A";
- neighbor2Name = "C";
- vectors[1] = makeLine(vertex, triangle.A, true);
- vectors[2] = makeLine(vertex, triangle.C, true);
- }
- else if(vertex == triangle.C) {
- vertexToNeighbor1 = triangle.A.sub(vertex); // CA
- vertexToNeighbor2 = triangle.B.sub(vertex); // CB
- neighbor1Name = "A";
- neighbor2Name = "B";
- vectors[1] = makeLine(vertex, triangle.A, true);
- vectors[2] = makeLine(vertex, triangle.B, true);
- }
- else {
- throw new IllegalArgumentException("The provided vertex: " + vertex + " does not match with any of the triangle's vertices.");
- }
- textAndStep("vector from " + vertexName + " to " + neighbor1Name + " = " + vertexToNeighbor1);
- textAndStep("vector from " + vertexName + " to " + neighbor2Name + " = " + vertexToNeighbor2);
- // they are on opposite sides if the dot product is less than zero
- vectors[0].changeColor("", Color.LIGHT_GRAY, null, null);
- boolean isOppositeNeighbor1 = vertexToCenter.dot(vertexToNeighbor1) < 0;
- vectors[1].changeColor("", Color.ORANGE, null, null);
- textAndStep(neighbor1Name + " is on opposite side = " + isOppositeNeighbor1);
- vectors[1].changeColor("", VECTOR_DEFAULT_COLOR, null, null);
- boolean isOppositeNeighbor2 = vertexToCenter.dot(vertexToNeighbor2) < 0;
- vectors[2].changeColor("", Color.ORANGE, null, null);
- textAndStep(neighbor2Name + " is on opposite side = " + isOppositeNeighbor2);
- vectors[0].hide();
- vectors[1].hide();
- vectors[2].hide();
- boolean radius_less_than_dist = circle.radius < distToCenter;
- textAndStep("radius smaller than distance = " + radius_less_than_dist);
- boolean result = radius_less_than_dist && isOppositeNeighbor1 && isOppositeNeighbor2;
- line = makeLine(vertex, circle.center, false);
- line.changeColor("", result ? Color.GREEN : Color.RED, null, null);
- if(result) {
- separatingAxis = makeLine(vertex, circle.center, false);
- }
- textAndStep("vertex is separating axis = " + result);
- line.hide();
- if(separatingAxis != null) {
- separatingAxis.hide();
- }
- return result;
- }
- /**
- *
- * @param circle
- * @param triangle
- * @param edge
- * @param start
- * @param end
- * @param other
- * @return
- */
- private boolean isEdgeSA(auxiliary.Circle circle, auxiliary.Triangle triangle, Vector2f edge, Vector2f start, Vector2f end, Vector2f other) {
- line = makeLine(circle.center.x, circle.center.y, circle.center.x + circle.radius, circle.center.y, false);
- textAndStep("radius = " + circle.radius);
- line.hide();
- Vector2f normalizedEdge = edge.normalize();
- vector = makeLine(start.x, start.y, start.x + normalizedEdge.x, start.y + normalizedEdge.y, true); // TODO: too small, does not show arrow in Animal !
- vector.changeColor("", VECTOR_DEFAULT_COLOR, null, null);
- textAndStep("normalized edge = " + normalizedEdge);
- vector.hide();
- Vector2f vecToCircle;
- if(edge == triangle.edgeAB) {
- vecToCircle = circle.center.sub(triangle.A);
- vector = makeLine(triangle.A, circle.center, true);
- }
- else if(edge == triangle.edgeAC) {
- // TODO: why not C, or: when A, when C ?
- vecToCircle = circle.center.sub(triangle.A);
- vector = makeLine(triangle.A, circle.center, true);
- }
- else if(edge == triangle.edgeBC) {
- vecToCircle = circle.center.sub(triangle.B);
- vector = makeLine(triangle.B, circle.center, true);
- }
- else {
- throw new IllegalArgumentException("The provided edge: " + edge + " does not match with any of the triangle's edges.");
- }
- textAndStep("vector to circle = " + vecToCircle);
- vector.hide();
- float dot = normalizedEdge.dot(vecToCircle);
- line = makeLine(start.x, start.y, start.x + dot, start.y + dot, false);
- textAndStep("dot product of normalizedEdge and vectorToCircle = " + dot);
- line.hide();
- Vector2f closestPointToCircle;
- if(dot <= 0) {
- closestPointToCircle = start;
- }
- else if(dot >= edge.length()) {
- closestPointToCircle = end;
- }
- else {
- closestPointToCircle = normalizedEdge.mul(dot).add(start);
- }
- line = makeLine(start, closestPointToCircle, false);
- textAndStep("closest point to circle = " + closestPointToCircle);
- line.hide();
- // check if the other vertex (the one that is not part of the current edge) and the circle-center lie on opposite sides of the edge
- Vector2f vecFromClosestPointToCircle = circle.center.sub(closestPointToCircle);
- vectors[0] = makeLine(closestPointToCircle, circle.center, true);
- textAndStep("vector from closest point to circle = " + vecFromClosestPointToCircle);
- Vector2f vecFromClosestPointToOtherVertex = other.sub(closestPointToCircle);
- vectors[1] = makeLine(closestPointToCircle, other, true);
- textAndStep("vector from closest point to other vertex = " + vecFromClosestPointToOtherVertex);
- boolean isOppositeOtherVertex = vecFromClosestPointToCircle.dot(vecFromClosestPointToOtherVertex) < 0;
- vectors[0].changeColor("", Color.BLUE, null, null);
- vectors[1].changeColor("", Color.BLUE, null, null);
- textAndStep("other vertex on opposite side of circle = " + isOppositeOtherVertex);
- vectors[0].hide();
- vectors[1].hide();
- boolean radius_less_than_dist_to_closest_point = circle.radius < vecFromClosestPointToCircle.length();
- textAndStep("radius less than distance to closest point = " + radius_less_than_dist_to_closest_point);
- boolean result = radius_less_than_dist_to_closest_point && isOppositeOtherVertex;
- line = makeLine(closestPointToCircle, circle.center, false);
- line.changeColor("", result ? Color.GREEN : Color.RED, null, null);
- if(result) {
- separatingAxis = makeLine(closestPointToCircle, circle.center, false);
- }
- textAndStep("is separating axis = " + result);
- line.hide();
- if(separatingAxis != null) {
- separatingAxis.hide();
- }
- return result;
- }
- // ====================================================================================================================================
- // ====================================================================================================================================
- private Circle makeCircle(float x, float y, float radius) {
- return makeCircle((int)x, (int)y, (int)radius);
- }
- private Circle makeCircle(int x, int y, int radius) {
- return new Circle(new AnimalCircleGenerator(lang), transformCoords(x, y), transformRadius(radius), "circle", null, circleProps);
- }
- private Triangle makeTriangle(Vector2f A, Vector2f B, Vector2f C) {
- return makeTriangle(A.x, A.y, B.x, B.y, C.x, C.y);
- }
- private Triangle makeTriangle(float Ax, float Ay, float Bx, float By, float Cx, float Cy) {
- return makeTriangle((int)Ax, (int)Ay, (int)Bx, (int)By, (int)Cx, (int)Cy);
- }
- private Triangle makeTriangle(int Ax, int Ay, int Bx, int By, int Cx, int Cy) {
- return new Triangle(new AnimalTriangleGenerator(lang),
- transformCoords(Ax, Ay),
- transformCoords(Bx, By),
- transformCoords(Cx, Cy),
- "triangle",
- null,
- triangleProps);
- }
- private Coordinates transformCoords(int x, int y) {
- // TODO: refactor magic numbers
- int newX = 600 + 40 * x;
- int newY = 300 - 40 * y;
- return new Coordinates(newX, newY);
- }
- private int transformRadius(int radius) {
- // TODO: refactor magic numbers
- int newRadius = 40 * radius;
- return newRadius;
- }
- private Rect makeRect(float upperLeftX, float upperLeftY, float lowerRightX, float lowerRightY) {
- return makeRect((int)upperLeftX, (int)upperLeftY, (int)lowerRightX, (int)lowerRightY);
- }
- private Rect makeRect(int upperLeftX, int upperLeftY, int lowerRightX, int lowerRightY) {
- return new Rect(new AnimalRectGenerator(lang), new Coordinates(upperLeftX, upperLeftY), new Coordinates(lowerRightX, lowerRightY), "rect", null, rectProps);
- }
- private Text makeText(String text, int x, int y) {
- return new Text(new AnimalTextGenerator(lang), new Coordinates(x, y), text, "text", null, textProps);
- }
- // TODO: in future probably not needed, possibly delete
- private int getY(auxiliary.Circle circle, auxiliary.Triangle triangle) {
- float lowest = circle.center.y + circle.radius;
- // origin at top left, hence ">"
- if(triangle.A.y > lowest) {
- lowest = triangle.A.y;
- }
- else if(triangle.B.y > lowest) {
- lowest = triangle.B.y;
- }
- else if(triangle.C.y > lowest) {
- lowest = triangle.C.y;
- }
- return (int)lowest + offsetY;
- }
- private void textAndStep(String text) {
- textAndStep(text, this.x, this.y);
- }
- private void textAndStep(String text, int x, int y) {
- textList.add(makeText(text, x, y));
- this.y += offsetY;
- lang.nextStep();
- }
- private void clearText() {
- for(Text text : textList) {
- text.setText("", null, null);
- }
- textList = new ArrayList<>();
- }
- private Point makePoint(int x, int y) {
- return new Point(new AnimalPointGenerator(lang), new Coordinates(x, y), "point", null, pointProps);
- }
- private Polyline makeLine(Vector2f from, Vector2f to, boolean isVector, boolean needsTransform) {
- return makeLine((int)from.x, (int)from.y, (int)to.x, (int)to.y, isVector, needsTransform);
- }
- private Polyline makeLine(float startX, float startY, float endX, float endY, boolean isVector, boolean needsTransform) {
- return makeLine((int)startX, (int)startY, (int)endX, (int)endY, isVector, needsTransform);
- }
- private Polyline makeLine(int startX, int startY, int endX, int endY, boolean isVector, boolean needsTransform) {
- Node[] nodeArray;
- if(needsTransform) {
- nodeArray = new Node[] {
- transformCoords(startX, startY),
- transformCoords(endX, endY)
- };
- }
- else {
- nodeArray = new Node[] {
- new Coordinates(startX, startY),
- new Coordinates(endX, endY)
- };
- }
- return new Polyline(new AnimalPolylineGenerator(lang), nodeArray, "line", null, isVector ? vectorProps : lineProps);
- }
- private void makeHeader() {
- makeRect(430, 25, 790, 50);
- TextProperties titleProps = new TextProperties();
- titleProps.set(AnimationPropertiesKeys.FONT_PROPERTY, new Font("Arial", Font.BOLD, 16));
- new Text(new AnimalTextGenerator(lang), new Coordinates(450, 27), "Separating Axis Theorem (Circle-Triangle)", "title", null, titleProps);
- }
- private void makeSideBox() {
- makeRect(900, 150, 1300, 380);
- }
- private void drawCoordSystem() {
- int xAxis = 300;
- int xAxisStart = 400;
- int xAxisEnd = 800;
- int yAxis = 600;
- int yAxisStart = 500;
- int yAxisEnd = 100;
- makeLine(xAxisStart, xAxis, xAxisEnd, xAxis, false); // x-axis (600px)
- makeLine(yAxis, yAxisStart, yAxis, yAxisEnd, false); // y-axis (400px)
- int offset = 40; // 60px = 1cm
- // x-axis
- for(int i=xAxisStart; i <= xAxisEnd; i+=offset) {
- makeLine(i, xAxis-5, i, xAxis+5, false);
- }
- // y-axis
- for(int i=yAxisStart; i >= yAxisEnd; i-=offset) {
- makeLine(yAxis-5, i, yAxis+5, i, false);
- }
- }
- // ====================================================================================================================================
- // ====================================================================================================================================
- // ====================================================================================================================================
- // ====================================================================================================================================
- // ====================================================================================================================================
- // ====================================================================================================================================
- public static void main(String[] args) {
- // careful: animalscript y-coord goes downwards (i.e. 110 is below 100)
- SAT sat = new SAT();
- sat.init();
- auxiliary.Circle C = new auxiliary.Circle(new Vector2f(-2, 1), 2);
- auxiliary.Triangle T = new auxiliary.Triangle(new Vector2f(1, 1), new Vector2f(3, 1), new Vector2f(2, 4));
- sat.hasSA(C, T);
- System.out.println(sat.lang);
- }
- public void showSourceCode() {
- // first set the visual properties for the source code
- SourceCodeProperties scProps = new SourceCodeProperties();
- scProps.set(AnimationPropertiesKeys.CONTEXTCOLOR_PROPERTY, Color.BLUE);
- scProps.set(AnimationPropertiesKeys.FONT_PROPERTY, new Font("Monospaced", Font.PLAIN, 12));
- scProps.set(AnimationPropertiesKeys.HIGHLIGHTCOLOR_PROPERTY, Color.RED);
- scProps.set(AnimationPropertiesKeys.COLOR_PROPERTY, Color.BLACK);
- // now create the source code entity
- sc = lang.newSourceCode(new Coordinates(40, 240), "sourceCode", null, scProps);
- // add code lines (the actual sorting algo)
- // parameters: code itself, name (can be null), indention level, display options
- sc.addCodeLine("line0", null, 0, null);
- sc.addCodeLine("line1", null, 0, null);
- sc.addCodeLine("line2", null, 0, null);
- sc.addCodeLine("line3", null, 0, null);
- sc.addCodeLine("line4", null, 0, null);
- sc.addCodeLine("line5", null, 0, null);
- sc.addCodeLine("line6", null, 0, null);
- sc.addCodeLine("line7", null, 0, null);
- sc.addCodeLine("line8", null, 0, null);
- sc.addCodeLine("line9", null, 0, null);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement