polygon_triangulation.pde

import java.util.ArrayList;
import java.util.List;

PFont f;
float mx,my,mxNext,myNext,intersect_x,intersect_y;
int i;
boolean accept=false;
int count=0;
int rectX,rectY;      // Position of square button
int circleX,circleY;  // Position of circle button
int rectSize=40;
int circleSize=10;
int threshold=60;
color inside=color(204,102,0);
color[]mycolors={#47586c, #bd776d, #012f46, #2A3A55, #552A3C, #FAD930, #FF600F, #729DD8, #9DAA76, #AA7692, #9376AA, #B9351E, #E32E2E, #29333E, #F50202, #4B3C50, #5D6293};
boolean accept_me=true;
List<Line> list;
List<CircleCoords> circle_list;
PolygonTriangulation polygonTriangulation;

public class Line {

    public float x1;
    public float y1;
    public float x2;
    public float y2;

    public Line(float x1, float y1, float x2, float y2) {
        this.x1 = x1;
        this.y1 = y1;
        this.x2 = x2;
        this.y2 = y2;
    }
}


    void setup() {
        size(600, 600);
        f = createFont("Arial", 16, true);
        background(102);
        list = new ArrayList<Line>();
        circle_list = new ArrayList<CircleCoords>();
        rectX = width / 2 - rectSize;
        rectY = (height - 30) - rectSize / 2;
        ellipseMode(CENTER);
    }

    boolean overRect(int x, int y, int width, int height) {
        if (mouseX >= x && mouseX <= x + width &&
                mouseY >= y && mouseY <= y + height) {
            return true;
        } else {
            return false;
        }
    }

    void arrow(int x1, int y1, int x2, int y2) {
        line(x1, y1, x2, y2);
        pushMatrix();
        translate(x2, y2);
        float a = atan2(x1 - x2, y2 - y1);
        rotate(a);
        line(0, 0, -10, -10);
        line(0, 0, 10, -10);
        popMatrix();
    }


    boolean is_simple_polygon(List<Line> list) {

        for (int i = 0; i < list.size(); i++) {
            for (int j = i + 2; j < list.size(); j++) {
                Line cl1 = list.get(i);
                Line cl2 = list.get(j);
                boolean _is_line_intersect = is_line_intersect(cl1.x1, cl1.y1, cl1.x2, cl1.y2, cl2.x1, cl2.y1, cl2.x2, cl2.y2);
                if (_is_line_intersect) return false;
            }
        }
        return true;
    }

    boolean is_line_intersect(float p0_x, float p0_y, float p1_x, float p1_y, float p2_x, float p2_y, float p3_x, float p3_y) {

        float s02_x, s02_y, s10_x, s10_y, s32_x, s32_y, s_numer, t_numer, denom, t;
        s10_x = p1_x - p0_x;
        s10_y = p1_y - p0_y;
        s32_x = p3_x - p2_x;
        s32_y = p3_y - p2_y;

        denom = s10_x * s32_y - s32_x * s10_y;
        if (denom == 0)
            return false; // Collinear
        boolean denomPositive = denom > 0;

        s02_x = p0_x - p2_x;
        s02_y = p0_y - p2_y;
        s_numer = s10_x * s02_y - s10_y * s02_x;
        if ((s_numer < 0) == denomPositive)
            return false; // No collision

        t_numer = s32_x * s02_y - s32_y * s02_x;
        if ((t_numer < 0) == denomPositive)
            return false; // No collision

        if (((s_numer > denom) == denomPositive) || ((t_numer > denom) == denomPositive))
            return false; // No collision
        // Collision detected
        t = t_numer / denom;

        intersect_x = p0_x + (t * s10_x);
        intersect_y = p0_y + (t * s10_y);

        ellipse(intersect_x, intersect_y, 16, 16);
        arrow((int) rectX, (int) rectY - 80, (int) intersect_x, (int) intersect_y + 5);
        return true;
    }

    void mousePressed() {
        if (overRect(rectX + threshold, rectY, rectSize, rectSize)) {
            list = new ArrayList<Line>();
            circle_list = new ArrayList<CircleCoords>();
            background(102);
            count = 0;
            accept_me = true;

        } else if (overRect(rectX, rectY, rectSize, rectSize)) {
            if (list.size() <= 0) {
                textFont(f, 20);
                text("PLEASE, INPUT POINTS!!!", 180, rectY - 60);
                text("PLEASE, PRESS RESET BUTTON!!!", 180, rectY - 40);
            } else if (!is_simple_polygon(list)) {

                textFont(f, 20);
                text("NOT A SIMPLE POLYGON!!!", 180, rectY - 60);

                text("PLEASE, PRESS RESET BUTTON!!!", 180, rectY - 40);

            } else {
                background(102);
                List<Point> point_list = new ArrayList<Point>();

                float firstX1 = list.get(0).x1;
                float firstY1 = list.get(0).y1;

                for (i = 0; i < list.size(); i++) {
                    Line cl = list.get(i);
                    Point point = new Point(cl.x1, cl.y1);
                    point_list.add(point);
                }

                Point point = new Point(firstX1, firstY1);

                point_list.add(point);

                polygonTriangulation = new PolygonTriangulation(point_list);

                polygonTriangulation.runPolygonTriangulation();

                List<Triangle> triangle_list = polygonTriangulation.getTriangles();

                for (i = 0; i < triangle_list.size(); i++) {
                    Triangle triangle = triangle_list.get(i);

                    fill(mycolors[int(random(0, 17))]);
                    beginShape();
                    vertex(triangle.getA().getX(), triangle.getA().getY());
                    vertex(triangle.getB().getX(), triangle.getB().getY());
                    vertex(triangle.getC().getX(), triangle.getC().getY());
                    endShape(CLOSE);

                }
                textFont(f, 12);
                int size = circle_list.size() - 1;
                int triangle_size = triangle_list.size() - 1;
                if (accept_me) {
                    text("NUMBER OF VERTICES: " + size, rectX - 30, rectY - 60);
                    fill(mycolors[int(random(0, 17))]);
                    text("NUMBER OF TRIANGLES: " + triangle_size, rectX - 30, rectY - 40);
                    fill(mycolors[int(random(0, 17))]);
                }
                count = 0;
            }
        } else if (count == 0) {
            mx = mouseX;
            my = mouseY;
            count = 2;
            CircleCoords circleCoords = new CircleCoords(mx, my, circleSize);
            circle_list.add(circleCoords);
        } else if (count == 1) {
            mxNext = mouseX;
            myNext = mouseY;

            Line myClass = new Line(mx, my, mxNext, myNext);
            list.add(myClass);
            CircleCoords circleCoords = new CircleCoords(mxNext, myNext, circleSize);
            circle_list.add(circleCoords);

            mx = mxNext;
            my = myNext;
            count = 2;
        }
    }


    void draw() {
        if (count != 0) {
            count = 1;
        }

        for (i = 0; i < list.size(); i++) {
            Line mc = list.get(i);
            line(mc.x1, mc.y1, mc.x2, mc.y2);
        }

        for (i = 0; i < circle_list.size(); i++) {
            CircleCoords circleCoords = circle_list.get(i);
            ellipse(circleCoords.x1, circleCoords.y1, circleCoords.circleSize, circleCoords.circleSize);
            fill(#9AB8B9);
        }

        rect(rectX, rectY, rectSize, rectSize);
        fill(#9AB8B9);
        rect(rectX + threshold, rectY, rectSize, rectSize);
        fill(#9AB8B9);

        textFont(f, 10);
        text("EXECUTE", rectX, rectY - 5);
        text("RESET", rectX + threshold, rectY - 5);
        textFont(f, 13);
        text("SIMPLE POLYGON TRIANGULATION", 180, 15);

    }


public class CircleCoords {
    public float x1;
    public float y1;
    public int circleSize;

    public CircleCoords(float x1, float y1, int circleSize) {
        this.x1 = x1;
        this.y1 = y1;
        this.circleSize = circleSize;
    }
}


public class Point {
    public float x;
    public float y;

    public float getX() {
        return x;
    }

    public float getY() {
        return y;
    }

    public Point(float x, float y) {
        this.x = x;
        this.y = y;
    }

    public Point(Point point) {
        this.x = point.x;
        this.y = point.y;
    }

    public Point() {
    }
}

public class PolygonTriangulation {

    public List<Point> points;
    public List<Point> nonconvexPoints;
    public List<Triangle> triangles;

    public boolean isCw;

    public PolygonTriangulation(List<Point> points) {
        this.points = new ArrayList<Point>();
        for (int i = 0; i < points.size(); i++)
            this.points.add(new Point(points.get(i)));
        nonconvexPoints = new ArrayList<Point>();

        triangles = new ArrayList<Triangle>();
        calcPolyOrientation();
        calcNonConvexPoints();
    }

    public void calcNonConvexPoints() {
        if (points.size() <= 3) return;

        Point p;
        Point v;
        Point u;
        // result value of test function
        int res = 0;
        for (int i = 0; i < points.size() - 1; i++) {
            p = points.get(i);
            Point tmp = points.get(i + 1);
            v = new Point();        // interpret v as vector from i to i+1
            v.x = tmp.x - p.x;
            v.y = tmp.y - p.y;

            if (i == points.size() - 2)
                u = points.get(0);
            else
                u = points.get(i + 2);

            res = (int) (u.x * v.y - u.y * v.x + v.x * p.y - v.y * p.x);
            if ((res > 0 && isCw) || (res <= 0 && !isCw)) {
                nonconvexPoints.add(tmp);
            }

        }
    }

    public void calcPolyOrientation() {
        if (points.size() < 3) return;

        int index = 0;
        Point pointOfIndex = points.get(0);
        for (int i = 1; i < points.size(); i++) {
            if (points.get(i).x < pointOfIndex.x) {
                pointOfIndex = points.get(i);
                index = i;
            } else if (points.get(i).x == pointOfIndex.x && points.get(i).y > pointOfIndex.y) {
                pointOfIndex = points.get(i);
                index = i;
            }
        }

        Point prevPointOfIndex;
        if (index == 0)
            prevPointOfIndex = points.get(points.size() - 1);
        else
            prevPointOfIndex = points.get(index - 1);
        Point v1 = new Point(pointOfIndex.x - prevPointOfIndex.x, pointOfIndex.y - prevPointOfIndex.y);
        Point succPointOfIndex;
        if (index == points.size() - 1)
            succPointOfIndex = points.get(0);
        else
            succPointOfIndex = points.get(index + 1);

        int res = (int) (succPointOfIndex.x * v1.y - succPointOfIndex.y * v1.x + v1.x * prevPointOfIndex.y - v1.y * prevPointOfIndex.x);

        isCw = (res <= 0 ? true : false);

    }

    public boolean isEar(Point p1, Point p2, Point p3) {
        if (!(isConvex(p1, p2, p3))) return false;

        for (int i = 0; i < nonconvexPoints.size(); i++) {
            if (new Triangle().isInside(p1, p2, p3, nonconvexPoints.get(i)))
                return false;
        }
        return true;
    }

    public boolean isConvex(Point p1, Point p2, Point p3) {
        Point v = new Point(p2.x - p1.x, p2.y - p1.y);
        int res = (int) (p3.x * v.y - p3.y * v.x + v.x * p1.y - v.y * p1.x);
        return !((res > 0 && isCw) || (res <= 0 && !isCw));
    }


    public int getIndex(int index, int offset) {
        int newindex;
        if (index + offset >= points.size())
            newindex = points.size() - (index + offset);
        else {
            if (index + offset < 0)
                newindex = points.size() + (index + offset);
            else
                newindex = index + offset;
        }
        return newindex;
    }

    public void runPolygonTriangulation() {
        if (points.size() <= 3) {
            textFont(f, 20);
            text("EDGES SHOULD BE >= 3!!!", 180, rectY - 60);
            text("PLEASE, PRESS RESET BUTTON!!!", 180, rectY - 40);

            accept_me = false;
            return;
        }

        triangles.clear();
        int index = 1;

        while (points.size() > 3) {

            if (isEar(points.get(getIndex(index, -1)), points.get(index), points.get(getIndex(index, 1)))) {
                triangles.add(new Triangle(points.get(getIndex(index, -1)), points.get(index), points.get(getIndex(index, 1))));
                points.remove(points.get(index));

                index = getIndex(index, -1);

            } else {
                index = getIndex(index, 1);
            }
        }
        triangles.add(new Triangle(points.get(0), points.get(1), points.get(2)));

    }

    public List<Triangle> getTriangles() {
        return triangles;
    }


}

public class Triangle {

    // coordinates
    private Point a;
    private Point b;
    private Point c;

    public Point getA() {
        return a;
    }

    public Point getB() {
        return b;
    }

    public Point getC() {
        return c;
    }

    public Triangle() {
    }

    public Triangle(Point a, Point b, Point c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }

    public boolean isInside(Point x, Point y, Point z, Point p) {
        Point v1 = new Point(y.x - x.x, y.y - x.y);
        Point v2 = new Point(z.x - x.x, z.y - x.y);

        double det = v1.x * v2.y - v2.x * v1.y;
        Point tmp = new Point(p.x - x.x, p.y - x.y);
        double lambda = (tmp.x * v2.y - v2.x * tmp.y) / det;
        double mue = (v1.x * tmp.y - tmp.x * v1.y) / det;

        return (lambda > 0 && mue > 0 && (lambda + mue) < 1);
    }
}