1 package cz.cuni.amis.pogamut.defcon.utils;
2
3 import java.util.Iterator;
4 import java.util.LinkedList;
5 import java.util.List;
6
7 import cz.cuni.amis.pogamut.base3d.worldview.object.Location;
8 import cz.cuni.amis.utils.Tuple2;
9
10
11
12
13
14
15
16 public class PolygonUtils {
17
18
19
20
21
22
23
24
25 public static LinkedList<Location> resizePoly(List<Location> poly,
26 double offset) {
27
28 if (poly.size() < 3)
29 return null;
30
31 LinkedList<Location> resized = new LinkedList<Location>();
32
33 Iterator<Location> iterator = poly.iterator();
34
35 Location old = iterator.next();
36 Location current;
37
38 Location shifted_old1;
39 Location shifted_current1;
40 Location shifted_old2;
41 Location shifted_current2;
42 Location tmp;
43 double length = 0d;
44 double param2;
45 Location dir1, dir2, diff;
46
47 current = iterator.next();
48
49 length = old.getDistance2D(current);
50 tmp = current.sub(old);
51 tmp = new Location(tmp.getX() + tmp.getY(), tmp.getY() - tmp.getX()).scale(offset/length);
52
53 shifted_old1 = new Location(old.getX() + tmp.getY(), old.getX() - tmp.getX());
54 shifted_current1 = new Location(current.getX() + tmp.getY(), current.getX() - tmp.getX());
55
56 while (iterator.hasNext()) {
57 current = iterator.next();
58
59 length = old.getDistance2D(current);
60 tmp = current.sub(old);
61 dir2 = tmp.invert();
62 tmp = new Location(tmp.getX() + tmp.getY(), tmp.getY() - tmp.getX()).scale(offset/length);
63
64 shifted_old2 = new Location(old.getX() + tmp.getY(), old.getX() - tmp.getX());
65 shifted_current2 = new Location(current.getX() + tmp.getY(), current.getX() - tmp.getX());
66
67
68
69 diff = new Location(shifted_old1.getX() - shifted_current2.getX(),
70 shifted_old1.getY() - shifted_current2.getY());
71
72 dir1 = shifted_current1.sub(shifted_old1);
73
74
75 Tuple2<Double, Location[]> result = partiallySolve2DGauss(dir1, dir2, diff);
76 param2 = result.getFirst();
77 dir1 = result.getSecond()[0];
78 dir2 = result.getSecond()[1];
79 diff = result.getSecond()[2];
80
81
82
83 resized.add(dir2.scale(param2));
84
85 shifted_old1 = shifted_old2;
86 shifted_current1 = shifted_current2;
87 }
88
89 System.gc();
90 return resized;
91 }
92
93 private static Tuple2<Double, Location[]> partiallySolve2DGauss(Location a1, Location a2, Location b) {
94
95 a2 = a2.setX(a2.x / a1.x);
96
97
98 b = b.setX(b.x / a1.x);
99
100
101 a1 = a1.setX(1);
102
103
104 a2.setY(a2.y / a1.y - a2.x);
105
106
107 b.setY(b.y / a1.y - b.x);
108
109
110 a1.setY(0);
111
112 double result = b.x / a2.y;
113
114
115 return new Tuple2<Double, Location[]>(result, new Location[]{a1,a2,b});
116 }
117
118 private class PolygonWithBarycenter {
119 LinkedList<Location> polygon = new LinkedList<Location>();
120 Location barycenter;
121 }
122
123 private class Candidates {
124 Location a, b, c;
125 }
126
127 public static LinkedList<Location> resizePoly2(LinkedList<Location> poly, double offset) {
128
129 if (poly == null)
130 return null;
131
132 if (poly.size() == 0)
133 return new LinkedList<Location>();
134
135 if (poly.size() < 3) {
136 LinkedList<Location> out = new LinkedList<Location>();
137
138 for (Location loc : poly) {
139 out.add(new Location(loc));
140 }
141
142 return out;
143 }
144
145
146 LinkedList<PolygonWithBarycenter> polygons = new LinkedList<PolygonWithBarycenter>();
147 LinkedList<LinkedList<Location>> convexity_breaking =
148 new LinkedList<LinkedList<Location>>();
149
150 Iterator<Location> iter = poly.iterator();
151 Location last = iter.next();
152 Location middle = iter.next();
153 Location current = null;
154 LinkedList<Location> breakers = null;
155 ReturnValueOfCheckDirection ret = null;
156
157 while (iter.hasNext()) {
158 current = iter.next();
159
160 ret =
161 checkDirection(last, middle, current, breakers, convexity_breaking);
162
163 breakers = ret.breakers;
164
165 last = middle;
166 middle = current;
167 }
168
169 iter = poly.iterator();
170 current = iter.next();
171
172
173 if (
174 (ret = checkDirection(last, middle, current, breakers, convexity_breaking)).ret) {
175 breakers = ret.breakers;
176 while (iter.hasNext()) {
177 current = iter.next();
178
179 if (!(ret = checkDirection(last, middle, current, breakers, convexity_breaking)).ret) {
180 breakers = ret.breakers;
181 break;
182 }
183 breakers = ret.breakers;
184 last = middle;
185 middle = current;
186 }
187 }
188
189 return null;
190 }
191
192 private static class ReturnValueOfCheckDirection {
193 LinkedList<Location> breakers;
194 boolean ret;
195
196 public ReturnValueOfCheckDirection(LinkedList<Location> breakers,
197 boolean ret) {
198 this.breakers = breakers;
199 this.ret = ret;
200 }
201 }
202
203 private static ReturnValueOfCheckDirection checkDirection(
204 Location last, Location middle, Location current,
205 LinkedList<Location> breakers,
206 LinkedList<LinkedList<Location>> convexity_breaking) {
207
208 Location diff_middle = middle.sub(last);
209 Location diff_last = current.sub(last);
210
211 Location ax = new Location(diff_middle.getY(), -diff_middle.getX());
212
213 if (diff_last.dot(ax) < 0) {
214 if (breakers == null) {
215 breakers = new LinkedList<Location>();
216 breakers.add(last);
217 }
218
219 breakers.add(middle);
220 return new ReturnValueOfCheckDirection(breakers, true);
221 } else {
222 if (breakers != null) {
223 breakers.add(middle);
224
225 convexity_breaking.add(breakers);
226 breakers = null;
227 }
228 return new ReturnValueOfCheckDirection(breakers, false);
229 }
230 }
231
232 private class Triangle {
233 Location a,b,c;
234
235 public Triangle(Location a, Location b, Location c) {
236 this.a = a;
237 this.b = b;
238 this.c = c;
239 }
240 }
241
242 private static double EPSILON = 0.001d;
243
244 public static LinkedList<Location> resizePoly3(LinkedList<Location> poly, double offset) {
245 LinkedList<Location> out = new LinkedList<Location>();
246 Location[] ret = resizePoly3((Location[])poly.toArray(), offset);
247 for (int i = 0; i < ret.length; ++i) {
248 out.add(ret[i]);
249 }
250
251 return out;
252 }
253
254 public static Location[] resizePoly3(Location[] poly, double offset) {
255
256 int size = poly.length;
257
258 if (size < 3) {
259 return deepCopy(poly);
260 }
261
262 int[] indices = triangulate(poly);
263
264 for (int i = 0; i < indices.length; ++i) {
265
266 }
267
268 Location[] out = new Location[size];
269
270 for (int i = 0; i < size; ++i) {
271 out[i] = poly[indices[i]];
272 }
273 return out;
274 }
275
276 private static int[] triangulate(Location[] vertices) {
277
278 int size = vertices.length;
279
280 int[] V = new int[size];
281 int[] indices = new int[size];
282 int current_index = 0;
283
284 if (0.0f < area(vertices))
285 {
286 for (int v = 0; v < size; v++)
287 V[v] = v;
288 }
289 else
290 {
291 for (int v = 0; v < size; v++)
292 V[v] = (size - 1) - v;
293 }
294 int nv = size;
295 int count = 2 * nv;
296 for (int m = 0, v = nv - 1; nv > 2;)
297 {
298 if (0 >= (count--))
299 return V;
300
301 int u = v;
302 if (nv <= u)
303 u = 0;
304 v = u + 1;
305 if (nv <= v)
306 v = 0;
307 int w = v + 1;
308 if (nv <= w)
309 w = 0;
310
311 if (snip(vertices, u, v, w, nv, V)) {
312 int a, b, c, s, t;
313 a = V[u];
314 b = V[v];
315 c = V[w];
316 indices[current_index++] = a;
317 indices[current_index++] = b;
318 indices[current_index++] = c;
319 m++;
320 for (s = v, t = v + 1; t < nv; s++, t++)
321 V[s] = V[t];
322 nv--;
323 count = 2 * nv;
324 }
325 }
326
327 return indices;
328 }
329
330
331 private static boolean checkDirection2(Location last, Location middle, Location current) {
332
333 Location diff_middle = middle.sub(last);
334 Location diff_last = current.sub(last);
335
336 Location ax = new Location(diff_middle.getY(), -diff_middle.getX());
337
338 return (diff_last.dot(ax) < 0);
339 }
340
341 private static float area(Location[] poly) {
342
343 if (poly.length < 3)
344 return 0f;
345
346 float A = 0.0f;
347
348 for (int i = poly.length - 1, j = 0; j < poly.length; i = j++)
349 A += poly[i].x * poly[j].y - poly[j].x * poly[i].y;
350
351 return (A * 0.5f);
352 }
353
354 private static Location[] deepCopy(Location[] toCopy) {
355 Location[] out = new Location[toCopy.length];
356
357 for (int i = 0; i < toCopy.length; ++i) {
358 out[i] = new Location(toCopy[i]);
359 }
360
361 return out;
362 }
363
364 private static boolean snip(Location[] vertices, int u, int v, int w, int n, int[] V)
365 {
366 int p;
367 Location A = vertices[V[u]];
368 Location B = vertices[V[v]];
369 Location C = vertices[V[w]];
370 if (EPSILON > (((B.x - A.x) * (C.y - A.y)) - ((B.y - A.y) * (C.x - A.x))) )
371 return false;
372 for (p = 0; p < n; p++)
373 {
374 if ((p == u) || (p == v) || (p == w))
375 continue;
376 Location P = vertices[V[p]];
377 if (insideTriangle(A, B, C, P))
378 return false;
379 }
380 return true;
381 }
382
383 private static boolean insideTriangle(Location A, Location B, Location C,
384 Location P)
385 {
386 double ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
387 double cCROSSap, bCROSScp, aCROSSbp;
388
389 ax = C.x - B.x; ay = C.y - B.y;
390 bx = A.x - C.x; by = A.y - C.y;
391 cx = B.x - A.x; cy = B.y - A.y;
392 apx = P.x - A.x; apy = P.y - A.y;
393 bpx = P.x - B.x; bpy = P.y - B.y;
394 cpx = P.x - C.x; cpy = P.y - C.y;
395
396 aCROSSbp = ax * bpy - ay * bpx;
397 cCROSSap = cx * apy - cy * apx;
398 bCROSScp = bx * cpy - by * cpx;
399
400 return ((aCROSSbp >= 0.0f) && (bCROSScp >= 0.0f) && (cCROSSap >= 0.0f));
401 }
402
403
404
405 }