001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017: package org.apache.harmony.awt.geom;
018:
019: import java.util.ArrayList;
020: import java.util.Iterator;
021: import java.util.List;
022:
023: public class CrossingHelper {
024:
025: private double[][] coords;
026: private int[] sizes;
027: private List<IntersectPoint> isectPoints = new ArrayList<IntersectPoint>();
028:
029: public CrossingHelper(double[][] coords, int[] sizes) {
030: this .coords = coords;
031: this .sizes = sizes;
032: }
033:
034: public IntersectPoint[] findCrossing() {
035: int pointCount1 = sizes[0] / 2;
036: int pointCount2 = sizes[1] / 2;
037: int[] indices = new int[pointCount1 + pointCount2];
038:
039: for (int i = 0; i < pointCount1 + pointCount2; i++) {
040: indices[i] = i;
041: }
042:
043: sort(coords[0], pointCount1, coords[1], pointCount2, indices);
044: // the set for the shapes edges storing
045: List<Edge> edges = new ArrayList<Edge>();
046: Edge edge;
047: int begIndex, endIndex;
048: int areaNumber;
049:
050: for (int i = 0; i < indices.length; i++) {
051: if (indices[i] < pointCount1) {
052: begIndex = indices[i];
053: endIndex = indices[i] - 1;
054:
055: if (endIndex < 0) {
056: endIndex = pointCount1 - 1;
057: }
058:
059: areaNumber = 0;
060: } else if (indices[i] < pointCount1 + pointCount2) {
061: begIndex = indices[i] - pointCount1;
062: endIndex = indices[i] - 1 - pointCount1;
063:
064: if (endIndex < 0) {
065: endIndex = pointCount2 - 1;
066: }
067:
068: areaNumber = 1;
069: } else {
070: throw new IndexOutOfBoundsException();
071: }
072:
073: if (!removeEdge(edges, begIndex, endIndex)) {
074: edge = new Edge(begIndex, endIndex, areaNumber);
075: intersectShape(edges, coords[0], pointCount1,
076: coords[1], pointCount2, edge);
077: edges.add(edge);
078: }
079:
080: begIndex = indices[i];
081: endIndex = indices[i] + 1;
082:
083: if ((begIndex < pointCount1) && (endIndex == pointCount1)) {
084: endIndex = 0;
085: } else if ((begIndex >= pointCount1)
086: && (endIndex == (pointCount2 + pointCount1))) {
087: endIndex = pointCount1;
088: }
089:
090: if (endIndex < pointCount1) {
091: areaNumber = 0;
092: } else {
093: areaNumber = 1;
094: endIndex -= pointCount1;
095: begIndex -= pointCount1;
096: }
097:
098: if (!removeEdge(edges, begIndex, endIndex)) {
099: edge = new Edge(begIndex, endIndex, areaNumber);
100: intersectShape(edges, coords[0], pointCount1,
101: coords[1], pointCount2, edge);
102: edges.add(edge);
103: }
104: }
105:
106: return isectPoints.toArray(new IntersectPoint[isectPoints
107: .size()]);
108: }
109:
110: private boolean removeEdge(List<Edge> edges, int begIndex,
111: int endIndex) {
112:
113: for (Edge edge : edges) {
114: if (edge.reverseCompare(begIndex, endIndex)) {
115: edges.remove(edge);
116: return true;
117: }
118: }
119:
120: return false;
121: }
122:
123: // return the quantity of intersect points
124: private void intersectShape(List<Edge> edges, double[] coords1,
125: int length1, double[] coords2, int length2, Edge initEdge) {
126: int areaOfEdge1, areaOfEdge2;
127: int initBegin, initEnd;
128: int addBegin, addEnd;
129: double x1, y1, x2, y2, x3, y3, x4, y4;
130: double[] point = new double[2];
131: Edge edge;
132:
133: if (initEdge.areaNumber == 0) {
134: x1 = coords1[2 * initEdge.begIndex];
135: y1 = coords1[2 * initEdge.begIndex + 1];
136: x2 = coords1[2 * initEdge.endIndex];
137: y2 = coords1[2 * initEdge.endIndex + 1];
138: areaOfEdge1 = 0;
139: } else {
140: x1 = coords2[2 * initEdge.begIndex];
141: y1 = coords2[2 * initEdge.begIndex + 1];
142: x2 = coords2[2 * initEdge.endIndex];
143: y2 = coords2[2 * initEdge.endIndex + 1];
144: areaOfEdge1 = 1;
145: }
146:
147: for (Iterator iter = edges.iterator(); iter.hasNext();) {
148: edge = (Edge) iter.next();
149:
150: if (edge.areaNumber == 0) {
151: x3 = coords1[2 * edge.begIndex];
152: y3 = coords1[2 * edge.begIndex + 1];
153: x4 = coords1[2 * edge.endIndex];
154: y4 = coords1[2 * edge.endIndex + 1];
155: areaOfEdge2 = 0;
156: } else {
157: x3 = coords2[2 * edge.begIndex];
158: y3 = coords2[2 * edge.begIndex + 1];
159: x4 = coords2[2 * edge.endIndex];
160: y4 = coords2[2 * edge.endIndex + 1];
161: areaOfEdge2 = 1;
162: }
163:
164: if ((areaOfEdge1 != areaOfEdge2)
165: && (GeometryUtil.intersectLines(x1, y1, x2, y2, x3,
166: y3, x4, y4, point) == 1)
167: && (!containsPoint(point))) {
168:
169: if (initEdge.areaNumber == 0) {
170: initBegin = initEdge.begIndex;
171: initEnd = initEdge.endIndex;
172: addBegin = edge.begIndex;
173: addEnd = edge.endIndex;
174: } else {
175: initBegin = edge.begIndex;
176: initEnd = edge.endIndex;
177: addBegin = initEdge.begIndex;
178: addEnd = initEdge.endIndex;
179: }
180:
181: if (((initEnd == length1 - 1) && (initBegin == 0 && initEnd > initBegin))
182: || (((initEnd != length1 - 1) || (initBegin != 0))
183: && ((initBegin != length1 - 1) || (initEnd != 0)) && (initBegin > initEnd))) {
184:
185: int temp = initBegin;
186: initBegin = initEnd;
187: initEnd = temp;
188: }
189:
190: if (((addEnd == length2 - 1) && (addBegin == 0) && (addEnd > addBegin))
191: || (((addEnd != length2 - 1) || (addBegin != 0))
192: && ((addBegin != length2 - 1) || (addEnd != 0)) && (addBegin > addEnd))) {
193:
194: int temp = addBegin;
195: addBegin = addEnd;
196: addEnd = temp;
197: }
198:
199: IntersectPoint ip;
200: for (Iterator i = isectPoints.iterator(); i.hasNext();) {
201: ip = (IntersectPoint) i.next();
202:
203: if ((initBegin == ip.getBegIndex(true))
204: && (initEnd == ip.getEndIndex(true))) {
205:
206: if (compare(ip.getX(), ip.getY(), point[0],
207: point[1]) > 0) {
208: initEnd = -(isectPoints.indexOf(ip) + 1);
209: ip.setBegIndex1(-(isectPoints.size() + 1));
210: } else {
211: initBegin = -(isectPoints.indexOf(ip) + 1);
212: ip.setEndIndex1(-(isectPoints.size() + 1));
213: }
214: }
215:
216: if ((addBegin == ip.getBegIndex(false))
217: && (addEnd == ip.getEndIndex(false))) {
218:
219: if (compare(ip.getX(), ip.getY(), point[0],
220: point[1]) > 0) {
221: addEnd = -(isectPoints.indexOf(ip) + 1);
222: ip.setBegIndex2(-(isectPoints.size() + 1));
223: } else {
224: addBegin = -(isectPoints.indexOf(ip) + 1);
225: ip.setEndIndex2(-(isectPoints.size() + 1));
226: }
227: }
228: }
229:
230: isectPoints.add(new IntersectPoint(initBegin, initEnd,
231: addBegin, addEnd, point[0], point[1]));
232: }
233: }
234: }
235:
236: // the array sorting
237: private static void sort(double[] coords1, int length1,
238: double[] coords2, int length2, int[] array) {
239: int temp;
240: int length = length1 + length2;
241: double x1, y1, x2, y2;
242:
243: for (int i = 1; i < length; i++) {
244: if (array[i - 1] < length1) {
245: x1 = coords1[2 * array[i - 1]];
246: y1 = coords1[2 * array[i - 1] + 1];
247: } else {
248: x1 = coords2[2 * (array[i - 1] - length1)];
249: y1 = coords2[2 * (array[i - 1] - length1) + 1];
250: }
251: if (array[i] < length1) {
252: x2 = coords1[2 * array[i]];
253: y2 = coords1[2 * array[i] + 1];
254: } else {
255: x2 = coords2[2 * (array[i] - length1)];
256: y2 = coords2[2 * (array[i] - length1) + 1];
257: }
258: int j = i;
259: while (j > 0 && compare(x1, y1, x2, y2) <= 0) {
260: temp = array[j];
261: array[j] = array[j - 1];
262: array[j - 1] = temp;
263: j--;
264: if (j > 0) {
265: if (array[j - 1] < length1) {
266: x1 = coords1[2 * array[j - 1]];
267: y1 = coords1[2 * array[j - 1] + 1];
268: } else {
269: x1 = coords2[2 * (array[j - 1] - length1)];
270: y1 = coords2[2 * (array[j - 1] - length1) + 1];
271: }
272: if (array[j] < length1) {
273: x2 = coords1[2 * array[j]];
274: y2 = coords1[2 * array[j] + 1];
275: } else {
276: x2 = coords2[2 * (array[j] - length1)];
277: y2 = coords2[2 * (array[j] - length1) + 1];
278: }
279: }
280: }
281: }
282: }
283:
284: public boolean containsPoint(double[] point) {
285: IntersectPoint ipoint;
286:
287: for (Iterator i = isectPoints.iterator(); i.hasNext();) {
288: ipoint = (IntersectPoint) i.next();
289:
290: if (ipoint.getX() == point[0] && ipoint.getY() == point[1]) {
291: return true;
292: }
293: }
294:
295: return false;
296: }
297:
298: public static int compare(double x1, double y1, double x2, double y2) {
299:
300: if ((x1 < x2) || (x1 == x2 && y1 < y2)) {
301: return 1;
302: } else if (x1 == x2 && y1 == y2) {
303: return 0;
304: }
305:
306: return -1;
307: }
308:
309: private static class Edge {
310: int begIndex;
311: int endIndex;
312: int areaNumber;
313:
314: public Edge(int begIndex, int endIndex, int areaNumber) {
315: this .begIndex = begIndex;
316: this .endIndex = endIndex;
317: this .areaNumber = areaNumber;
318: }
319:
320: public boolean reverseCompare(int begIndex, int endIndex) {
321: return this.begIndex == endIndex
322: && this.endIndex == begIndex;
323: }
324: }
325: }
|