package com.sundablog.clipper;
import com.sundablog.clipper.Path.Join;
import com.sundablog.clipper.Path.OutRec;
import com.sundablog.clipper.Point.LongPoint;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.logging.Level;
import java.util.logging.Logger;
/**
* DefaultClipper类 - 多边形裁剪器的主要实现类
* 继承自ClipperBase，提供了多边形裁剪算法的完整实现，包括:
* 1. 多边形之间的交集、并集、差集、异或操作
* 2. 多边形简化处理
* 3. Minkowski和与差计算
* 4. 支持开放和闭合路径的裁剪
*/
public class DefaultClipper extends ClipperBase {
/**
* 相交节点内部类 - 用于存储边之间的交点信息
*/
private class IntersectNode {
/** 第一个边 */
Edge edge1;
/** 第二个边 */
Edge Edge2;
/** 交点坐标 */
private LongPoint pt;
/** 获取交点坐标 */
LongPoint getPt() {
return pt;
}
/** 设置交点坐标 */
void setPt( LongPoint pt ) {
this.pt = pt;
}
}
/**
* 获取水平边的方向和范围
* @param HorzEdge 水平边
* @param Dir 方向数组（输出参数）
* @param Left 左边界数组（输出参数）
* @param Right 右边界数组（输出参数）
*/
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;
}
}
/**
* 计算两个线段的重叠范围
* @param a1 第一个线段起点坐标
* @param a2 第一个线段终点坐标
* @param b1 第二个线段起点坐标
* @param b2 第二个线段终点坐标
* @param Left 重叠区域左边界（输出参数）
* @param Right 重叠区域右边界（输出参数）
* @return 是否存在重叠
*/
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];
}
/**
* 检查第一个输出区域是否在第二个输出区域的右侧
* @param outRec1 第一个输出区域
* @param outRec2 第二个输出区域
* @return 如果outRec1在outRec2右侧返回true
*/
private static boolean isOutRec1RightOfOutRec2(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
/**
* 点在多边形内判断算法
* 基于Hormann & Agathos的"任意多边形的点在内问题"算法
* @param pt 待测试点
* @param op 多边形的输出点链表
* @return 0:点在多边形外, +1:点在多边形内, -1:点在多边形边界上
*/
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;
}
//------------------------------------------------------------------------------
/**
* 连接两条水平边
* @param op1 第一个输出点
* @param op1b 第一个输出点边界
* @param op2 第二个输出点
* @param op2b 第二个输出点边界
* @param Pt 连接点
* @param DiscardLeft 是否丢弃左侧
* @return 是否成功连接
*/
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( new LongPoint( 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( new LongPoint( 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( new LongPoint( 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( new LongPoint( 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;
}
/**
* 连接两个多边形点
* @param j 连接对象
* @param outRec1 第一个输出区域
* @param outRec2 第二个输出区域
* @return 是否成功连接
*/
private static 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 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() );
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() )) {
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() );
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() )) {
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;
}
}
}
/**
* Minkowski运算的核心实现
* @param pattern 模式路径
* @param path 目标路径
* @param IsSum 是否为Minkowski和运算
* @param IsClosed 路径是否闭合
* @return 运算结果路径集合
*/
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;
}
/**
* 计算两个多边形的Minkowski差
* @param poly1 第一个多边形
* @param poly2 第二个多边形
* @return Minkowski差运算结果
*/
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;
}
/**
* 计算模式多边形与路径的Minkowski和
* @param pattern 模式多边形
* @param path 目标路径
* @param pathIsClosed 路径是否闭合
* @return Minkowski和运算结果
*/
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;
}
/**
* 计算模式多边形与多个路径的Minkowski和
* @param pattern 模式多边形
* @param paths 目标路径集合
* @param pathIsClosed 路径是否闭合
* @return Minkowski和运算结果
*/
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;
}
/**
* 判断一个多边形是否包含另一个多边形
* @param outPt1 第一个多边形的输出点
* @param outPt2 第二个多边形的输出点
* @return 如果poly2包含poly1返回true
*/
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
//------------------------------------------------------------------------------
/**
* 简化单个多边形（使用奇偶填充规则）
* @param poly 待简化的多边形
* @return 简化后的多边形集合
*/
public static Paths simplifyPolygon(Path poly ) {
return simplifyPolygon( poly, PolyFillType.EVEN_ODD );
}
/**
* 简化单个多边形
* @param poly 待简化的多边形
* @param fillType 填充类型
* @return 简化后的多边形集合
*/
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;
}
/**
* 简化多个多边形（使用奇偶填充规则）
* @param polys 待简化的多边形集合
* @return 简化后的多边形集合
*/
public static Paths simplifyPolygons(Paths polys ) {
return simplifyPolygons( polys, PolyFillType.EVEN_ODD );
}
/**
* 简化多个多边形
* @param polys 待简化的多边形集合
* @param fillType 填充类型
* @return 简化后的多边形集合
*/
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;
}
/** 裁剪类型 */
private ClipType clipType;
/** 最大值对象 */
private Maxima maxima;
/** 已排序的边 */
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;
/** Z填充回调函数 */
private ZFillCallback zFillFunction;
/** 是否反转解决方案 */
private final boolean reverseSolution;
/** 是否严格简单多边形 */
private final boolean strictlySimple;
/** 日志记录器 */
private final static Logger LOGGER = Logger.getLogger( DefaultClipper.class.getName() );
/**
* 默认构造函数
*/
public DefaultClipper() {
this( 0 );
}
/**
* 构造函数，带有初始化选项
* @param InitOptions 初始化选项
*/
public DefaultClipper( int InitOptions ) //constructor
{
super( (PRESERVE_COLINEAR & InitOptions) != 0 );
scanbeam = null;
maxima = null;
activeEdges = null;
sortedEdges = null;
intersectList = new ArrayList<>();
intersectNodeComparer = ( node1, node2 ) -> {
final long i = node2.getPt().getY() - node1.getPt().getY();
if (i > 0) {
return 1;
}
else if (i < 0) {
return -1;
}
else {
return 0;
}
};
usingPolyTree = false;
joins = new ArrayList<>();
ghostJoins = new ArrayList<>();
reverseSolution = (REVERSE_SOLUTION & InitOptions) != 0;
strictlySimple = (STRICTLY_SIMPLE & InitOptions) != 0;
zFillFunction = null;
}
/**
* 将边添加到已排序边列表
* @param edge 要添加的边
*/
private void addEdgeToSEL( Edge edge ) {
LOGGER.entering( DefaultClipper.class.getName(), "addEdgeToSEL" );
//SEL pointers in PEdge are use to build transient lists of horizontal edges.
//However, since we don't need to worry about processing order, all additions
//are made to the front of the list ...
if (sortedEdges == null) {
sortedEdges = edge;
edge.prevInSEL = null;
edge.nextInSEL = null;
}
else {
edge.nextInSEL = sortedEdges;
edge.prevInSEL = null;
sortedEdges.prevInSEL = edge;
sortedEdges = edge;
}
}
/**
* 添加幽灵连接
* @param Op 输出点
* @param OffPt 偏移点
*/
private void addGhostJoin(Path.OutPt Op, LongPoint OffPt ) {
final Join j = new Join();
j.outPt1 = Op;
j.setOffPt( new LongPoint( OffPt ) );
ghostJoins.add( j );
}
/**
* 添加连接
* @param Op1 第一个输出点
* @param Op2 第二个输出点
* @param OffPt 偏移点
*/
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( new LongPoint( OffPt ) );
joins.add( j );
}
/**
* 添加局部最大多边形
* @param e1 第一个边
* @param e2 第二个边
* @param pt 点坐标
*/
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 );
}
}
/**
* 添加局部最小多边形
* @param e1 第一个边
* @param e2 第二个边
* @param pt 点坐标
* @return 输出点
*/
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 && prevE.getTop().getY() < pt.getY() && e.getTop().getY() < pt.getY()) {
long xPrev = Edge.topX( prevE, pt.getY() );
long xE = Edge.topX( e, pt.getY() );
if (xPrev == xE && e.windDelta != 0 && prevE.windDelta != 0 &&
Point.slopesEqual( new LongPoint( xPrev, pt.getY() ), prevE.getTop(), new LongPoint( xE, pt.getY() ), e.getTop() )) {
final Path.OutPt outPt = addOutPt( prevE, pt );
addJoin( result, outPt, e.getTop() );
}
}
return result;
}
/**
* 添加输出点到边
* @param e 边
* @param pt 点坐标
* @return 输出点
*/
private Path.OutPt addOutPt(Edge e, LongPoint pt ) {
LOGGER.entering( DefaultClipper.class.getName(), "addOutPt" );
if (e.outIdx < 0) {
final OutRec outRec = createOutRec();
outRec.isOpen = e.windDelta == 0;
final Path.OutPt newOp = new Path.OutPt();
outRec.setPoints( newOp );
newOp.idx = outRec.Idx;
newOp.setPt( new LongPoint( 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();
final boolean ToFront = e.side == Edge.Side.LEFT;
if (LOGGER.isLoggable( Level.FINEST )) {
LOGGER.finest( "op=" + Path.OutPt.getPointCount( op ) );
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;
}
}
/**
* 获取边的最后一个输出点
* @param e 边
* @return 输出点
*/
private Path.OutPt getLastOutPt(Edge e) {
OutRec outRec = polyOuts.get( e.outIdx );
if (e.side == Edge.Side.LEFT)
return outRec.getPoints();
else
return outRec.getPoints().prev;
}
/**
* 将两个多边形连接起来
* @param e1 第一个边
* @param e2 第二个边
*/
private void appendPolygon(Edge e1, Edge e2 ) {
LOGGER.entering( DefaultClipper.class.getName(), "appendPolygon" );
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 (isOutRec1RightOfOutRec2( outRec1, outRec2 )) {
holeStateRec = outRec2;
}
else if (isOutRec1RightOfOutRec2( outRec2, outRec1 )) {
holeStateRec = outRec1;
}
else {
holeStateRec = Path.OutPt.getLowerMostRec( outRec1, outRec2 );
}
//get the start and ends of both output polygons and
//join E2 poly onto E1 poly and delete pointers to E2 ...
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() = " + Path.OutPt.getPointCount( p1_lft ) );
LOGGER.finest( "p1_rt.getPointCount() = " + Path.OutPt.getPointCount( p1_rt ) );
LOGGER.finest( "p2_lft.getPointCount() = " + Path.OutPt.getPointCount( p2_lft ) );
LOGGER.finest( "p2_rt.getPointCount() = " + Path.OutPt.getPointCount( p2_rt ) );
//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 );
}
}
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;
}
}
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 = e1.side;
break;
}
e = e.nextInAEL;
}
outRec2.Idx = outRec1.Idx;
}
/**
* 构建交点列表
* @param topY 扫描线Y坐标
*/
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 );
if (pt[0].getY() < topY) {
pt[0] = new LongPoint( Edge.topX( e, topY ), topY );
}
final IntersectNode newNode = new IntersectNode();
newNode.edge1 = e;
newNode.Edge2 = eNext;
newNode.setPt( new LongPoint( pt[0] ) ); // TODO is new instance necessary?
intersectList.add( newNode );
swapPositionsInSEL( e, eNext );
isModified = true;
}
else {
e = eNext;
}
}
if (e.prevInSEL != null) {
e.prevInSEL.nextInSEL = null;
}
else {
break;
}
}
sortedEdges = null;
}
/**
* 构建结果多边形
* @param polyg 结果多边形集合
*/
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 = Path.OutPt.getPointCount( p );
LOGGER.finest( "cnt = " + cnt );
if (cnt < 2) {
continue;
}
final Path pg = new Path( cnt );
for (int j = 0; j < cnt; j++) {
pg.add( new LongPoint( p.getPt() ) );
p = p.prev;
}
polyg.add( pg );
}
}
/**
* 构建多边形树结果
* @param polytree 多边形树
*/
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 = Path.OutPt.getPointCount( outRec.getPoints() );
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;
}
}
/**
* 从已排序边列表中删除边
* @param e 边数组（输出参数）
* @return 是否删除成功
*/
private boolean deleteFromSEL( Edge[] e ) {
LOGGER.entering( DefaultClipper.class.getName(), "deleteFromSEL" );
//Pop edge from front of SEL (ie SEL is a FILO list)
e[0] = sortedEdges;
if (e[0] == null) {
return false;
}
final Edge oldE = e[0];
sortedEdges = e[0].nextInSEL;
if (sortedEdges != null) {
sortedEdges.prevInSEL = null;
}
oldE.nextInSEL = null;
oldE.prevInSEL = null;
return true;
}
/**
* 判断两个水平线段是否重叠
* @param seg1a 线段1的起点
* @param seg1b 线段1的终点
* @param seg2a 线段2的起点
* @param seg2b 线段2的终点
* @return 是否重叠
*/
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;
}
/**
* 处理最大值
* @param e 边
*/
private void doMaxima( Edge e ) {
final Edge eMaxPair = e.getMaximaPairEx();
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( new LongPoint( 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());
}
}
/**
* 检查两个边是否相邻
* @param inode 相交节点
* @return 是否相邻
*/
private boolean EdgesAdjacent( IntersectNode inode ) {
return inode.edge1.nextInSEL == inode.Edge2 || inode.edge1.prevInSEL == inode.Edge2;
}
/**
* 执行裁剪操作（使用奇偶填充规则）
* @param clipType 裁剪类型
* @param solution 结果路径集合
* @return 是否执行成功
*/
@Override
public boolean execute(ClipType clipType, Paths solution ) {
return execute( clipType, solution, PolyFillType.EVEN_ODD, PolyFillType.EVEN_ODD );
}
/**
* 执行裁剪操作并将结果放入多边形树（使用奇偶填充规则）
* @param clipType 裁剪类型
* @param polytree 多边形树
* @return 是否执行成功
*/
@Override
public boolean execute(ClipType clipType, PolyTree polytree ) {
return execute( clipType, polytree, PolyFillType.EVEN_ODD, PolyFillType.EVEN_ODD );
}
/**
* 执行裁剪操作
* @param clipType 裁剪类型
* @param solution 结果路径集合
* @param subjFillType 主体填充类型
* @param clipFillType 裁剪区域填充类型
* @return 是否执行成功
*/
@Override
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();
}
}
}
/**
* 执行裁剪操作并将结果放入多边形树
* @param clipType 裁剪类型
* @param polytree 多边形树
* @param subjFillType 主体填充类型
* @param clipFillType 裁剪区域填充类型
* @return 是否执行成功
*/
@Override
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;
}
}
/**
* 内部执行裁剪操作的核心方法
* @return 是否执行成功
*/
private boolean executeInternal() {
try {
reset();
sortedEdges = null;
maxima = null;
long[] botY = new long[1], topY = new long[1];
if (!popScanbeam( botY )) return false;
insertLocalMinimaIntoAEL( botY[0] );
while ( popScanbeam( topY ) || localMinimaPending()) {
processHorizontals();
ghostJoins.clear();
if (!processIntersections( topY[0] )) {
return false;
}
processEdgesAtTopOfScanbeam( topY[0] );
botY[0] = topY[0];
insertLocalMinimaIntoAEL( botY[0] );
}
//fix orientations ...
for (OutRec outRec : polyOuts) {
if (outRec.getPoints() == null || outRec.isOpen) {
continue;
}
if ((outRec.isHole ^ reverseSolution) == outRec.area() > 0) {
outRec.getPoints().reversePolyPtLinks();
}
}
joinCommonEdges();
for (OutRec outRec : polyOuts) {
if (outRec.getPoints() == null) {
continue;
}
else if (outRec.isOpen) {
fixupOutPolygon( outRec );
}
else {
fixupOutPolygon( outRec );
}
}
if (strictlySimple) {
doSimplePolygons();
}
return true;
}
//catch { return false; }
finally {
joins.clear();
ghostJoins.clear();
}
}
/**
* 修复FirstLeft指针（情况1）
* @param OldOutRec 旧输出区域
* @param NewOutRec 新输出区域
*/
private void fixupFirstLefts1(OutRec OldOutRec, OutRec NewOutRec ) {
for (OutRec outRec : polyOuts) {
final OutRec firstLeft = OutRec.parseFirstLeft( outRec.firstLeft );
if (outRec.getPoints() != null && firstLeft == OldOutRec) {
if (poly2ContainsPoly1( outRec.getPoints(), NewOutRec.getPoints() )) {
outRec.firstLeft = NewOutRec;
}
}
}
}
/**
* 修复FirstLeft指针（情况2）
* @param innerOutRec 内部输出区域
* @param outerOutRec 外部输出区域
*/
private void fixupFirstLefts2(OutRec innerOutRec, OutRec outerOutRec ) {
//A polygon has split into two such that one is now the inner of the other.
//It's possible that these polygons now wrap around other polygons, so check
//every polygon that's also contained by OuterOutRec's FirstLeft container
//(including nil) to see if they've become inner to the new inner polygon ...
final OutRec orfl = outerOutRec.firstLeft;
for (OutRec outRec : polyOuts) {
if (outRec.getPoints() == null || outRec == outerOutRec || outRec == innerOutRec) {
continue;
}
final OutRec firstLeft = OutRec.parseFirstLeft( outRec.firstLeft );
if (firstLeft != orfl && firstLeft != innerOutRec && firstLeft != outerOutRec) {
continue;
}
if (poly2ContainsPoly1( outRec.getPoints(), innerOutRec.getPoints() )) {
outRec.firstLeft = innerOutRec;
}
else if (poly2ContainsPoly1( outRec.getPoints(), outerOutRec.getPoints() )) {
outRec.firstLeft = outerOutRec;
}
else if (outRec.firstLeft == innerOutRec || outRec.firstLeft == outerOutRec) {
outRec.firstLeft = orfl;
}
}
}
/**
* 修复FirstLeft指针（情况3）
* @param oldOutRec 旧输出区域
* @param newOutRec 新输出区域
*/
private void fixupFirstLefts3(OutRec oldOutRec, OutRec newOutRec ) {
//same as FixupFirstLefts1 but doesn't call Poly2ContainsPoly1()
for (OutRec outRec : polyOuts) {
final OutRec firstLeft = OutRec.parseFirstLeft( outRec.firstLeft );
if (outRec.getPoints() != null && firstLeft == oldOutRec) {
outRec.firstLeft = newOutRec;
}
}
}
/**
* 修复交点顺序
* @return 是否成功修复
*/
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;
}
/**
* 修复输出折线
* 移除折线中连续重复的点，保持折线的平滑性和简洁性
* @param outrec 输出记录对象，包含需要修复的折线点
*/
private void fixupOutPolyline(OutRec outrec) {
Path.OutPt pp = outrec.getPoints();
Path.OutPt lastPP = pp.prev;
// 遍历所有点，查找并移除重复点
while (pp != lastPP) {
pp = pp.next;
// 检查当前点是否与其前一个点重复
if (pp.getPt() == pp.prev.getPt()) {
// 如果是最后一个点，更新lastPP
if (pp == lastPP) {
lastPP = pp.prev;
}
// 移除重复点，重新连接链表
Path.OutPt tmpPP = pp.prev;
tmpPP.next = pp.next;
pp.next.prev = tmpPP;
pp = tmpPP;
}
}
// 如果只剩下一个点，将输出点设置为null（无效折线）
if (pp == pp.prev) {
outrec.setPoints(null);
}
}
//------------------------------------------------------------------------------
/**
* 修复输出多边形
* 移除重复点并通过删除中间顶点来简化连续的平行边
* @param outRec 输出记录对象，包含需要修复的多边形点
*/
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();
// 判断是否需要保留共线点
final boolean preserveCol = preserveCollinear || strictlySimple;
// 无限循环，直到所有点都处理完毕
for (;;) {
// 检查多边形是否有效（至少需要3个不同的点）
if (pp.prev == pp || pp.prev == pp.next) {
outRec.setPoints(null);
return;
}
// 检查是否为重复点或共线边
if (pp.getPt().equals(pp.next.getPt()) || pp.getPt().equals(pp.prev.getPt())
|| Point.slopesEqual(pp.prev.getPt(), pp.getPt(), pp.next.getPt())
&& (!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);
}
/**
* 获取输出记录
* 通过索引获取对应的输出记录，并确保返回的是代表整个多边形的记录（处理合并情况）
* @param idx 输出记录的索引
* @return 有效的输出记录
*/
private OutRec getOutRec(int idx) {
OutRec outrec = polyOuts.get(idx);
// 处理可能的合并情况，确保返回根记录
while (outrec != polyOuts.get(outrec.Idx)) {
outrec = polyOuts.get(outrec.Idx);
}
return outrec;
}
/**
* 将边插入到活动边列表(AEL)
* 根据边的位置关系，将边正确插入到活动边列表的适当位置
* @param edge 要插入的边
* @param startEdge 插入的起始位置参考边，为null时从列表头部开始
*/
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;
}
}
//------------------------------------------------------------------------------
/**
* 将局部最小值插入到活动边列表(AEL)
* 处理多边形的局部最小值点，并将相关边插入到活动边列表
* @param botY 扫描线的底部Y坐标
*/
private void insertLocalMinimaIntoAEL(long botY) {
LOGGER.entering(DefaultClipper.class.getName(), "insertLocalMinimaIntoAEL");
LocalMinima[] lm = new LocalMinima[1];
// 弹出并处理所有Y坐标等于botY的局部最小值
while (popLocalMinima(botY, lm)) {
final Edge lb = lm[0].leftBound; // 左边界边
final Edge rb = lm[0].rightBound; // 右边界边
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()) {
if (rb.nextInLML != null) {
insertScanbeam(rb.nextInLML.getTop().getY());
}
addEdgeToSEL(rb);
}
else {
insertScanbeam(rb.getTop().getY());
}
}
// 如果左右边界不都存在，继续下一个局部最小值
if (lb == null || rb == null) {
continue;
}
// 如果输出多边形与水平右边界共享边，后续需要连接
if (Op1 != null && rb.isHorizontal() && ghostJoins.size() > 0 && rb.windDelta != 0) {
for (int i = 0; i < ghostJoins.size(); i++) {
// 如果水平右边界与"虚"水平线重叠，则将"虚"连接转换为实连接
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
&& Point.slopesEqual(lb.prevInAEL.getCurrent(), lb.prevInAEL.getTop(), lb.getCurrent(), lb.getTop()) && 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 && Point.slopesEqual(rb.prevInAEL.getCurrent(), rb.prevInAEL.getTop(), rb.getCurrent(), rb.getTop()) && 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) {
// 注意：计算绕组计数等时，IntersectEdges()假设在交点上方参数1在参数2的右侧
intersectEdges(rb, e, lb.getCurrent()); // 这里顺序很重要
e = e.nextInAEL;
}
}
}
}
}
//------------------------------------------------------------------------------
/**
* 处理两条边的相交
* 计算边相交点，更新绕组计数，并生成相应的输出点
* @param e1 第一条边
* @param e2 第二条边
* @param pt 相交点坐标
*/
private void intersectEdges(Edge e1, Edge e2, LongPoint pt) {
LOGGER.entering(DefaultClipper.class.getName(), "insersectEdges");
// e1在交点下方位于e2的左侧，因此除了在交点插入e1的情况外，e1在AEL中位于e2之前
final boolean e1Contributing = e1.outIdx >= 0;
final boolean e2Contributing = e2.outIdx >= 0;
setZ(pt, e1, e2);
// 如果任一边在开放路径上
if (e1.windDelta == 0 || e2.windDelta == 0) {
// 忽略subject-subject开放路径相交，除非它们都是开放路径且都是'贡献最大值'
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;
}
// 更新绕组计数
// 假设e1在交点上方位于e2的右侧
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: // EVEN_ODD, NON_ZERO
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)) {
// 两条边当前都不贡献输出
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);
}
}
}
/**
* 计算两条边的交点
* 使用代数方法精确计算两条边的交点坐标
* @param edge1 第一条边
* @param edge2 第二条边
* @param ipV 用于存储交点的数组，结果会保存在ipV[0]中
*/
private void intersectPoint(Edge edge1, Edge edge2, LongPoint[] ipV) {
final LongPoint ip = ipV[0] = new LongPoint();
double b1, b2;
// 注意：对于非常大的坐标值，由于双精度浮点数舍入误差，SlopesEqual()可能返回false
// 但edge.Dx值可能相等
if (edge1.deltaX == edge2.deltaX) {
// 平行边，取当前扫描线Y坐标
ip.setY(edge1.getCurrent().getY());
ip.setX(Edge.topX(edge1, ip.getY()));
return;
}
if (edge1.getDelta().getX() == 0) {
// edge1是垂直线
ip.setX(edge1.getBot().getX());
if (edge2.isHorizontal()) {
ip.setY(edge2.getBot().getY());
}
else {
// 计算edge2的截距并求交点
b2 = edge2.getBot().getY() - edge2.getBot().getX() / edge2.deltaX;
ip.setY(Math.round(ip.getX() / edge2.deltaX + b2));
}
}
else if (edge2.getDelta().getX() == 0) {
// edge2是垂直线
ip.setX(edge2.getBot().getX());
if (edge1.isHorizontal()) {
ip.setY(edge1.getBot().getY());
}
else {
// 计算edge1的截距并求交点
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));
// 选择更垂直的边来计算X坐标，以提高精度
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()) {
// 取较高的顶部Y坐标
if (edge1.getTop().getY() > edge2.getTop().getY()) {
ip.setY(edge1.getTop().getY());
}
else {
ip.setY(edge2.getTop().getY());
}
// 再次计算X坐标
if (Math.abs(edge1.deltaX) < Math.abs(edge2.deltaX)) {
ip.setX(Edge.topX(edge1, ip.getY()));
}
else {
ip.setX(Edge.topX(edge2, ip.getY()));
}
}
// 确保交点不高于当前扫描线底部
if (ip.getY() > edge1.getCurrent().getY()) {
ip.setY(edge1.getCurrent().getY());
// 选择更垂直的边来推导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;
}
// 获取具有正确孔洞状态的多边形片段
OutRec holeStateRec;
if (outRec1 == outRec2) {
holeStateRec = outRec1;
}
else if (isOutRec1RightOfOutRec2(outRec1, outRec2)) {
holeStateRec = outRec2;
}
else if (isOutRec1RightOfOutRec2(outRec2, outRec1)) {
holeStateRec = outRec1;
}
else {
holeStateRec = Path.OutPt.getLowerMostRec(outRec1, outRec2);
}
// 尝试连接点
if (!joinPoints(join, outRec1, outRec2)) {
continue;
}
if (outRec1 == outRec2) {
// 不是连接两个多边形，而是将一个多边形分割成两个新多边形
outRec1.setPoints(join.outPt1);
outRec1.bottomPt = null;
outRec2 = createOutRec();
outRec2.setPoints(join.outPt2);
// 更新所有OutRec2.Pts的Idx
updateOutPtIdxs(outRec2);
// 处理多边形包含关系
if (poly2ContainsPoly1(outRec2.getPoints(), outRec1.getPoints())) {
// outRec1包含outRec2
outRec2.isHole = !outRec1.isHole;
outRec2.firstLeft = outRec1;
if (usingPolyTree) {
fixupFirstLefts2(outRec2, outRec1);
}
// 根据面积和孔洞状态调整多边形方向
if ((outRec2.isHole ^ reverseSolution) == outRec2.area() > 0) {
outRec2.getPoints().reversePolyPtLinks();
}
}
else if (poly2ContainsPoly1(outRec1.getPoints(), outRec2.getPoints())) {
// outRec2包含outRec1
outRec2.isHole = outRec1.isHole;
outRec1.isHole = !outRec2.isHole;
outRec2.firstLeft = outRec1.firstLeft;
outRec1.firstLeft = outRec2;
if (usingPolyTree) {
fixupFirstLefts2(outRec1, outRec2);
}
// 调整多边形方向
if ((outRec1.isHole ^ reverseSolution) == outRec1.area() > 0) {
outRec1.getPoints().reversePolyPtLinks();
}
}
else {
// 两个多边形完全分离
outRec2.isHole = outRec1.isHole;
outRec2.firstLeft = outRec1.firstLeft;
// 修复可能需要重新分配给OutRec2的FirstLeft指针
if (usingPolyTree) {
fixupFirstLefts1(outRec1, outRec2);
}
}
}
else {
// 将两个多边形连接在一起
outRec2.setPoints(null);
outRec2.bottomPt = null;
outRec2.Idx = outRec1.Idx;
// 更新孔洞状态和FirstLeft指针
outRec1.isHole = holeStateRec.isHole;
if (holeStateRec == outRec2) {
outRec1.firstLeft = outRec2.firstLeft;
}
outRec2.firstLeft = outRec1;
// 修复可能需要重新分配给OutRec1的FirstLeft指针
if (usingPolyTree) {
fixupFirstLefts3(outRec2, outRec1);
}
}
}
}
/**
* 处理扫描线顶部的边
* 在扫描线顶部处理各种边的情况，包括顶点、水平线和中间点
* @param topY 当前扫描线的顶部Y坐标
*/
private void processEdgesAtTopOfScanbeam(long topY) {
LOGGER.entering(DefaultClipper.class.getName(), "processEdgesAtTopOfScanbeam");
Edge e = activeEdges;
while (e != null) {
// 1. 处理顶点，将其视为'弯曲'的水平边，但排除带有水平边的顶点
boolean IsMaximaEdge = e.isMaxima(topY);
if (IsMaximaEdge) {
final Edge eMaxPair = e.getMaximaPairEx();
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. 提升水平边，否则更新Curr.getX()和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);
// 设置Z值
if (e.getTop().getY() == topY) {
e.getCurrent().setZ(e.getTop().getZ());
}
else if (e.getBot().getY() == topY) {
e.getCurrent().setZ(e.getBot().getZ());
}
else {
e.getCurrent().setZ(0L);
}
}
// 严格简单模式下，如果'e'被另一条边接触，确保两条边都在此处有顶点
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); // 严格简单模式（类型3）连接
}
}
e = e.nextInAEL;
}
}
// 3. 处理扫描线顶部的水平边
processHorizontals();
maxima = null;
// 4. 提升中间顶点
e = activeEdges;
while (e != null) {
if (e.isIntermediate(topY)) {
Path.OutPt op = null;
if (e.outIdx >= 0) {
op = addOutPt(e, e.getTop());
}
// 更新边到AEL
final Edge[] t = new Edge[] { e };
updateEdgeIntoAEL(t);
e = t[0];
// 如果输出多边形共享边，后续需要连接
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() && Point.slopesEqual(e.getCurrent(), e.getTop(), ePrev.getCurrent(), ePrev.getTop()) && 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() && Point.slopesEqual(e.getCurrent(), e.getTop(), eNext.getCurrent(), eNext.getTop()) && 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");
}
/**
* 处理单条水平边
* 处理水平边与其他边的交互，生成相应的输出点和连接
* @param horzEdge 要处理的水平边
*/
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.windDelta == 0; // 判断是否为开放路径
// 获取水平边的方向和左右端点
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();
}
// 处理顶点
Maxima currMax = maxima;
if (currMax != null) {
// 获取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.getTop().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;
// 处理连续的水平边
for (;;) {
final boolean IsLastHorz = horzEdge == eLastHorz;
// 获取水平边方向上的下一个边
Edge e = horzEdge.getNextInAEL(dir[0]);
while (e != null) {
// 在水平边与顶点接触的位置插入额外坐标，帮助后续多边形简化
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;
// 如果到达中间水平边的末端，也退出循环
if (e.getCurrent().getX() == horzEdge.getTop().getX() && horzEdge.nextInLML != null && e.deltaX < horzEdge.nextInLML.deltaX) {
break;
}
// 添加输出点和连接
if (horzEdge.outIdx >= 0 && !isOpen) { // 注意：可能会多次执行
if (dir[0] == Direction.LEFT_TO_RIGHT) setZ(e.getCurrent(), horzEdge, e);
else setZ(e.getCurrent(), e, horzEdge);
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());
}
// 处理与顶点对的匹配
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) {
final LongPoint Pt = new LongPoint(e.getCurrent().getX(), horzEdge.getCurrent().getY());
intersectEdges(horzEdge, e, Pt);
}
else {
final LongPoint Pt = new LongPoint(e.getCurrent().getX(), horzEdge.getCurrent().getY());
intersectEdges(e, horzEdge, Pt);
}
// 交换位置并继续处理
final Edge eNext = e.getNextInAEL(dir[0]);
swapPositionsInAEL(horzEdge, e);
e = eNext;
} // end while
// 如果下一条边不是水平边，跳出循环
if (horzEdge.nextInLML == null || !horzEdge.nextInLML.isHorizontal()) break;
// 更新水平边并继续处理
final Edge[] t = new Edge[] { horzEdge };
updateEdgeIntoAEL(t);
horzEdge = t[0];
if (horzEdge.outIdx >= 0) {
addOutPt(horzEdge, horzEdge.getBot());
}
getHorzDirection(horzEdge, dir, horzLeft, horzRight);
} // end for (;;)
// 处理水平边结束后的情况
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;
}
// 注意：此时horzEdge不再是水平边
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)) {
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)) {
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);
}
}
//------------------------------------------------------------------------------
/**
* 处理所有水平边
* 从排序边列表(SEL)中删除并处理所有水平边
*/
private void processHorizontals() {
Edge[] horzEdge = new Edge[1];
while (deleteFromSEL(horzEdge)) {
processHorizontal(horzEdge[0]);
}
}
//------------------------------------------------------------------------------
/**
* 处理扫描线中的交点
* 构建交点列表并处理所有交点
* @param topY 当前扫描线的顶部Y坐标
* @return 如果成功处理所有交点则返回true，否则返回false
*/
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();
}
//------------------------------------------------------------------------------
/**
* 插入顶点到顶点列表
* 将顶点添加到双向链表中，保持按X坐标升序排序，忽略重复
* @param x 顶点的X坐标
*/
private void insertMaxima(long x) {
// 双向链表：按升序排序，忽略重复
final Maxima newMax = new 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 {
// 查找合适的插入位置
Maxima m = maxima;
while (m.next != null && (x >= m.next.x)) {
m = m.next;
}
if (x == m.x) {
return; // 忽略重复项
}
// 在m和m.Next之间插入newMax
newMax.next = m.next;
newMax.prev = m;
if (m.next != null) m.next.prev = newMax;
m.next = newMax;
}
}
/**
* 设置孔洞状态
* 根据前一个贡献边确定输出记录的孔洞状态和FirstLeft指针
* @param e 当前边
* @param outRec 输出记录
*/
private void setHoleState(Edge e, OutRec outRec) {
Edge e2 = e.prevInAEL;
Edge eTmp = null;
// 查找前一个贡献边
while (e2 != null) {
if (e2.outIdx >= 0 && e2.windDelta != 0) {
if (eTmp == null) {
eTmp = e2;
}
else if (eTmp.outIdx == e2.outIdx) {
eTmp = null; // 配对边
}
}
e2 = e2.prevInAEL;
}
// 根据是否找到未配对的前一个贡献边确定孔洞状态
if (eTmp == null) {
outRec.firstLeft = null;
outRec.isHole = false;
}
else {
outRec.firstLeft = polyOuts.get(eTmp.outIdx);
outRec.isHole = !outRec.firstLeft.isHole;
}
}
/**
* 设置Z坐标值
* 根据边的端点或通过回调函数设置点的Z坐标
* @param pt 要设置Z坐标的点
* @param e1 第一条边
* @param e2 第二条边
*/
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 {
// 使用回调函数计算交点的Z值
zFillFunction.zFill(e1.getBot(), e1.getTop(), e2.getBot(), e2.getTop(), pt);
}
}
//------------------------------------------------------------------------------;
/**
* 交换边在排序边列表(SEL)中的位置
* @param edge1 第一条边
* @param edge2 第二条边
*/
private void swapPositionsInSEL(Edge edge1, Edge edge2) {
// 检查边是否在SEL中
if (edge1.nextInSEL == null && edge1.prevInSEL == null) {
return;
}
if (edge2.nextInSEL == null && edge2.prevInSEL == null) {
return;
}
// 处理边相邻的情况
if (edge1.nextInSEL == edge2) {
// edge1后面是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) {
// edge2后面是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插入到edge2的位置
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插入到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;
}
}
/**
* 更新边到活动边列表(AEL)
* 将当前边替换为其下一条边，并保持AEL的连接关系
* @param eV 边数组，包含要更新的边和用于返回更新后的边
*/
private void updateEdgeIntoAEL(Edge[] eV) {
Edge e = eV[0];
if (e.nextInLML == null) {
throw new IllegalStateException("UpdateEdgeIntoAEL: invalid call");
}
// 保存当前边在AEL中的位置信息
final Edge AelPrev = e.prevInAEL;
final Edge AelNext = e.nextInAEL;
// 传递输出索引信息
e.nextInLML.outIdx = e.outIdx;
// 更新AEL中的连接关系
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(new LongPoint(e.getBot()));
e.prevInAEL = AelPrev;
e.nextInAEL = AelNext;
// 非水平边需要插入扫描线
if (!e.isHorizontal()) {
insertScanbeam(e.getTop().getY());
}
}
/**
* 更新输出点的索引
* 确保输出记录中的所有点都有正确的索引引用
* @param outrec 输出记录
*/
private void updateOutPtIdxs(OutRec outrec) {
Path.OutPt op = outrec.getPoints();
// 遍历所有点并设置索引
do {
op.idx = outrec.Idx;
op = op.prev;
}
while (op != outrec.getPoints());
}
/**
* 更新绕组计数
* 计算并设置边的绕组计数和辅助绕组计数
* @param edge 要更新绕组计数的边
*/
private void updateWindingCount(Edge edge) {
LOGGER.entering(DefaultClipper.class.getName(), "updateWindingCount");
Edge e = edge.prevInAEL;
// 找到AEL中在'edge'之前且类型相同的边
while (e != null && (e.polyTyp != edge.polyTyp || e.windDelta == 0)) {
e = e.prevInAEL;
}
// 根据不同情况初始化绕组计数
if (e == null) {
// 没有前导边的情况
PolyFillType pft;
pft = (edge.polyTyp == PolyType.SUBJECT ? subjFillType : clipFillType);
if (edge.windDelta == 0) {
edge.windCnt = (pft == PolyFillType.NEGATIVE ? -1 : 1);
}
else {
edge.windCnt = edge.windDelta;
}
edge.windCnt2 = 0;
e = activeEdges; // 准备计算WindCnt2
}
else if (edge.windDelta == 0 && clipType != ClipType.UNION) {
// 开放路径的情况
edge.windCnt = 1;
edge.windCnt2 = e.windCnt2;
e = e.nextInAEL; // 准备计算WindCnt2
}
else if (edge.isEvenOddFillType(clipFillType, subjFillType)) {
// 奇偶填充规则
if (edge.windDelta == 0) {
// 检查是否在subject多边形内部
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; // 准备计算WindCnt2
}
else {
// 非零/正负填充规则
if (e.windCnt * e.windDelta < 0) {
// 前导边正在减少绕组计数，我们在前导多边形外部
if (Math.abs(e.windCnt) > 1) {
// 在前导多边形外部但仍在另一个多边形内部
if (e.windDelta * edge.windDelta < 0) {
edge.windCnt = e.windCnt;
}
else {
edge.windCnt = e.windCnt + edge.windDelta;
}
}
else {
// 现在在所有同类型多边形外部，设置自己的绕组计数
edge.windCnt = edge.windDelta == 0 ? 1 : edge.windDelta;
}
}
else {
// 前导边正在增加绕组计数，我们在前导多边形内部
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; // 准备计算WindCnt2
}
// 更新辅助绕组计数
if (edge.isEvenOddAltFillType(clipFillType, subjFillType)) {
// 奇偶填充规则
while (e != edge) {
if (e.windDelta != 0) {
edge.windCnt2 = edge.windCnt2 == 0 ? 1 : 0;
}
e = e.nextInAEL;
}
}
else {
// 非零/正负填充规则
while (e != edge) {
edge.windCnt2 += e.windDelta;
e = e.nextInAEL;
}
}
}
} //end Clipper
最后修改：2025 年 12 月 01 日
© 允许规范转载