001: /*
002: * <copyright>
003: *
004: * Copyright 1997-2004 BBNT Solutions, LLC
005: * under sponsorship of the Defense Advanced Research Projects
006: * Agency (DARPA).
007: *
008: * You can redistribute this software and/or modify it under the
009: * terms of the Cougaar Open Source License as published on the
010: * Cougaar Open Source Website (www.cougaar.org).
011: *
012: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
013: * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
014: * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
015: * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
016: * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
017: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
018: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
019: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
020: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
021: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
022: * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
023: *
024: * </copyright>
025: */
026: // **********************************************************************
027: //
028: //
029: //
030: //
031: //
032: //
033: //
034: // **********************************************************************
035: package org.cougaar.mlm.debug.ui.draw;
036:
037: //import netscape.application.Point;
038:
039: /** class DrawUtil
040: *
041: * Drawing utility functions
042: *
043: **/
044: public class DrawUtil {
045:
046: /** Bresenham's line algorithm. Returns an array of points to draw. */
047: public final static Point[] bresenham_line(Point pt1, Point pt2) {
048: return bresenham_line(pt1.x, pt1.y, pt2.x, pt2.y);
049: }
050:
051: /** Bresenham's line algorithm. */
052: public final static Point[] bresenham_line(int x1, int y1, int x2,
053: int y2) {
054: // This is actually NOT bresenhams algorithm. It is faster!
055: // -rmf
056:
057: // System.out.println("DrawUtil.bresenham_line(" +
058: // x1 + "," + y1 + ")->(" + x2 + "," + y2 + ")");
059: int i;
060: int d, x, y, ax, ay, sx, sy, dx, dy, t;
061:
062: dx = x2 - x1;
063: ax = Math.abs(dx) << 1;
064: sx = MoreMath.sign(dx);
065: dy = y2 - y1;
066: ay = Math.abs(dy) << 1;
067: sy = MoreMath.sign(dy);
068:
069: t = Math.max(Math.abs(dx), Math.abs(dy)) + 1;
070: Point[] ret_val = new Point[t];
071:
072: x = x1;
073: y = y1;
074: if (ax > ay) { /* x dominant */
075: d = ay - (ax >> 1);
076: for (i = 0;;) {
077: ret_val[i++] = new Point(x, y);
078: //ret_val[i].x = x; ret_val[i++].y = y;
079: if (x == x2)
080: return ret_val;
081: if (d >= 0) {
082: y += sy;
083: d -= ax;
084: }
085: x += sx;
086: d += ay;
087: }
088: } else { /* y dominant */
089: d = ax - (ay >> 1);
090: for (i = 0;;) {
091: ret_val[i++] = new Point(x, y);
092: //ret_val[i].x = x; ret_val[i++].y = y;
093: if (y == y2)
094: return ret_val;
095: if (d >= 0) {
096: x += sx;
097: d -= ay;
098: }
099: y += sy;
100: d += ax;
101: }
102: }
103: }
104:
105: //////////////////////////////////////////////////////////////////////////
106:
107: /** inside_polygon() - tests if a point is inside a polygon */
108: public final static boolean inside_polygon(int[] xpts, int[] ypts,
109: int ptx, int pty) {
110:
111: int j, inside_flag = 0;
112: int numverts = xpts.length;
113: if (numverts <= 2)
114: return false;
115: Point vtx0 = new Point(0, 0), vtx1 = new Point(0, 0);
116: double dv0; // prevents OVERFLOW!!
117: int crossings = 0;
118: boolean xflag0 = false, yflag0 = false, yflag1 = false;
119:
120: // vtx0 = (Point)pgon.elementAt(numverts-1);/*&pgon[numverts-1];*/
121: vtx0.x = xpts[numverts - 1];
122: vtx0.y = ypts[numverts - 1];
123: // get test bit for above/below Y axis
124: yflag0 = ((dv0 = vtx0.y - pty) >= 0);
125:
126: for (j = 0; j < numverts; j++) {
127: if ((j & 0x1) != 0) { //HACK - slightly changed
128: // vtx0 = (Point)pgon.elementAt(j);/*&pgon[j];*/
129: vtx0.x = xpts[j];
130: vtx0.y = ypts[j];
131: yflag0 = ((dv0 = vtx0.y - pty) >= 0);
132: } else {
133: // vtx1 = (Point)pgon.elementAt(j);/*&pgon[j];*/
134: vtx1.x = xpts[j];
135: vtx1.y = ypts[j];
136: yflag1 = (vtx1.y >= pty);
137: }
138:
139: /* check if points not both above/below X axis - can't hit ray */
140: if (yflag0 != yflag1) {
141: /* check if points on same side of Y axis */
142: if ((xflag0 = (vtx0.x >= ptx)) == (vtx1.x >= ptx)) {
143: if (xflag0)
144: crossings++;
145: } else {
146: crossings += ((vtx0.x - dv0 * (vtx1.x - vtx0.x)
147: / (vtx1.y - vtx0.y)) >= ptx) ? 1 : 0;
148: }
149: }
150: inside_flag = crossings & 0x01;
151: }
152: return (inside_flag != 0);
153: }
154:
155: //////////////////////////////////////////////////////////////////////////
156:
157: /** closestPolyDistance() - returns the distance from Point (x,y)
158: to the closest line segment in the Poly (int[] xpts, ypts) */
159: public final static float closestPolyDistance(int[] xpts,
160: int[] ypts, int ptx, int pty, boolean connected) {
161: int npts = (connected) ? xpts.length : xpts.length - 1;
162: if (npts == 1)
163: return distance(xpts[0], ypts[0], ptx, pty);
164: if (npts == 0)
165: return Float.POSITIVE_INFINITY;
166:
167: Point from = new Point(0, 0), to = new Point(0, 0);
168: float temp, distance = Float.POSITIVE_INFINITY;
169: int i, j;
170:
171: from.x = xpts[0];
172: from.y = ypts[0];
173: for (i = 0, j = 1; i < npts; i++, j = (i + 1) % xpts.length) {
174: to.x = xpts[j];
175: to.y = ypts[j];
176: temp = distance_to_line(from.x, from.y, to.x, to.y, ptx,
177: pty);
178: // System.out.println(
179: // "\tdistance from line (" + from.x + "," + from.y + "<->" +
180: // to.x + "," + to.y + ") to point (" + ptx + "," + pty + ")=" +
181: // temp);
182: if (temp < distance)
183: distance = temp;
184: from.x = to.x;
185: from.y = to.y;
186: }
187: return distance;
188: }
189:
190: /** distance() - 2D distance formula */
191: public final static float distance(int x1, int y1, int x2, int y2) {
192: int xdiff = x2 - x1;
193: int ydiff = y2 - y1;
194: return (float) Math
195: .sqrt((float) (xdiff * xdiff + ydiff * ydiff));
196: }
197:
198: /** distance_to_endpoint() - distance to closest endpoint */
199: public final static float distance_to_endpoint(int x1, int y1,
200: int x2, int y2, int x, int y) {
201: return (float) Math.min(distance(x1, y1, x, y), distance(x2,
202: y2, x, y));
203: }
204:
205: /****************************************************************
206: *
207: * distance_to_line(): Compute the distance from point (x,y) to a
208: * line by computing the perpendicular line from (x,y) to the
209: * line and finding the intersection of this perpendicular and
210: * the line. If the intersection is on the line segment, then
211: * the distance is the distance from the mouse to the
212: * intersection, otherwise it is the distance from (x,y) to the
213: * nearest endpoint.
214: *
215: * Equations used to compute distance:
216: * m = (y2-y1)/(x2-x1) slope of the line
217: * y = mx + b equation of the line
218: * c = -1/m slope of line perpendicular to it
219: * y = cx + d equation of perpendicular line
220: * xi = (d-b)/(m-c) x-intersection, from equating the two line equations
221: * y1 = c* xi + d y-intersection
222: * distance = sqrt(sqr(x-xi) + sqr(y-yi)) distance between two points
223: *
224: ****************************************************************/
225: public final static float distance_to_line(int x1, int y1, int x2,
226: int y2, int x, int y) {
227: float m; /* slope of the line */
228: float c; /* slope of a line perpendicular to the line */
229: float b; /* y intercept of line */
230: float d; /* y intercept of a line perpendicular to the line */
231: int xi, yi; /* intersection of line and perpendicular */
232:
233: if (x2 == x1) /* vertical line */
234: {
235: if (y1 <= y && y <= y2 || y2 <= y && y <= y1)
236: return (float) Math.abs(x - x1); // mouse is alongside line
237: return distance_to_endpoint(x1, y1, x2, y2, x, y);
238: }
239:
240: if (y2 == y1) /* horizontal line */
241: {
242: if (x1 <= x && x <= x2 || x2 <= x && x <= x1)
243: return (float) Math.abs(y - y1); // mouse is alongside line
244: return distance_to_endpoint(x1, y1, x2, y2, x, y);
245: }
246:
247: m = ((float) (y2 - y1)) / ((float) (x2 - x1)); /* slope of the line */
248: c = -1.0f / m; /* slope of perpendicular line */
249: d = (float) y - c * (float) x;/* perpendicular line through mouse */
250: b = (float) y1 - m * (float) x1; /* the line in the drawing */
251:
252: // NOTE: round error
253: xi = (int) MoreMath.qint((d - b) / (m - c));// x intersection
254: yi = (int) MoreMath.qint(c * (float) xi + d);// y intersection
255:
256: /*
257: * If intersection is on the line segment
258: * distance is distance from mouse to it.
259: */
260: if ((x1 <= xi && xi <= x2 || x2 <= xi && xi <= x1)
261: && (y1 <= yi && yi <= y2 || y2 <= yi && yi <= y1))
262: return distance(xi, yi, x, y);
263:
264: /* distance is distance from mouse to nearest endpt */
265: return distance_to_endpoint(x1, y1, x2, y2, x, y);
266: }
267:
268: //////////////////////////////////////////////////////////////////////////
269:
270: /* generateWideLine() - generates a line with width lw, returns an
271: OMVector of 4 x-y coords. */
272: public static OMVector generateWideLine(int lw, int x1, int y1,
273: int x2, int y2) {
274: OMVector ret_val = new OMVector(2);
275: int[] x = new int[4];
276: int[] y = new int[4];
277:
278: // calculate the offsets
279: // lw = lw -1;
280: int off1 = (int) lw / 2;
281: int off2 = (lw % 2 == 1) ? (int) lw / 2 + 1 : (int) lw / 2;
282:
283: // slope <= 1
284: if (Math.abs((float) (y2 - y1) / (float) (x2 - x1)) <= 1f) {
285: x[0] = x[3] = x1;
286: x[1] = x[2] = x2;
287:
288: y[0] = y1 + off1;
289: y[1] = y2 + off1;
290: y[2] = y2 - off2;
291: y[3] = y1 - off2;
292:
293: ret_val.add(x);
294: ret_val.add(y);
295: }
296:
297: // slope > 1
298: else {
299: x[0] = x1 + off1;
300: x[1] = x2 + off1;
301: x[2] = x2 - off2;
302: x[3] = x1 - off2;
303:
304: y[0] = y[3] = y1;
305: y[1] = y[2] = y2;
306:
307: ret_val.add(x);
308: ret_val.add(y);
309: }
310:
311: return ret_val;
312: }
313:
314: /** generateWidePoly() - generates a polygon or polyline with
315: positive width lw, returns OMVector of x-y array pairs of
316: coordinates of polygon segments. the parameter altx must
317: either be null, or a mirror image of xpts. */
318: public static OMVector generateWidePoly(int lw, int[] xpts,
319: int[] ypts, int[] altx, boolean connect) {
320: return generateWidePoly(lw, xpts.length, xpts, ypts, altx,
321: connect);
322: }
323:
324: public static OMVector generateWidePoly(int lw, int len,
325: int[] xpts, int[] ypts, int[] altx, boolean connect) {
326: OMVector ret_val = new OMVector(len * 4);
327: int off1 = 0, off2 = 0;
328: int[] x = null, y = null, a_x = null;
329:
330: int end = (connect) ? len : len - 1;
331: // lw = lw -1;
332:
333: for (int i = 0, j = 1; i < end; i++, j = (i + 1) % len) {
334: x = new int[4];
335: y = new int[4];
336:
337: // calculate the offsets - HACK not consistent?
338: off1 = (int) lw / 2;
339: off2 = (lw % 2 == 1) ? (int) lw / 2 + 1 : (int) lw / 2;
340:
341: // slope <= 1
342: if (Math.abs((float) (ypts[j] - ypts[i])
343: / (float) (xpts[j] - xpts[i])) <= 1f) {
344: x[0] = x[3] = xpts[i];
345: x[1] = x[2] = xpts[j];
346:
347: y[0] = ypts[i] + off1;
348: y[1] = ypts[j] + off1;
349: y[2] = ypts[j] - off2;
350: y[3] = ypts[i] - off2;
351:
352: ret_val.add(x);
353: ret_val.add(y);
354:
355: if (altx != null) {
356: a_x = new int[4];
357: a_x[0] = a_x[3] = altx[i];
358: a_x[1] = a_x[2] = altx[j];
359: ret_val.add(a_x);
360: ret_val.add(y);
361: }
362: }
363:
364: // slope > 1
365: else {
366: x[0] = xpts[i] + off1;
367: x[1] = xpts[j] + off1;
368: x[2] = xpts[j] - off2;
369: x[3] = xpts[i] - off2;
370:
371: y[0] = y[3] = ypts[i];
372: y[1] = y[2] = ypts[j];
373:
374: ret_val.add(x);
375: ret_val.add(y);
376:
377: if (altx != null) {
378: a_x = new int[4];
379: a_x[0] = altx[i] + off1;
380: a_x[1] = altx[j] + off1;
381: a_x[2] = altx[j] - off2;
382: a_x[3] = altx[i] - off2;
383: ret_val.add(a_x);
384: ret_val.add(y);
385: }
386: }
387: }
388: return ret_val;
389: }
390:
391: //////////////////////////////////////////////////////////////////////////
392:
393: /** main() - for testing */
394: public static void main(String[] args) {
395:
396: // 3-4-5 triangle
397: System.out.println(distance(0, 0, 3, 4));
398: System.out.println(distance(0, 0, -3, 4));
399: System.out.println(distance(0, 0, -3, -4));
400: System.out.println(distance(0, 0, 3, -4));
401: System.out.println();
402:
403: System.out.println(distance_to_line(0, 0, 2, 2, 0, 2)); // root 2
404: System.out.println(distance_to_line(0, 0, 2, 0, 0, 2)); // 2
405: System.out.println(distance_to_line(0, 0, 2, 0, -1, -1)); // root 2
406: System.out.println(distance_to_line(0, 0, 2, 0, 1, 0)); // 0
407: System.out.println(distance_to_line(0, 0, 2, 2, 1, 0)); // rounded!
408: System.out.println();
409:
410: int[] xpts = new int[3];
411: int[] ypts = new int[3];
412: xpts[0] = 0;
413: ypts[0] = 0;
414: xpts[1] = 3;
415: ypts[1] = 0;
416: xpts[2] = 3;
417: ypts[2] = 4;
418:
419: System.out.println(closestPolyDistance(xpts, ypts, 0, 4, true));
420: System.out
421: .println(closestPolyDistance(xpts, ypts, 0, 4, false));//3
422:
423: xpts[0] = 0;
424: ypts[0] = 0;
425: xpts[1] = 2;
426: ypts[1] = 0;
427: xpts[2] = 2;
428: ypts[2] = 2;
429: System.out.println(closestPolyDistance(xpts, ypts, 0, 1, true));//round
430: System.out
431: .println(closestPolyDistance(xpts, ypts, 0, 1, false));//1
432:
433: // linewidth testing
434:
435: System.out.println("");
436: OMVector vec = generateWideLine(3, 0, 0, 5, 5);
437: vec.resetEnumerator();
438: int[] x = (int[]) vec.nextElement(true);
439: int[] y = (int[]) vec.nextElement(true);
440: System.out.print("wide line: ");
441: for (int i = 0; i < x.length; i++) {
442: System.out.print(x[i] + "," + y[i] + " ");
443: }
444: System.out.println("");
445:
446: System.out.println("");
447: vec = generateWideLine(4, 0, 0, -5, -3);
448: vec.resetEnumerator();
449: x = (int[]) vec.nextElement(true);
450: y = (int[]) vec.nextElement(true);
451: System.out.print("wide line: ");
452: for (int i = 0; i < x.length; i++) {
453: System.out.print(x[i] + "," + y[i] + " ");
454: }
455: System.out.println("");
456: System.out.println("");
457:
458: xpts = new int[4];
459: ypts = new int[4];
460: xpts[0] = 0;
461: ypts[0] = 0;
462: xpts[1] = 5;
463: ypts[1] = 2;
464: xpts[2] = 4;
465: ypts[2] = 8;
466: xpts[3] = -2;
467: ypts[3] = 6;
468: vec = generateWidePoly(3, xpts, ypts, null, false);
469: vec.resetEnumerator();
470: while (vec.hasMoreElements()) {
471: x = (int[]) vec.nextElement(true);
472: y = (int[]) vec.nextElement(true);
473: System.out.print("wide line: ");
474: for (int i = 0; i < x.length; i++) {
475: System.out.print(x[i] + "," + y[i] + " ");
476: }
477: System.out.println("");
478: }
479: }
480: }
|