Inicialmente implementé el algoritmo de Hoey-Shamos, sin embargo, es demasiado complejo para la capacidad de mantenimiento en el futuro (no tengo nada que decir sobre esto), y no estaba informando correctamente, por lo que usaré un algoritmo de fuerza bruta optimizado.

Mi pregunta es: ¿Cómo puedo optimizar este código para que sea utilizable?

Tal como está, mi código contiene un bucle anidado para, iterando la misma lista dos veces.

EDITAR: Convirtió las líneas en un HashSet y usó dos bucles foreach ... afeitado a unos 45 segundos de escanear 10,000. Todavía no es suficiente.

foreach (Line2D g in lines)
{                   
foreach (Line2D h in lines)
{
    if (g.intersectsLine(h))
    {
        return false;
    }
}                  

 } // end 'lines' for each loop

Si fuerzo a mi método "intersectsLine ()" para que devuelva falso (para propósitos de prueba) todavía se necesitan 8 segundos para escanear 10,000 registros (tengo 700,000 registros). Esto es demasiado largo, así que necesito optimizar este pedazo de código.

Intenté eliminar líneas de la Lista después de haber sido comparada con todas las demás líneas, sin embargo, hay un problema de precisión (no se sabe por qué) y el aumento de velocidad es apenas perceptible.

Aquí está mi método intersectsLine. Encontré un enfoque alternativoaquí pero parece que sería más lento con todas las llamadas de métodos y todo eso. Calcular la pendiente no me parece que tomaría demasiada computación (¿Me corrige si me equivoco?)

public bool intersectsLine(Line2D comparedLine)
{

//tweakLine(comparedLine);
if (this.Equals(comparedLine) ||
    P2.Equals(comparedLine.P1) ||
    P1.Equals(comparedLine.P2))
{
    return false;
}

double firstLineSlopeX, firstLineSlopeY, secondLineSlopeX, secondLineSlopeY;

firstLineSlopeX = X2 - X1;
firstLineSlopeY = Y2 - Y1;

secondLineSlopeX = comparedLine.X2 - comparedLine.X1;
secondLineSlopeY = comparedLine.Y2 - comparedLine.Y1;

double s, t;
s = (-firstLineSlopeY * (X1 - comparedLine.X1) + firstLineSlopeX * (Y1 - comparedLine.Y1)) / (-secondLineSlopeX * firstLineSlopeY + firstLineSlopeX * secondLineSlopeY);
t = (secondLineSlopeX * (Y1 - comparedLine.Y1) - secondLineSlopeY * (X1 - comparedLine.X1)) / (-secondLineSlopeX * firstLineSlopeY + firstLineSlopeX * secondLineSlopeY);

if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
{
    //console.WriteLine("s = {0}, t = {1}", s, t);
    //console.WriteLine("this: " + this);
    //console.WriteLine("other: " + comparedLine);
    return true;
}

return false; // No collision */

}

EDITAR: El mayor cuello de botella son los grandes polígonos! Excluí correr polígonos con más de 100 líneas, y corrió más de 700,000 polígonos en 5:10. Que está en el rango aceptable! ¿Seguramente hay una manera de ver si vale la pena calcular un polígono antes de ejecutar este código? Tengo acceso a las propiedades XMin, Xmax, YMin e YMax si eso ayuda.

Corrió otra prueba, limitando los polígonos a menos de 1000 líneas cada uno. Tomó un poco más de una hora.

Eliminé toda la limitación de polígonos, y ha estado funcionando durante 36 horas ahora ... todavía no hay resultados.

Un par de ideas que tengo:

-Cuando genere mi hashset de líneas, tenga otro hashset / Lista que tenga candidatos para la intersección. Solo agregaría líneas a esta lista si existe la posibilidad de una intersección. ¿Pero cómo elimino / agrego posibilidades? Si solo hay tres líneas que podrían cruzarse con otras, estaría comparando 4000 líneas contra 3 en lugar de 4000. Esto solo podría hacer una GRAN diferencia.

-Si el mismo punto ocurre dos veces, excepto el primer y el último punto, omita la ejecución del bucle anidado.

Editar:

Información sobre los polígonos: 700,000 en total.

Hay más de cuatro mil polígonos con 1,000 o más puntos.

Hay 2 polígonos con 70,000 o más puntos.

Creo que es posible reducir esto a unos quince minutos con un poco de creatividad.