module MatchingEllipses open System open System.Linq open System.Collections open System.Collections.Generic open Types open Utils let matchingScoreThreshold1 = 0.6 let matchingScoreThreshold2 = 1.0 type EllipseScore (matchingScore: float, e: Ellipse) = let mutable matchingScore = matchingScore member this.MatchingScore = matchingScore member this.Ellipse = e member val Processed = false with get, set member val Removed = false with get, set member this.AddMatchingScore(score: float) = matchingScore <- matchingScore + score interface KdTree.I2DCoords with member this.X = e.Cx member this.Y = e.Cy type MatchingEllipses (radiusMin: float) = let ellipses = List() member this.Add (e: Ellipse) = ellipses.Add(EllipseScore(0.0, e)) member this.Ellipses : Ellipse list = // 1) Create a kd-tree from the ellipses list. let tree = KdTree.Tree.buildTree (List.ofSeq ellipses) // 2) Compute the matching score of each ellipses. let windowSize = radiusMin for e in ellipses do e.Processed <- true let areaE = e.Ellipse.Area let window = { KdTree.minX = e.Ellipse.Cx - windowSize / 2.0 KdTree.maxX = e.Ellipse.Cx + windowSize / 2.0 KdTree.minY = e.Ellipse.Cy - windowSize / 2.0 KdTree.maxY = e.Ellipse.Cy + windowSize / 2.0 } for other in KdTree.Tree.search tree window do if not other.Processed then let areaOther = other.Ellipse.Area match EEOver.EEOverlapArea e.Ellipse other.Ellipse with | Some (commonArea, _, _) -> let matchingScore = 2.0 * commonArea / (areaE + areaOther) if matchingScore >= matchingScoreThreshold1 then other.AddMatchingScore(matchingScore) e.AddMatchingScore(matchingScore) | _ -> () // 3) Sort ellipses by their score. ellipses.Sort(fun e1 e2 -> e2.MatchingScore.CompareTo(e1.MatchingScore)) // 4) Remove ellipses wich have a low score. let i = ellipses.BinarySearch(EllipseScore(matchingScoreThreshold2, Ellipse(0.0, 0.0, 0.0, 0.0, 0.0)), { new IComparer with member this.Compare(e1, e2) = e2.MatchingScore.CompareTo(e1.MatchingScore) }) |> abs let nbToRemove = ellipses.Count - i if nbToRemove > 0 then for j in i .. nbToRemove - 1 do ellipses.[j].Removed <- true ellipses.RemoveRange(i, nbToRemove) // 5) Remove ellipses whose center is into an ellipse with a better score for e in ellipses do if not e.Removed then let window = { KdTree.minX = e.Ellipse.Cx - e.Ellipse.A KdTree.maxX = e.Ellipse.Cx + e.Ellipse.A KdTree.minY = e.Ellipse.Cy - e.Ellipse.A KdTree.maxY = e.Ellipse.Cy + e.Ellipse.A } for other in KdTree.Tree.search tree window do if not other.Removed && other.MatchingScore < e.MatchingScore then if e.Ellipse.Contains other.Ellipse.Cx other.Ellipse.Cy then other.Removed <- true ellipses.RemoveAll(fun e -> e.Removed) |> ignore List.ofSeq ellipses |> List.map (fun e -> e.Ellipse)