1 package org.newdawn.slick.geom;
2
3 import javax.annotation.Nonnull;
4 import java.io.Serializable;
5
6 /**
7 * The description of any 2D shape that can be transformed. The points provided approximate the intent
8 * of the shape.
9 *
10 * @author Mark
11 */
12 public abstract class Shape implements Serializable {
13 /**
14 *
15 */
16 private static final long serialVersionUID = 1L;
17 /** The points representing this polygon. */
18 float[] points;
19 /** Center point of the polygon. */
20 float[] center;
21 /** The left most point of this shape. */
22 float x;
23 /** The top most point of this shape. */
24 float y;
25 /** The right most point of this shape */
26 float maxX;
27 /** The bottom most point of this shape */
28 float maxY;
29 /** The left most point of this shape. */
30 float minX;
31 /** The top most point of this shape. */
32 float minY;
33 /** Radius of a circle that can completely enclose this shape. */
34 float boundingCircleRadius;
35 /** Flag to tell whether points need to be generated */
36 boolean pointsDirty;
37 /** The triangles that define the shape */
38 private transient Triangulator tris;
39 /** True if the triangles need updating */
40 private boolean trianglesDirty;
41
42 /**
43 * Shape constructor.
44 *
45 */
46 Shape() {
47 pointsDirty = true;
48 }
49
50 /**
51 * Set the location of this shape
52 *
53 * @param x The x coordinate of the new location of the shape
54 * @param y The y coordinate of the new location of the shape
55 */
56 public void setLocation(float x, float y) {
57 setX(x);
58 setY(y);
59 }
60
61 /**
62 * Apply a transformation and return a new shape. This will not alter the current shape but will
63 * return the transformed shape.
64 *
65 * @param transform The transform to be applied
66 * @return The transformed shape.
67 */
68 public abstract Shape transform(Transform transform);
69
70 /**
71 * Subclasses implement this to create the points of the shape.
72 *
73 */
74 protected abstract void createPoints();
75
76 /**
77 * Get the x location of the left side of this shape.
78 *
79 * @return The x location of the left side of this shape.
80 */
81 public float getX() {
82 return x;
83 }
84
85 /**
86 * Set the x position of the left side this shape.
87 *
88 * @param x The new x position of the left side this shape.
89 */
90 void setX(float x) {
91 if (x != this.x) {
92 float dx = x - this.x;
93 this.x = x;
94
95 if ((points == null) || (center == null)) {
96 checkPoints();
97 }
98 // update the points in the special case
99 for (int i=0;i<points.length/2;i++) {
100 points[i*2] += dx;
101 }
102 center[0] += dx;
103 x += dx;
104 maxX += dx;
105 minX += dx;
106 trianglesDirty = true;
107 }
108 }
109
110 /**
111 * Set the y position of the top of this shape.
112 *
113 * @param y The new y position of the top of this shape.
114 */
115 void setY(float y) {
116 if (y != this.y) {
117 float dy = y - this.y;
118 this.y = y;
119
120 if ((points == null) || (center == null)) {
121 checkPoints();
122 }
123 // update the points in the special case
124 for (int i=0;i<points.length/2;i++) {
125 points[(i*2)+1] += dy;
126 }
127 center[1] += dy;
128 y += dy;
129 maxY += dy;
130 minY += dy;
131 trianglesDirty = true;
132 }
133 }
134
135 /**
136 * Get the y position of the top of this shape.
137 *
138 * @return The y position of the top of this shape.
139 */
140 public float getY() {
141 return y;
142 }
143
144 /**
145 * Set the location of this shape
146 *
147 * @param loc The new location of the shape
148 */
149 public void setLocation(@Nonnull Vector2f loc) {
150 setX(loc.x);
151 setY(loc.y);
152 }
153
154 /**
155 * Get the x center of this shape.
156 *
157 * @return The x center of this shape.
158 */
159 float getCenterX() {
160 checkPoints();
161
162 return center[0];
163 }
164
165 /**
166 * Set the x center of this shape.
167 *
168 * @param centerX The center point to set.
169 */
170 public void setCenterX(float centerX) {
171 if ((points == null) || (center == null)) {
172 checkPoints();
173 }
174
175 float xDiff = centerX - getCenterX();
176 setX(x + xDiff);
177 }
178
179 /**
180 * Get the y center of this shape.
181 *
182 * @return The y center of this shape.
183 */
184 float getCenterY() {
185 checkPoints();
186
187 return center[1];
188 }
189
190 /**
191 * Set the y center of this shape.
192 *
193 * @param centerY The center point to set.
194 */
195 public void setCenterY(float centerY) {
196 if ((points == null) || (center == null)) {
197 checkPoints();
198 }
199
200 float yDiff = centerY - getCenterY();
201 setY(y + yDiff);
202 }
203
204 /**
205 * Get the right most point of this shape.
206 *
207 * @return The right most point of this shape.
208 */
209 public float getMaxX() {
210 checkPoints();
211 return maxX;
212 }
213 /**
214 * Get the bottom most point of this shape.
215 *
216 * @return The bottom most point of this shape.
217 */
218 public float getMaxY() {
219 checkPoints();
220 return maxY;
221 }
222
223 /**
224 * Get the left most point of this shape.
225 *
226 * @return The left most point of this shape.
227 */
228 public float getMinX() {
229 checkPoints();
230 return minX;
231 }
232
233 /**
234 * Get the top most point of this shape.
235 *
236 * @return The top most point of this shape.
237 */
238 public float getMinY() {
239 checkPoints();
240 return minY;
241 }
242
243 /**
244 * Get the radius of a circle that can completely enclose this shape.
245 *
246 * @return The radius of the circle.
247 */
248 public float getBoundingCircleRadius() {
249 checkPoints();
250 return boundingCircleRadius;
251 }
252
253 /**
254 * Get the point closet to the center of all the points in this Shape
255 *
256 * @return The x,y coordinates of the center.
257 */
258 public float[] getCenter() {
259 checkPoints();
260 return center;
261 }
262
263 /**
264 * Get the points that outline this shape. Use CW winding rule
265 *
266 * @return an array of x,y points
267 */
268 public float[] getPoints() {
269 checkPoints();
270 return points;
271 }
272
273 /**
274 * Get the number of points in this polygon
275 *
276 * @return The number of points in this polygon
277 */
278 public int getPointCount() {
279 checkPoints();
280 return points.length / 2;
281 }
282
283 /**
284 * Get a single point in this polygon
285 *
286 * @param index The index of the point to retrieve
287 * @return The point's coordinates
288 */
289 @Nonnull
290 public float[] getPoint(int index) {
291 checkPoints();
292
293 float result[] = new float[2];
294
295 result[0] = points[index * 2];
296 result[1] = points[index * 2 + 1];
297
298 return result;
299 }
300
301 /**
302 * Get the combine normal of a given point
303 *
304 * @param index The index of the point whose normal should be retrieved
305 * @return The combined normal of a given point
306 */
307 @Nonnull
308 public float[] getNormal(int index) {
309 float[] current = getPoint(index);
310 float[] prev = getPoint(index - 1 < 0 ? getPointCount() - 1 : index - 1);
311 float[] next = getPoint(index + 1 >= getPointCount() ? 0 : index + 1);
312
313 float[] t1 = getNormal(prev, current);
314 float[] t2 = getNormal(current, next);
315
316 if ((index == 0) && (!closed())) {
317 return t2;
318 }
319 if ((index == getPointCount()-1) && (!closed())) {
320 return t1;
321 }
322
323 float tx = (t1[0]+t2[0])/2;
324 float ty = (t1[1]+t2[1])/2;
325 float len = (float) Math.sqrt((tx*tx)+(ty*ty));
326 return new float[] {tx/len,ty/len};
327 }
328
329 /**
330 * Check if the shape passed is entirely contained within
331 * this shape.
332 *
333 * @param other The other shape to test against this one
334 * @return True if the other shape supplied is entirely contained
335 * within this one.
336 */
337 public boolean contains(@Nonnull Shape other) {
338 if (other.intersects(this)) {
339 return false;
340 }
341
342 for (int i=0;i<other.getPointCount();i++) {
343 float[] pt = other.getPoint(i);
344 if (!contains(pt[0], pt[1])) {
345 return false;
346 }
347 }
348
349 return true;
350 }
351 /**
352 * Get the normal of the line between two points
353 *
354 * @param start The start point
355 * @param end The end point
356 * @return The normal of the line between the two points
357 */
358 @Nonnull
359 private float[] getNormal(float[] start, float[] end) {
360 float dx = start[0] - end[0];
361 float dy = start[1] - end[1];
362 float len = (float) Math.sqrt((dx*dx)+(dy*dy));
363 dx /= len;
364 dy /= len;
365 return new float[] {-dy,dx};
366 }
367
368 /**
369 * Check if the given point is part of the path that
370 * forms this shape
371 *
372 * @param x The x position of the point to check
373 * @param y The y position of the point to check
374 * @return True if the point is includes in the path of the polygon
375 */
376 public boolean includes(float x, float y) {
377 if (points.length == 0) {
378 return false;
379 }
380
381 checkPoints();
382
383 Line testLine = new Line(0,0,0,0);
384 Vector2f pt = new Vector2f(x,y);
385
386 for (int i=0;i<points.length;i+=2) {
387 int n = i+2;
388 if (n >= points.length) {
389 n = 0;
390 }
391 testLine.set(points[i], points[i+1], points[n], points[n+1]);
392
393 if (testLine.on(pt)) {
394 return true;
395 }
396 }
397
398 return false;
399 }
400
401 /**
402 * Get the index of a given point
403 *
404 * @param x The x coordinate of the point
405 * @param y The y coordinate of the point
406 * @return The index of the point or -1 if the point is not part of this shape path
407 */
408 public int indexOf(float x, float y) {
409 for (int i=0;i<points.length;i+=2) {
410 if ((points[i] == x) && (points[i+1] == y)) {
411 return i / 2;
412 }
413 }
414
415 return -1;
416 }
417
418 /**
419 * Check if this polygon contains the given point
420 *
421 * @param x The x position of the point to check
422 * @param y The y position of the point to check
423 * @return True if the point is contained in the polygon
424 */
425 public boolean contains(float x, float y) {
426 checkPoints();
427 if (points.length == 0) {
428 return false;
429 }
430
431 boolean result = false;
432 float xnew,ynew;
433 float xold,yold;
434 float x1,y1;
435 float x2,y2;
436 int npoints = points.length;
437
438 xold=points[npoints - 2];
439 yold=points[npoints - 1];
440 for (int i=0;i < npoints;i+=2) {
441 xnew = points[i];
442 ynew = points[i + 1];
443 if (xnew > xold) {
444 x1 = xold;
445 x2 = xnew;
446 y1 = yold;
447 y2 = ynew;
448 }
449 else {
450 x1 = xnew;
451 x2 = xold;
452 y1 = ynew;
453 y2 = yold;
454 }
455 if ((xnew < x) == (x <= xold) /* edge "open" at one end */
456 && ((double)y - (double)y1) * (x2 - x1)
457 < ((double)y2 - (double)y1) * (x - x1)) {
458 result = !result;
459 }
460 xold = xnew;
461 yold = ynew;
462 }
463
464 return result;
465 }
466
467 /**
468 * Check if this shape intersects with the shape provided.
469 *
470 * @param shape The shape to check if it intersects with this one.
471 * @return True if the shapes do intersect, false otherwise.
472 */
473 public boolean intersects(@Nonnull Shape shape) {
474 /*
475 * Intersection formula used:
476 * (x4 - x3)(y1 - y3) - (y4 - y3)(x1 - x3)
477 * UA = ---------------------------------------
478 * (y4 - y3)(x2 - x1) - (x4 - x3)(y2 - y1)
479 *
480 * (x2 - x1)(y1 - y3) - (y2 - y1)(x1 - x3)
481 * UB = ---------------------------------------
482 * (y4 - y3)(x2 - x1) - (x4 - x3)(y2 - y1)
483 *
484 * if UA and UB are both between 0 and 1 then the lines intersect.
485 *
486 * Source: http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
487 */
488 checkPoints();
489
490 boolean result = false;
491 float points[] = getPoints(); // (x3, y3) and (x4, y4)
492 float thatPoints[] = shape.getPoints(); // (x1, y1) and (x2, y2)
493 int length = points.length;
494 int thatLength = thatPoints.length;
495 double unknownA;
496 double unknownB;
497
498 if (!closed()) {
499 length -= 2;
500 }
501 if (!shape.closed()) {
502 thatLength -= 2;
503 }
504
505 // x1 = thatPoints[j]
506 // x2 = thatPoints[j + 2]
507 // y1 = thatPoints[j + 1]
508 // y2 = thatPoints[j + 3]
509 // x3 = points[i]
510 // x4 = points[i + 2]
511 // y3 = points[i + 1]
512 // y4 = points[i + 3]
513 for(int i=0;i<length;i+=2) {
514 int iNext = i+2;
515 if (iNext >= points.length) {
516 iNext = 0;
517 }
518
519 for(int j=0;j<thatLength;j+=2) {
520 int jNext = j+2;
521 if (jNext >= thatPoints.length) {
522 jNext = 0;
523 }
524
525 unknownA = (((points[iNext] - points[i]) * (double) (thatPoints[j + 1] - points[i + 1])) -
526 ((points[iNext+1] - points[i + 1]) * (thatPoints[j] - points[i]))) /
527 (((points[iNext+1] - points[i + 1]) * (thatPoints[jNext] - thatPoints[j])) -
528 ((points[iNext] - points[i]) * (thatPoints[jNext+1] - thatPoints[j + 1])));
529 unknownB = (((thatPoints[jNext] - thatPoints[j]) * (double) (thatPoints[j + 1] - points[i + 1])) -
530 ((thatPoints[jNext+1] - thatPoints[j + 1]) * (thatPoints[j] - points[i]))) /
531 (((points[iNext+1] - points[i + 1]) * (thatPoints[jNext] - thatPoints[j])) -
532 ((points[iNext] - points[i]) * (thatPoints[jNext+1] - thatPoints[j + 1])));
533
534 if(unknownA >= 0 && unknownA <= 1 && unknownB >= 0 && unknownB <= 1) {
535 result = true;
536 break;
537 }
538 }
539 if(result) {
540 break;
541 }
542 }
543
544 return result;
545 }
546
547 /**
548 * Check if a particular location is a vertex of this polygon
549 *
550 * @param x The x coordinate to check
551 * @param y The y coordinate to check
552 * @return True if the cordinates supplied are a vertex of this polygon
553 */
554 public boolean hasVertex(float x, float y) {
555 if (points.length == 0) {
556 return false;
557 }
558
559 checkPoints();
560
561 for (int i=0;i<points.length;i+=2) {
562 if ((points[i] == x) && (points[i+1] == y)) {
563 return true;
564 }
565 }
566
567 return false;
568 }
569
570 /**
571 * Get the center of this polygon.
572 *
573 */
574 void findCenter() {
575 center = new float[]{0, 0};
576 int length = points.length;
577 for(int i=0;i<length;i+=2) {
578 center[0] += points[i];
579 center[1] += points[i + 1];
580 }
581 center[0] /= (length / 2);
582 center[1] /= (length / 2);
583 }
584
585 /**
586 * Calculate the radius of a circle that can completely enclose this shape.
587 *
588 */
589 void calculateRadius() {
590 boundingCircleRadius = 0;
591
592 for(int i=0;i<points.length;i+=2) {
593 float temp = ((points[i] - center[0]) * (points[i] - center[0])) +
594 ((points[i + 1] - center[1]) * (points[i + 1] - center[1]));
595 boundingCircleRadius = (boundingCircleRadius > temp) ? boundingCircleRadius : temp;
596 }
597 boundingCircleRadius = (float)Math.sqrt(boundingCircleRadius);
598 }
599
600 /**
601 * Calculate the triangles that can fill this shape
602 */
603 void calculateTriangles() {
604 if ((!trianglesDirty) && (tris != null)) {
605 return;
606 }
607 if (points.length >= 6) {
608 tris = new NeatTriangulator();
609 for (int i=0;i<points.length;i+=2) {
610 tris.addPolyPoint(points[i], points[i+1]);
611 }
612 tris.triangulate();
613 }
614
615 trianglesDirty = false;
616 }
617
618 /**
619 * Increase triangulation
620 */
621 public void increaseTriangulation() {
622 checkPoints();
623 calculateTriangles();
624
625 tris = new OverTriangulator(tris);
626 }
627
628 /**
629 * The triangles that define the filled version of this shape
630 *
631 * @return The triangles that define the
632 */
633 public Triangulator getTriangles() {
634 checkPoints();
635 calculateTriangles();
636 return tris;
637 }
638
639 /**
640 * Check the dirty flag and create points as necessary.
641 */
642 final void checkPoints() {
643 if (pointsDirty) {
644 createPoints();
645 findCenter();
646 calculateRadius();
647
648 if (points.length > 0) {
649 maxX = points[0];
650 maxY = points[1];
651 minX = points[0];
652 minY = points[1];
653 for (int i=0;i<points.length/2;i++) {
654 maxX = Math.max(points[i*2],maxX);
655 maxY = Math.max(points[(i*2)+1],maxY);
656 minX = Math.min(points[i*2],minX);
657 minY = Math.min(points[(i*2)+1],minY);
658 }
659 }
660 pointsDirty = false;
661 trianglesDirty = true;
662 }
663 }
664
665 /**
666 * Cause all internal state to be generated and cached
667 */
668 public void preCache() {
669 checkPoints();
670 getTriangles();
671 }
672
673 /**
674 * True if this is a closed shape
675 *
676 * @return True if this is a closed shape
677 */
678 public boolean closed() {
679 return true;
680 }
681
682 /**
683 * Prune any required points in this shape
684 *
685 * @return The new shape with points pruned
686 */
687 @Nonnull
688 public Shape prune() {
689 Polygon result = new Polygon();
690
691 for (int i=0;i<getPointCount();i++) {
692 int next = i+1 >= getPointCount() ? 0 : i+1;
693 int prev = i-1 < 0 ? getPointCount() - 1 : i-1;
694
695 float dx1 = getPoint(i)[0] - getPoint(prev)[0];
696 float dy1 = getPoint(i)[1] - getPoint(prev)[1];
697 float dx2 = getPoint(next)[0] - getPoint(i)[0];
698 float dy2 = getPoint(next)[1] - getPoint(i)[1];
699
700 float len1 = (float) Math.sqrt((dx1*dx1) + (dy1*dy1));
701 float len2 = (float) Math.sqrt((dx2*dx2) + (dy2*dy2));
702 dx1 /= len1;
703 dy1 /= len1;
704 dx2 /= len2;
705 dy2 /= len2;
706
707 if ((dx1 != dx2) || (dy1 != dy2)) {
708 result.addPoint(getPoint(i)[0],getPoint(i)[1]);
709 }
710 }
711
712 return result;
713 }
714
715 /**
716 * Subtract the given shape from this one. Note that this method only deals
717 * with edges, it will not create holes in polygons.
718 *
719 * @param other The other shape to subtract from this one
720 * @return The newly created set of shapes resulting from the operation
721 */
722 public Shape[] subtract(Shape other) {
723 return new GeomUtil().subtract(this, other);
724 }
725
726 /**
727 * Join this shape with another.
728 *
729 * @param other The other shape to join with this one
730 * @return The newly created set of shapes resulting from the operation
731 */
732 public Shape[] union(Shape other) {
733 return new GeomUtil().union(this, other);
734 }
735
736 /**
737 * Get the width of the shape
738 *
739 * @return The width of the shape
740 */
741 public float getWidth() {
742 checkPoints();
743 return maxX - minX;
744 }
745
746
747 /**
748 * Get the height of the shape
749 *
750 * @return The height of the shape
751 */
752 public float getHeight() {
753 checkPoints();
754 return maxY - minY;
755 }
756 }