Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 package org.ros.android.view.visualization.shape;
00018
00019 import java.util.List;
00020
00028 public class Triangulate {
00029
00030 private static final float EPSILON = 1e-9f;
00031
00035 public static class Point {
00036 private final float x;
00037 private final float y;
00038
00039 public Point(final float x, final float y) {
00040 this.x = x;
00041 this.y = y;
00042 }
00043
00044 public float x() {
00045 return x;
00046 }
00047
00048 public float y() {
00049 return y;
00050 }
00051 }
00052
00060 public static boolean process(final Point[] contour, List<Point> result) {
00061
00062 int n = contour.length;
00063 if (n < 3) {
00064 return false;
00065 }
00066
00067 int[] V = new int[n];
00068
00069
00070 if (0.0f < area(contour)) {
00071 for (int v = 0; v < n; v++) {
00072 V[v] = v;
00073 }
00074 } else {
00075 for (int v = 0; v < n; v++) {
00076 V[v] = (n - 1) - v;
00077 }
00078 }
00079
00080 int nv = n;
00081
00082
00083 int count = 2 * nv;
00084
00085 for (int m = 0, v = nv - 1; nv > 2; ) {
00086
00087 if (0 >= (count--)) {
00088
00089 return false;
00090 }
00091
00092
00093 int u = v;
00094 if (nv <= u) {
00095 u = 0;
00096 }
00097 v = u + 1;
00098 if (nv <= v) {
00099 v = 0;
00100 }
00101 int w = v + 1;
00102 if (nv <= w) {
00103 w = 0;
00104 }
00105
00106 if (snip(contour, u, v, w, nv, V)) {
00107
00108 final int a = V[u];
00109 final int b = V[v];
00110 final int c = V[w];
00111
00112
00113 result.add(contour[a]);
00114 result.add(contour[b]);
00115 result.add(contour[c]);
00116
00117 m++;
00118
00119
00120 for (int s = v, t = v + 1; t < nv; s++, t++) {
00121 V[s] = V[t];
00122 }
00123 nv--;
00124
00125
00126 count = 2 * nv;
00127 }
00128 }
00129
00130 return true;
00131 }
00132
00139 public static float area(final Point[] contour) {
00140 final int n = contour.length;
00141 float A = 0.0f;
00142 for (int p = n - 1, q = 0; q < n; p = q++) {
00143 A += contour[p].x() * contour[q].y() - contour[q].x() * contour[p].y();
00144 }
00145 return A * 0.5f;
00146 }
00147
00154 public static boolean isInsideTriangle(final float Ax, final float Ay,
00155 final float Bx, final float By,
00156 final float Cx, final float Cy,
00157 final float Px, final float Py) {
00158 final float ax = Cx - Bx;
00159 final float ay = Cy - By;
00160 final float bx = Ax - Cx;
00161 final float by = Ay - Cy;
00162 final float cx = Bx - Ax;
00163 final float cy = By - Ay;
00164 final float apx = Px - Ax;
00165 final float apy = Py - Ay;
00166 final float bpx = Px - Bx;
00167 final float bpy = Py - By;
00168 final float cpx = Px - Cx;
00169 final float cpy = Py - Cy;
00170 final float aCROSSbp = ax * bpy - ay * bpx;
00171 final float cCROSSap = cx * apy - cy * apx;
00172 final float bCROSScp = bx * cpy - by * cpx;
00173 return ((aCROSSbp >= 0.0f) && (bCROSScp >= 0.0f) && (cCROSSap >= 0.0f));
00174 }
00175
00176 private static boolean snip(Point[] contour, int u, int v, int w, int n, int[] V) {
00177 final float Ax = contour[V[u]].x();
00178 final float Ay = contour[V[u]].y();
00179 final float Bx = contour[V[v]].x();
00180 final float By = contour[V[v]].y();
00181 final float Cx = contour[V[w]].x();
00182 final float Cy = contour[V[w]].y();
00183
00184 if (EPSILON > (((Bx - Ax) * (Cy - Ay)) - ((By - Ay) * (Cx - Ax)))) {
00185 return false;
00186 }
00187
00188 for (int p = 0; p < n; p++) {
00189 if ((p == u) || (p == v) || (p == w)) {
00190 continue;
00191 }
00192 final float Px = contour[V[p]].x();
00193 final float Py = contour[V[p]].y();
00194 if (isInsideTriangle(Ax, Ay, Bx, By, Cx, Cy, Px, Py)) {
00195 return false;
00196 }
00197 }
00198 return true;
00199 }
00200 }