135
136 /* Constants to tag the left and right curves in the edge list */
137 public static final int CTAG_LEFT = 0;
138 public static final int CTAG_RIGHT = 1;
139
140 /* Constants to classify edges */
141 public static final int ETAG_IGNORE = 0;
142 public static final int ETAG_ENTER = 1;
143 public static final int ETAG_EXIT = -1;
144
145 /* Constants used to classify result state */
146 public static final int RSTAG_INSIDE = 1;
147 public static final int RSTAG_OUTSIDE = -1;
148
149 public abstract void newRow();
150
151 public abstract int classify(Edge e);
152
153 public abstract int getState();
154
155 public Vector calculate(Vector left, Vector right) {
156 Vector edges = new Vector();
157 addEdges(edges, left, AreaOp.CTAG_LEFT);
158 addEdges(edges, right, AreaOp.CTAG_RIGHT);
159 edges = pruneEdges(edges);
160 if (false) {
161 System.out.println("result: ");
162 int numcurves = edges.size();
163 Curve[] curvelist = (Curve[]) edges.toArray(new Curve[numcurves]);
164 for (int i = 0; i < numcurves; i++) {
165 System.out.println("curvelist["+i+"] = "+curvelist[i]);
166 }
167 }
168 return edges;
169 }
170
171 private static void addEdges(Vector edges, Vector curves, int curvetag) {
172 Enumeration enum_ = curves.elements();
173 while (enum_.hasMoreElements()) {
174 Curve c = (Curve) enum_.nextElement();
175 if (c.getOrder() > 0) {
176 edges.add(new Edge(c, curvetag));
177 }
178 }
179 }
180
181 private static Comparator YXTopComparator = new Comparator() {
182 public int compare(Object o1, Object o2) {
183 Curve c1 = ((Edge) o1).getCurve();
184 Curve c2 = ((Edge) o2).getCurve();
185 double v1, v2;
186 if ((v1 = c1.getYTop()) == (v2 = c2.getYTop())) {
187 if ((v1 = c1.getXTop()) == (v2 = c2.getXTop())) {
188 return 0;
189 }
190 }
191 if (v1 < v2) {
192 return -1;
193 }
194 return 1;
195 }
196 };
197
198 private Vector pruneEdges(Vector edges) {
199 int numedges = edges.size();
200 if (numedges < 2) {
201 return edges;
202 }
203 Edge[] edgelist = (Edge[]) edges.toArray(new Edge[numedges]);
204 Arrays.sort(edgelist, YXTopComparator);
205 if (false) {
206 System.out.println("pruning: ");
207 for (int i = 0; i < numedges; i++) {
208 System.out.println("edgelist["+i+"] = "+edgelist[i]);
209 }
210 }
211 Edge e;
212 int left = 0;
213 int right = 0;
214 int cur = 0;
215 int next = 0;
216 double yrange[] = new double[2];
217 Vector subcurves = new Vector();
218 Vector chains = new Vector();
219 Vector links = new Vector();
220 // Active edges are between left (inclusive) and right (exclusive)
221 while (left < numedges) {
222 double y = yrange[0];
223 // Prune active edges that fall off the top of the active y range
224 for (cur = next = right - 1; cur >= left; cur--) {
225 e = edgelist[cur];
226 if (e.getCurve().getYBot() > y) {
227 if (next > cur) {
228 edgelist[next] = e;
229 }
230 next--;
231 }
232 }
233 left = next + 1;
234 // Grab a new "top of Y range" if the active edges are empty
235 if (left >= right) {
236 if (right >= numedges) {
237 break;
238 }
239 y = edgelist[right].getCurve().getYTop();
368 System.out.println("num links = "+links.size());
369 System.out.println("y top = "+yrange[0]);
370 if (right < numedges) {
371 System.out.println("y top of next curve = "+
372 edgelist[right].getCurve().getYTop());
373 } else {
374 System.out.println("no more curves");
375 }
376 for (cur = left; cur < right; cur++) {
377 e = edgelist[cur];
378 System.out.println(e);
379 int eq = e.getEquivalence();
380 if (eq != 0) {
381 System.out.println(" was equal to "+eq+"...");
382 }
383 }
384 }
385 if (false) {
386 System.out.println("new links:");
387 for (int i = 0; i < links.size(); i++) {
388 CurveLink link = (CurveLink) links.elementAt(i);
389 System.out.println(" "+link.getSubCurve());
390 }
391 }
392 resolveLinks(subcurves, chains, links);
393 links.clear();
394 // Finally capture the bottom of the valid Y range as the top
395 // of the next Y range.
396 yrange[0] = yend;
397 }
398 finalizeSubCurves(subcurves, chains);
399 Vector ret = new Vector();
400 Enumeration enum_ = subcurves.elements();
401 while (enum_.hasMoreElements()) {
402 CurveLink link = (CurveLink) enum_.nextElement();
403 ret.add(link.getMoveto());
404 CurveLink nextlink = link;
405 while ((nextlink = nextlink.getNext()) != null) {
406 if (!link.absorb(nextlink)) {
407 ret.add(link.getSubCurve());
408 link = nextlink;
409 }
410 }
411 ret.add(link.getSubCurve());
412 }
413 return ret;
414 }
415
416 public static void finalizeSubCurves(Vector subcurves, Vector chains) {
417 int numchains = chains.size();
418 if (numchains == 0) {
419 return;
420 }
421 if ((numchains & 1) != 0) {
422 throw new InternalError("Odd number of chains!");
423 }
424 ChainEnd[] endlist = new ChainEnd[numchains];
425 chains.toArray(endlist);
426 for (int i = 1; i < numchains; i += 2) {
427 ChainEnd open = endlist[i - 1];
428 ChainEnd close = endlist[i];
429 CurveLink subcurve = open.linkTo(close);
430 if (subcurve != null) {
431 subcurves.add(subcurve);
432 }
433 }
434 chains.clear();
435 }
436
437 private static CurveLink[] EmptyLinkList = new CurveLink[2];
438 private static ChainEnd[] EmptyChainList = new ChainEnd[2];
439
440 public static void resolveLinks(Vector subcurves,
441 Vector chains,
442 Vector links)
443 {
444 int numlinks = links.size();
445 CurveLink[] linklist;
446 if (numlinks == 0) {
447 linklist = EmptyLinkList;
448 } else {
449 if ((numlinks & 1) != 0) {
450 throw new InternalError("Odd number of new curves!");
451 }
452 linklist = new CurveLink[numlinks+2];
453 links.toArray(linklist);
454 }
455 int numchains = chains.size();
456 ChainEnd[] endlist;
457 if (numchains == 0) {
458 endlist = EmptyChainList;
459 } else {
460 if ((numchains & 1) != 0) {
461 throw new InternalError("Odd number of chains!");
462 }
|
135
136 /* Constants to tag the left and right curves in the edge list */
137 public static final int CTAG_LEFT = 0;
138 public static final int CTAG_RIGHT = 1;
139
140 /* Constants to classify edges */
141 public static final int ETAG_IGNORE = 0;
142 public static final int ETAG_ENTER = 1;
143 public static final int ETAG_EXIT = -1;
144
145 /* Constants used to classify result state */
146 public static final int RSTAG_INSIDE = 1;
147 public static final int RSTAG_OUTSIDE = -1;
148
149 public abstract void newRow();
150
151 public abstract int classify(Edge e);
152
153 public abstract int getState();
154
155 public Vector<Curve> calculate(Vector<Curve> left, Vector<Curve> right) {
156 Vector<Edge> edges = new Vector<>();
157 addEdges(edges, left, AreaOp.CTAG_LEFT);
158 addEdges(edges, right, AreaOp.CTAG_RIGHT);
159 Vector<Curve> curves = pruneEdges(edges);
160 if (false) {
161 System.out.println("result: ");
162 int numcurves = curves.size();
163 Curve[] curvelist = curves.toArray(new Curve[numcurves]);
164 for (int i = 0; i < numcurves; i++) {
165 System.out.println("curvelist["+i+"] = "+curvelist[i]);
166 }
167 }
168 return curves;
169 }
170
171 private static void addEdges(Vector<Edge> edges, Vector<Curve> curves, int curvetag) {
172 Enumeration<Curve> enum_ = curves.elements();
173 while (enum_.hasMoreElements()) {
174 Curve c = enum_.nextElement();
175 if (c.getOrder() > 0) {
176 edges.add(new Edge(c, curvetag));
177 }
178 }
179 }
180
181 private static Comparator<Edge> YXTopComparator = new Comparator<Edge>() {
182 public int compare(Edge o1, Edge o2) {
183 Curve c1 = o1.getCurve();
184 Curve c2 = o2.getCurve();
185 double v1, v2;
186 if ((v1 = c1.getYTop()) == (v2 = c2.getYTop())) {
187 if ((v1 = c1.getXTop()) == (v2 = c2.getXTop())) {
188 return 0;
189 }
190 }
191 if (v1 < v2) {
192 return -1;
193 }
194 return 1;
195 }
196 };
197
198 private Vector<Curve> pruneEdges(Vector<Edge> edges) {
199 int numedges = edges.size();
200 if (numedges < 2) {
201 Vector<Curve> rt = new Vector<>();
202 for (Edge edge: edges) {
203 rt.add(edge.getCurve());
204 }
205 return rt;
206 }
207 Edge[] edgelist = edges.toArray(new Edge[numedges]);
208 Arrays.sort(edgelist, YXTopComparator);
209 if (false) {
210 System.out.println("pruning: ");
211 for (int i = 0; i < numedges; i++) {
212 System.out.println("edgelist["+i+"] = "+edgelist[i]);
213 }
214 }
215 Edge e;
216 int left = 0;
217 int right = 0;
218 int cur = 0;
219 int next = 0;
220 double yrange[] = new double[2];
221 Vector<CurveLink> subcurves = new Vector<>();
222 Vector<ChainEnd> chains = new Vector<>();
223 Vector<CurveLink> links = new Vector<>();
224 // Active edges are between left (inclusive) and right (exclusive)
225 while (left < numedges) {
226 double y = yrange[0];
227 // Prune active edges that fall off the top of the active y range
228 for (cur = next = right - 1; cur >= left; cur--) {
229 e = edgelist[cur];
230 if (e.getCurve().getYBot() > y) {
231 if (next > cur) {
232 edgelist[next] = e;
233 }
234 next--;
235 }
236 }
237 left = next + 1;
238 // Grab a new "top of Y range" if the active edges are empty
239 if (left >= right) {
240 if (right >= numedges) {
241 break;
242 }
243 y = edgelist[right].getCurve().getYTop();
372 System.out.println("num links = "+links.size());
373 System.out.println("y top = "+yrange[0]);
374 if (right < numedges) {
375 System.out.println("y top of next curve = "+
376 edgelist[right].getCurve().getYTop());
377 } else {
378 System.out.println("no more curves");
379 }
380 for (cur = left; cur < right; cur++) {
381 e = edgelist[cur];
382 System.out.println(e);
383 int eq = e.getEquivalence();
384 if (eq != 0) {
385 System.out.println(" was equal to "+eq+"...");
386 }
387 }
388 }
389 if (false) {
390 System.out.println("new links:");
391 for (int i = 0; i < links.size(); i++) {
392 CurveLink link = links.elementAt(i);
393 System.out.println(" "+link.getSubCurve());
394 }
395 }
396 resolveLinks(subcurves, chains, links);
397 links.clear();
398 // Finally capture the bottom of the valid Y range as the top
399 // of the next Y range.
400 yrange[0] = yend;
401 }
402 finalizeSubCurves(subcurves, chains);
403 Vector<Curve> ret = new Vector<>();
404 Enumeration<CurveLink> enum_ = subcurves.elements();
405 while (enum_.hasMoreElements()) {
406 CurveLink link = enum_.nextElement();
407 ret.add(link.getMoveto());
408 CurveLink nextlink = link;
409 while ((nextlink = nextlink.getNext()) != null) {
410 if (!link.absorb(nextlink)) {
411 ret.add(link.getSubCurve());
412 link = nextlink;
413 }
414 }
415 ret.add(link.getSubCurve());
416 }
417 return ret;
418 }
419
420 public static void finalizeSubCurves(Vector<CurveLink> subcurves,
421 Vector<ChainEnd> chains) {
422 int numchains = chains.size();
423 if (numchains == 0) {
424 return;
425 }
426 if ((numchains & 1) != 0) {
427 throw new InternalError("Odd number of chains!");
428 }
429 ChainEnd[] endlist = new ChainEnd[numchains];
430 chains.toArray(endlist);
431 for (int i = 1; i < numchains; i += 2) {
432 ChainEnd open = endlist[i - 1];
433 ChainEnd close = endlist[i];
434 CurveLink subcurve = open.linkTo(close);
435 if (subcurve != null) {
436 subcurves.add(subcurve);
437 }
438 }
439 chains.clear();
440 }
441
442 private static CurveLink[] EmptyLinkList = new CurveLink[2];
443 private static ChainEnd[] EmptyChainList = new ChainEnd[2];
444
445 public static void resolveLinks(Vector<CurveLink> subcurves,
446 Vector<ChainEnd> chains,
447 Vector<CurveLink> links)
448 {
449 int numlinks = links.size();
450 CurveLink[] linklist;
451 if (numlinks == 0) {
452 linklist = EmptyLinkList;
453 } else {
454 if ((numlinks & 1) != 0) {
455 throw new InternalError("Odd number of new curves!");
456 }
457 linklist = new CurveLink[numlinks+2];
458 links.toArray(linklist);
459 }
460 int numchains = chains.size();
461 ChainEnd[] endlist;
462 if (numchains == 0) {
463 endlist = EmptyChainList;
464 } else {
465 if ((numchains & 1) != 0) {
466 throw new InternalError("Odd number of chains!");
467 }
|