import java.util.ArrayList;
import java.util.List;
 
/**
 * 指紋特征點(diǎn)實(shí)體類：存儲(chǔ)特征點(diǎn)核心信息
 */
class FingerprintMinutia {
    private int x;          // 特征點(diǎn)x坐標(biāo)
    private int y;          // 特征點(diǎn)y坐標(biāo)
    private int direction;  // 特征點(diǎn)方向（0-359度，簡化為整數(shù)）
    private MinutiaType type; // 特征點(diǎn)類型：端點(diǎn)/分叉點(diǎn)
 
    // 特征點(diǎn)類型枚舉
    public enum MinutiaType {
        END_POINT,    // 端點(diǎn)
        BIFURCATION   // 分叉點(diǎn)
    }
 
    public FingerprintMinutia(int x, int y, int direction, MinutiaType type) {
        this.x = x;
        this.y = y;
        this.direction = direction % 360; // 確保方向在0-359范圍內(nèi)
        this.type = type;
    }
 
    // Getter方法
    public int getX() { return x; }
    public int getY() { return y; }
    public int getDirection() { return direction; }
    public MinutiaType getType() { return type; }
}
 
/**
 * 指紋匹配核心算法類
 */
public class FingerprintMatcher {
    // 距離權(quán)重（特征點(diǎn)坐標(biāo)相似度占比）
    private static final double DISTANCE_WEIGHT = 0.6;
    // 方向權(quán)重（特征點(diǎn)方向相似度占比）
    private static final double DIRECTION_WEIGHT = 0.3;
    // 類型權(quán)重（特征點(diǎn)類型匹配占比）
    private static final double TYPE_WEIGHT = 0.1;
    // 匹配閾值（相似度≥此值則判定匹配）
    private static final double MATCH_THRESHOLD = 0.8;
 
    /**
     * 計(jì)算兩個(gè)特征點(diǎn)的相似度
     * @param m1 待匹配指紋特征點(diǎn)
     * @param m2 模板指紋特征點(diǎn)
     * @return 單個(gè)特征點(diǎn)相似度（0-1）
     */
    private double calculateMinutiaSimilarity(FingerprintMinutia m1, FingerprintMinutia m2) {
        // 1. 計(jì)算坐標(biāo)歐式距離相似度（歸一化到0-1）
        double distance = Math.sqrt(Math.pow(m1.getX() - m2.getX(), 2) + Math.pow(m1.getY() - m2.getY(), 2));
        // 假設(shè)特征點(diǎn)坐標(biāo)范圍0-500，距離越大相似度越低
        double distanceSimilarity = Math.max(0, 1 - distance / 500);
 
        // 2. 計(jì)算方向相似度（角度差越小相似度越高）
        int directionDiff = Math.abs(m1.getDirection() - m2.getDirection());
        directionDiff = Math.min(directionDiff, 360 - directionDiff); // 取最小角度差（如350度差等價(jià)于10度）
        double directionSimilarity = Math.max(0, 1 - directionDiff / 180.0);
 
        // 3. 計(jì)算類型相似度（類型相同為1，不同為0）
        double typeSimilarity = m1.getType() == m2.getType() ? 1 : 0;
 
        // 加權(quán)求和得到單個(gè)特征點(diǎn)相似度
        return distanceSimilarity * DISTANCE_WEIGHT
                + directionSimilarity * DIRECTION_WEIGHT
                + typeSimilarity * TYPE_WEIGHT;
    }
 
