MergedSegment.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows;
using System.Diagnostics;

namespace EdgeClustering
{
    /// \author Manuel Keglevic
    /// \author Thomas Schulz
    /// <summary>
    /// Used to merge segments together depending on the corresponding KDE peaks and 
    /// a angular threshold.
    /// </summary>
    public class MergedSegment : IEquatable<MergedSegment>
    {
        public static double threshold = 15;

        /// <summary>
        /// Convenience class for storing Segments
        /// </summary>
        public class Segment {

            public Segment(int x, int y, double angle, int n)
            {
                this.x = x;
                this.y = y;
                this.angle = angle;
                this.n = n;
            }

            public int x;
            public int y;
            public double angle;
            public int n;
        };

        private double[] borders = new double[2];
        public List<Segment> segments = new List<Segment>();
        public double averageAngle; 

        public MergedSegment(Segment segment)
        {
            segments.Add(segment);
            borders[0] = segment.angle;
            borders[1] = segment.angle;

            CalculateWeightedAverage();
        }

        /// <summary>
        /// Returns the corresponding x value to the given y value <code>y</code> 
        /// for the line with point <code>P (Px, Py)</code> and gradient 
        /// <code>k</code>.
        /// </summary>
        /// <param name="y">The Y-coordinate for which the corresponding 
        /// X-coordinate should be calculated</param>
        /// <param name="k">The gradient of the line</param>
        /// <param name="Px">The X-coordinate of a linepoint <code>P</code></param>
        /// <param name="Py">The Y-coordinate of a linepoint <code>P</code></param>
        /// <returns>The X-coordinate for the passed arguments</returns>
        private double CalculateXPos(double y, double k, double Px, double Py)
        {
            return (((y - Py) / k) + Px);
        }

        /// <summary>
        /// Returns the corresponding y value to the given x value <code>x</code> 
        /// for the line with point <code>P (Px, Py)</code> and gradient 
        /// <code>k</code>.
        /// </summary>
        /// <param name="x">The X-coordinate for which the corresponding 
        /// Y-coordinate should be calculated</param>
        /// <param name="k">The gradient of the line</param>
        /// <param name="Px">The X-coordinate of a linepoint <code>P</code></param>
        /// <param name="Py">The Y-coordinate of a linepoint <code>P</code></param>
        /// <returns>The Y-coordinate for the passed arguments</returns>
        private double CalculateYPos(double x, double k, double Px, double Py)
        {
            return (Py + (x - Px) * k);
        }

