Detectando intersecciones entre múltiples líneas

Podemos detectar intersecciones entre líneas mediante el tipo Digi21.DigiNG.Topology.IntersectionDetector, que es una clase abstracta que define métodos de extensión sobre el tipo Digi21.DigiNG.ReadOnlyLine o sobre una secuencia de líneas IEnumerable<Digi21.DigiNG.ReadOnlyLine>.

Estos métodos de extensión disponen de varias sobrecargas que nos van a permitir filtrar el tipo de intersecciones que queremos detectar, de manera que podemos llegar a realizar consultas con un altísimo nivel de detalle, por ejemplo, podríamos realizar búsquedas tan extrañas como intersecciones entre dos líneas, la primera forzosamente con el código A y un número par de vértices y la segunda con código B y con un número par de vértices.
Las posibilidades son infinitas.

Todas las sobrecargas devuelven una secuencia objetos de Digi21.DigiNG.Entities.SegmentPointer como por ejemplo el siguiente recorte en el que te muestro la primera sobrecarga:

        public static IEnumerable<IGrouping<Point2D, SegmentPointer>> DetectIntersections(
            this IEnumerable<ReadOnlyLine> entities);

Y por su parte, el tipo SegmentPointer tiene el siguiente aspecto:

        public class SegmentPointer
        {
            public SegmentPointer(
                ReadOnlyLine line,
                int firstVertex,
                int secondVertex);

            public int FirstVertex { get; }
            public ReadOnlyLine Line { get; }
            public int SecondVertex { get; }
        }

que si te fijas tiene tres propiedades: Una que devuelve la línea implicada en la intersección, y otras dos que nos indican entre que vértices de esa línea se ha detectado la intersección. Si el valor almacenado en estas dos últimas propiedades coincide, significa que la intersección se detectó en ese vértice, y si no coinciden, las coordenadas de la intersección estarán en el segmento que une los dos vértices.

Utilizar estos métodos es trivial, tan solo tenemos que añadir una referencia al ensamblado Digi21.DigiNG.Topology, hacer visible en nuestro código el espacio de nombres Digi21.DigiNG.Topology y llamar al método de extensión que nos interese o sobre una línea o sobre una secuencia de líneas.

En este post nos vamos a centrar únicamente en los métodos de extensión que se aplican a secuencias de entidades. En el próximo post nos centraremos en las sobrecargas que se aplican a una línea en concreto.

Aquí el vídeo relacionado con este código

El siguiente código detecta las intersecciones de todas las entidades del archivo de dibujo activo, añadiendo una tarea en la ventana de tareas de la aplicación por cada intersección, de modo que cuando el usuario hace doble clic sobre la tarea se desplaza la ventana de dibujo a las coordenadas de la intersección:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Digi21.DigiNG.Plugin.Command;
using Digi21.DigiNG;
using Digi21.DigiNG.Topology;
using Digi21.Digi3D;
using Digi21.DigiNG.Entities;
using Digi21.Math;

namespace Pruebas
{
    [Command(Name = "detectar_intersecciones")]
    public class DetectarIntersecciones : Command
    {
        public DetectarIntersecciones()
        {
            this.Initialize += new EventHandler(DetectarIntersecciones_Initialize);
        }

        void DetectarIntersecciones_Initialize(object sender, EventArgs e)
        {
            var líneas = from entidad in DigiNG.DrawingFile
                         where entidad is ReadOnlyLine
                         select entidad as ReadOnlyLine;

            foreach (var intersección in líneas.DetectIntersections())
            {
                Digi3D.Tasks.Add(new TaskGotoPoint(
                    (Point3D)intersección.Key,
                    "Detectada una intersección",
                    TaskSeverity.Error,
                    DigiNG.DrawingFile.Path,
                    "detectar_intersecciones"));
            }

            Dispose();
        }
    }
}

Pero podemos hacer las cosas mejor, ya que el método lo que nos ha devuelto es una secuencia de grupos (cuya clave principal es la coordenada de la intersección), así que podríamos hacer que en la barra de tareas apareciera únicamente una tarea por cada punto en el que se ha detectado una intersección y que dicha tarea tenga como nodos hijos una subtarea por cada entidad. Al hacer doble clic sobre la tarea se desplazará la cámara a las coordenadas de la intersección, y al hacer doble clic sobre cada subtarea, se animará durante dos segundos la línea en cuestión:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Digi21.DigiNG.Plugin.Command;
using Digi21.DigiNG;
using Digi21.DigiNG.Topology;
using Digi21.Digi3D;
using Digi21.DigiNG.Entities;
using Digi21.Math;

