package com.sundablog.clipper;
import com.sundablog.clipper.Clipper.ClipType;
import com.sundablog.clipper.Clipper.Direction;
import com.sundablog.clipper.Clipper.PolyFillType;
import com.sundablog.clipper.Clipper.PolyType;
import com.sundablog.clipper.Point.LongPoint;
import java.util.logging.Logger;
/**
* Edge类表示多边形裁剪算法中的边对象
* 包含边的几何信息、多边形类型、连接关系等属性
* 以及各种用于处理边的方法，如排序、交点计算、边状态维护等
*/
class Edge {
/**
* 边在多边形中的位置方向枚举
*/
enum Side {
LEFT, // 左边
RIGHT // 右边
}
/**
* 判断边e2是否应该插入到e1之前
* 用于活动边列表(AEL)的排序
* @param e1 第一条边
* @param e2 第二条边
* @return 如果e2应该在e1前面则返回true
*/
static boolean doesE2InsertBeforeE1(Edge e1, Edge e2 ) {
if (e2.current.getX() == e1.current.getX()) {
if (e2.top.getY() > e1.top.getY()) {
return e2.top.getX() < topX( e1, e2.top.getY() );
}
else {
return e1.top.getX() > topX( e2, e1.top.getY() );
}
}
else {
return e2.current.getX() < e1.current.getX();
}
}
/**
* 判断两条边是否具有相同的斜率
* 用于检测平行线
* @param e1 第一条边
* @param e2 第二条边
* @return 如果斜率相同则返回true
*/
static boolean slopesEqual(Edge e1, Edge e2 ) {
// 使用交叉相乘比较斜率，避免浮点精度问题
return e1.getDelta().getY() * e2.getDelta().getX() == e1.getDelta().getX() * e2.getDelta().getY();
}
/**
* 交换两条边的输出索引
* @param edge1 第一条边
* @param edge2 第二条边
*/
static void swapPolyIndexes(Edge edge1, Edge edge2 ) {
final int outIdx = edge1.outIdx;
edge1.outIdx = edge2.outIdx;
edge2.outIdx = outIdx;
}
/**
* 交换两条边的方向
* @param edge1 第一条边
* @param edge2 第二条边
*/
static void swapSides(Edge edge1, Edge edge2 ) {
final Side side = edge1.side;
edge1.side = edge2.side;
edge2.side = side;
}
/**
* 计算在指定Y坐标处的X坐标值
* 用于扫描线算法中边的X坐标插值
* @param edge 边对象
* @param currentY 当前Y坐标
* @return 对应的X坐标值
*/
static long topX(Edge edge, long currentY ) {
if (currentY == edge.getTop().getY()) {
return edge.getTop().getX();
}
// 使用线性插值计算X坐标
return edge.getBot().getX() + Math.round( edge.deltaX * (currentY - edge.getBot().getY()) );
}
// 边的底部端点
private final LongPoint bot;
// 当前点（在每个新的扫描线处更新）
private final LongPoint current;
// 边的顶部端点
private final LongPoint top;
// 边的方向向量（top - bot）
private final LongPoint delta;
// 斜率的倒数（dx/dy），用于扫描线算法中的X坐标计算
double deltaX;
// 多边形类型（SUBJECT或CLIP）
PolyType polyTyp;
// 边在解多边形中的方向（LEFT或RIGHT）
Side side;
// 环绕方向增量（1或-1，取决于环绕方向）
int windDelta;
// 环绕计数
int windCnt;
// 相反多边形类型的环绕计数
int windCnt2;
// 输出索引，用于标识边属于哪个输出多边形
int outIdx;
// 边在原始多边形中的下一条边
Edge next;
// 边在原始多边形中的前一条边
Edge prev;
// 局部最小值链表中的下一条边
Edge nextInLML;
// 活动边列表中的下一条边
Edge nextInAEL;
// 活动边列表中的前一条边
Edge prevInAEL;
// 排序边列表中的下一条边
Edge nextInSEL;
// 排序边列表中的前一条边
Edge prevInSEL;
// 跳过标记常量
protected final static int SKIP = -2;
// 未分配标记常量
protected final static int UNASSIGNED = -1;
// 水平线标记常量（特殊值）
protected final static double HORIZONTAL = -3.4E+38;
// 日志记录器
private final static Logger LOGGER = Logger.getLogger( Edge.class.getName() );
/**
* 构造函数，初始化边的各种点坐标对象
*/
public Edge() {
delta = new LongPoint();
top = new LongPoint();
bot = new LongPoint();
current = new LongPoint();
}
/**
* 查找下一个局部最小值点
* 在扫描线算法中用于构建局部最小值链表
* @return 包含局部最小值点的边
*/
public Edge findNextLocMin() {
Edge e = this;
Edge e2;
for (;;) {
// 查找下一个局部最低点
while (!e.bot.equals( e.prev.bot ) || e.current.equals( e.top )) {
e = e.next;
}
// 如果找到非水平边的局部最低点
if (e.deltaX != Edge.HORIZONTAL && e.prev.deltaX != Edge.HORIZONTAL) {
break;
}
// 处理水平边的情况
while (e.prev.deltaX == Edge.HORIZONTAL) {
e = e.prev;
}
e2 = e;
while (e.deltaX == Edge.HORIZONTAL) {
e = e.next;
}
if (e.top.getY() == e.prev.bot.getY()) {
continue; // 只是中间水平边
}
// 选择正确的局部最小值
if (e2.prev.bot.getX() < e.bot.getX()) {
e = e2;
}
break;
}
return e;
}
/**
* 获取边的底部端点
* @return 底部端点坐标
*/
public LongPoint getBot() {
return bot;
}
/**
* 获取边的当前点
* @return 当前点坐标
*/
public LongPoint getCurrent() {
return current;
}
/**
* 获取边的方向向量
* @return 方向向量
*/
public LongPoint getDelta() {
return delta;
}
/**
* 获取共享同一个顶点的另一条边（最大值对）
* @return 如果存在最大值对，则返回对应的边；否则返回null
*/
public Edge getMaximaPair() {
if (next.top.equals( top ) && next.nextInLML == null) {
return next;
}
else if (prev.top.equals( top ) && prev.nextInLML == null) {
return prev;
}
return null;
}
/**
* 高级版本的getMaximaPair，还检查最大值对是否在活动边列表中
* @return 如果存在有效的最大值对，则返回对应的边；否则返回null
*/
Edge getMaximaPairEx() {
// 与getMaximaPair类似，但如果最大值对不在活动边列表中则返回null（水平线除外）
Edge result = getMaximaPair();
if (result == null || result.outIdx == Edge.SKIP ||
((result.nextInAEL == result.prevInAEL) && !result.isHorizontal())) {
return null;
}
return result;
}
/**
* 根据指定方向获取活动边列表中的下一条边
* @param direction 遍历方向（LEFT_TO_RIGHT或RIGHT_TO_LEFT）
* @return 下一条边
*/
public Edge getNextInAEL(Direction direction ) {
return direction == Direction.LEFT_TO_RIGHT ? nextInAEL : prevInAEL;
}
/**
* 获取边的顶部端点
* @return 顶部端点坐标
*/
public LongPoint getTop() {
return top;
}
/**
* 判断边是否对最终裁剪结果有贡献
* 根据填充类型和裁剪操作类型确定边是否应该被包含在结果中
* @param clipFillType 裁剪多边形的填充类型
* @param subjFillType 主体多边形的填充类型
* @param clipType 裁剪操作类型（INTERSECTION、UNION、DIFFERENCE、XOR）
* @return 如果边对结果有贡献则返回true
*/
public boolean isContributing(PolyFillType clipFillType, PolyFillType subjFillType, ClipType clipType ) {
LOGGER.entering( Edge.class.getName(), "isContributing" );
// 根据边的多边形类型确定使用哪种填充规则
PolyFillType pft, pft2;
if (polyTyp == PolyType.SUBJECT) {
pft = subjFillType;
pft2 = clipFillType;
}
else {
pft = clipFillType;
pft2 = subjFillType;
}
// 根据填充规则检查环绕计数
switch (pft) {
case EVEN_ODD:
// 如果是内部的主题线则返回false
if (windDelta == 0 && windCnt != 1) {
return false;
}
break;
case NON_ZERO:
if (Math.abs( windCnt ) != 1) {
return false;
}
break;
case POSITIVE:
if (windCnt != 1) {
return false;
}
break;
default: // PolyFillType.pftNegative
if (windCnt != -1) {
return false;
}
break;
}
// 根据裁剪操作类型和相反多边形的填充规则确定是否贡献
switch (clipType) {
case INTERSECTION:
switch (pft2) {
case EVEN_ODD:
case NON_ZERO:
return windCnt2 != 0;
case POSITIVE:
return windCnt2 > 0;
default:
return windCnt2 < 0;
}
case UNION:
switch (pft2) {
case EVEN_ODD:
case NON_ZERO:
return windCnt2 == 0;
case POSITIVE:
return windCnt2 <= 0;
default:
return windCnt2 >= 0;
}
case DIFFERENCE:
if (polyTyp == PolyType.SUBJECT) {
switch (pft2) {
case EVEN_ODD:
case NON_ZERO:
return windCnt2 == 0;
case POSITIVE:
return windCnt2 <= 0;
default:
return windCnt2 >= 0;
}
}
else {
switch (pft2) {
case EVEN_ODD:
case NON_ZERO:
return windCnt2 != 0;
case POSITIVE:
return windCnt2 > 0;
default:
return windCnt2 < 0;
}
}
case XOR:
if (windDelta == 0) {
switch (pft2) {
case EVEN_ODD:
case NON_ZERO:
return windCnt2 == 0;
case POSITIVE:
return windCnt2 <= 0;
default:
return windCnt2 >= 0;
}
}
else {
return true;
}
}
return true;
}
/**
* 判断相反多边形类型是否使用奇偶填充规则
* @param clipFillType 裁剪多边形的填充类型
* @param subjFillType 主体多边形的填充类型
* @return 如果相反多边形使用奇偶规则则返回true
*/
public boolean isEvenOddAltFillType(PolyFillType clipFillType, PolyFillType subjFillType ) {
if (polyTyp == PolyType.SUBJECT) {
return clipFillType == PolyFillType.EVEN_ODD;
}
else {
return subjFillType == PolyFillType.EVEN_ODD;
}
}
/**
* 判断当前多边形类型是否使用奇偶填充规则
* @param clipFillType 裁剪多边形的填充类型
* @param subjFillType 主体多边形的填充类型
* @return 如果当前多边形使用奇偶规则则返回true
*/
public boolean isEvenOddFillType(PolyFillType clipFillType, PolyFillType subjFillType ) {
if (polyTyp == PolyType.SUBJECT) {
return subjFillType == PolyFillType.EVEN_ODD;
}
else {
return clipFillType == PolyFillType.EVEN_ODD;
}
}
/**
* 判断边是否为水平线
* @return 如果是水平线则返回true
*/
public boolean isHorizontal() {
return delta.getY() == 0;
}
/**
* 判断边是否为中间边（非局部最小值和最大值的边）
* @param y 当前扫描线Y坐标
* @return 如果是中间边则返回true
*/
public boolean isIntermediate( double y ) {
return top.getY() == y && nextInLML != null;
}
/**
* 判断边是否为最大值边
* @param Y 当前Y坐标
* @return 如果是最大值边则返回true
*/
public boolean isMaxima( double Y ) {
return top.getY() == Y && nextInLML == null;
}
/**
* 反转水平边的方向
* 交换顶部和底部的X坐标，使它们符合边界的自然进展
* 这样它们的底部X坐标将与相邻的下部边对齐
*/
public void reverseHorizontal() {
// 交换水平边的顶部和底部X坐标
// 使其遵循边界的自然进展
long temp = top.getX();
top.setX( bot.getX() );
bot.setX( temp );
// 交换Z坐标（可能用于3D操作）
temp = top.getZ();
top.setZ( bot.getZ() );
bot.setZ( temp );
}
/**
* 设置边的底部端点
* @param bot 新的底部端点
*/
public void setBot( LongPoint bot ) {
this.bot.set( bot );
}
/**
* 设置边的当前点
* @param current 新的当前点
*/
public void setCurrent( LongPoint current ) {
this.current.set( current );
}
/**
* 设置边的顶部端点
* @param top 新的顶部端点
*/
public void setTop( LongPoint top ) {
this.top.set( top );
}
/**
* 重写toString方法，返回边的详细信息
* @return 边的字符串表示
*/
@Override
public String toString() {
return "TEdge [Bot=" + bot + ", Curr=" + current + ", Top=" + top + ", Delta=" + delta + ", Dx=" + deltaX + ", PolyTyp=" + polyTyp + ", Side=" + side
+ ", WindDelta=" + windDelta + ", WindCnt=" + windCnt + ", WindCnt2=" + windCnt2 + ", OutIdx=" + outIdx + ", Next=" + next + ", Prev="
+ prev + ", NextInLML=" + nextInLML + ", NextInAEL=" + nextInAEL + ", PrevInAEL=" + prevInAEL + ", NextInSEL=" + nextInSEL
+ ", PrevInSEL=" + prevInSEL + "]";
}
/**
* 更新边的方向向量和斜率
* 计算deltaX（dx/dy）用于扫描线算法中的X坐标计算
*/
public void updateDeltaX() {
// 计算方向向量（top - bot）
delta.setX( top.getX() - bot.getX() );
delta.setY( top.getY() - bot.getY() );
// 如果是水平线，使用特殊标记值
if (delta.getY() == 0) {
deltaX = Edge.HORIZONTAL;
}
else {
// 计算斜率的倒数（dx/dy）
deltaX = (double) delta.getX() / delta.getY();
}
}
}
最后修改：2025 年 12 月 03 日
© 允许规范转载