Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- private Polygon[] regularizeLeftist(Point[] vertexes,
- HashMap<Point, Point> next, HashMap<Point, Point> prev,
- Edge[][] edges, pdouble currentx) {
- Vector<Point> points = new Vector<Point>(2 * n);
- for (int i = 0; i < n; i++) {
- points.add(vertexes[i]);
- if (i < n - 1) {
- next.put(vertexes[i], vertexes[i + 1]);
- } else {
- next.put(vertexes[i], vertexes[0]);
- }
- if (i > 0) {
- prev.put(vertexes[i], vertexes[i - 1]);
- } else {
- prev.put(vertexes[i], vertexes[n - 1]);
- }
- }
- Arrays.sort(vertexes, new PointsComparator());
- currentx.value = vertexes[0].x;
- for (int i = 0; i < n; i++) {
- edges[vertexes[i].number][next.get(vertexes[i]).number] = new Edge(
- vertexes[i], next.get(vertexes[i]), currentx);
- }
- TreeSet<Edge> line = new TreeSet<Edge>();
- Point v;
- Point w;
- Point vnext;
- Point vprev;
- Edge enext;
- Edge eprev;
- for (int i = 0; i < n; i++) {
- currentx.value = vertexes[i].x;
- v = vertexes[i];
- vnext = next.get(v);
- vprev = prev.get(v);
- if (vnext.x < v.x && vprev.x < v.x) {
- if (vnext.y > vprev.y) {
- enext = line.higher(edges[v.number][vnext.number]);
- eprev = line.lower(edges[vprev.number][v.number]);
- } else {
- eprev = line.lower(edges[v.number][vnext.number]);
- enext = line.higher(edges[vprev.number][v.number]);
- }
- line.remove(edges[v.number][vnext.number]);
- line.remove(edges[vprev.number][v.number]);
- if (enext != null)
- enext.controlPoint = v;
- continue;
- }
- if (vprev.x < v.x && v.x < vnext.x) {
- enext = line.higher(edges[vprev.number][v.number]);
- eprev = line.lower(edges[vprev.number][v.number]);
- line.remove(edges[vprev.number][v.number]);
- line.add(edges[v.number][vnext.number]);
- if (enext != null)
- enext.controlPoint = v;
- edges[v.number][vnext.number].controlPoint = v;
- continue;
- }
- if (vnext.x < v.x && v.x < vprev.x) {
- enext = line.higher(edges[v.number][vnext.number]);
- eprev = line.lower(edges[v.number][vnext.number]);
- line.remove(edges[v.number][vnext.number]);
- line.add(edges[vprev.number][v.number]);
- if (enext != null)
- enext.controlPoint = v;
- edges[vprev.number][v.number].controlPoint = v;
- continue;
- }
- if (vnext.x > v.x && vprev.x > v.x) {
- if (vnext.y > vprev.y) {
- enext = line.higher(edges[v.number][vnext.number]);
- eprev = line.lower(edges[vprev.number][v.number]);
- } else {
- eprev = line.lower(edges[v.number][vnext.number]);
- enext = line.higher(edges[vprev.number][v.number]);
- }
- line.add(edges[vprev.number][v.number]);
- line.add(edges[v.number][vnext.number]);
- if (new geometry.Vector(vprev, v)
- .vectorMultiplication(new geometry.Vector(v, vnext)) > 0) {
- if (enext != null)
- enext.controlPoint = v;
- edges[vprev.number][v.number].controlPoint = edges[v.number][vnext.number].controlPoint = v;
- continue;
- }
- w = null;
- if (enext != null && eprev != null)
- w = enext.controlPoint;
- if (w != null) {
- Point tmp1 = v.clone();
- Point tmp2 = w.clone();
- points.add(tmp1);
- points.add(tmp2);
- next.put(tmp1, tmp2);
- prev.put(tmp2, tmp1);
- next.put(tmp2, next.get(w));
- prev.put(next.get(w), tmp2);
- next.put(vprev, tmp1);
- prev.put(tmp1, vprev);
- next.put(w, v);
- prev.put(v, w);
- edges[w.number][v.number] = new Edge(w, v, currentx);
- edges[v.number][w.number] = new Edge(v, w, currentx);
- if (vnext.y > vprev.y) {
- enext.controlPoint = v;
- edges[vprev.number][v.number].controlPoint = tmp1;
- edges[v.number][vnext.number].controlPoint = v;
- } else {
- enext.controlPoint = tmp1;
- edges[vprev.number][v.number].controlPoint = v;
- edges[v.number][vnext.number].controlPoint = tmp1;
- }
- }
- }
- }
- Vector<Polygon> withoutLeftist = new Vector<Polygon>();
- Vector<Point> current = new Vector<Point>();
- HashMap<Point, Boolean> was = new HashMap<Point, Boolean>();
- Point tmp;
- for (int i = 0; i < points.size(); i++) {
- tmp = points.get(i);
- if (was.get(tmp) == null) {
- current.clear();
- while (was.get(tmp) == null) {
- was.put(tmp, true);
- current.add(tmp);
- tmp = next.get(tmp);
- }
- withoutLeftist.add(new Polygon(current.size(), current));
- }
- }
- Polygon[] result = new Polygon[withoutLeftist.size()];
- for (int i = 0; i < withoutLeftist.size(); i++) {
- result[i] = withoutLeftist.get(i);
- }
- return result;
- }
- private Polygon[] regularizeRightist(Vector<Point> allPoints,
- HashMap<Point, Point> next, HashMap<Point, Point> prev,
- Edge[][] edges, pdouble currentx) {
- Arrays.sort(vertexes, new PointsComparator());
- Point v;
- Point vnext;
- Point vprev;
- Point w;
- Edge enext;
- Edge eprev;
- TreeSet<Edge> line = new TreeSet<Edge>();
- Vector<Point> points = new Vector<Point>(2 * n);
- for (int i = 0; i < n; i++) {
- points.add(vertexes[i]);
- }
- for (int i = n - 1; i >= 0; i--) {
- currentx.value = vertexes[i].x;
- v = vertexes[i];
- vnext = next.get(v);
- vprev = prev.get(v);
- if (vnext.x > v.x && vprev.x > v.x) {
- if (vnext.y > vprev.y) {
- enext = line.higher(edges[v.number][vnext.number]);
- eprev = line.lower(edges[vprev.number][v.number]);
- } else {
- eprev = line.lower(edges[v.number][vnext.number]);
- enext = line.higher(edges[vprev.number][v.number]);
- }
- line.remove(edges[v.number][vnext.number]);
- line.remove(edges[vprev.number][v.number]);
- if (enext != null)
- enext.controlPoint = v;
- continue;
- }
- if (vprev.x < v.x && v.x < vnext.x) {
- enext = line.higher(edges[v.number][vnext.number]);
- eprev = line.lower(edges[v.number][vnext.number]);
- line.remove(edges[v.number][vnext.number]);
- line.add(edges[vprev.number][v.number]);
- if (enext != null)
- enext.controlPoint = v;
- edges[vprev.number][v.number].controlPoint = v;
- continue;
- }
- if (vnext.x < v.x && v.x < vprev.x) {
- enext = line.higher(edges[vprev.number][v.number]);
- eprev = line.lower(edges[vprev.number][v.number]);
- line.remove(edges[vprev.number][v.number]);
- line.add(edges[v.number][vnext.number]);
- if (enext != null)
- enext.controlPoint = v;
- edges[v.number][vnext.number].controlPoint = v;
- continue;
- }
- if (vnext.x < v.x && vprev.x < v.x) {
- if (vnext.y > vprev.y) {
- enext = line.higher(edges[v.number][vnext.number]);
- eprev = line.lower(edges[vprev.number][v.number]);
- } else {
- eprev = line.lower(edges[v.number][vnext.number]);
- enext = line.higher(edges[vprev.number][v.number]);
- }
- line.add(edges[vprev.number][v.number]);
- line.add(edges[v.number][vnext.number]);
- if (new geometry.Vector(vprev, v)
- .vectorMultiplication(new geometry.Vector(v, vnext)) > 0) {
- edges[vprev.number][v.number].controlPoint = edges[v.number][vnext.number].controlPoint = v;
- if (enext != null)
- enext.controlPoint = v;
- continue;
- }
- w = null;
- if (enext != null && eprev != null)
- w = enext.controlPoint;
- if (w != null) {
- Point tmp1 = v.clone();
- Point tmp2 = w.clone();
- points.add(tmp1);
- points.add(tmp2);
- next.put(tmp2, tmp1);
- prev.put(tmp1, tmp2);
- next.put(tmp1, vnext);
- prev.put(vnext, tmp1);
- next.put(prev.get(w), tmp2);
- prev.put(tmp2, prev.get(w));
- next.put(v, w);
- prev.put(w, v);
- edges[w.number][v.number] = new Edge(w, v, currentx);
- edges[v.number][w.number] = new Edge(v, w, currentx);
- if (vnext.y < vprev.y) {
- edges[vprev.number][v.number].controlPoint = tmp1;
- edges[v.number][vnext.number].controlPoint = v;
- enext.controlPoint = v;
- } else {
- edges[vprev.number][v.number].controlPoint = v;
- edges[v.number][vnext.number].controlPoint = tmp1;
- enext.controlPoint = tmp1;
- }
- }
- }
- }
- Vector<Polygon> res = new Vector<Polygon>();
- Vector<Point> current = new Vector<Point>();
- HashMap<Point, Boolean> was = new HashMap<Point, Boolean>();
- Point tmp;
- for (int i = 0; i < points.size(); i++) {
- tmp = points.get(i);
- if (was.get(tmp) == null) {
- current.clear();
- while (was.get(tmp) == null) {
- was.put(tmp, true);
- current.add(tmp);
- tmp = next.get(tmp);
- }
- res.add(new Polygon(current.size(), current));
- }
- }
- Polygon[] result = new Polygon[res.size()];
- for (int i = 0; i < res.size(); i++) {
- result[i] = res.get(i);
- }
- allPoints.addAll(points);
- return result;
- }
- public Polygon[] doRegularization() {
- for (int i = 0; i < n; i++) {
- vertexes[i].number = i;
- }
- Point[] copy = new Point[n];
- for (int i = 0; i < n; i++) {
- copy[i] = vertexes[i].clone();
- }
- HashMap<Point, Point> next = new HashMap<Point, Point>();
- HashMap<Point, Point> prev = new HashMap<Point, Point>();
- Edge[][] edges = new Edge[n][n];
- Random rand = new Random();
- double angle = rand.nextDouble() * 0.0001 + 0.0001;
- for (int i = 0; i < n; i++) {
- copy[i].rotate(Math.cos(angle), Math.sin(angle));
- }
- pdouble currentx = new pdouble(0);
- Polygon[] withoutLeftist = regularizeLeftist(copy, next, prev, edges,
- currentx);
- Polygon[] cur;
- Vector<Polygon> withoutBreaks = new Vector<Polygon>(2 * n);
- Vector<Point> allPoints = new Vector<Point>(2 * n);
- for (int i = 0; i < withoutLeftist.length; i++) {
- cur = withoutLeftist[i].regularizeRightist(allPoints, next, prev,
- edges, currentx);
- for (int j = 0; j < cur.length; j++) {
- withoutBreaks.add(cur[j]);
- }
- }
- Polygon[] result = new Polygon[withoutBreaks.size()];
- for (int i = 0; i < withoutBreaks.size(); i++) {
- result[i] = withoutBreaks.get(i);
- }
- for (int i = 0; i < allPoints.size(); i++) {
- Point tmp = allPoints.get(i);
- tmp.x = vertexes[tmp.number].x;
- tmp.y = vertexes[tmp.number].y;
- }
- return result;
- }
- private Polygon[] triangulateMonotone() {
- if (n == 3)
- return new Polygon[] { this };
- HashMap<Point, Point> next = new HashMap<Point, Point>();
- HashMap<Point, Point> prev = new HashMap<Point, Point>();
- for (int i = 0; i < n; i++) {
- if (i == 0)
- prev.put(vertexes[i], vertexes[n - 1]);
- else
- prev.put(vertexes[i], vertexes[i - 1]);
- next.put(vertexes[i], vertexes[(i + 1) % n]);
- }
- Vector<Polygon> result = new Vector<Polygon>(n);
- Point min = new Point(Double.POSITIVE_INFINITY, 0);
- Point max = new Point(Double.NEGATIVE_INFINITY, 0);
- for (int i = 0; i < n; i++) {
- if (vertexes[i].x < min.x)
- min = vertexes[i];
- if (vertexes[i].x > max.x)
- max = vertexes[i];
- }
- Point up = min;
- Point down = min;
- Point nextup;
- Point nextdown;
- Point previous;
- Point tmp;
- while (down == min || up != next.get(down)) {
- nextup = prev.get(up);
- nextdown = next.get(down);
- if (up == down && up == min) {
- if (nextdown.x < nextup.x)
- down = nextdown;
- else
- up = nextup;
- continue;
- }
- if (down == next.get(up)) {
- if (nextup.x < nextdown.x) {
- if (down == min) {
- if (new geometry.Vector(nextup, up)
- .vectorMultiplication(new geometry.Vector(up,
- down)) > 0) {
- result.add(new Polygon(3, new Point[] { up, down,
- nextup }));
- up = nextup;
- } else {
- result.add(new Polygon(3, new Point[] { up, down,
- nextdown }));
- down = nextdown;
- }
- } else {
- result.add(new Polygon(3, new Point[] { up, down,
- nextup }));
- up = nextup;
- }
- } else {
- if (up == min) {
- if (new geometry.Vector(up, down)
- .vectorMultiplication(new geometry.Vector(down,
- nextdown)) > 0) {
- result.add(new Polygon(3, new Point[] { up, down,
- nextdown }));
- down = nextdown;
- } else {
- result.add(new Polygon(3, new Point[] { nextup, up,
- down }));
- up = nextup;
- }
- } else {
- result.add(new Polygon(3, new Point[] { up, down,
- nextdown }));
- down = nextdown;
- }
- }
- continue;
- }
- if (nextup.x < nextdown.x) {
- previous = next.get(up);
- tmp = new Segment(previous, up).intersect(new Segment(nextup,
- down))[0];
- if (tmp == null) {
- result
- .add(new Polygon(3,
- new Point[] { down, nextup, up }));
- up = nextup;
- } else {
- result.add(new Polygon(3,
- new Point[] { down, nextdown, up }));
- down = nextdown;
- }
- } else {
- previous = prev.get(down);
- tmp = new Segment(previous, down).intersect(new Segment(
- nextdown, up))[0];
- if (tmp == null) {
- result.add(new Polygon(3,
- new Point[] { down, nextdown, up }));
- down = nextdown;
- } else {
- result
- .add(new Polygon(3,
- new Point[] { down, nextup, up }));
- up = nextup;
- }
- }
- }
- Polygon[] ans = new Polygon[result.size()];
- int j = 0;
- for (Iterator<Polygon> i = result.iterator(); i.hasNext();) {
- ans[j++] = i.next();
- }
- return ans;
- }
- public Polygon[] doTriangulation() {
- Polygon[] monotones = doRegularization();
- Vector<Polygon> result = new Vector<Polygon>();
- Polygon[] current;
- for (int i = 0; i < monotones.length; i++) {
- current = monotones[i].triangulateMonotone();
- for (int j = 0; j < current.length; j++) {
- result.add(current[j]);
- }
- }
- Polygon[] triangles = new Polygon[result.size()];
- int j = 0;
- for (Iterator<Polygon> i = result.iterator(); i.hasNext();) {
- triangles[j++] = i.next();
- }
- return triangles;
- }
Add Comment
Please, Sign In to add comment