namespace Pruebas
{
    [Command(Name = "detectar_intersecciones")]
    public class DetectarIntersecciones : Command
    {
        public DetectarIntersecciones()
        {
            this.Initialize += new EventHandler(DetectarIntersecciones_Initialize);
        }

        void DetectarIntersecciones_Initialize(object sender, EventArgs e)
        {
            var líneas = from entidad in DigiNG.DrawingFile
                         where entidad is ReadOnlyLine
                         select entidad as ReadOnlyLine;

            foreach (var intersección in líneas.DetectIntersections())
            {
                List<ITask> subtareas = new List<ITask>();
                foreach (var entidad in intersección)
                {
                    string títuloSubtarea = string.Format(
                        "Intersección entre los vértices {0} y {1}",
                        entidad.FirstVertex,
                        entidad.SecondVertex);

                    subtareas.Add(new TaskAnimateEntity(
                        entidad.Line,
                        2,
                        títuloSubtarea,
                        TaskSeverity.Error));
                }

                string títuloTarea = string.Format(
                    "Detectada una intersección en las coordenadas {0}",
                    intersección.Key);

                Digi3D.Tasks.Add(new TaskGotoPoint(
                    (Point3D)intersección.Key,
                    títuloTarea,
                    TaskSeverity.Error,
                    DigiNG.DrawingFile.Path,
                    "detectar_intersecciones",
                    subtareas.ToArray()));
            }

            Dispose();
        }
    }
}

Especializaciones

Los métodos de extensión DetectIntersections disponen de varias sobrecargas que nos van a permitir realizar búsquedas especializadas.

Aquí el vídeo relacionado con este código

La primera de ellas nos permite que pasemos un predicado de tipo Func<Point2D, bool> para indicar si queremos que se añada una determinada intersección al resultado.

Para ello vamos a modificar nuestra orden para hacer que únicamente detecte intersecciones dentro de un rango de coordenadas máximas y mínimas pasadas por parámetro.
Si el usuario no pasa parámetros a la orden, se mostrarán todas las intersecciones, y si pasa cuatro parámetros (xmin, ymin, xmax, ymax) se mostrarán únicamente las intersecciones dentro de este rango de coordenadas.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Digi21.DigiNG.Plugin.Command;
using Digi21.DigiNG;
using Digi21.DigiNG.Topology;
using Digi21.Digi3D;
using Digi21.DigiNG.Entities;
using Digi21.Math;

namespace Pruebas
{
    [Command(Name = "detectar_intersecciones")]
    public class DetectarIntersecciones : Command
    {
        private Window2D maxmin = Window2D.WholeWorld;

        public DetectarIntersecciones()
        {
            this.Initialize += new EventHandler(DetectarIntersecciones_Initialize);
        }

        void DetectarIntersecciones_Initialize(object sender, EventArgs e)
        {
            if (this.Args.Length == 4)
            {
                maxmin.Xmin = double.Parse(this.Args[0]);
                maxmin.Ymin = double.Parse(this.Args[1]);
                maxmin.Xmax = double.Parse(this.Args[2]);
                maxmin.Ymax = double.Parse(this.Args[3]);
            }

            var líneas = from entidad in DigiNG.DrawingFile
                         where entidad is ReadOnlyLine
                         select entidad as ReadOnlyLine;

            var intersecciones = líneas.DetectIntersections(
                (Point2D coordenada) => maxmin.Contains(coordenada));

            foreach (var intersección in intersecciones)
            {
                List<ITask> subtareas = new List<ITask>();
                foreach (var entidad in intersección)
                {
                    string títuloSubtarea = string.Format(
                        "Intersección entre los vértices {0} y {1}",
                        entidad.FirstVertex,
                        entidad.SecondVertex);

                    subtareas.Add(new TaskAnimateEntity(
                        entidad.Line,
                        2,
                        títuloSubtarea,
                        TaskSeverity.Error));
                }

                string títuloTarea = string.Format(
                    "Detectada una intersección en las coordenadas {0}",
                    intersección.Key);

                Digi3D.Tasks.Add(new TaskGotoPoint(
                    (Point3D)intersección.Key,
                    títuloTarea,
                    TaskSeverity.Error,
                    DigiNG.DrawingFile.Path,
                    "detectar_intersecciones",
                    subtareas.ToArray()));
            }

            Dispose();
        }
    }
}

Pero hay más sobrecargas: La siguiente nos permite indicar si queremos o no incluir una línea (mediante un predicado de tipo Func<Entity, bool>) en el proceso.

Podemos utilizar esta sobrecarga para filtrar por códigos por ejemplo.

