iText 5 itextpdf.jar Source Code
itextpdf.jar is a component in iText 5 Java library to provide core functionalities.
iText Java library allows you to generate and manage PDF documents.
The Source Code files are provided at iText GitHub site.
You can compile it to generate your JAR file, using pom.xml as the build configuration file.
The source code of itextpdf-5.5.14.jar is provided below:
✍: FYIcenter.com
⏎ com/itextpdf/text/pdf/parser/clipper/DefaultClipper.java
/*
*
* This file is part of the iText (R) project.
* Copyright (c) 2014-2015 iText Group NV
* Authors: Bruno Lowagie, Paulo Soares, et al.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU Affero General Public License version 3
* as published by the Free Software Foundation with the addition of the
* following permission added to Section 15 as permitted in Section 7(a):
* FOR ANY PART OF THE COVERED WORK IN WHICH THE COPYRIGHT IS OWNED BY
* ITEXT GROUP. ITEXT GROUP DISCLAIMS THE WARRANTY OF NON INFRINGEMENT
* OF THIRD PARTY RIGHTS
*
* This program is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
* or FITNESS FOR A PARTICULAR PURPOSE.
* See the GNU Affero General Public License for more details.
* You should have received a copy of the GNU Affero General Public License
* along with this program; if not, see http://www.gnu.org/licenses or write to
* the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
* Boston, MA, 02110-1301 USA, or download the license from the following URL:
* http://itextpdf.com/terms-of-use/
*
* The interactive user interfaces in modified source and object code versions
* of this program must display Appropriate Legal Notices, as required under
* Section 5 of the GNU Affero General Public License.
*
* In accordance with Section 7(b) of the GNU Affero General Public License,
* a covered work must retain the producer line in every PDF that is created
* or manipulated using iText.
*
* You can be released from the requirements of the license by purchasing
* a commercial license. Buying such a license is mandatory as soon as you
* develop commercial activities involving the iText software without
* disclosing the source code of your own applications.
* These activities include: offering paid services to customers as an ASP,
* serving PDFs on the fly in a web application, shipping iText with a closed
* source product.
*
* For more information, please contact iText Software Corp. at this
* address: sales@itextpdf.com
*
*
* This class is based on the C# open source freeware library Clipper:
* http://www.angusj.com/delphi/clipper.php
* The original classes were distributed under the Boost Software License:
*
* Freeware for both open source and commercial applications
* Copyright 2010-2014 Angus Johnson
* Boost Software License - Version 1.0 - August 17th, 2003
*
* Permission is hereby granted, free of charge, to any person or organization
* obtaining a copy of the software and accompanying documentation covered by
* this license (the "Software") to use, reproduce, display, distribute,
* execute, and transmit the Software, and to prepare derivative works of the
* Software, and to permit third-parties to whom the Software is furnished to
* do so, all subject to the following:
*
* The copyright notices in the Software and this entire statement, including
* the above license grant, this restriction and the following disclaimer,
* must be included in all copies of the Software, in whole or in part, and
* all derivative works of the Software, unless such copies or derivative
* works are solely in the form of machine-executable object code generated by
* a source language processor.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
* SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
* FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
* ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
* DEALINGS IN THE SOFTWARE.
*/
package com.itextpdf.text.pdf.parser.clipper;
import com.itextpdf.text.pdf.parser.clipper.Path.Join;
import com.itextpdf.text.pdf.parser.clipper.Path.OutRec;
import com.itextpdf.text.pdf.parser.clipper.Point.LongPoint;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.logging.Logger;
public class DefaultClipper extends ClipperBase {
private class IntersectNode {
Edge edge1;
Edge Edge2;
private LongPoint pt;
public LongPoint getPt() {
return pt;
}
public void setPt( LongPoint pt ) {
this.pt = pt;
}
};
private static void getHorzDirection( Edge HorzEdge, Direction[] Dir, long[] Left, long[] Right ) {
if (HorzEdge.getBot().getX() < HorzEdge.getTop().getX()) {
Left[0] = HorzEdge.getBot().getX();
Right[0] = HorzEdge.getTop().getX();
Dir[0] = Direction.LEFT_TO_RIGHT;
}
else {
Left[0] = HorzEdge.getTop().getX();
Right[0] = HorzEdge.getBot().getX();
Dir[0] = Direction.RIGHT_TO_LEFT;
}
}
private static boolean getOverlap( long a1, long a2, long b1, long b2, long[] Left, long[] Right ) {
if (a1 < a2) {
if (b1 < b2) {
Left[0] = Math.max( a1, b1 );
Right[0] = Math.min( a2, b2 );
}
else {
Left[0] = Math.max( a1, b2 );
Right[0] = Math.min( a2, b1 );
}
}
else {
if (b1 < b2) {
Left[0] = Math.max( a2, b1 );
Right[0] = Math.min( a1, b2 );
}
else {
Left[0] = Math.max( a2, b2 );
Right[0] = Math.min( a1, b1 );
}
}
return Left[0] < Right[0];
}
private static boolean isParam1RightOfParam2( OutRec outRec1, OutRec outRec2 ) {
do {
outRec1 = outRec1.firstLeft;
if (outRec1 == outRec2) {
return true;
}
}
while (outRec1 != null);
return false;
}
//See "The Point in Polygon Problem for Arbitrary Polygons" by Hormann & Agathos
//http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.5498&rep=rep1&type=pdf
private static int isPointInPolygon( LongPoint pt, Path.OutPt op ) {
//returns 0 if false, +1 if true, -1 if pt ON polygon boundary
int result = 0;
final Path.OutPt startOp = op;
final long ptx = pt.getX(), pty = pt.getY();
long poly0x = op.getPt().getX(), poly0y = op.getPt().getY();
do {
op = op.next;
final long poly1x = op.getPt().getX(), poly1y = op.getPt().getY();
if (poly1y == pty) {
if (poly1x == ptx || poly0y == pty && poly1x > ptx == poly0x < ptx) {
return -1;
}
}
if (poly0y < pty != poly1y < pty) {
if (poly0x >= ptx) {
if (poly1x > ptx) {
result = 1 - result;
}
else {
final double d = (double) (poly0x - ptx) * (poly1y - pty) - (double) (poly1x - ptx) * (poly0y - pty);
if (d == 0) {
return -1;
}
if (d > 0 == poly1y > poly0y) {
result = 1 - result;
}
}
}
else {
if (poly1x > ptx) {
final double d = (double) (poly0x - ptx) * (poly1y - pty) - (double) (poly1x - ptx) * (poly0y - pty);
if (d == 0) {
return -1;
}
if (d > 0 == poly1y > poly0y) {
result = 1 - result;
}
}
}
}
poly0x = poly1x;
poly0y = poly1y;
}
while (startOp != op);
return result;
}
//------------------------------------------------------------------------------
private static boolean joinHorz( Path.OutPt op1, Path.OutPt op1b, Path.OutPt op2, Path.OutPt op2b, LongPoint Pt, boolean DiscardLeft ) {
final Direction Dir1 = op1.getPt().getX() > op1b.getPt().getX() ? Direction.RIGHT_TO_LEFT : Direction.LEFT_TO_RIGHT;
final Direction Dir2 = op2.getPt().getX() > op2b.getPt().getX() ? Direction.RIGHT_TO_LEFT : Direction.LEFT_TO_RIGHT;
if (Dir1 == Dir2) {
return false;
}
//When DiscardLeft, we want Op1b to be on the Left of Op1, otherwise we
//want Op1b to be on the Right. (And likewise with Op2 and Op2b.)
//So, to facilitate this while inserting Op1b and Op2b ...
//when DiscardLeft, make sure we're AT or RIGHT of Pt before adding Op1b,
//otherwise make sure we're AT or LEFT of Pt. (Likewise with Op2b.)
if (Dir1 == Direction.LEFT_TO_RIGHT) {
while (op1.next.getPt().getX() <= Pt.getX() && op1.next.getPt().getX() >= op1.getPt().getX() && op1.next.getPt().getY() == Pt.getY()) {
op1 = op1.next;
}
if (DiscardLeft && op1.getPt().getX() != Pt.getX()) {
op1 = op1.next;
}
op1b = op1.duplicate( !DiscardLeft );
if (!op1b.getPt().equals( Pt )) {
op1 = op1b;
op1.setPt( Pt );
op1b = op1.duplicate( !DiscardLeft );
}
}
else {
while (op1.next.getPt().getX() >= Pt.getX() && op1.next.getPt().getX() <= op1.getPt().getX() && op1.next.getPt().getY() == Pt.getY()) {
op1 = op1.next;
}
if (!DiscardLeft && op1.getPt().getX() != Pt.getX()) {
op1 = op1.next;
}
op1b = op1.duplicate( DiscardLeft );
if (!op1b.getPt().equals( Pt )) {
op1 = op1b;
op1.setPt( Pt );
op1b = op1.duplicate( DiscardLeft );
}
}
if (Dir2 == Direction.LEFT_TO_RIGHT) {
while (op2.next.getPt().getX() <= Pt.getX() && op2.next.getPt().getX() >= op2.getPt().getX() && op2.next.getPt().getY() == Pt.getY()) {
op2 = op2.next;
}
if (DiscardLeft && op2.getPt().getX() != Pt.getX()) {
op2 = op2.next;
}
op2b = op2.duplicate( !DiscardLeft );
if (!op2b.getPt().equals( Pt )) {
op2 = op2b;
op2.setPt( Pt );
op2b = op2.duplicate( !DiscardLeft );
}
;
}
else {
while (op2.next.getPt().getX() >= Pt.getX() && op2.next.getPt().getX() <= op2.getPt().getX() && op2.next.getPt().getY() == Pt.getY()) {
op2 = op2.next;
}
if (!DiscardLeft && op2.getPt().getX() != Pt.getX()) {
op2 = op2.next;
}
op2b = op2.duplicate( DiscardLeft );
if (!op2b.getPt().equals( Pt )) {
op2 = op2b;
op2.setPt( Pt );
op2b = op2.duplicate( DiscardLeft );
}
;
}
;
if (Dir1 == Direction.LEFT_TO_RIGHT == DiscardLeft) {
op1.prev = op2;
op2.next = op1;
op1b.next = op2b;
op2b.prev = op1b;
}
else {
op1.next = op2;
op2.prev = op1;
op1b.prev = op2b;
op2b.next = op1b;
}
return true;
}
private boolean joinPoints( Join j, OutRec outRec1, OutRec outRec2 ) {
Path.OutPt op1 = j.outPt1, op1b;
Path.OutPt op2 = j.outPt2, op2b;
//There are 3 kinds of joins for output polygons ...
//1. Horizontal joins where Join.OutPt1 & Join.OutPt2 are a vertices anywhere
//along (horizontal) collinear edges (& Join.OffPt is on the same horizontal).
//2. Non-horizontal joins where Join.OutPt1 & Join.OutPt2 are at the same
//location at the Bottom of the overlapping segment (& Join.OffPt is above).
//3. StrictlySimple joins where edges touch but are not collinear and where
//Join.OutPt1, Join.OutPt2 & Join.OffPt all share the same point.
final boolean isHorizontal = j.outPt1.getPt().getY() == j.getOffPt().getY();
if (isHorizontal && j.getOffPt().equals( j.outPt1.getPt() ) && j.getOffPt().equals( j.outPt2.getPt() )) {
//Strictly Simple join ...
if (outRec1 != outRec2) {
return false;
}
op1b = j.outPt1.next;
while (op1b != op1 && op1b.getPt().equals( j.getOffPt() )) {
op1b = op1b.next;
}
final boolean reverse1 = op1b.getPt().getY() > j.getOffPt().getY();
op2b = j.outPt2.next;
while (op2b != op2 && op2b.getPt().equals( j.getOffPt() )) {
op2b = op2b.next;
}
final boolean reverse2 = op2b.getPt().getY() > j.getOffPt().getY();
if (reverse1 == reverse2) {
return false;
}
if (reverse1) {
op1b = op1.duplicate( false );
op2b = op2.duplicate( true );
op1.prev = op2;
op2.next = op1;
op1b.next = op2b;
op2b.prev = op1b;
j.outPt1 = op1;
j.outPt2 = op1b;
return true;
}
else {
op1b = op1.duplicate( true );
op2b = op2.duplicate( false );
op1.next = op2;
op2.prev = op1;
op1b.prev = op2b;
op2b.next = op1b;
j.outPt1 = op1;
j.outPt2 = op1b;
return true;
}
}
else if (isHorizontal) {
//treat horizontal joins differently to non-horizontal joins since with
//them we're not yet sure where the overlapping is. OutPt1.Pt & OutPt2.Pt
//may be anywhere along the horizontal edge.
op1b = op1;
while (op1.prev.getPt().getY() == op1.getPt().getY() && op1.prev != op1b && op1.prev != op2) {
op1 = op1.prev;
}
while (op1b.next.getPt().getY() == op1b.getPt().getY() && op1b.next != op1 && op1b.next != op2) {
op1b = op1b.next;
}
if (op1b.next == op1 || op1b.next == op2) {
return false;
} //a flat 'polygon'
op2b = op2;
while (op2.prev.getPt().getY() == op2.getPt().getY() && op2.prev != op2b && op2.prev != op1b) {
op2 = op2.prev;
}
while (op2b.next.getPt().getY() == op2b.getPt().getY() && op2b.next != op2 && op2b.next != op1) {
op2b = op2b.next;
}
if (op2b.next == op2 || op2b.next == op1) {
return false;
} //a flat 'polygon'
final long[] LeftV = new long[1], RightV = new long[1];
//Op1 -. Op1b & Op2 -. Op2b are the extremites of the horizontal edges
if (!getOverlap( op1.getPt().getX(), op1b.getPt().getX(), op2.getPt().getX(), op2b.getPt().getX(), LeftV, RightV )) {
return false;
}
final long Left = LeftV[0];
final long Right = RightV[0];
//DiscardLeftSide: when overlapping edges are joined, a spike will created
//which needs to be cleaned up. However, we don't want Op1 or Op2 caught up
//on the discard Side as either may still be needed for other joins ...
LongPoint Pt;
boolean DiscardLeftSide;
if (op1.getPt().getX() >= Left && op1.getPt().getX() <= Right) {
Pt = new LongPoint( op1.getPt() );
DiscardLeftSide = op1.getPt().getX() > op1b.getPt().getX();
}
else if (op2.getPt().getX() >= Left && op2.getPt().getX() <= Right) {
Pt = new LongPoint( op2.getPt() );
DiscardLeftSide = op2.getPt().getX() > op2b.getPt().getX();
}
else if (op1b.getPt().getX() >= Left && op1b.getPt().getX() <= Right) {
Pt = new LongPoint( op1b.getPt() );
DiscardLeftSide = op1b.getPt().getX() > op1.getPt().getX();
}
else {
Pt = new LongPoint( op2b.getPt() );
DiscardLeftSide = op2b.getPt().getX() > op2.getPt().getX();
}
j.outPt1 = op1;
j.outPt2 = op2;
return joinHorz( op1, op1b, op2, op2b, Pt, DiscardLeftSide );
}
else {
//nb: For non-horizontal joins ...
// 1. Jr.OutPt1.getPt().getY() == Jr.OutPt2.getPt().getY()
// 2. Jr.OutPt1.Pt > Jr.OffPt.getY()
//make sure the polygons are correctly oriented ...
op1b = op1.next;
while (op1b.getPt().equals( op1.getPt() ) && op1b != op1) {
op1b = op1b.next;
}
final boolean Reverse1 = op1b.getPt().getY() > op1.getPt().getY() || !Point.slopesEqual( op1.getPt(), op1b.getPt(), j.getOffPt(), useFullRange );
if (Reverse1) {
op1b = op1.prev;
while (op1b.getPt().equals( op1.getPt() ) && op1b != op1) {
op1b = op1b.prev;
}
if (op1b.getPt().getY() > op1.getPt().getY() || !Point.slopesEqual( op1.getPt(), op1b.getPt(), j.getOffPt(), useFullRange )) {
return false;
}
}
;
op2b = op2.next;
while (op2b.getPt().equals( op2.getPt() ) && op2b != op2) {
op2b = op2b.next;
}
final boolean Reverse2 = op2b.getPt().getY() > op2.getPt().getY() || !Point.slopesEqual( op2.getPt(), op2b.getPt(), j.getOffPt(), useFullRange );
if (Reverse2) {
op2b = op2.prev;
while (op2b.getPt().equals( op2.getPt() ) && op2b != op2) {
op2b = op2b.prev;
}
if (op2b.getPt().getY() > op2.getPt().getY() || !Point.slopesEqual( op2.getPt(), op2b.getPt(), j.getOffPt(), useFullRange )) {
return false;
}
}
if (op1b == op1 || op2b == op2 || op1b == op2b || outRec1 == outRec2 && Reverse1 == Reverse2) {
return false;
}
if (Reverse1) {
op1b = op1.duplicate( false );
op2b = op2.duplicate( true );
op1.prev = op2;
op2.next = op1;
op1b.next = op2b;
op2b.prev = op1b;
j.outPt1 = op1;
j.outPt2 = op1b;
return true;
}
else {
op1b = op1.duplicate( true );
op2b = op2.duplicate( false );
op1.next = op2;
op2.prev = op1;
op1b.prev = op2b;
op2b.next = op1b;
j.outPt1 = op1;
j.outPt2 = op1b;
return true;
}
}
}
private static Paths minkowski( Path pattern, Path path, boolean IsSum, boolean IsClosed ) {
final int delta = IsClosed ? 1 : 0;
final int polyCnt = pattern.size();
final int pathCnt = path.size();
final Paths result = new Paths( pathCnt );
if (IsSum) {
for (int i = 0; i < pathCnt; i++) {
final Path p = new Path( polyCnt );
for (final LongPoint ip : pattern) {
p.add( new LongPoint( path.get( i ).getX() + ip.getX(), path.get( i ).getY() + ip.getY(), 0 ) );
}
result.add( p );
}
}
else {
for (int i = 0; i < pathCnt; i++) {
final Path p = new Path( polyCnt );
for (final LongPoint ip : pattern) {
p.add( new LongPoint( path.get( i ).getX() - ip.getX(), path.get( i ).getY() - ip.getY(), 0 ) );
}
result.add( p );
}
}
final Paths quads = new Paths( (pathCnt + delta) * (polyCnt + 1) );
for (int i = 0; i < pathCnt - 1 + delta; i++) {
for (int j = 0; j < polyCnt; j++) {
final Path quad = new Path( 4 );
quad.add( result.get( i % pathCnt ).get( j % polyCnt ) );
quad.add( result.get( (i + 1) % pathCnt ).get( j % polyCnt ) );
quad.add( result.get( (i + 1) % pathCnt ).get( (j + 1) % polyCnt ) );
quad.add( result.get( i % pathCnt ).get( (j + 1) % polyCnt ) );
if (!quad.orientation()) {
Collections.reverse( quad );
}
quads.add( quad );
}
}
return quads;
}
public static Paths minkowskiDiff( Path poly1, Path poly2 ) {
final Paths paths = minkowski( poly1, poly2, false, true );
final DefaultClipper c = new DefaultClipper();
c.addPaths( paths, PolyType.SUBJECT, true );
c.execute( ClipType.UNION, paths, PolyFillType.NON_ZERO, PolyFillType.NON_ZERO );
return paths;
}
public static Paths minkowskiSum( Path pattern, Path path, boolean pathIsClosed ) {
final Paths paths = minkowski( pattern, path, true, pathIsClosed );
final DefaultClipper c = new DefaultClipper();
c.addPaths( paths, PolyType.SUBJECT, true );
c.execute( ClipType.UNION, paths, PolyFillType.NON_ZERO, PolyFillType.NON_ZERO );
return paths;
}
public static Paths minkowskiSum( Path pattern, Paths paths, boolean pathIsClosed ) {
final Paths solution = new Paths();
final DefaultClipper c = new DefaultClipper();
for (int i = 0; i < paths.size(); ++i) {
final Paths tmp = minkowski( pattern, paths.get( i ), true, pathIsClosed );
c.addPaths( tmp, PolyType.SUBJECT, true );
if (pathIsClosed) {
final Path path = paths.get( i ).TranslatePath( pattern.get( 0 ) );
c.addPath( path, PolyType.CLIP, true );
}
}
c.execute( ClipType.UNION, solution, PolyFillType.NON_ZERO, PolyFillType.NON_ZERO );
return solution;
}
private static boolean poly2ContainsPoly1( Path.OutPt outPt1, Path.OutPt outPt2 ) {
Path.OutPt op = outPt1;
do {
//nb: PointInPolygon returns 0 if false, +1 if true, -1 if pt on polygon
final int res = isPointInPolygon( op.getPt(), outPt2 );
if (res >= 0) {
return res > 0;
}
op = op.next;
}
while (op != outPt1);
return true;
}
//------------------------------------------------------------------------------
// SimplifyPolygon functions ...
// Convert self-intersecting polygons into simple polygons
//------------------------------------------------------------------------------
public static Paths simplifyPolygon( Path poly ) {
return simplifyPolygon( poly, PolyFillType.EVEN_ODD );
}
public static Paths simplifyPolygon( Path poly, PolyFillType fillType ) {
final Paths result = new Paths();
final DefaultClipper c = new DefaultClipper( STRICTLY_SIMPLE );
c.addPath( poly, PolyType.SUBJECT, true );
c.execute( ClipType.UNION, result, fillType, fillType );
return result;
}
public static Paths simplifyPolygons( Paths polys ) {
return simplifyPolygons( polys, PolyFillType.EVEN_ODD );
}
public static Paths simplifyPolygons( Paths polys, PolyFillType fillType ) {
final Paths result = new Paths();
final DefaultClipper c = new DefaultClipper( STRICTLY_SIMPLE );
c.addPaths( polys, PolyType.SUBJECT, true );
c.execute( ClipType.UNION, result, fillType, fillType );
return result;
}
protected final List<OutRec> polyOuts;
private ClipType clipType;
private Scanbeam scanbeam;
private Path.Maxima maxima;
private Edge activeEdges;
private Edge sortedEdges;
private final List<IntersectNode> intersectList;
private final Comparator<IntersectNode> intersectNodeComparer;
private PolyFillType clipFillType;
//------------------------------------------------------------------------------
private PolyFillType subjFillType;
//------------------------------------------------------------------------------
private final List<Join> joins;
//------------------------------------------------------------------------------
private final List<Join> ghostJoins;
private boolean usingPolyTree;
public ZFillCallback zFillFunction;
//------------------------------------------------------------------------------
private final boolean reverseSolution;
//------------------------------------------------------------------------------
private final boolean strictlySimple;
private final static Logger LOGGER = Logger.getLogger( DefaultClipper.class.getName() );
public DefaultClipper() {
this( 0 );
}
public DefaultClipper( int InitOptions ) //constructor
{
super( (PRESERVE_COLINEAR & InitOptions) != 0 );
scanbeam = null;
maxima = null;
activeEdges = null;
sortedEdges = null;
intersectList = new ArrayList<IntersectNode>();
intersectNodeComparer = new Comparator<IntersectNode>() {
public int compare(IntersectNode o1, IntersectNode o2) {
final long i = o2.getPt().getY() - o1.getPt().getY();
if (i > 0) {
return 1;
}
else if (i < 0) {
return -1;
}
else {
return 0;
}
}
};
usingPolyTree = false;
polyOuts = new ArrayList<OutRec>();
joins = new ArrayList<Join>();
ghostJoins = new ArrayList<Join>();
reverseSolution = (REVERSE_SOLUTION & InitOptions) != 0;
strictlySimple = (STRICTLY_SIMPLE & InitOptions) != 0;
zFillFunction = null;
}
private void insertScanbeam(long Y)
{
//single-linked list: sorted descending, ignoring dups.
if (scanbeam == null)
{
scanbeam = new Scanbeam();
scanbeam.next = null;
scanbeam.y = Y;
}
else if (Y > scanbeam.y)
{
Scanbeam newSb = new Scanbeam();
newSb.y = Y;
newSb.next = scanbeam;
scanbeam = newSb;
}
else
{
Scanbeam sb2 = scanbeam;
while (sb2.next != null && (Y <= sb2.next.y)) sb2 = sb2.next;
if (Y == sb2.y) return; //ie ignores duplicates
Scanbeam newSb = new Scanbeam();
newSb.y = Y;
newSb.next = sb2.next;
sb2.next = newSb;
}
}
//------------------------------------------------------------------------------
private void InsertMaxima(long X)
{
//double-linked list: sorted ascending, ignoring dups.
Path.Maxima newMax = new Path.Maxima();
newMax.X = X;
if (maxima == null)
{
maxima = newMax;
maxima.Next = null;
maxima.Prev = null;
}
else if (X < maxima.X)
{
newMax.Next = maxima;
newMax.Prev = null;
maxima = newMax;
}
else
{
Path.Maxima m = maxima;
while (m.Next != null && (X >= m.Next.X)) m = m.Next;
if (X == m.X) return; //ie ignores duplicates (& CG to clean up newMax)
//insert newMax between m and m.Next ...
newMax.Next = m.Next;
newMax.Prev = m;
if (m.Next != null) m.Next.Prev = newMax;
m.Next = newMax;
}
}
//------------------------------------------------------------------------------
private void addEdgeToSEL( Edge edge ) {
LOGGER.entering( DefaultClipper.class.getName(), "addEdgeToSEL" );
//SEL pointers in PEdge are reused to build a list of horizontal edges.
//However, we don't need to worry about order with horizontal edge processing.
if (sortedEdges == null) {
sortedEdges = edge;
edge.prevInSEL = null;
edge.nextInSEL = null;
}
else {
edge.nextInSEL = sortedEdges;
edge.prevInSEL = null;
sortedEdges.prevInSEL = edge;
sortedEdges = edge;
}
}
private void addGhostJoin( Path.OutPt Op, LongPoint OffPt ) {
final Join j = new Join();
j.outPt1 = Op;
j.setOffPt( OffPt );
ghostJoins.add( j );
}
//------------------------------------------------------------------------------
private void addJoin( Path.OutPt Op1, Path.OutPt Op2, LongPoint OffPt ) {
LOGGER.entering(DefaultClipper.class.getName(), "addJoin");
final Join j = new Join();
j.outPt1 = Op1;
j.outPt2 = Op2;
j.setOffPt( OffPt );
joins.add( j );
}
//------------------------------------------------------------------------------
private void addLocalMaxPoly( Edge e1, Edge e2, LongPoint pt ) {
addOutPt(e1, pt);
if (e2.windDelta == 0) {
addOutPt( e2, pt );
}
if (e1.outIdx == e2.outIdx) {
e1.outIdx = Edge.UNASSIGNED;
e2.outIdx = Edge.UNASSIGNED;
}
else if (e1.outIdx < e2.outIdx) {
appendPolygon( e1, e2 );
}
else {
appendPolygon( e2, e1 );
}
}
//------------------------------------------------------------------------------
private Path.OutPt addLocalMinPoly( Edge e1, Edge e2, LongPoint pt ) {
LOGGER.entering( DefaultClipper.class.getName(), "addLocalMinPoly" );
Path.OutPt result;
Edge e, prevE;
if (e2.isHorizontal() || e1.deltaX > e2.deltaX) {
result = addOutPt( e1, pt );
e2.outIdx = e1.outIdx;
e1.side = Edge.Side.LEFT;
e2.side = Edge.Side.RIGHT;
e = e1;
if (e.prevInAEL == e2) {
prevE = e2.prevInAEL;
}
else {
prevE = e.prevInAEL;
}
}
else {
result = addOutPt( e2, pt );
e1.outIdx = e2.outIdx;
e1.side = Edge.Side.RIGHT;
e2.side = Edge.Side.LEFT;
e = e2;
if (e.prevInAEL == e1) {
prevE = e1.prevInAEL;
}
else {
prevE = e.prevInAEL;
}
}
if (prevE != null && prevE.outIdx >= 0 &&
Edge.topX( prevE, pt.getY() ) == Edge.topX( e, pt.getY() ) &&
Edge.slopesEqual( e, prevE, useFullRange ) &&
e.windDelta != 0 && prevE.windDelta != 0) {
final Path.OutPt outPt = addOutPt( prevE, pt );
addJoin( result, outPt, e.getTop() );
}
return result;
}
private Path.OutPt addOutPt( Edge e, LongPoint pt ) {
LOGGER.entering( DefaultClipper.class.getName(), "addOutPt" );
if (e.outIdx < 0)
{
OutRec outRec = createOutRec();
outRec.isOpen = (e.windDelta == 0);
Path.OutPt newOp = new Path.OutPt();
outRec.pts = newOp;
newOp.idx = outRec.Idx;
newOp.pt = pt;
newOp.next = newOp;
newOp.prev = newOp;
if (!outRec.isOpen)
setHoleState(e, outRec);
e.outIdx = outRec.Idx; //nb: do this after SetZ !
return newOp;
}
else {
final OutRec outRec = polyOuts.get( e.outIdx );
//OutRec.Pts is the 'Left-most' point & OutRec.Pts.Prev is the 'Right-most'
final Path.OutPt op = outRec.getPoints();
boolean ToFront = (e.side == Edge.Side.LEFT);
LOGGER.finest( "op=" + op.getPointCount() );
LOGGER.finest( ToFront + " " + pt + " " + op.getPt() );
if (ToFront && pt.equals( op.getPt() )) {
return op;
}
else if (!ToFront && pt.equals( op.prev.getPt() )) {
return op.prev;
}
final Path.OutPt newOp = new Path.OutPt();
newOp.idx = outRec.Idx;
newOp.setPt( new LongPoint( pt ) );
newOp.next = op;
newOp.prev = op.prev;
newOp.prev.next = newOp;
op.prev = newOp;
if (ToFront) {
outRec.setPoints( newOp );
}
return newOp;
}
}
private Path.OutPt GetLastOutPt(Edge e)
{
OutRec outRec = polyOuts.get(e.outIdx);
if (e.side == Edge.Side.LEFT)
return outRec.pts;
else
return outRec.pts.prev;
}
//------------------------------------------------------------------------------
private void appendPolygon( Edge e1, Edge e2 ) {
LOGGER.entering( DefaultClipper.class.getName(), "appendPolygon" );
//get the start and ends of both output polygons ...
final OutRec outRec1 = polyOuts.get( e1.outIdx );
final OutRec outRec2 = polyOuts.get( e2.outIdx );
LOGGER.finest( "" + e1.outIdx );
LOGGER.finest( "" + e2.outIdx );
OutRec holeStateRec;
if (isParam1RightOfParam2( outRec1, outRec2 )) {
holeStateRec = outRec2;
}
else if (isParam1RightOfParam2( outRec2, outRec1 )) {
holeStateRec = outRec1;
}
else {
holeStateRec = Path.OutPt.getLowerMostRec( outRec1, outRec2 );
}
final Path.OutPt p1_lft = outRec1.getPoints();
final Path.OutPt p1_rt = p1_lft.prev;
final Path.OutPt p2_lft = outRec2.getPoints();
final Path.OutPt p2_rt = p2_lft.prev;
LOGGER.finest( "p1_lft.getPointCount() = " + p1_lft.getPointCount() );
LOGGER.finest( "p1_rt.getPointCount() = " + p1_rt.getPointCount() );
LOGGER.finest( "p2_lft.getPointCount() = " + p2_lft.getPointCount() );
LOGGER.finest( "p2_rt.getPointCount() = " + p2_rt.getPointCount() );
Edge.Side side;
//join e2 poly onto e1 poly and delete pointers to e2 ...
if (e1.side == Edge.Side.LEFT) {
if (e2.side == Edge.Side.LEFT) {
//z y x a b c
p2_lft.reversePolyPtLinks();
p2_lft.next = p1_lft;
p1_lft.prev = p2_lft;
p1_rt.next = p2_rt;
p2_rt.prev = p1_rt;
outRec1.setPoints( p2_rt );
}
else {
//x y z a b c
p2_rt.next = p1_lft;
p1_lft.prev = p2_rt;
p2_lft.prev = p1_rt;
p1_rt.next = p2_lft;
outRec1.setPoints( p2_lft );
}
side = Edge.Side.LEFT;
}
else {
if (e2.side == Edge.Side.RIGHT) {
//a b c z y x
p2_lft.reversePolyPtLinks();
p1_rt.next = p2_rt;
p2_rt.prev = p1_rt;
p2_lft.next = p1_lft;
p1_lft.prev = p2_lft;
}
else {
//a b c x y z
p1_rt.next = p2_lft;
p2_lft.prev = p1_rt;
p1_lft.prev = p2_rt;
p2_rt.next = p1_lft;
}
side = Edge.Side.RIGHT;
}
outRec1.bottomPt = null;
if (holeStateRec.equals( outRec2 )) {
if (outRec2.firstLeft != outRec1) {
outRec1.firstLeft = outRec2.firstLeft;
}
outRec1.isHole = outRec2.isHole;
}
outRec2.setPoints( null );
outRec2.bottomPt = null;
outRec2.firstLeft = outRec1;
final int OKIdx = e1.outIdx;
final int ObsoleteIdx = e2.outIdx;
e1.outIdx = Edge.UNASSIGNED; //nb: safe because we only get here via AddLocalMaxPoly
e2.outIdx = Edge.UNASSIGNED;
Edge e = activeEdges;
while (e != null) {
if (e.outIdx == ObsoleteIdx) {
e.outIdx = OKIdx;
e.side = side;
break;
}
e = e.nextInAEL;
}
outRec2.Idx = outRec1.Idx;
}
//------------------------------------------------------------------------------
private void buildIntersectList( long topY ) {
if (activeEdges == null) {
return;
}
//prepare for sorting ...
Edge e = activeEdges;
sortedEdges = e;
while (e != null) {
e.prevInSEL = e.prevInAEL;
e.nextInSEL = e.nextInAEL;
e.getCurrent().setX( Edge.topX( e, topY ) );
e = e.nextInAEL;
}
//bubblesort ...
boolean isModified = true;
while (isModified && sortedEdges != null) {
isModified = false;
e = sortedEdges;
while (e.nextInSEL != null) {
final Edge eNext = e.nextInSEL;
final LongPoint[] pt = new LongPoint[1];
if (e.getCurrent().getX() > eNext.getCurrent().getX()) {
intersectPoint( e, eNext, pt );
final IntersectNode newNode = new IntersectNode();
newNode.edge1 = e;
newNode.Edge2 = eNext;
newNode.setPt( pt[0] );
intersectList.add( newNode );
swapPositionsInSEL( e, eNext );
isModified = true;
}
else {
e = eNext;
}
}
if (e.prevInSEL != null) {
e.prevInSEL.nextInSEL = null;
}
else {
break;
}
}
sortedEdges = null;
}
//------------------------------------------------------------------------------
private void buildResult( Paths polyg ) {
polyg.clear();
for (int i = 0; i < polyOuts.size(); i++) {
final OutRec outRec = polyOuts.get( i );
if (outRec.getPoints() == null) {
continue;
}
Path.OutPt p = outRec.getPoints().prev;
final int cnt = p.getPointCount();
LOGGER.finest( "cnt = " + cnt );
if (cnt < 2) {
continue;
}
final Path pg = new Path( cnt );
for (int j = 0; j < cnt; j++) {
pg.add( p.getPt() );
p = p.prev;
}
polyg.add( pg );
}
}
private void buildResult2( PolyTree polytree ) {
polytree.Clear();
//add each output polygon/contour to polytree ...
for (int i = 0; i < polyOuts.size(); i++) {
final OutRec outRec = polyOuts.get( i );
final int cnt = outRec.getPoints() != null ? outRec.getPoints().getPointCount() : 0;
if (outRec.isOpen && cnt < 2 || !outRec.isOpen && cnt < 3) {
continue;
}
outRec.fixHoleLinkage();
final PolyNode pn = new PolyNode();
polytree.getAllPolys().add( pn );
outRec.polyNode = pn;
Path.OutPt op = outRec.getPoints().prev;
for (int j = 0; j < cnt; j++) {
pn.getPolygon().add( op.getPt() );
op = op.prev;
}
}
//fixup PolyNode links etc ...
for (int i = 0; i < polyOuts.size(); i++) {
final OutRec outRec = polyOuts.get( i );
if (outRec.polyNode == null) {
continue;
}
else if (outRec.isOpen) {
outRec.polyNode.setOpen( true );
polytree.addChild( outRec.polyNode );
}
else if (outRec.firstLeft != null && outRec.firstLeft.polyNode != null) {
outRec.firstLeft.polyNode.addChild( outRec.polyNode );
}
else {
polytree.addChild( outRec.polyNode );
}
}
}
private void copyAELToSEL() {
Edge e = activeEdges;
sortedEdges = e;
while (e != null) {
e.prevInSEL = e.prevInAEL;
e.nextInSEL = e.nextInAEL;
e = e.nextInAEL;
}
}
private OutRec createOutRec() {
final OutRec result = new OutRec();
result.Idx = Edge.UNASSIGNED;
result.isHole = false;
result.isOpen = false;
result.firstLeft = null;
result.setPoints( null );
result.bottomPt = null;
result.polyNode = null;
polyOuts.add( result );
result.Idx = polyOuts.size() - 1;
return result;
}
private void deleteFromAEL( Edge e ) {
LOGGER.entering( DefaultClipper.class.getName(), "deleteFromAEL" );
final Edge AelPrev = e.prevInAEL;
final Edge AelNext = e.nextInAEL;
if (AelPrev == null && AelNext == null && e != activeEdges) {
return; //already deleted
}
if (AelPrev != null) {
AelPrev.nextInAEL = AelNext;
}
else {
activeEdges = AelNext;
}
if (AelNext != null) {
AelNext.prevInAEL = AelPrev;
}
e.nextInAEL = null;
e.prevInAEL = null;
LOGGER.exiting( DefaultClipper.class.getName(), "deleteFromAEL" );
}
private void deleteFromSEL( Edge e ) {
LOGGER.entering( DefaultClipper.class.getName(), "deleteFromSEL" );
final Edge SelPrev = e.prevInSEL;
final Edge SelNext = e.nextInSEL;
if (SelPrev == null && SelNext == null && !e.equals( sortedEdges )) {
return; //already deleted
}
if (SelPrev != null) {
SelPrev.nextInSEL = SelNext;
}
else {
sortedEdges = SelNext;
}
if (SelNext != null) {
SelNext.prevInSEL = SelPrev;
}
e.nextInSEL = null;
e.prevInSEL = null;
}
private boolean doHorzSegmentsOverlap( long seg1a, long seg1b, long seg2a, long seg2b ) {
if (seg1a > seg1b) {
final long tmp = seg1a;
seg1a = seg1b;
seg1b = tmp;
}
if (seg2a > seg2b) {
final long tmp = seg2a;
seg2a = seg2b;
seg2b = tmp;
}
return (seg1a < seg2b) && (seg2a < seg1b);
}
private void doMaxima( Edge e ) {
final Edge eMaxPair = e.getMaximaPair();
if (eMaxPair == null) {
if (e.outIdx >= 0) {
addOutPt( e, e.getTop() );
}
deleteFromAEL( e );
return;
}
Edge eNext = e.nextInAEL;
while (eNext != null && eNext != eMaxPair) {
final LongPoint tmp = new LongPoint( e.getTop() );
intersectEdges( e, eNext, tmp );
e.setTop( tmp );
swapPositionsInAEL( e, eNext );
eNext = e.nextInAEL;
}
if (e.outIdx == Edge.UNASSIGNED && eMaxPair.outIdx == Edge.UNASSIGNED) {
deleteFromAEL( e );
deleteFromAEL( eMaxPair );
}
else if (e.outIdx >= 0 && eMaxPair.outIdx >= 0) {
if (e.outIdx >= 0) {
addLocalMaxPoly( e, eMaxPair, e.getTop() );
}
deleteFromAEL( e );
deleteFromAEL( eMaxPair );
}
else if (e.windDelta == 0) {
if (e.outIdx >= 0) {
addOutPt( e, e.getTop() );
e.outIdx = Edge.UNASSIGNED;
}
deleteFromAEL( e );
if (eMaxPair.outIdx >= 0) {
addOutPt( eMaxPair, e.getTop() );
eMaxPair.outIdx = Edge.UNASSIGNED;
}
deleteFromAEL( eMaxPair );
}
else {
throw new IllegalStateException( "DoMaxima error" );
}
}
//------------------------------------------------------------------------------
private void doSimplePolygons() {
int i = 0;
while (i < polyOuts.size()) {
final OutRec outrec = polyOuts.get( i++ );
Path.OutPt op = outrec.getPoints();
if (op == null || outrec.isOpen) {
continue;
}
do //for each Pt in Polygon until duplicate found do ...
{
Path.OutPt op2 = op.next;
while (op2 != outrec.getPoints()) {
if (op.getPt().equals( op2.getPt() ) && !op2.next.equals( op ) && !op2.prev.equals( op )) {
//split the polygon into two ...
final Path.OutPt op3 = op.prev;
final Path.OutPt op4 = op2.prev;
op.prev = op4;
op4.next = op;
op2.prev = op3;
op3.next = op2;
outrec.setPoints( op );
final OutRec outrec2 = createOutRec();
outrec2.setPoints( op2 );
updateOutPtIdxs( outrec2 );
if (poly2ContainsPoly1( outrec2.getPoints(), outrec.getPoints() )) {
//OutRec2 is contained by OutRec1 ...
outrec2.isHole = !outrec.isHole;
outrec2.firstLeft = outrec;
if (usingPolyTree) {
fixupFirstLefts2( outrec2, outrec );
}
}
else if (poly2ContainsPoly1( outrec.getPoints(), outrec2.getPoints() )) {
//OutRec1 is contained by OutRec2 ...
outrec2.isHole = outrec.isHole;
outrec.isHole = !outrec2.isHole;
outrec2.firstLeft = outrec.firstLeft;
outrec.firstLeft = outrec2;
if (usingPolyTree) {
fixupFirstLefts2( outrec, outrec2 );
}
}
else {
//the 2 polygons are separate ...
outrec2.isHole = outrec.isHole;
outrec2.firstLeft = outrec.firstLeft;
if (usingPolyTree) {
fixupFirstLefts1( outrec, outrec2 );
}
}
op2 = op; //ie get ready for the next iteration
}
op2 = op2.next;
}
op = op.next;
}
while (op != outrec.getPoints());
}
}
//------------------------------------------------------------------------------
private boolean EdgesAdjacent( IntersectNode inode ) {
return inode.edge1.nextInSEL == inode.Edge2 || inode.edge1.prevInSEL == inode.Edge2;
}
//------------------------------------------------------------------------------
public boolean execute(ClipType clipType, Paths solution,
PolyFillType FillType)
{
return execute(clipType, solution, FillType, FillType);
}
public boolean execute(ClipType clipType, PolyTree polytree)
{
return execute(clipType, polytree, PolyFillType.EVEN_ODD);
}
public boolean execute(ClipType clipType, PolyTree polytree,
PolyFillType FillType)
{
return execute(clipType, polytree, FillType, FillType);
}
public boolean execute(ClipType clipType, Paths solution) {
return execute(clipType, solution, PolyFillType.EVEN_ODD);
}
public boolean execute( ClipType clipType, Paths solution, PolyFillType subjFillType, PolyFillType clipFillType ) {
synchronized (this) {
if (hasOpenPaths) {
throw new IllegalStateException( "Error: PolyTree struct is needed for open path clipping." );
}
solution.clear();
this.subjFillType = subjFillType;
this.clipFillType = clipFillType;
this.clipType = clipType;
usingPolyTree = false;
boolean succeeded;
try {
succeeded = executeInternal();
//build the return polygons ...
if (succeeded) {
buildResult( solution );
}
return succeeded;
}
finally {
polyOuts.clear();
}
}
}
public boolean execute( ClipType clipType, PolyTree polytree, PolyFillType subjFillType, PolyFillType clipFillType ) {
synchronized (this) {
this.subjFillType = subjFillType;
this.clipFillType = clipFillType;
this.clipType = clipType;
usingPolyTree = true;
boolean succeeded;
try {
succeeded = executeInternal();
//build the return polygons ...
if (succeeded) {
buildResult2( polytree );
}
}
finally {
polyOuts.clear();
}
return succeeded;
}
}
//------------------------------------------------------------------------------
private boolean executeInternal() {
try {
reset();
if (currentLM == null)
return false;
long botY = popScanbeam();
do {
insertLocalMinimaIntoAEL(botY);
processHorizontals();
ghostJoins.clear();
if (scanbeam == null)
break;
long topY = popScanbeam();
if (!processIntersections(topY))
return false;
processEdgesAtTopOfScanbeam(topY);
botY = topY;
} while (scanbeam != null || currentLM != null);
//fix orientations ...
for (int i = 0; i < polyOuts.size(); i++) {
OutRec outRec = polyOuts.get(i);
if (outRec.pts == null || outRec.isOpen)
continue;
if ((outRec.isHole ^ reverseSolution) == (outRec.area() > 0))
outRec.getPoints().reversePolyPtLinks();
}
joinCommonEdges();
for (int i = 0; i < polyOuts.size(); i++) {
OutRec outRec = polyOuts.get(i);
if (outRec.getPoints() == null)
continue;
else if (outRec.isOpen)
fixupOutPolyline(outRec);
else
fixupOutPolygon(outRec);
}
if (strictlySimple)
doSimplePolygons();
return true;
}
//catch { return false; }
finally {
joins.clear();
ghostJoins.clear();
}
}
//------------------------------------------------------------------------------
private void fixupFirstLefts1( OutRec OldOutRec, OutRec NewOutRec ) {
for (int i = 0; i < polyOuts.size(); i++) {
final OutRec outRec = polyOuts.get( i );
if (outRec.getPoints() == null || outRec.firstLeft == null) {
continue;
}
final OutRec firstLeft = parseFirstLeft(outRec.firstLeft);
if (firstLeft.equals( OldOutRec )) {
if (poly2ContainsPoly1( outRec.getPoints(), NewOutRec.getPoints() )) {
outRec.firstLeft = NewOutRec;
}
}
}
}
private void fixupFirstLefts2( OutRec OldOutRec, OutRec NewOutRec ) {
for (final OutRec outRec : polyOuts) {
if (outRec.firstLeft == OldOutRec ) {
outRec.firstLeft = NewOutRec;
}
}
}
private boolean fixupIntersectionOrder() {
//pre-condition: intersections are sorted bottom-most first.
//Now it's crucial that intersections are made only between adjacent edges,
//so to ensure this the order of intersections may need adjusting ...
Collections.sort( intersectList, intersectNodeComparer );
copyAELToSEL();
final int cnt = intersectList.size();
for (int i = 0; i < cnt; i++) {
if (!EdgesAdjacent( intersectList.get( i ) )) {
int j = i + 1;
while (j < cnt && !EdgesAdjacent( intersectList.get( j ) )) {
j++;
}
if (j == cnt) {
return false;
}
final IntersectNode tmp = intersectList.get( i );
intersectList.set( i, intersectList.get( j ) );
intersectList.set( j, tmp );
}
swapPositionsInSEL( intersectList.get( i ).edge1, intersectList.get( i ).Edge2 );
}
return true;
}
//----------------------------------------------------------------------
private void fixupOutPolyline(OutRec outrec)
{
Path.OutPt pp = outrec.pts;
Path.OutPt lastPP = pp.prev;
while (pp != lastPP)
{
pp = pp.next;
if (pp.pt.equals(pp.prev.pt))
{
if (pp == lastPP) lastPP = pp.prev;
Path.OutPt tmpPP = pp.prev;
tmpPP.next = pp.next;
pp.next.prev = tmpPP;
pp = tmpPP;
}
}
if (pp == pp.prev) outrec.pts = null;
}
private void fixupOutPolygon( OutRec outRec ) {
//FixupOutPolygon() - removes duplicate points and simplifies consecutive
//parallel edges by removing the middle vertex.
Path.OutPt lastOK = null;
outRec.bottomPt = null;
Path.OutPt pp = outRec.getPoints();
boolean preserveCol = preserveCollinear || strictlySimple;
for (;;) {
if (pp.prev == pp || pp.prev == pp.next) {
outRec.setPoints( null );
return;
}
//test for duplicate points and collinear edges ...
if (pp.getPt().equals( pp.next.getPt() ) || pp.getPt().equals( pp.prev.getPt() )
|| Point.slopesEqual( pp.prev.getPt(), pp.getPt(), pp.next.getPt(), useFullRange )
&& (!preserveCol || !Point.isPt2BetweenPt1AndPt3( pp.prev.getPt(), pp.getPt(), pp.next.getPt() ))) {
lastOK = null;
pp.prev.next = pp.next;
pp.next.prev = pp.prev;
pp = pp.prev;
}
else if (pp == lastOK) {
break;
}
else {
if (lastOK == null) {
lastOK = pp;
}
pp = pp.next;
}
}
outRec.setPoints( pp );
}
private OutRec getOutRec( int idx ) {
OutRec outrec = polyOuts.get( idx );
while (outrec != polyOuts.get( outrec.Idx )) {
outrec = polyOuts.get( outrec.Idx );
}
return outrec;
}
private void insertEdgeIntoAEL( Edge edge, Edge startEdge ) {
LOGGER.entering( DefaultClipper.class.getName(), "insertEdgeIntoAEL" );
if (activeEdges == null) {
edge.prevInAEL = null;
edge.nextInAEL = null;
LOGGER.finest( "Edge " + edge.outIdx + " -> " + null );
activeEdges = edge;
}
else if (startEdge == null && Edge.doesE2InsertBeforeE1( activeEdges, edge )) {
edge.prevInAEL = null;
edge.nextInAEL = activeEdges;
LOGGER.finest( "Edge " + edge.outIdx + " -> " + edge.nextInAEL.outIdx );
activeEdges.prevInAEL = edge;
activeEdges = edge;
}
else {
LOGGER.finest( "activeEdges unchanged" );
if (startEdge == null) {
startEdge = activeEdges;
}
while (startEdge.nextInAEL != null &&
!Edge.doesE2InsertBeforeE1( startEdge.nextInAEL, edge )) {
startEdge = startEdge.nextInAEL;
}
edge.nextInAEL = startEdge.nextInAEL;
if (startEdge.nextInAEL != null) {
startEdge.nextInAEL.prevInAEL = edge;
}
edge.prevInAEL = startEdge;
startEdge.nextInAEL = edge;
}
}
//------------------------------------------------------------------------------
private void insertLocalMinimaIntoAEL( long botY ) {
LOGGER.entering( DefaultClipper.class.getName(), "insertLocalMinimaIntoAEL" );
while (currentLM != null && currentLM.y == botY) {
final Edge lb = currentLM.leftBound;
final Edge rb = currentLM.rightBound;
popLocalMinima();
Path.OutPt Op1 = null;
if (lb == null) {
insertEdgeIntoAEL( rb, null );
updateWindingCount( rb );
if (rb.isContributing( clipFillType, subjFillType, clipType )) {
Op1 = addOutPt( rb, rb.getBot() );
}
}
else if (rb == null) {
insertEdgeIntoAEL( lb, null );
updateWindingCount( lb );
if (lb.isContributing( clipFillType, subjFillType, clipType )) {
Op1 = addOutPt( lb, lb.getBot() );
}
insertScanbeam( lb.getTop().getY() );
}
else {
insertEdgeIntoAEL( lb, null );
insertEdgeIntoAEL( rb, lb );
updateWindingCount( lb );
rb.windCnt = lb.windCnt;
rb.windCnt2 = lb.windCnt2;
if (lb.isContributing( clipFillType, subjFillType, clipType )) {
Op1 = addLocalMinPoly( lb, rb, lb.getBot() );
}
insertScanbeam( lb.getTop().getY() );
}
if (rb != null) {
if (rb.isHorizontal()) {
addEdgeToSEL( rb );
}
else {
insertScanbeam( rb.getTop().getY() );
}
}
if (lb == null || rb == null) {
continue;
}
//if output polygons share an Edge with a horizontal rb, they'll need joining later ...
if (Op1 != null && rb.isHorizontal() &&
ghostJoins.size() > 0 && rb.windDelta != 0) {
for (int i = 0; i < ghostJoins.size(); i++) {
//if the horizontal Rb and a 'ghost' horizontal overlap, then convert
//the 'ghost' join to a real join ready for later ...
final Join j = ghostJoins.get( i );
if (doHorzSegmentsOverlap( j.outPt1.getPt().getX(), j.getOffPt().getX(), rb.getBot().getX(), rb.getTop().getX() )) {
addJoin( j.outPt1, Op1, j.getOffPt() );
}
}
}
if (lb.outIdx >= 0 && lb.prevInAEL != null &&
lb.prevInAEL.getCurrent().getX() == lb.getBot().getX() &&
lb.prevInAEL.outIdx >= 0 &&
Edge.slopesEqual( lb.prevInAEL, lb, useFullRange ) &&
lb.windDelta != 0 && lb.prevInAEL.windDelta != 0) {
final Path.OutPt Op2 = addOutPt( lb.prevInAEL, lb.getBot() );
addJoin( Op1, Op2, lb.getTop() );
}
if (lb.nextInAEL != rb) {
if (rb.outIdx >= 0 && rb.prevInAEL.outIdx >= 0 &&
Edge.slopesEqual( rb.prevInAEL, rb, useFullRange ) &&
rb.windDelta != 0 && rb.prevInAEL.windDelta != 0) {
final Path.OutPt Op2 = addOutPt( rb.prevInAEL, rb.getBot() );
addJoin( Op1, Op2, rb.getTop() );
}
Edge e = lb.nextInAEL;
if (e != null) {
while (e != rb) {
//nb: For calculating winding counts etc, IntersectEdges() assumes
//that param1 will be to the right of param2 ABOVE the intersection ...
intersectEdges( rb, e, lb.getCurrent() ); //order important here
e = e.nextInAEL;
}
}
}
}
}
//------------------------------------------------------------------------------
// private void insertScanbeam( long y ) {
// LOGGER.entering( DefaultClipper.class.getName(), "insertScanbeam" );
//
// if (scanbeam == null) {
// scanbeam = new Scanbeam();
// scanbeam.next = null;
// scanbeam.y = y;
// }
// else if (y > scanbeam.y) {
// final Scanbeam newSb = new Scanbeam();
// newSb.y = y;
// newSb.next = scanbeam;
// scanbeam = newSb;
// }
// else {
// Scanbeam sb2 = scanbeam;
// while (sb2.next != null && y <= sb2.next.y) {
// sb2 = sb2.next;
// }
// if (y == sb2.y) {
// return; //ie ignores duplicates
// }
// final Scanbeam newSb = new Scanbeam();
// newSb.y = y;
// newSb.next = sb2.next;
// sb2.next = newSb;
// }
// }
//------------------------------------------------------------------------------
private void intersectEdges( Edge e1, Edge e2, LongPoint pt ) {
LOGGER.entering( DefaultClipper.class.getName(), "insersectEdges" );
//e1 will be to the left of e2 BELOW the intersection. Therefore e1 is before
//e2 in AEL except when e1 is being inserted at the intersection point ...
final boolean e1Contributing = e1.outIdx >= 0;
final boolean e2Contributing = e2.outIdx >= 0;
setZ( pt, e1, e2 );
//if either edge is on an OPEN path ...
if (e1.windDelta == 0 || e2.windDelta == 0) {
//ignore subject-subject open path intersections UNLESS they
//are both open paths, AND they are both 'contributing maximas' ...
if (e1.windDelta == 0 && e2.windDelta == 0) {
return;
}
else if (e1.polyTyp == e2.polyTyp &&
e1.windDelta != e2.windDelta && clipType == ClipType.UNION) {
if (e1.windDelta == 0) {
if (e2Contributing) {
addOutPt( e1, pt );
if (e1Contributing) {
e1.outIdx = Edge.UNASSIGNED;
}
}
}
else {
if (e1Contributing) {
addOutPt( e2, pt );
if (e2Contributing) {
e2.outIdx = Edge.UNASSIGNED;
}
}
}
}
else if (e1.polyTyp != e2.polyTyp) {
if (e1.windDelta == 0 && Math.abs( e2.windCnt ) == 1 && (clipType != ClipType.UNION || e2.windCnt2 == 0)) {
addOutPt( e1, pt );
if (e1Contributing) {
e1.outIdx = Edge.UNASSIGNED;
}
}
else if (e2.windDelta == 0 && Math.abs( e1.windCnt ) == 1 && (clipType != ClipType.UNION || e1.windCnt2 == 0)) {
addOutPt( e2, pt );
if (e2Contributing) {
e2.outIdx = Edge.UNASSIGNED;
}
}
}
return;
}
//update winding counts...
//assumes that e1 will be to the Right of e2 ABOVE the intersection
if (e1.polyTyp == e2.polyTyp) {
if (e1.isEvenOddFillType( clipFillType, subjFillType )) {
final int oldE1WindCnt = e1.windCnt;
e1.windCnt = e2.windCnt;
e2.windCnt = oldE1WindCnt;
}
else {
if (e1.windCnt + e2.windDelta == 0) {
e1.windCnt = -e1.windCnt;
}
else {
e1.windCnt += e2.windDelta;
}
if (e2.windCnt - e1.windDelta == 0) {
e2.windCnt = -e2.windCnt;
}
else {
e2.windCnt -= e1.windDelta;
}
}
}
else {
if (!e2.isEvenOddFillType( clipFillType, subjFillType )) {
e1.windCnt2 += e2.windDelta;
}
else {
e1.windCnt2 = e1.windCnt2 == 0 ? 1 : 0;
}
if (!e1.isEvenOddFillType( clipFillType, subjFillType )) {
e2.windCnt2 -= e1.windDelta;
}
else {
e2.windCnt2 = e2.windCnt2 == 0 ? 1 : 0;
}
}
PolyFillType e1FillType, e2FillType, e1FillType2, e2FillType2;
if (e1.polyTyp == PolyType.SUBJECT) {
e1FillType = subjFillType;
e1FillType2 = clipFillType;
}
else {
e1FillType = clipFillType;
e1FillType2 = subjFillType;
}
if (e2.polyTyp == PolyType.SUBJECT) {
e2FillType = subjFillType;
e2FillType2 = clipFillType;
}
else {
e2FillType = clipFillType;
e2FillType2 = subjFillType;
}
int e1Wc, e2Wc;
switch (e1FillType) {
case POSITIVE:
e1Wc = e1.windCnt;
break;
case NEGATIVE:
e1Wc = -e1.windCnt;
break;
default:
e1Wc = Math.abs( e1.windCnt );
break;
}
switch (e2FillType) {
case POSITIVE:
e2Wc = e2.windCnt;
break;
case NEGATIVE:
e2Wc = -e2.windCnt;
break;
default:
e2Wc = Math.abs( e2.windCnt );
break;
}
if (e1Contributing && e2Contributing) {
if (e1Wc != 0 && e1Wc != 1 || e2Wc != 0 && e2Wc != 1 || e1.polyTyp != e2.polyTyp && clipType != ClipType.XOR) {
addLocalMaxPoly( e1, e2, pt );
}
else {
addOutPt( e1, pt );
addOutPt( e2, pt );
Edge.swapSides( e1, e2 );
Edge.swapPolyIndexes( e1, e2 );
}
}
else if (e1Contributing) {
if (e2Wc == 0 || e2Wc == 1) {
addOutPt( e1, pt );
Edge.swapSides( e1, e2 );
Edge.swapPolyIndexes( e1, e2 );
}
}
else if (e2Contributing) {
if (e1Wc == 0 || e1Wc == 1) {
addOutPt( e2, pt );
Edge.swapSides( e1, e2 );
Edge.swapPolyIndexes( e1, e2 );
}
}
else if ((e1Wc == 0 || e1Wc == 1) && (e2Wc == 0 || e2Wc == 1)) {
//neither edge is currently contributing ...
int e1Wc2, e2Wc2;
switch (e1FillType2) {
case POSITIVE:
e1Wc2 = e1.windCnt2;
break;
case NEGATIVE:
e1Wc2 = -e1.windCnt2;
break;
default:
e1Wc2 = Math.abs( e1.windCnt2 );
break;
}
switch (e2FillType2) {
case POSITIVE:
e2Wc2 = e2.windCnt2;
break;
case NEGATIVE:
e2Wc2 = -e2.windCnt2;
break;
default:
e2Wc2 = Math.abs( e2.windCnt2 );
break;
}
if (e1.polyTyp != e2.polyTyp) {
addLocalMinPoly( e1, e2, pt );
}
else if (e1Wc == 1 && e2Wc == 1) {
switch (clipType) {
case INTERSECTION:
if (e1Wc2 > 0 && e2Wc2 > 0) {
addLocalMinPoly( e1, e2, pt );
}
break;
case UNION:
if (e1Wc2 <= 0 && e2Wc2 <= 0) {
addLocalMinPoly( e1, e2, pt );
}
break;
case DIFFERENCE:
if (e1.polyTyp == PolyType.CLIP && e1Wc2 > 0 && e2Wc2 > 0 || e1.polyTyp == PolyType.SUBJECT && e1Wc2 <= 0 && e2Wc2 <= 0) {
addLocalMinPoly( e1, e2, pt );
}
break;
case XOR:
addLocalMinPoly( e1, e2, pt );
break;
}
}
else {
Edge.swapSides( e1, e2 );
}
}
}
private void intersectPoint( Edge edge1, Edge edge2, LongPoint[] ipV ) {
final LongPoint ip = ipV[0] = new LongPoint();
double b1, b2;
//nb: with very large coordinate values, it's possible for SlopesEqual() to
//return false but for the edge.Dx value be equal due to double precision rounding.
if (edge1.deltaX == edge2.deltaX) {
ip.setY( edge1.getCurrent().getY() );
ip.setX( Edge.topX( edge1, ip.getY() ) );
return;
}
if (edge1.getDelta().getX() == 0) {
ip.setX( edge1.getBot().getX() );
if (edge2.isHorizontal()) {
ip.setY( edge2.getBot().getY() );
}
else {
b2 = edge2.getBot().getY() - edge2.getBot().getX() / edge2.deltaX;
ip.setY( Math.round( ip.getX() / edge2.deltaX + b2 ) );
}
}
else if (edge2.getDelta().getX() == 0) {
ip.setX( edge2.getBot().getX() );
if (edge1.isHorizontal()) {
ip.setY( edge1.getBot().getY() );
}
else {
b1 = edge1.getBot().getY() - edge1.getBot().getX() / edge1.deltaX;
ip.setY( Math.round( ip.getX() / edge1.deltaX + b1 ) );
}
}
else {
b1 = edge1.getBot().getX() - edge1.getBot().getY() * edge1.deltaX;
b2 = edge2.getBot().getX() - edge2.getBot().getY() * edge2.deltaX;
final double q = (b2 - b1) / (edge1.deltaX - edge2.deltaX);
ip.setY( Math.round( q ) );
if (Math.abs( edge1.deltaX ) < Math.abs( edge2.deltaX )) {
ip.setX( Math.round( edge1.deltaX * q + b1 ) );
}
else {
ip.setX( Math.round( edge2.deltaX * q + b2 ) );
}
}
if (ip.getY() < edge1.getTop().getY() || ip.getY() < edge2.getTop().getY()) {
if (edge1.getTop().getY() > edge2.getTop().getY()) {
ip.setY( edge1.getTop().getY() );
}
else {
ip.setY( edge2.getTop().getY() );
}
if (Math.abs( edge1.deltaX ) < Math.abs( edge2.deltaX )) {
ip.setX( Edge.topX( edge1, ip.getY() ) );
}
else {
ip.setX( Edge.topX( edge2, ip.getY() ) );
}
}
//finally, don't allow 'ip' to be BELOW curr.getY() (ie bottom of scanbeam) ...
if (ip.getY() > edge1.getCurrent().getY()) {
ip.setY( edge1.getCurrent().getY() );
//better to use the more vertical edge to derive X ...
if (Math.abs( edge1.deltaX ) > Math.abs( edge2.deltaX )) {
ip.setX( Edge.topX( edge2, ip.getY() ) );
}
else {
ip.setX( Edge.topX( edge1, ip.getY() ) );
}
}
}
private void joinCommonEdges() {
for (int i = 0; i < joins.size(); i++) {
final Join join = joins.get( i );
final OutRec outRec1 = getOutRec( join.outPt1.idx );
OutRec outRec2 = getOutRec( join.outPt2.idx );
if (outRec1.getPoints() == null || outRec2.getPoints() == null) {
continue;
}
if (outRec1.isOpen || outRec2.isOpen) continue;
//get the polygon fragment with the correct hole state (FirstLeft)
//before calling JoinPoints() ...
OutRec holeStateRec;
if (outRec1 == outRec2) {
holeStateRec = outRec1;
}
else if (isParam1RightOfParam2( outRec1, outRec2 )) {
holeStateRec = outRec2;
}
else if (isParam1RightOfParam2( outRec2, outRec1 )) {
holeStateRec = outRec1;
}
else {
holeStateRec = Path.OutPt.getLowerMostRec( outRec1, outRec2 );
}
if (!joinPoints( join, outRec1, outRec2 )) {
continue;
}
if (outRec1 == outRec2) {
//instead of joining two polygons, we've just created a new one by
//splitting one polygon into two.
outRec1.setPoints( join.outPt1 );
outRec1.bottomPt = null;
outRec2 = createOutRec();
outRec2.setPoints( join.outPt2 );
//update all OutRec2.Pts Idx's ...
updateOutPtIdxs( outRec2 );
//We now need to check every OutRec.FirstLeft pointer. If it points
//to OutRec1 it may need to point to OutRec2 instead ...
if (usingPolyTree) {
for (int j = 0; j < polyOuts.size() - 1; j++) {
final OutRec oRec = polyOuts.get( j );
if (oRec.getPoints() == null || parseFirstLeft(oRec.firstLeft) != outRec1 || oRec.isHole == outRec1.isHole) {
continue;
}
if (poly2ContainsPoly1( oRec.getPoints(), join.outPt2 )) {
oRec.firstLeft = outRec2;
}
}
}
if (poly2ContainsPoly1( outRec2.getPoints(), outRec1.getPoints() )) {
//outRec2 is contained by outRec1 ...
outRec2.isHole = !outRec1.isHole;
outRec2.firstLeft = outRec1;
//fixup FirstLeft pointers that may need reassigning to OutRec1
if (usingPolyTree) {
fixupFirstLefts2( outRec2, outRec1 );
}
if ((outRec2.isHole ^ reverseSolution) == outRec2.area() > 0) {
outRec2.getPoints().reversePolyPtLinks();
}
}
else if (poly2ContainsPoly1( outRec1.getPoints(), outRec2.getPoints() )) {
//outRec1 is contained by outRec2 ...
outRec2.isHole = outRec1.isHole;
outRec1.isHole = !outRec2.isHole;
outRec2.firstLeft = outRec1.firstLeft;
outRec1.firstLeft = outRec2;
//fixup FirstLeft pointers that may need reassigning to OutRec1
if (usingPolyTree) {
fixupFirstLefts2( outRec1, outRec2 );
}
if ((outRec1.isHole ^ reverseSolution) == outRec1.area() > 0) {
outRec1.getPoints().reversePolyPtLinks();
}
}
else {
//the 2 polygons are completely separate ...
outRec2.isHole = outRec1.isHole;
outRec2.firstLeft = outRec1.firstLeft;
//fixup FirstLeft pointers that may need reassigning to OutRec2
if (usingPolyTree) {
fixupFirstLefts1( outRec1, outRec2 );
}
}
}
else {
//joined 2 polygons together ...
outRec2.setPoints( null );
outRec2.bottomPt = null;
outRec2.Idx = outRec1.Idx;
outRec1.isHole = holeStateRec.isHole;
if (holeStateRec == outRec2) {
outRec1.firstLeft = outRec2.firstLeft;
}
outRec2.firstLeft = outRec1;
//fixup FirstLeft pointers that may need reassigning to OutRec1
if (usingPolyTree) {
fixupFirstLefts2( outRec2, outRec1 );
}
}
}
}
private long popScanbeam() {
LOGGER.entering( DefaultClipper.class.getName(), "popBeam" );
final long y = scanbeam.y;
scanbeam = scanbeam.next;
return y;
}
private void processEdgesAtTopOfScanbeam( long topY ) {
LOGGER.entering( DefaultClipper.class.getName(), "processEdgesAtTopOfScanbeam" );
Edge e = activeEdges;
while (e != null) {
//1. process maxima, treating them as if they're 'bent' horizontal edges,
// but exclude maxima with horizontal edges. nb: e can't be a horizontal.
boolean IsMaximaEdge = e.isMaxima( topY );
if (IsMaximaEdge) {
final Edge eMaxPair = e.getMaximaPair();
IsMaximaEdge = eMaxPair == null || !eMaxPair.isHorizontal();
}
if (IsMaximaEdge) {
if (strictlySimple) InsertMaxima(e.getTop().getX());
final Edge ePrev = e.prevInAEL;
doMaxima( e );
if (ePrev == null) {
e = activeEdges;
}
else {
e = ePrev.nextInAEL;
}
}
else {
//2. promote horizontal edges, otherwise update Curr.getX() and Curr.getY() ...
if (e.isIntermediate( topY ) && e.nextInLML.isHorizontal()) {
final Edge[] t = new Edge[] { e };
updateEdgeIntoAEL( t );
e = t[0];
if (e.outIdx >= 0) {
addOutPt( e, e.getBot() );
}
addEdgeToSEL( e );
}
else {
e.getCurrent().setX( Edge.topX( e, topY ) );
e.getCurrent().setY( topY );
}
//When StrictlySimple and 'e' is being touched by another edge, then
//make sure both edges have a vertex here ...
if (strictlySimple) {
final Edge ePrev = e.prevInAEL;
if (e.outIdx >= 0 && e.windDelta != 0 && ePrev != null && ePrev.outIdx >= 0 && ePrev.getCurrent().getX() == e.getCurrent().getX()
&& ePrev.windDelta != 0) {
final LongPoint ip = new LongPoint( e.getCurrent() );
setZ( ip, ePrev, e );
final Path.OutPt op = addOutPt( ePrev, ip );
final Path.OutPt op2 = addOutPt( e, ip );
addJoin( op, op2, ip ); //StrictlySimple (type-3) join
}
}
e = e.nextInAEL;
}
}
//3. Process horizontals at the Top of the scanbeam ...
processHorizontals();
maxima = null;
//4. Promote intermediate vertices ...
e = activeEdges;
while (e != null) {
if (e.isIntermediate( topY )) {
Path.OutPt op = null;
if (e.outIdx >= 0) {
op = addOutPt( e, e.getTop() );
}
final Edge[] t = new Edge[] { e };
updateEdgeIntoAEL( t );
e = t[0];
//if output polygons share an edge, they'll need joining later ...
final Edge ePrev = e.prevInAEL;
final Edge eNext = e.nextInAEL;
if (ePrev != null && ePrev.getCurrent().getX() == e.getBot().getX() && ePrev.getCurrent().getY() == e.getBot().getY() && op != null
&& ePrev.outIdx >= 0 && ePrev.getCurrent().getY() > ePrev.getTop().getY() && Edge.slopesEqual( e, ePrev, useFullRange ) && e.windDelta != 0
&& ePrev.windDelta != 0) {
final Path.OutPt op2 = addOutPt( ePrev, e.getBot() );
addJoin( op, op2, e.getTop() );
}
else if (eNext != null && eNext.getCurrent().getX() == e.getBot().getX() && eNext.getCurrent().getY() == e.getBot().getY() && op != null
&& eNext.outIdx >= 0 && eNext.getCurrent().getY() > eNext.getTop().getY() && Edge.slopesEqual( e, eNext, useFullRange ) && e.windDelta != 0
&& eNext.windDelta != 0) {
final Path.OutPt op2 = addOutPt( eNext, e.getBot() );
addJoin( op, op2, e.getTop() );
}
}
e = e.nextInAEL;
}
LOGGER.exiting( DefaultClipper.class.getName(), "processEdgesAtTopOfScanbeam" );
}
private void processHorizontal( Edge horzEdge ) {
LOGGER.entering( DefaultClipper.class.getName(), "isHorizontal" );
final Direction[] dir = new Direction[1];
final long[] horzLeft = new long[1], horzRight = new long[1];
boolean IsOpen = horzEdge.outIdx >= 0 && polyOuts.get(horzEdge.outIdx).isOpen;
getHorzDirection( horzEdge, dir, horzLeft, horzRight );
Edge eLastHorz = horzEdge, eMaxPair = null;
while (eLastHorz.nextInLML != null && eLastHorz.nextInLML.isHorizontal()) {
eLastHorz = eLastHorz.nextInLML;
}
if (eLastHorz.nextInLML == null) {
eMaxPair = eLastHorz.getMaximaPair();
}
Path.Maxima currMax = maxima;
if (currMax != null)
{
//get the first maxima in range (X) ...
if (dir[0] == Direction.LEFT_TO_RIGHT)
{
while (currMax != null && currMax.X <= horzEdge.getBot().getX())
currMax = currMax.Next;
if (currMax != null && currMax.X >= eLastHorz.getBot().getX())
currMax = null;
}
else
{
while (currMax.Next != null && currMax.Next.X < horzEdge.getBot().getX())
currMax = currMax.Next;
if (currMax.X <= eLastHorz.getTop().getX()) currMax = null;
}
}
Path.OutPt op1 = null;
for (;;) { //loop through consec. horizontal edges
final boolean IsLastHorz = horzEdge == eLastHorz;
Edge e = horzEdge.getNextInAEL( dir[0] );
while (e != null) {
//this code block inserts extra coords into horizontal edges (in output
//polygons) whereever maxima touch these horizontal edges. This helps
//'simplifying' polygons (ie if the Simplify property is set).
if (currMax != null)
{
if (dir[0] == Direction.LEFT_TO_RIGHT)
{
while (currMax != null && currMax.X < e.getCurrent().getX())
{
if (horzEdge.outIdx >= 0 && !IsOpen)
addOutPt(horzEdge, new LongPoint(currMax.X, horzEdge.getBot().getY()));
currMax = currMax.Next;
}
}
else
{
while (currMax != null && currMax.X > e.getCurrent().getX())
{
if (horzEdge.outIdx >= 0 && !IsOpen)
addOutPt(horzEdge, new LongPoint(currMax.X, horzEdge.getBot().getY()));
currMax = currMax.Prev;
}
}
};
if (dir[0] == Direction.LEFT_TO_RIGHT && e.getCurrent().getX() > horzRight[0] || dir[0] == Direction.RIGHT_TO_LEFT
&& e.getCurrent().getX() < horzLeft[0]) break;
//Also break if we've got to the end of an intermediate horizontal edge ...
//nb: Smaller Dx's are to the right of larger Dx's ABOVE the horizontal.
if (e.getCurrent().getX() == horzEdge.getTop().getX() && horzEdge.nextInLML != null &&
e.deltaX < horzEdge.nextInLML.deltaX) break;
if (horzEdge.outIdx >= 0 && !IsOpen) //note: may be done multiple times
{
op1 = addOutPt(horzEdge, e.getCurrent());
Edge eNextHorz = sortedEdges;
while (eNextHorz != null)
{
if (eNextHorz.outIdx >= 0 &&
doHorzSegmentsOverlap(horzEdge.getBot().getX(),
horzEdge.getTop().getX(), eNextHorz.getBot().getX(), eNextHorz.getTop().getX()))
{
Path.OutPt op2 = GetLastOutPt(eNextHorz);
addJoin(op2, op1, eNextHorz.getTop());
}
eNextHorz = eNextHorz.nextInSEL;
}
addGhostJoin(op1, horzEdge.getBot());
}
//OK, so far we're still in range of the horizontal Edge but make sure
//we're at the last of consec. horizontals when matching with eMaxPair
if(e == eMaxPair && IsLastHorz)
{
if (horzEdge.outIdx >= 0)
addLocalMaxPoly(horzEdge, eMaxPair, horzEdge.getTop());
deleteFromAEL(horzEdge);
deleteFromAEL(eMaxPair);
return;
}
if(dir[0] == Direction.LEFT_TO_RIGHT)
{
LongPoint Pt = new LongPoint(e.getCurrent().getX(), horzEdge.getCurrent().getY());
intersectEdges(horzEdge, e, Pt);
}
else
{
LongPoint Pt = new LongPoint(e.getCurrent().getX(), horzEdge.getCurrent().getY());
intersectEdges(e, horzEdge, Pt);
}
Edge eNext = e.getNextInAEL(dir[0]);
swapPositionsInAEL(horzEdge, e);
e = eNext;
} //end while
//Break out of loop if HorzEdge.NextInLML is not also horizontal ...
if (horzEdge.nextInLML == null || !horzEdge.nextInLML.isHorizontal()) break;
Edge[] temp = new Edge[1];
temp[0] = horzEdge;
updateEdgeIntoAEL(temp);
horzEdge = temp[0];
if (horzEdge.outIdx >= 0) addOutPt(horzEdge, horzEdge.getBot());
getHorzDirection(horzEdge, dir, horzLeft, horzRight);
} //end for (;;)
if (horzEdge.outIdx >= 0 && op1 == null)
{
op1 = GetLastOutPt(horzEdge);
Edge eNextHorz = sortedEdges;
while (eNextHorz != null)
{
if (eNextHorz.outIdx >= 0 &&
doHorzSegmentsOverlap(horzEdge.getBot().getX(),
horzEdge.getTop().getX(), eNextHorz.getBot().getX(), eNextHorz.getTop().getX()))
{
Path.OutPt op2 = GetLastOutPt(eNextHorz);
addJoin(op2, op1, eNextHorz.getTop());
}
eNextHorz = eNextHorz.nextInSEL;
}
addGhostJoin(op1, horzEdge.getTop());
}
if (horzEdge.nextInLML != null) {
if (horzEdge.outIdx >= 0) {
op1 = addOutPt( horzEdge, horzEdge.getTop());
final Edge[] t = new Edge[] { horzEdge };
updateEdgeIntoAEL( t );
horzEdge = t[0];
if (horzEdge.windDelta == 0) {
return;
}
//nb: HorzEdge is no longer horizontal here
final Edge ePrev = horzEdge.prevInAEL;
final Edge eNext = horzEdge.nextInAEL;
if (ePrev != null && ePrev.getCurrent().getX() == horzEdge.getBot().getX() && ePrev.getCurrent().getY() == horzEdge.getBot().getY()
&& ePrev.windDelta != 0 && ePrev.outIdx >= 0 && ePrev.getCurrent().getY() > ePrev.getTop().getY()
&& Edge.slopesEqual( horzEdge, ePrev, useFullRange )) {
final Path.OutPt op2 = addOutPt( ePrev, horzEdge.getBot() );
addJoin( op1, op2, horzEdge.getTop() );
}
else if (eNext != null && eNext.getCurrent().getX() == horzEdge.getBot().getX() && eNext.getCurrent().getY() == horzEdge.getBot().getY()
&& eNext.windDelta != 0 && eNext.outIdx >= 0 && eNext.getCurrent().getY() > eNext.getTop().getY()
&& Edge.slopesEqual( horzEdge, eNext, useFullRange )) {
final Path.OutPt op2 = addOutPt( eNext, horzEdge.getBot() );
addJoin( op1, op2, horzEdge.getTop() );
}
}
else {
final Edge[] t = new Edge[] { horzEdge };
updateEdgeIntoAEL( t );
horzEdge = t[0];
}
}
else {
if (horzEdge.outIdx >= 0) {
addOutPt( horzEdge, horzEdge.getTop() );
}
deleteFromAEL( horzEdge );
}
}
//------------------------------------------------------------------------------
private void processHorizontals( ) {
LOGGER.entering( DefaultClipper.class.getName(), "processHorizontals" );
Edge horzEdge = sortedEdges;
while (horzEdge != null) {
deleteFromSEL( horzEdge );
processHorizontal( horzEdge);
horzEdge = sortedEdges;
}
}
//------------------------------------------------------------------------------
private boolean processIntersections( long topY ) {
LOGGER.entering( DefaultClipper.class.getName(), "processIntersections" );
if (activeEdges == null) {
return true;
}
try {
buildIntersectList( topY );
if (intersectList.size() == 0) {
return true;
}
if (intersectList.size() == 1 || fixupIntersectionOrder()) {
processIntersectList();
}
else {
return false;
}
}
catch (final Exception e) {
sortedEdges = null;
intersectList.clear();
throw new IllegalStateException( "ProcessIntersections error", e );
}
sortedEdges = null;
return true;
}
private void processIntersectList() {
for (int i = 0; i < intersectList.size(); i++) {
final IntersectNode iNode = intersectList.get( i );
{
intersectEdges( iNode.edge1, iNode.Edge2, iNode.getPt() );
swapPositionsInAEL( iNode.edge1, iNode.Edge2 );
}
}
intersectList.clear();
}
//------------------------------------------------------------------------------
@Override
protected void reset() {
super.reset();
scanbeam = null;
maxima = null;
activeEdges = null;
sortedEdges = null;
LocalMinima lm = minimaList;
while (lm != null) {
insertScanbeam( lm.y );
lm = lm.next;
}
}
private void setHoleState( Edge e, OutRec outRec ) {
boolean isHole = false;
Edge e2 = e.prevInAEL;
while (e2 != null) {
if (e2.outIdx >= 0 && e2.windDelta != 0) {
isHole = !isHole;
if (outRec.firstLeft == null) {
outRec.firstLeft = polyOuts.get( e2.outIdx );
}
}
e2 = e2.prevInAEL;
}
if (isHole) {
outRec.isHole = true;
}
}
private void setZ( LongPoint pt, Edge e1, Edge e2 ) {
if (pt.getZ() != 0 || zFillFunction == null) {
return;
}
else if (pt.equals( e1.getBot() )) {
pt.setZ( e1.getBot().getZ() );
}
else if (pt.equals( e1.getTop() )) {
pt.setZ( e1.getTop().getZ() );
}
else if (pt.equals( e2.getBot() )) {
pt.setZ( e2.getBot().getZ() );
}
else if (pt.equals( e2.getTop() )) {
pt.setZ( e2.getTop().getZ() );
}
else {
zFillFunction.zFill( e1.getBot(), e1.getTop(), e2.getBot(), e2.getTop(), pt );
}
}
private void swapPositionsInAEL( Edge edge1, Edge edge2 ) {
LOGGER.entering( DefaultClipper.class.getName(), "swapPositionsInAEL" );
//check that one or other edge hasn't already been removed from AEL ...
if (edge1.nextInAEL == edge1.prevInAEL || edge2.nextInAEL == edge2.prevInAEL) {
return;
}
if (edge1.nextInAEL == edge2) {
final Edge next = edge2.nextInAEL;
if (next != null) {
next.prevInAEL = edge1;
}
final Edge prev = edge1.prevInAEL;
if (prev != null) {
prev.nextInAEL = edge2;
}
edge2.prevInAEL = prev;
edge2.nextInAEL = edge1;
edge1.prevInAEL = edge2;
edge1.nextInAEL = next;
}
else if (edge2.nextInAEL == edge1) {
final Edge next = edge1.nextInAEL;
if (next != null) {
next.prevInAEL = edge2;
}
final Edge prev = edge2.prevInAEL;
if (prev != null) {
prev.nextInAEL = edge1;
}
edge1.prevInAEL = prev;
edge1.nextInAEL = edge2;
edge2.prevInAEL = edge1;
edge2.nextInAEL = next;
}
else {
final Edge next = edge1.nextInAEL;
final Edge prev = edge1.prevInAEL;
edge1.nextInAEL = edge2.nextInAEL;
if (edge1.nextInAEL != null) {
edge1.nextInAEL.prevInAEL = edge1;
}
edge1.prevInAEL = edge2.prevInAEL;
if (edge1.prevInAEL != null) {
edge1.prevInAEL.nextInAEL = edge1;
}
edge2.nextInAEL = next;
if (edge2.nextInAEL != null) {
edge2.nextInAEL.prevInAEL = edge2;
}
edge2.prevInAEL = prev;
if (edge2.prevInAEL != null) {
edge2.prevInAEL.nextInAEL = edge2;
}
}
if (edge1.prevInAEL == null) {
activeEdges = edge1;
}
else if (edge2.prevInAEL == null) {
activeEdges = edge2;
}
LOGGER.exiting( DefaultClipper.class.getName(), "swapPositionsInAEL" );
}
//------------------------------------------------------------------------------;
private void swapPositionsInSEL( Edge edge1, Edge edge2 ) {
if (edge1.nextInSEL == null && edge1.prevInSEL == null) {
return;
}
if (edge2.nextInSEL == null && edge2.prevInSEL == null) {
return;
}
if (edge1.nextInSEL == edge2) {
final Edge next = edge2.nextInSEL;
if (next != null) {
next.prevInSEL = edge1;
}
final Edge prev = edge1.prevInSEL;
if (prev != null) {
prev.nextInSEL = edge2;
}
edge2.prevInSEL = prev;
edge2.nextInSEL = edge1;
edge1.prevInSEL = edge2;
edge1.nextInSEL = next;
}
else if (edge2.nextInSEL == edge1) {
final Edge next = edge1.nextInSEL;
if (next != null) {
next.prevInSEL = edge2;
}
final Edge prev = edge2.prevInSEL;
if (prev != null) {
prev.nextInSEL = edge1;
}
edge1.prevInSEL = prev;
edge1.nextInSEL = edge2;
edge2.prevInSEL = edge1;
edge2.nextInSEL = next;
}
else {
final Edge next = edge1.nextInSEL;
final Edge prev = edge1.prevInSEL;
edge1.nextInSEL = edge2.nextInSEL;
if (edge1.nextInSEL != null) {
edge1.nextInSEL.prevInSEL = edge1;
}
edge1.prevInSEL = edge2.prevInSEL;
if (edge1.prevInSEL != null) {
edge1.prevInSEL.nextInSEL = edge1;
}
edge2.nextInSEL = next;
if (edge2.nextInSEL != null) {
edge2.nextInSEL.prevInSEL = edge2;
}
edge2.prevInSEL = prev;
if (edge2.prevInSEL != null) {
edge2.prevInSEL.nextInSEL = edge2;
}
}
if (edge1.prevInSEL == null) {
sortedEdges = edge1;
}
else if (edge2.prevInSEL == null) {
sortedEdges = edge2;
}
}
private void updateEdgeIntoAEL( Edge[] eV ) {
Edge e = eV[0];
if (e.nextInLML == null) {
throw new IllegalStateException( "UpdateEdgeIntoAEL: invalid call" );
}
final Edge AelPrev = e.prevInAEL;
final Edge AelNext = e.nextInAEL;
e.nextInLML.outIdx = e.outIdx;
if (AelPrev != null) {
AelPrev.nextInAEL = e.nextInLML;
}
else {
activeEdges = e.nextInLML;
}
if (AelNext != null) {
AelNext.prevInAEL = e.nextInLML;
}
e.nextInLML.side = e.side;
e.nextInLML.windDelta = e.windDelta;
e.nextInLML.windCnt = e.windCnt;
e.nextInLML.windCnt2 = e.windCnt2;
eV[0] = e = e.nextInLML;
e.setCurrent( e.getBot() );
e.prevInAEL = AelPrev;
e.nextInAEL = AelNext;
if (!e.isHorizontal()) {
insertScanbeam( e.getTop().getY() );
}
}
private void updateOutPtIdxs( OutRec outrec ) {
Path.OutPt op = outrec.getPoints();
do {
op.idx = outrec.Idx;
op = op.prev;
}
while (op != outrec.getPoints());
}
private void updateWindingCount( Edge edge ) {
LOGGER.entering( DefaultClipper.class.getName(), "updateWindingCount" );
Edge e = edge.prevInAEL;
//find the edge of the same polytype that immediately preceeds 'edge' in AEL
while (e != null && (e.polyTyp != edge.polyTyp || e.windDelta == 0)) {
e = e.prevInAEL;
}
if (e == null) {
edge.windCnt = edge.windDelta == 0 ? 1 : edge.windDelta;
edge.windCnt2 = 0;
e = activeEdges; //ie get ready to calc WindCnt2
}
else if (edge.windDelta == 0 && clipType != ClipType.UNION) {
edge.windCnt = 1;
edge.windCnt2 = e.windCnt2;
e = e.nextInAEL; //ie get ready to calc WindCnt2
}
else if (edge.isEvenOddFillType( clipFillType, subjFillType )) {
//EvenOdd filling ...
if (edge.windDelta == 0) {
//are we inside a subj polygon ...
boolean Inside = true;
Edge e2 = e.prevInAEL;
while (e2 != null) {
if (e2.polyTyp == e.polyTyp && e2.windDelta != 0) {
Inside = !Inside;
}
e2 = e2.prevInAEL;
}
edge.windCnt = Inside ? 0 : 1;
}
else {
edge.windCnt = edge.windDelta;
}
edge.windCnt2 = e.windCnt2;
e = e.nextInAEL; //ie get ready to calc WindCnt2
}
else {
//nonZero, Positive or Negative filling ...
if (e.windCnt * e.windDelta < 0) {
//prev edge is 'decreasing' WindCount (WC) toward zero
//so we're outside the previous polygon ...
if (Math.abs( e.windCnt ) > 1) {
//outside prev poly but still inside another.
//when reversing direction of prev poly use the same WC
if (e.windDelta * edge.windDelta < 0) {
edge.windCnt = e.windCnt;
}
else {
edge.windCnt = e.windCnt + edge.windDelta;
}
}
else {
//now outside all polys of same polytype so set own WC ...
edge.windCnt = edge.windDelta == 0 ? 1 : edge.windDelta;
}
}
else {
//prev edge is 'increasing' WindCount (WC) away from zero
//so we're inside the previous polygon ...
if (edge.windDelta == 0) {
edge.windCnt = e.windCnt < 0 ? e.windCnt - 1 : e.windCnt + 1;
}
else if (e.windDelta * edge.windDelta < 0) {
edge.windCnt = e.windCnt;
}
else {
edge.windCnt = e.windCnt + edge.windDelta;
}
}
edge.windCnt2 = e.windCnt2;
e = e.nextInAEL; //ie get ready to calc WindCnt2
}
//update WindCnt2 ...
if (edge.isEvenOddAltFillType( clipFillType, subjFillType )) {
//EvenOdd filling ...
while (e != edge) {
if (e.windDelta != 0) {
edge.windCnt2 = edge.windCnt2 == 0 ? 1 : 0;
}
e = e.nextInAEL;
}
}
else {
//nonZero, Positive or Negative filling ...
while (e != edge) {
edge.windCnt2 += e.windDelta;
e = e.nextInAEL;
}
}
}
} //end Clipper
⏎ com/itextpdf/text/pdf/parser/clipper/DefaultClipper.java
Or download all of them as a single archive file:
File name: itextpdf-5.5.14-fyi.zip File size: 2163839 bytes Release date: 2009-10-09 Download
⇒ iText-2.1.6.jar - iText, a JAVA-PDF library
⇐ iText layout.jar Source Code
2021-07-03, 110519👍, 0💬