        /// <summary>
        /// Returns the mesh edge for this MergedSegment, or null if the 
        /// Segment is too small.
        /// </summary>
        /// <returns>The mesh edge for this MergedSegment, or null if the 
        /// Segment is too small.</returns>
        public SimpleEdge CalculateMeshEdge()
        {
            double normal = averageAngle + 90;
            if (normal >= 180) normal -= 180;
            List<GridPoint> points = new List<GridPoint>();
            int xmin = int.MaxValue, xmax = 0, ymin = int.MaxValue, ymax = 0;

            foreach (Segment s in segments) {
                int x = s.x, y = s.y;
                points.Add(new GridPoint(x, y));
                if (x > xmax) xmax = x;
                if (x < xmin) xmin = x;
                if (y > ymax) ymax = y;
                if (y < ymin) ymin = y;
            }

            xmax++;
            ymax++;
            double xcenter = (double)(xmax + xmin) / 2.0;
            double ycenter = (double)(ymax + ymin) / 2.0;
            int maxDist = (Math.Max((xmax - xmin), (ymax - ymin)) + 1) / 2;

            double gradient = Math.Sin(normal * Math.PI / 180.0) / Math.Cos(normal * Math.PI / 180.0);

            // TODO ymax or ymax + 1 ?
            if (gradient == double.NaN)
            {
                return new SimpleEdge(new Point(xcenter, (int)ymin), new Point(xcenter, (int)ymax));
            }

            List<GridPoint> possiblePoints = new List<GridPoint>();
            GridPoint tmp = null;

            // find points along the normal in the segment
            #region Find possible points
            for (int offset = 0; offset <= maxDist; offset++) {
                int x = (int)xcenter, y = (int)ycenter;
                // move if ...contains(...) for efficiency
                if (offset == 0)
                {
                    if (x != xcenter || y != ycenter)
                    {
                        if (points.Contains(tmp = new GridPoint(x, y)))
                            possiblePoints.Add(tmp);
                    }
                    else if (gradient >= 0 && points.Contains(tmp = new GridPoint(x, y)))
                        possiblePoints.Add(tmp);
                }
                else
                {
                    double ycalcplusd = CalculateYPos(x + offset, gradient, xcenter, ycenter);
                    int ycalcplus = (int)ycalcplusd;
                    if (ycalcplusd - ycalcplus == 0)
                    {
                        if (gradient < 0 && points.Contains(tmp = new GridPoint(x + offset, ycalcplus - 1)))
                            possiblePoints.Add(tmp);
                        else if (gradient >= 0 && points.Contains(tmp = new GridPoint(x + offset, ycalcplus)))
                            possiblePoints.Add(tmp);
                    }
                    else if (points.Contains(tmp = new GridPoint(x + offset, ycalcplus)))
                        possiblePoints.Add(tmp);

                    double xcalcplusd = CalculateXPos(y + offset, gradient, xcenter, ycenter);
                    int xcalcplus = (int)xcalcplusd;
                    if (xcalcplusd - xcalcplus == 0)
                    {
                        if (gradient < 0 && xcalcplusd - xcalcplus == 0 && points.Contains(tmp = new GridPoint(xcalcplus - 1, y + offset)))
                            possiblePoints.Add(tmp);
                        else if (gradient > 0 && points.Contains(tmp = new GridPoint(xcalcplus, y + offset)))
                            possiblePoints.Add(tmp);
                    }
                    else if (points.Contains(tmp = new GridPoint(xcalcplus, y + offset)))
                        possiblePoints.Add(tmp);

                    double ycalcminusd = CalculateYPos(x - offset + 1, gradient, xcenter, ycenter);
                    int ycalcminus = (int)ycalcminusd;
                    if (ycalcminusd - ycalcminus == 0)
                    {
                        if (gradient > 0 && points.Contains(tmp = new GridPoint(x - offset, ycalcminus - 1)))
                            possiblePoints.Add(tmp);
                        else if (gradient <= 0 && points.Contains(tmp = new GridPoint(x - offset, ycalcminus)))
                            possiblePoints.Add(tmp);
                    }
                    else if (points.Contains(tmp = new GridPoint(x - offset, ycalcminus)))
                        possiblePoints.Add(tmp);

                    double xcalcminusd = CalculateXPos(y - offset + 1, gradient, xcenter, ycenter);
                    int xcalcminus = (int)xcalcminusd;
                    if (xcalcminusd - xcalcminus == 0)
                    {
                        if (gradient > 0 && points.Contains(tmp = new GridPoint(xcalcminus - 1, y - offset)))
                            possiblePoints.Add(tmp);
                        else if (gradient < 0 && points.Contains(tmp = new GridPoint(xcalcminus, y - offset)))
                            possiblePoints.Add(tmp);
                    }
                    else if (points.Contains(tmp = new GridPoint(xcalcminus, y - offset)))
                        possiblePoints.Add(tmp);
                }
            }
            #endregion

            // if there are no possible points, return null
            if (possiblePoints.Count == 0) return null;

            // find min and max
            #region Min and Max of possible points
            GridPoint[] p = new GridPoint[4];
            p[0] = new GridPoint(int.MaxValue, int.MaxValue);   // xmin
            p[1] = new GridPoint(0, 0);     // xmax
            p[2] = new GridPoint(int.MaxValue, int.MaxValue);   // ymin
            p[3] = new GridPoint(0, 0);     // ymax
            xmin = int.MaxValue;
            xmax = 0;
            ymin = int.MaxValue;
            ymax = 0;

            foreach (GridPoint po in possiblePoints) {
                if (po.X <= p[0].X && ( (po.X != p[0].X) || ((po.Y < p[0].Y) && (gradient > 0)) || ((po.Y > p[0].Y) && (gradient < 0)) )) p[0] = po;
                if (po.X >= p[1].X && ( (po.X != p[1].X) || ((po.Y > p[1].Y) && (gradient > 0)) || ((po.Y < p[1].Y) && (gradient < 0)) )) p[1] = po;
                if (po.Y <= p[2].Y) p[2] = po;
                if (po.Y >= p[3].Y) p[3] = po;

                if (po.X > xmax) xmax = po.X;
                if (po.X < xmin) xmin = po.X;
                if (po.Y > ymax) ymax = po.Y;
                if (po.Y < ymin) ymin = po.Y;
            }

            GridPoint gpmin, gpmax;
            bool ymode = false;

            if (p[0].X != p[1].X)
            {
                gpmin = p[0];
                gpmax = p[1];
            }
            else
            {
                ymode = true;
                gpmin = p[2];
                gpmax = p[3];
            }
            #endregion

            // calculate exact coordinates of min and max
            Point min = new Point (gpmin.X, gpmin.Y), max = new Point(gpmax.X, gpmax.Y);
            #region Exact coordinates for gradient != 0
            if (gradient > 0)
            {
                double ycalc = CalculateYPos(gpmin.X, gradient, xcenter, ycenter);
                if (ycalc - gpmin.Y <= 1 && ycalc - gpmin.Y >= 0)
                {
                    min.X = gpmin.X;
                    min.Y = ycalc;
                }
                else
                {
                    double xcalc = CalculateXPos(gpmin.Y, gradient, xcenter, ycenter);
                    if (xcalc - gpmin.X > 1 || xcalc - gpmin.X < 0) 
                        Console.WriteLine("Something's wrong! - MergedSegments#CalculateMeshEdge():[calculate exact coordinates]");
                    min.X = xcalc;
                    min.Y = gpmin.Y;
                }
                ycalc = CalculateYPos(gpmax.X + 1, gradient, xcenter, ycenter);
                if (ycalc - gpmax.Y <= 1 && ycalc - gpmax.Y >= 0)
                {
                    max.X = gpmax.X + 1;
                    max.Y = ycalc;
                }
                else
                {
                    double xcalc = CalculateXPos(gpmax.Y + 1, gradient, xcenter, ycenter);
                    if (xcalc - gpmax.X > 1 || xcalc - gpmax.X < 0) 
                        Console.WriteLine("Something's wrong! - MergedSegments#CalculateMeshEdge():[calculate exact coordinates]");
                    max.X = xcalc;
                    max.Y = gpmax.Y + 1;
                }
            }
            else if (gradient < 0)
            {
                if (ymode) // min and max are swapped
                {
                    double ycalc = CalculateYPos(gpmin.X + 1, gradient, xcenter, ycenter);
                    if (ycalc - gpmin.Y <= 1 && ycalc - gpmin.Y >= 0)
                    {
                        min.X = gpmin.X + 1;
                        min.Y = ycalc;
                    }
                    else
                    {
                        double xcalc = CalculateXPos(gpmin.Y, gradient, xcenter, ycenter);
                        if (xcalc - gpmin.X > 1 || xcalc - gpmin.X < 0)
                            Console.WriteLine("Something's wrong! - MergedSegments#CalculateMeshEdge():[calculate exact coordinates]");
                        min.X = xcalc;
                        min.Y = gpmin.Y;
                    }

                    ycalc = CalculateYPos(gpmax.X, gradient, xcenter, ycenter);
                    if (ycalc - gpmax.Y <= 1 && ycalc - gpmax.Y >= 0)
                    {
                        max.X = gpmax.X;
                        max.Y = ycalc;
                    }
                    else
                    {
                        double xcalc = CalculateXPos(gpmax.Y + 1, gradient, xcenter, ycenter);
                        if (xcalc - gpmax.X > 1 || xcalc - gpmax.X < 0)
                            Console.WriteLine("Something's wrong! - MergedSegments#CalculateMeshEdge():[calculate exact coordinates]");
                        max.X = xcalc;
                        max.Y = gpmax.Y + 1;
                    }
                }
                else
                {
                    double ycalc = CalculateYPos(gpmin.X, gradient, xcenter, ycenter);
                    if (ycalc - gpmin.Y <= 1 && ycalc - gpmin.Y >= 0)
                    {
                        min.X = gpmin.X;
                        min.Y = ycalc;
                    }
                    else
                    {
                        double xcalc = CalculateXPos(gpmin.Y + 1, gradient, xcenter, ycenter);
                        if (xcalc - gpmin.X > 1 || xcalc - gpmin.X < 0)
                            Console.WriteLine("Something's wrong! - MergedSegments#CalculateMeshEdge():[calculate exact coordinates]");
                        min.X = xcalc;
                        min.Y = gpmin.Y + 1;
                    }

                    ycalc = CalculateYPos(gpmax.X + 1, gradient, xcenter, ycenter);
                    if (ycalc - gpmax.Y <= 1 && ycalc - gpmax.Y >= 0)
                    {
                        max.X = gpmax.X + 1;
                        max.Y = ycalc;
                    }
                    else
                    {
                        double xcalc = CalculateXPos(gpmax.Y, gradient, xcenter, ycenter);
                        if (xcalc - gpmax.X > 1 || xcalc - gpmax.X < 0)
                            Console.WriteLine("Something's wrong! - MergedSegments#CalculateMeshEdge():[calculate exact coordinates]");
                        max.X = xcalc;
                        max.Y = gpmax.Y;
                    }
                }
            }
            #endregion

            Console.WriteLine("(" + min.X + "; " + min.Y + ") - (" + max.X + "; " + max.Y + ")");

            return new SimpleEdge(min, max);
        }
       
