ControlMeshEdge.cs

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

namespace EdgeClustering
{
    /// \author Manuel Keglevic
    /// \author Thomas Schulz
    /// <summary>
    /// Edges used for Control Mesh computations.
    /// </summary>
    class ControlMeshEdge
    {
        private ControlMeshVertex v1;
        /// <summary>
        /// First vertex of the edge.
        /// </summary>
        public ControlMeshVertex V1
        {
            get { return v1; }
            set { v1 = value; UpdateBoundingBox(); }
        }

        private ControlMeshVertex v2;
        /// <summary>
        /// Second Vertex of the edge.
        /// </summary>
        public ControlMeshVertex V2
        {
            get { return v2; }
            set { v2 = value; UpdateBoundingBox(); }
        }

        //      0|1   0 | 1
        // bbox[x|y, min|max]
        private int[,] bbox;

        /// <summary>
        /// Creates a new ControlMeshEdge.
        /// </summary>
        /// <param name="v1">first Vertex of the edge.</param>
        /// <param name="v2">second Vertex of the edge.</param>
        public ControlMeshEdge(ref ControlMeshVertex v1, ref ControlMeshVertex v2)
        {
            this.v1 = v1;
            this.v2 = v2;
            UpdateBoundingBox();
        }

        /// <summary>
        /// Computes intersection points with all EnhancedEdges in <code>edges</code>
        /// and adds the weighted average as new control point to intersecting edges.
        /// 
        /// <para>
        /// Before intersection, a bounding box check is performed.
        /// </para>
        /// </summary>
        /// <param name="edges">The edges of the graph as EnhancedEdges</param>
        public void Intersect(ref List<EnhancedEdge> edges)
        {
            int[,] otherBBox;
            List<EnhancedEdge> myEdges = new List<EnhancedEdge>();
            List<Vector> points = new List<Vector>();

            Vector U1 = new Vector(v1.X, v1.Y);
            Vector U2 = new Vector(v2.X, v2.Y);
            Vector u = U2 - U1;
            double frac = u.Y / u.X; // is only used if u.X is not 0

            for (int i = 0; i < edges.Count; i++)
            {
                // check bounding boxes
                otherBBox = CalculateBoundingBoxFor(edges[i]);
                if (bbox[0, 0] > otherBBox[0, 1] || bbox[0, 1] < otherBBox[0, 0] || 
                    bbox[1, 0] > otherBBox[1, 1] || bbox[1, 1] < otherBBox[1, 0])
                    continue;

                // intersect
                Vector V1 = new Vector(edges[i].A.X, edges[i].A.Y);
                Vector V2 = new Vector(edges[i].B.X, edges[i].B.Y);
                Vector v = V2 - V1;
                Vector p;

                if (u.X != 0)
                {
                    double innerfrac = (v.Y - v.X * frac);
                    if (innerfrac == 0) continue; // lines are parallel

                    double t = (U1.Y + frac * V1.X - frac * U1.X - V1.Y) / innerfrac;
                    p = V1 + v * t;
                }
                else
                {   // control edge is vertical
                    if (v.X != 0)
                    {
                        double t = (U1.X - V1.X) / v.X;
                        double y = V1.Y + v.Y / v.X * (U1.X - V1.X);
                        p = new Vector(U1.X, y);
                    }
                    else
                    {   // parallel vertical lines
                        continue;
                    }
                }

                // check if intersection is on the linesegment
                if (!( ((p.X >= V1.X && p.X <= V2.X) || (p.X >= V2.X && p.X <= V1.X)) &&
                    ((p.Y >= V1.Y && p.Y <= V2.Y) || (p.Y >= V2.Y && p.Y <= V1.Y)) &&
                    ((p.X >= U1.X && p.X <= U2.X) || (p.X >= U2.X && p.X <= U1.X)) &&
                    ((p.Y >= U1.Y && p.Y <= U2.Y) || (p.Y >= U2.Y && p.Y <= U1.Y)) ))
                    continue;

                // add to my edges
                myEdges.Add(edges[i]);
                // add intersection point
                points.Add(p);
            }

            // if there is no valid intersection, return
            if (points.Count == 0) return;

            // compute mean of intersection points (must be ON the control mesh edge!!)
            Vector mean = new Vector();
            foreach (Vector p in points)
            {
                mean += p;
            }

            mean /= points.Count;

            Point controlPoint = new Point(mean.X, mean.Y);

            // add the new control point to my edges
            foreach (EnhancedEdge ee in myEdges)
            {
                ee.AddControlPoint(controlPoint);
            }
        }

        /// <summary>
        /// Returns the bounding box of the EnhancedEdge <code>ee</code>.
        /// 
        /// <para>
        /// The returned array has the following format: 
        /// <code>bbox[0, 0] = xmin</code>, 
        /// <code>bbox[0, 1] = xmax</code>, 
        /// <code>bbox[1, 0] = ymin</code> and
        /// <code>bbox[1, 1] = ymax</code>.
        /// </para>
        /// </summary>
        /// <param name="ee">The EnhancedEdge for which the bounding box should
        /// be calculated</param>
        /// <returns>The bounding box of <code>ee</code></returns>
        private int[,] CalculateBoundingBoxFor(EnhancedEdge ee)
        {
            int[,] bb = new int[2, 2];
            bb[0, 0] = int.MaxValue;
            bb[1, 0] = int.MaxValue;
            //assumtion: vertices have positive x & y values

            if (ee.A.X > bb[0, 1]) bb[0, 1] = (int)ee.A.X + 1;
            if (ee.A.X < bb[0, 0]) bb[0, 0] = (int)ee.A.X;
            if (ee.A.Y > bb[1, 1]) bb[1, 1] = (int)ee.A.Y + 1;
            if (ee.A.Y < bb[1, 0]) bb[1, 0] = (int)ee.A.Y;

            if (ee.B.X > bb[0, 1]) bb[0, 1] = (int)ee.B.X + 1;
            if (ee.B.X < bb[0, 0]) bb[0, 0] = (int)ee.B.X;
            if (ee.B.Y > bb[1, 1]) bb[1, 1] = (int)ee.B.Y + 1;
            if (ee.B.Y < bb[1, 0]) bb[1, 0] = (int)ee.B.Y;

            return bb;
        }

        /// <summary>
        /// Updates the bounding box of this control mesh edge.
        /// </summary>
        private void UpdateBoundingBox()
        {
            if (bbox == null)
            {
                bbox = new int[2, 2];
                bbox[0, 0] = int.MaxValue;
                bbox[1, 0] = int.MaxValue;
                //assumtion: vertices have positive x & y values
            }

            if (v1.X > bbox[0, 1]) bbox[0, 1] = (int)v1.X + 1;
            if (v1.X < bbox[0, 0]) bbox[0, 0] = (int)v1.X;
            if (v1.Y > bbox[1, 1]) bbox[1, 1] = (int)v1.Y + 1;
            if (v1.Y < bbox[1, 0]) bbox[1, 0] = (int)v1.Y;

            if (v2.X > bbox[0, 1]) bbox[0, 1] = (int)v2.X + 1;
            if (v2.X < bbox[0, 0]) bbox[0, 0] = (int)v2.X;
            if (v2.Y > bbox[1, 1]) bbox[1, 1] = (int)v2.Y + 1;
            if (v2.Y < bbox[1, 0]) bbox[1, 0] = (int)v2.Y;
        }
    }
}

---