Inicialmente implementei o algoritmo Hoey-Shamos, mas ele é muito complexo para manutenção futura (não tenho nada a dizer sobre isso), e ele não estava reportando corretamente, então um algoritmo de força bruta otimizado é o que eu vou usar.

Minha pergunta é: como posso otimizar esse código para ser utilizável?

Como está, meu código contém um loop aninhado, iterando a mesma lista duas vezes.

EDIT: Transformou linhas em um HashSet e usou dois loops foreach ... raspou cerca de 45 segundos da varredura de 10.000. Ainda não é suficiente.

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

 } // end 'lines' for each loop

Se eu forçar o método "intersectsLine ()" a retornar false (para fins de teste), ainda demorará 8 segundos para varrer 10.000 registros (tenho 700.000 registros). Isso é muito longo, então eu preciso otimizar esse pedaço de código.

Eu tentei remover linhas da lista depois que ela foi comparada a todas as outras linhas, no entanto, há um problema de precisão (não sei por que) e o aumento de velocidade é quase imperceptível.

Aqui está o meu método intersectsLine. Eu encontrei uma abordagem alternativaAqui mas parece que seria mais lento com todas as chamadas de método e outros enfeites. Calcular a inclinação não me parece que seria preciso muita computação (corrija-me se estiver errado?)

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: O maior gargalo são os grandes polígonos! Excluí polígonos em execução com mais de 100 linhas e executava todos os 700.000 polígonos em 5:10. Qual é o intervalo aceitável! Certamente há uma maneira de ver se vale a pena calcular um polígono antes de executar este código? Eu tenho acesso às propriedades XMin, Xmax, YMin e YMax se isso ajudar?

Fiz outro teste, limitando os polígonos a menos de 1000 linhas cada. Demorou um pouco mais de uma hora.

Eu removi toda a limitação de polígonos, e ela está funcionando há 36 horas agora ... ainda sem resultados.

Algumas ideias que tenho:

-Quando eu gerar minhas linhas hashset, tenha outro hashset / List que tenha candidatos para interseção. Eu só adicionaria linhas a essa lista se houvesse uma chance de interseção. Mas como eliminar / adicionar possibilidades? Se houver apenas três linhas que poderiam se cruzar com outras, eu estaria comparando 4.000 linhas contra 3 em vez de 4. Isso sozinho poderia fazer uma enorme diferença.

-Se o mesmo ponto ocorrer duas vezes, exceto o primeiro e o último ponto, omita a execução do loop for aninhado.

Editar:

Informações sobre os polígonos: 700.000 no total

Existem mais de quatro mil polígonos com 1.000 ou mais pontos

Existem 2 polígonos com 70.000 ou mais pontos

Acho que é possível fazer isso com quinze minutos ou mais com um pouco de criatividade.