1 /* =============================================================================
5 * =============================================================================
7 * Copyright (C) Stanford University, 2006. All Rights Reserved.
10 * =============================================================================
12 * For the license of bayes/sort.h and bayes/sort.c, please see the header
15 * ------------------------------------------------------------------------
17 * For the license of kmeans, please see kmeans/LICENSE.kmeans
19 * ------------------------------------------------------------------------
21 * For the license of ssca2, please see ssca2/COPYRIGHT
23 * ------------------------------------------------------------------------
25 * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the
26 * header of the files.
28 * ------------------------------------------------------------------------
30 * For the license of lib/rbtree.h and lib/rbtree.c, please see
31 * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree
33 * ------------------------------------------------------------------------
35 * Unless otherwise noted, the following license applies to STAMP files:
37 * Copyright (c) 2007, Stanford University
38 * All rights reserved.
40 * Redistribution and use in source and binary forms, with or without
41 * modification, are permitted provided that the following conditions are
44 * * Redistributions of source code must retain the above copyright
45 * notice, this list of conditions and the following disclaimer.
47 * * Redistributions in binary form must reproduce the above copyright
48 * notice, this list of conditions and the following disclaimer in
49 * the documentation and/or other materials provided with the
52 * * Neither the name of Stanford University nor the names of its
53 * contributors may be used to endorse or promote products derived
54 * from this software without specific prior written permission.
56 * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
57 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
58 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
59 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
60 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
61 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
62 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
63 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
64 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
65 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
66 * THE POSSIBILITY OF SUCH DAMAGE.
68 * =============================================================================
71 public class element {
72 coordinate coordinates[];
74 coordinate circumCenter;
79 coordinate midpoints[]; /* midpoint of each edge */
80 double radii[]; /* half of edge length */
81 edge encroachedEdgePtr; /* opposite obtuse angle */
83 List_t neighborListPtr;
89 /* =============================================================================
91 * -- put smallest coordinate in position 0
92 * =============================================================================
94 static void minimizeCoordinates (element elementPtr) {
95 coordinate[] coordinates = elementPtr.coordinates;
96 int numCoordinate = elementPtr.numCoordinate;
99 for (int i = 1; i < numCoordinate; i++) {
100 if (coordinate.coordinate_compare(coordinates[i], coordinates[minPosition]) < 0) {
105 while(minPosition != 0) {
106 coordinate tmp = coordinates[0];
107 for (int j = 0; j < (numCoordinate - 1); j++) {
108 coordinates[j] = coordinates[j+1];
110 coordinates[numCoordinate-1] = tmp;
116 /* =============================================================================
118 * -- Sets isSkinny to TRUE if the angle constraint is not met
119 * =============================================================================
121 void checkAngles (double angleConstraint) {
122 //double angleConstraint = global_angleConstraint;
125 yada.Assert(numCoordinate == 2 || numCoordinate == 3);
126 isReferenced = false;
128 encroachedEdgePtr = null;
130 if (numCoordinate == 3) {
132 for (i = 0; i < 3; i++) {
133 double angle = coordinate.coordinate_angle(coordinates[i],
134 coordinates[(i + 1) % 3],
135 coordinates[(i + 2) % 3]);
136 yada.Assert(angle > 0.0);
137 yada.Assert(angle < 180.0);
139 encroachedEdgePtr = edges[(i + 1) % 3];
141 if (angle < angleConstraint) {
144 if (angle < minAngle) {
148 yada.Assert(minAngle < 180.0);
153 /* =============================================================================
154 * calculateCircumCenter
156 * Given three points A(ax,ay), B(bx,by), C(cx,cy), circumcenter R(rx,ry):
159 * | by - ay (||b - a||)^2 |
161 * | cy - ay (||c - a||)^2 |
163 * rx = ax - -----------------------------
165 * | bx - ax by - ay |
167 * | cx - ax cy - ay |
171 * | bx - ax (||b - a||)^2 |
173 * | cx - ax (||c - a||)^2 |
175 * ry = ay + -----------------------------
177 * | bx - ax by - ay |
179 * | cx - ax cy - ay |
182 * =============================================================================
184 void calculateCircumCircle() {
185 coordinate circumCenterPtr = this.circumCenter;
187 yada.Assert(numCoordinate == 2 || numCoordinate == 3);
189 if (numCoordinate == 2) {
190 circumCenterPtr.x = (coordinates[0].x + coordinates[1].x) / 2.0;
191 circumCenterPtr.y = (coordinates[0].y + coordinates[1].y) / 2.0;
193 double ax = coordinates[0].x;
194 double ay = coordinates[0].y;
195 double bx = coordinates[1].x;
196 double by = coordinates[1].y;
197 double cx = coordinates[2].x;
198 double cy = coordinates[2].y;
199 double bxDelta = bx - ax;
200 double byDelta = by - ay;
201 double cxDelta = cx - ax;
202 double cyDelta = cy - ay;
203 double bDistance2 = (bxDelta * bxDelta) + (byDelta * byDelta);
204 double cDistance2 = (cxDelta * cxDelta) + (cyDelta * cyDelta);
205 double xNumerator = (byDelta * cDistance2) - (cyDelta * bDistance2);
206 double yNumerator = (bxDelta * cDistance2) - (cxDelta * bDistance2);
207 double denominator = 2 * ((bxDelta * cyDelta) - (cxDelta * byDelta));
208 double rx = ax - (xNumerator / denominator);
209 double ry = ay + (yNumerator / denominator);
210 yada.Assert(fabs(denominator) > DBL_MIN); /* make sure not colinear */
211 circumCenterPtr.x = rx;
212 circumCenterPtr.y = ry;
215 elementPtr.circumRadius = coordinate.coordinate_distance(circumCenterPtr,
220 /* =============================================================================
223 * Note: Makes pairPtr sorted; i.e., coordinate_compare(first, second) < 0
224 * =============================================================================
226 public void setEdge(int i) {
227 coordinate firstPtr = coordinates[i];
228 coordinate secondPtr = coordinates[(i + 1) % numCoordinate];
230 edge edgePtr = edges[i];
231 int cmp = coordinate.coordinate_compare(firstPtr, secondPtr);
232 yada.Assert(cmp != 0);
234 edgePtr.firstPtr = firstPtr;
235 edgePtr.secondPtr = secondPtr;
237 edgePtr.firstPtr = secondPtr;
238 edgePtr.secondPtr = firstPtr;
241 coordinate midpointPtr = elementPtr.midpoints[i];
242 midpointPtr.x = (firstPtr.x + secondPtr.x) / 2.0;
243 midpointPtr.y = (firstPtr.y + secondPtr.y) / 2.0;
245 elementPtr.radii[i] = coordinate.coordinate_distance(firstPtr, midpointPtr);
249 /* =============================================================================
251 * =============================================================================
253 void initEdges(coordinate coordinates, int numCoordinate) {
254 numEdge = ((numCoordinate * (numCoordinate - 1)) / 2);
256 for (int e = 0; e < numEdge; e++) {
262 /* =============================================================================
264 * =============================================================================
266 int element_compare (element aElementPtr, element bElementPtr) {
267 int aNumCoordinate = aElementPtr.numCoordinate;
268 int bNumCoordinate = bElementPtr.numCoordinate;
269 coordinate aCoordinates[] = aElementPtr.coordinates;
270 coordinate bCoordinates[] = bElementPtr.coordinates;
272 if (aNumCoordinate < bNumCoordinate) {
274 } else if (aNumCoordinate > bNumCoordinate) {
278 for (int i = 0; i < aNumCoordinate; i++) {
279 int compareCoordinate =
280 coordinate.coordinate_compare(aCoordinates[i], bCoordinates[i]);
281 if (compareCoordinate != 0) {
282 return compareCoordinate;
290 /* =============================================================================
291 * element_listCompare
294 * =============================================================================
296 int element_listCompare (Object aPtr, Object bPtr) {
297 element aElementPtr = (element)aPtr;
298 element bElementPtr = (element)bPtr;
300 return element_compare(aElementPtr, bElementPtr);
304 /* =============================================================================
308 * =============================================================================
310 int element_mapCompare(Object aPtr, Object bPtr) {
311 element aElementPtr = (element)(aPtr.firstPtr);
312 element bElementPtr = (element)(bPtr.firstPtr);
314 return element_compare(aElementPtr, bElementPtr);
318 /* =============================================================================
321 * Contains a copy of input arg 'coordinates'
322 * =============================================================================
324 public element(coordinate[] coordinates, int numCoordinate) {
325 this.coordinates=new coordinate[3];
326 this.midpoints=new coordinate[3]; /* midpoint of each edge */
327 this.radii=new double[3]; /* half of edge length */
329 this.edges=new edge[3];
330 for (int i = 0; i < numCoordinate; i++) {
331 this.coordinates[i] = coordinates[i];
333 this.numCoordinate = numCoordinate;
334 minimizeCoordinates();
336 calculateCircumCircle();
337 initEdges(coordinates, numCoordinate);
338 neighborListPtr = new List_t(0);//TMLIST_ALLOC(element_listCompare);
340 isReferenced = false;
344 /* =============================================================================
346 * =============================================================================
348 int element_getNumEdge() {
353 /* =============================================================================
356 * Returned edgePtr is sorted; i.e., coordinate_compare(first, second) < 0
357 * =============================================================================
359 edge element_getEdge(int i) {
360 if (i < 0 || i > numEdge)
366 /* =============================================================================
367 * element_compareEdge
368 * =============================================================================
370 static int compareEdge(edge aEdgePtr, edge bEdgePtr) {
371 int diffFirst = coordinate.coordinate_compare((coordinate)aEdgePtr.firstPtr,
372 (coordinate)bEdgePtr.firstPtr);
374 return ((diffFirst != 0) ?
376 (coordinate.coordinate_compare((coordinate)aEdgePtr.secondPtr,
377 (coordinate)bEdgePtr.secondPtr)));
381 /* ============================================================================
382 * element_listCompareEdge
385 * ============================================================================
387 int element_listCompareEdge (Object aPtr, Object bPtr) {
388 edge aEdgePtr = (edge)(aPtr);
389 edge bEdgePtr = (edge)(bPtr);
391 return compareEdge(aEdgePtr, bEdgePtr);
395 /* =============================================================================
396 * element_mapCompareEdge
399 * =============================================================================
401 int element_mapCompareEdge (Object aPtr, Object bPtr) {
402 edge aEdgePtr = (edge)(aPtr.firstPtr);
403 edge bEdgePtr = (edge)(bPtr.firstPtr);
405 return compareEdge(aEdgePtr, bEdgePtr);
409 /* =============================================================================
410 * element_heapCompare
412 * For use in heap_t. Consider using minAngle instead of "do not care".
413 * =============================================================================
415 int element_heapCompare (Object aPtr, Object bPtr) {
416 element aElementPtr = (element)aPtr;
417 element bElementPtr = (element)bPtr;
419 if (aElementPtr.encroachedEdgePtr!=null) {
420 if (bElementPtr.encroachedEdgePtr!=null) {
421 return 0; /* do not care */
427 if (bElementPtr.encroachedEdgePtr!=null) {
431 return 0; /* do not care */
435 /* =============================================================================
436 * element_isInCircumCircle
437 * =============================================================================
439 boolean element_isInCircumCircle(coordinate coordinatePtr) {
440 double distance = coordinate.coordinate_distance(coordinatePtr, circumCenter);
441 return distance <= circumRadius;
445 /* =============================================================================
447 * =============================================================================
449 boolean isEncroached() {
450 return encroachedEdgePtr!=null;
454 /* =============================================================================
455 * element_setEncroached
456 * =============================================================================
458 void element_clearEncroached() {
459 encroachedEdgePtr = null;
463 /* =============================================================================
464 * element_getEncroachedPtr
465 * =============================================================================
467 edge element_getEncroachedPtr() {
468 return encroachedEdgePtr;
472 /* =============================================================================
474 * =============================================================================
476 boolean element_isSkinny() {
481 /* =============================================================================
483 * -- Does it need to be refined?
484 * =============================================================================
486 boolean element_isBad() {
487 return (isEncroached() || element_isSkinny());
491 /* =============================================================================
492 * TMelement_isReferenced
493 * -- Held by another data structure?
494 * =============================================================================
496 boolean element_isReferenced () {
501 /* =============================================================================
502 * TMelement_setIsReferenced
503 * =============================================================================
505 void element_setIsReferenced(boolean status) {
506 isReferenced= status;
510 /* =============================================================================
512 * -- Can we deallocate?
513 * =============================================================================
516 /* =============================================================================
517 * TMelement_isGarbage
518 * -- Can we deallocate?
519 * =============================================================================
521 boolean element_isGarbage() {
527 /* =============================================================================
528 * TMelement_setIsGarbage
529 * =============================================================================
531 void element_setIsGarbage(boolean status) {
536 /* =============================================================================
537 * TMelement_addNeighbor
538 * =============================================================================
540 void element_addNeighbor(element neighborPtr) {
541 neighborListPtr.insert(neighborPtr);
545 /* =============================================================================
546 * element_getNeighborListPtr
547 * =============================================================================
549 List_t element_getNeighborListPtr () {
550 return neighborListPtr;
554 /* =============================================================================
555 * element_getCommonEdge
557 * Returns pointer to aElementPtr's shared edge
558 * =============================================================================
560 edge element_getCommonEdge (element aElementPtr, element bElementPtr) {
561 edge aEdges[] = aElementPtr.edges;
562 edge bEdges[] = bElementPtr.edges;
563 int aNumEdge = aElementPtr.numEdge;
564 int bNumEdge = bElementPtr.numEdge;
566 for (int a = 0; a < aNumEdge; a++) {
567 edge aEdgePtr = aEdges[a];
568 for (int b = 0; b < bNumEdge; b++) {
569 edge bEdgePtr = bEdges[b];
570 if (compareEdge(aEdgePtr, bEdgePtr) == 0) {
580 /* =============================================================================
581 * element_getNewPoint
582 * -- Either the element is encroached or is skinny, so get the new point to add
583 * =============================================================================
585 coordinate element_getNewPoint() {
586 if (encroachedEdgePtr!=null) {
587 for (int e = 0; e < numEdge; e++) {
588 if (compareEdge(encroachedEdgePtr, edges[e]) == 0) {
598 /* =============================================================================
599 * element_checkAngles
601 * Return FALSE if minimum angle constraint not met
602 * =============================================================================
604 boolean element_checkAngles(double angleConstraint) {
605 // double angleConstraint = global_angleConstraint;
606 if (numCoordinate == 3) {
607 for (int i = 0; i < 3; i++) {
608 double angle = coordinate.coordinate_angle(coordinates[i],
609 coordinates[(i + 1) % 3],
610 coordinates[(i + 2) % 3]);
611 if (angle < angleConstraint) {
620 /* =============================================================================
622 * =============================================================================
624 void element_print() {
625 for (int c = 0; c < numCoordinate; c++) {
626 coordinates[c].coordinate_print();
627 System.out.println(" ");
632 /* =============================================================================
634 * =============================================================================
636 void element_printEdge (edge edgePtr) {
637 ((coordinate)edgePtr.firstPtr).coordinate_print();
638 System.out.println(" -> ");
639 ((coordinate)edgePtr.secondPtr).coordinate_print();
643 /* =============================================================================
644 * element_printAngles
645 * =============================================================================
647 void element_printAngles() {
648 if (numCoordinate == 3) {
649 for (int i = 0; i < 3; i++) {
650 double angle = coordinate.coordinate_angle(coordinates[i],
651 coordinates[(i + 1) % 3],
652 coordinates[(i + 2) % 3]);
653 System.out.println(angle);