Aquí el vídeo relacionado con este código
Veámoslo creando una nueva orden que detecta intersecciones entre las líneas con los códigos pasados por parámetro.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Digi21.DigiNG.Plugin.Command;
using Digi21.DigiNG.Topology;
using Digi21.DigiNG;
using Digi21.DigiNG.Entities;
using UtilidadesDigi;
using Digi21.Digi3D;
using Digi21.Math;

namespace Acme
{
    [Command(Name = "detectar_intersecciones_cod")]
    public class DetectarInterseccionesCod : Command
    {
        public DetectarInterseccionesCod()
        {
            this.Initialize += new EventHandler(DetectarInterseccionesCod_Initialize);
        }

        //bool MeInteresaEstaLínea(ReadOnlyLine línea)
        //{
        //    return línea.TieneAlgúnCódigo(this.Args);
        //}

        void DetectarInterseccionesCod_Initialize(object sender, EventArgs e)
        {
            try
            {
                if (this.Args.Length == 0)
                {
                    Digi3D.Music(MusicType.Error);
                    Digi3D.ShowBallon(
                        "detectar_intersecciones_cod",
                        "No has indicado los códigos de las entidades para la detección de intersecciones",
                        2,
                        BallonIcon.Error);
                    return;
                }

                var intersecciones = DigiNG.DrawingFile.SoloLíneas().DetectIntersections(
                    línea => línea.TieneAlgúnCódigo(this.Args));

                foreach (var intersección in intersecciones)
                {
                    List<ITask> subtareas = new List<ITask>();
                    foreach (var entidad in intersección)
                    {
                        string títuloSubtarea = string.Format(
                            "Intersección entre los vértices {0} y {1}",
                            entidad.FirstVertex,
                            entidad.SecondVertex);

                        subtareas.Add(new TaskAnimateEntity(
                            entidad.Line,
                            2,
                            títuloSubtarea,
                            TaskSeverity.Error));
                    }

                    Digi3D.Tasks.Add(new TaskGotoPoint(
                        (Point3D)intersección.Key,
                        "Detectada una intersección",
                        TaskSeverity.Error,
                        DigiNG.DrawingFile.Path,
                        "detectar_intersecciones",
                        subtareas.ToArray()));
                }
                DigiNG.RenderScene();

            }
            finally
            {
                Dispose();
            }
        }
    }
}

La siguiente sobrecarga nos permite especificar si permitimos analizar las intersecciones entre dos líneas. Cada vez que el algoritmo detecta que dos líneas son candidatas a tener intersecciones, el algoritmo llama a nuestro predicado para que le indiquemos si le damos permiso para analizar las intersecciones entre esas dos líneas.

Supón que quieres que únicamente se analicen las intersecciones entre línas de tipo A con líneas de tipo B, pero nunca intersecciones de líneas de tipo A con líneas de tipo A y de tipo B con tipo B

Aquí el vídeo relacionado con este código

Vamos a crear una orden nueva que esperae dos códigos y analice únicamente las intersecciones entre líneas que tengan una el primer código y otra el segundo o viceversa, pero nunca intersecciones de dos líneas con el mismo código.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Digi21.DigiNG.Plugin.Command;
using Digi21.DigiNG.Topology;
using Digi21.DigiNG;
using Digi21.DigiNG.Entities;
using UtilidadesDigi;
using Digi21.Digi3D;
using Digi21.Math;

namespace Acme
{
    [Command(Name = "detectar_intersecciones_códigos_distintos")]
    public class DetectarInterseccionesCódigosDistintos : Command
    {
        public DetectarInterseccionesCódigosDistintos()
        {
            this.Initialize += new EventHandler(DetectarInterseccionesCódigosDistintos_Initialize);
        }

        //private bool PermitoCalcularInterseccionesEntreEstasDosLíneas(ReadOnlyLine líneaA, ReadOnlyLine líneaB)
        //{
        //    return líneaA.TieneElCódigo(this.Args[0]) && líneaB.TieneElCódigo(this.Args[1]) ||
        //        líneaA.TieneElCódigo(this.Args[1]) && líneaB.TieneElCódigo(this.Args[0]);
        //}