        /// <summary>
        /// Merges the angular boardes of two MergedSegments. This is used to check if two
        /// MergedSegments can be merged.
        /// </summary>
        /// <param name="b1">angular boarder one</param>
        /// <param name="b2">angular boarder two</param>
        /// <returns></returns>
        public double[] MergeBorders(double[] b1, double[] b2)
        {
            //boardes 
            double[] borders = { b1[0], b1[1], b2[0], b2[1] };
            
            double[] minMax = { 180, 0 };
            foreach (double b in borders)
            {
                if(b < minMax[0])
                    minMax[0] = b;
                if(b > minMax[1])
                    minMax[1] = b;  
            }

            double[] med = {minMax[0],minMax[1]};
            //double split = (minMax[1] - minMax[0]) / 2.0;

            foreach (double b in borders)
            {
                if (b < 90 && b > med[0])
                    med[0] = b;
                if (b > 90 && b < med[1])
                    med[1] = b;
            }

            if (Math.Abs(minMax[1] - minMax[0]) <= threshold)
                return minMax;

            if (Math.Abs(med[1] - med[0]) >= 180.0 - threshold)
                return med;

            return null;
        }

        /// <summary>
        /// Checks if two MergedSegments are 8-Way Connected.
        /// </summary>
        /// <param name="segment"></param>
        /// <returns>true if connected, otherwise false</returns>
        private bool CheckConnectivity(MergedSegment segment)
        {
            int xDiff, yDiff;

            foreach (Segment s1 in this.segments)
            {
                foreach (Segment s2 in segment.segments)
                {
                    xDiff = Math.Abs(s1.x - s2.x);
                    yDiff = Math.Abs(s1.y - s2.y);

                    if (xDiff <= 1 && yDiff <= 1)
                        return true;
                }
            }
            return false;

            //return true;
        }