    /**
     * 指紋特征點(diǎn)集匹配（最優(yōu)匹配策略：每個(gè)待匹配點(diǎn)找模板中最相似的點(diǎn)）
     * @param targetMinutiae 待匹配指紋特征點(diǎn)集
     * @param templateMinutiae 模板指紋特征點(diǎn)集
     * @return 整體相似度（0-1），及是否匹配
     */
    public MatchResult match(List<FingerprintMinutia> targetMinutiae, List<FingerprintMinutia> templateMinutiae) {
        // 空值/空集校驗(yàn)
        if (targetMinutiae == null || targetMinutiae.isEmpty() || templateMinutiae == null || templateMinutiae.isEmpty()) {
            return new MatchResult(0.0, false);
        }
 
        double totalSimilarity = 0.0;
        int matchedCount = 0;
 
        // 遍歷待匹配特征點(diǎn)，為每個(gè)點(diǎn)找模板中最相似的點(diǎn)
        for (FingerprintMinutia target : targetMinutiae) {
            double maxSimilarity = 0.0;
            for (FingerprintMinutia template : templateMinutiae) {
                double sim = calculateMinutiaSimilarity(target, template);
                if (sim > maxSimilarity) {
                    maxSimilarity = sim;
                }
            }
            // 僅當(dāng)單特征點(diǎn)相似度≥0.5時(shí)，計(jì)入有效匹配
            if (maxSimilarity >= 0.5) {
                totalSimilarity += maxSimilarity;
                matchedCount++;
            }
        }
 
        // 計(jì)算整體相似度（有效匹配點(diǎn)的平均相似度）
        double overallSimilarity = matchedCount == 0 ? 0 : totalSimilarity / matchedCount;
        boolean isMatched = overallSimilarity >= MATCH_THRESHOLD;
 
        return new MatchResult(overallSimilarity, isMatched);
    }
 
    /**
     * 匹配結(jié)果實(shí)體類
     */
    public static class MatchResult {
        private double similarity; // 整體相似度
        private boolean isMatched;  // 是否匹配
 
        public MatchResult(double similarity, boolean isMatched) {
            this.similarity = similarity;
            this.isMatched = isMatched;
        }
 
        public double getSimilarity() { return similarity; }
        public boolean isMatched() { return isMatched; }
    }
 
    // 測試用例
    public static void main(String[] args) {
        FingerprintMatcher matcher = new FingerprintMatcher();
 
        // 1. 構(gòu)建模板指紋特征點(diǎn)集（模擬真實(shí)指紋提取的特征點(diǎn)）
        List<FingerprintMinutia> template = new ArrayList<>();
        template.add(new FingerprintMinutia(100, 200, 30, FingerprintMinutia.MinutiaType.END_POINT));
        template.add(new FingerprintMinutia(150, 250, 60, FingerprintMinutia.MinutiaType.BIFURCATION));
        template.add(new FingerprintMinutia(200, 300, 90, FingerprintMinutia.MinutiaType.END_POINT));
 
        // 2. 構(gòu)建待匹配指紋1（匹配：特征點(diǎn)與模板高度相似）
        List<FingerprintMinutia> target1 = new ArrayList<>();
        target1.add(new FingerprintMinutia(102, 201, 32, FingerprintMinutia.MinutiaType.END_POINT));
        target1.add(new FingerprintMinutia(149, 252, 58, FingerprintMinutia.MinutiaType.BIFURCATION));
        target1.add(new FingerprintMinutia(201, 301, 91, FingerprintMinutia.MinutiaType.END_POINT));
 
        // 3. 構(gòu)建待匹配指紋2（不匹配：特征點(diǎn)差異大）
        List<FingerprintMinutia> target2 = new ArrayList<>();
        target2.add(new FingerprintMinutia(300, 400, 120, FingerprintMinutia.MinutiaType.END_POINT));
        target2.add(new FingerprintMinutia(350, 450, 150, FingerprintMinutia.MinutiaType.BIFURCATION));
        target2.add(new FingerprintMinutia(400, 500, 180, FingerprintMinutia.MinutiaType.END_POINT));
 
        // 4. 執(zhí)行匹配并輸出結(jié)果
        MatchResult result1 = matcher.match(target1, template);
        System.out.println("待匹配指紋1：");
        System.out.println("整體相似度：" + String.format("%.2f", result1.getSimilarity()));
        System.out.println("是否匹配：" + (result1.isMatched() ? "是" : "否"));
 
        MatchResult result2 = matcher.match(target2, template);
        System.out.println("\n待匹配指紋2：");
        System.out.println("整體相似度：" + String.format("%.2f", result2.getSimilarity()));
        System.out.println("是否匹配：" + (result2.isMatched() ? "是" : "否"));
    }
}