        void DetectarInterseccionesCódigosDistintos_Initialize(object sender, EventArgs e)
        {
            try
            {
                if (this.Args.Length != 2)
                {
                    Digi3D.Music(MusicType.Error);
                    Digi3D.ShowBallon(
                        "detectar_intersecciones_códigos_distintos",
                        "No has indicado los dos códigos con los que trabajar",
                        2,
                        BallonIcon.Error);
                    return;
                }

                var intersecciones = DigiNG.DrawingFile.SoloLíneas().DetectIntersections(
                    (líneaA, líneaB) =>
                        líneaA.TieneElCódigo(this.Args[0]) && líneaB.TieneElCódigo(this.Args[1]) ||
                        líneaA.TieneElCódigo(this.Args[1]) && líneaB.TieneElCódigo(this.Args[0]));

                foreach (var intersección in intersecciones)
                {
                    List<ITask> subtareas = new List<ITask>();
                    foreach (var entidad in intersección)
                    {
                        string títuloSubtarea = string.Format(
                            "Intersección entre los vértices {0} y {1}",
                            entidad.FirstVertex,
                            entidad.SecondVertex);

                        subtareas.Add(new TaskAnimateEntity(
                            entidad.Line,
                            2,
                            títuloSubtarea,
                            TaskSeverity.Error));
                    }

                    Digi3D.Tasks.Add(new TaskGotoPoint(
                        (Point3D)intersección.Key,
                        "Detectada una intersección",
                        TaskSeverity.Error,
                        DigiNG.DrawingFile.Path,
                        "detectar_intersecciones",
                        subtareas.ToArray()));
                }
                DigiNG.RenderScene();

            }
            finally
            {
                Dispose();
            }
        }
    }
}

Pero podríamos haber optimizado el proceso anterior, ya que el algoritmo va a llamar a nuestro predicado por todas las entidades que tengan posibilidad de cruzarse, independientemente de sus códigos.

El resto de sobrecargas son combinaciones las sobrecargas anteriores, de modo que existe una que nos permite pasarle dos predicados: uno para indicar si analizar las intersecciones de una línea y otro para indicar si permitimos analizar las intersecciones entre un par de líneas, de modo que la siguiente modificación mejora sustancialmente la velocidad de proceso del algoritmo con idéntico resultado:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Digi21.DigiNG.Plugin.Command;
using Digi21.DigiNG.Topology;
using Digi21.DigiNG;
using Digi21.DigiNG.Entities;
using UtilidadesDigi;
using Digi21.Digi3D;
using Digi21.Math;

namespace Acme
{
    [Command(Name = "detectar_intersecciones_códigos_distintos")]
    public class DetectarInterseccionesCódigosDistintos : Command
    {
        public DetectarInterseccionesCódigosDistintos()
        {
            this.Initialize += new EventHandler(DetectarInterseccionesCódigosDistintos_Initialize);
        }

        //private bool PermitoCalcularInterseccionesEntreEstasDosLíneas(ReadOnlyLine líneaA, ReadOnlyLine líneaB)
        //{
        //    return líneaA.TieneElCódigo(this.Args[0]) && líneaB.TieneElCódigo(this.Args[1]) ||
        //        líneaA.TieneElCódigo(this.Args[1]) && líneaB.TieneElCódigo(this.Args[0]);
        //}

        void DetectarInterseccionesCódigosDistintos_Initialize(object sender, EventArgs e)
        {
            try
            {
                if (this.Args.Length != 2)
                {
                    Digi3D.Music(MusicType.Error);
                    Digi3D.ShowBallon(
                        "detectar_intersecciones_códigos_distintos",
                        "No has indicado los dos códigos con los que trabajar",
                        2,
                        BallonIcon.Error);
                    return;
                }

                var intersecciones = DigiNG.DrawingFile.SoloLíneas().DetectIntersections(
                    línea => línea.TieneAlgúnCódigo(this.Args),
                    (líneaA, líneaB) =>
                        líneaA.TieneElCódigo(this.Args[0]) && líneaB.TieneElCódigo(this.Args[1]) ||
                        líneaA.TieneElCódigo(this.Args[1]) && líneaB.TieneElCódigo(this.Args[0]));

                foreach (var intersección in intersecciones)
                {
                    List<ITask> subtareas = new List<ITask>();
                    foreach (var entidad in intersección)
                    {
                        string títuloSubtarea = string.Format(
                            "Intersección entre los vértices {0} y {1}",
                            entidad.FirstVertex,
                            entidad.SecondVertex);

                        subtareas.Add(new TaskAnimateEntity(
                            entidad.Line,
                            2,
                            títuloSubtarea,
                            TaskSeverity.Error));
                    }

                    Digi3D.Tasks.Add(new TaskGotoPoint(
                        (Point3D)intersección.Key,
                        "Detectada una intersección",
                        TaskSeverity.Error,
                        DigiNG.DrawingFile.Path,
                        "detectar_intersecciones",
                        subtareas.ToArray()));
                }
                DigiNG.RenderScene();

            }
            finally
            {
                Dispose();
            }
        }
    }
}