        /// <summary>
        /// Calculates the weighted average angle of all segment edges representing all segments
        /// in the MergedSegment.
        /// </summary>
        private void CalculateWeightedAverage()
        {
            double diff = Math.Abs(borders[0] - borders[1]);
            int n = 0;
            double sum = 0;

            foreach (Segment s in segments)
            {
                if (diff > threshold)
                    Console.WriteLine("Stop");
                //Wegen dem Rund herum zeig
                if (diff > threshold && s.angle > 90)
                {
                    sum += (s.angle - 180) * s.n;

                }
                else
                    sum += s.angle * s.n;
               
                n += s.n;
            }

            //Normalize
            sum /= n;

            //Wieder zurück drehen fall kleiner 0
            if (sum < 0)
                sum += 180;

            if (sum == 0)
                Console.WriteLine("Stop");
            averageAngle = sum;
        }

        /// <summary>
        /// Add another MergedSegment to this MergedSegment.
        /// </summary>
        /// <param name="segment"></param>
        public void AddMergedSegment(MergedSegment segment)
        {
            double[] bnew = MergeBorders(borders, segment.borders);

            if (bnew != null)
            {
                if (CheckConnectivity(segment))
                {
                    segments.AddRange(segment.segments);
                    borders = bnew;
                    CalculateWeightedAverage();
                }
            }
        }

        public bool Equals(MergedSegment other)
        {
            if (MergeBorders(this.borders, other.borders) != null)
                if(CheckConnectivity(other))
                    return true;
         
            return false;
        }

        public override bool Equals(Object obj)
        {
            if (obj == null) return base.Equals(obj);

            if (!(obj is MergedSegment))
                throw new InvalidCastException("The 'obj' argument is not a MergedSegment object.");
            else
                return Equals(obj as MergedSegment);
        }

        public override int GetHashCode()
        {
            return this.GetHashCode();
        }
    }
}

---