Contar a quantidade de triângulos em uma imagem é uma tarefa comumente usada em testes cerebrais. Você recebe uma imagem que contém formas que consistem em triângulos. Você deve encontrar todos os triângulos possíveis na figura.

Tarefa

Você recebe uma lista de linhas em um formato de sua escolha. Você deve então gerar uma lista de triângulos encontrados nesse

Entrada

Você recebe uma lista de linhas, cada uma dada por quatro coordenadas inteiras (por exemplo x1 y1 x2 y2). Você pode escolher o formato de entrada, desde que esteja claramente documentado. Exemplos:

0 4 8 1
0 4 9 5
8 1 9 5
2 8 0 4
9 5 2 8

[[0, 4, 8, 1], [0, 4, 9, 5], [8, 1, 9, 5], [2, 8, 0, 4], [9, 5, 2, 8]]

Aqui está a mesma entrada que uma imagem:

Outro, com interseções (apenas em um formato para economizar espaço):

[[2, 1, 5, 0], [2, 1, 2, 7], [5, 0, 6, 6], [5, 0, 2, 7], [6, 6, 2, 1], [2, 7, 6, 6]]

Resultado

Você deve exibir uma lista de todos os triângulos, cada um dado por seis coordenadas de ponto flutuante (por exemplo x1 y1 x2 y2 x3 y3), na imagem especificada pela entrada. Eles podem não ser números inteiros, pois as linhas podem se cruzar a qualquer momento. Você pode escolher o formato de saída, desde que esteja claramente documentado. Saídas de exemplo para as entradas de exemplo acima:

0 4 8 1 9 5
0 4 9 5 2 8

[[0, 4, 8, 3, 9, 5], [0, 4, 9, 5, 2, 8]]

[[2, 1, 5, 0, 2, 7], [2, 1, 5, 0, 6, 6], [5, 0, 6, 6, 2, 7], [2, 1, 6, 6, 2, 7], [2, 1, 5, 0, 3.674, 3.093], [5, 0, 6, 6, 3.674, 3.093], [6, 6, 2, 7, 3.674, 3.093], [2, 7, 2, 1, 3.674, 3.093]]

Você pode assumir que

• não há casos de arestas em que uma linha cruze uma interseção, mas nenhuma linha, como

  [[0, 9, 1, 8], [1, 8, 2, 9], [2, 9, 3, 8], [3, 8, 4, 9], [4, 9, 0, 9]]
  

• não há ângulos acima de 179 graus, como

  [[0, 0, 0, 1], [0, 1, 0, 2], [0, 2, 0, 0]]
  

Regras

• Você pode usar qualquer idioma que desejar.
• Nenhum recurso externo deve ser usado.
• Aplicam-se brechas padrão .

Pontuação

Isso é código-golfe , então a resposta mais curta em bytes vence.

PostGIS, 162

Eu acho que isso está de acordo com as regras, é uma consulta ao PostGIS, que é uma extensão do PostgreSQL. A entrada é assumida como uma tabela de coordenadas para cada linha chamada L A saída é um conjunto de linhas com a definição de polígono para os triângulos formados.

SELECT ST_AsText(D)FROM(SELECT(ST_Dump(ST_Polygonize(B))).geom D FROM(SELECT ST_Union(ST_MakeLine(ST_Point(A,B),ST_Point(C,D)))B FROM L)A)B WHERE ST_NPoints(D)=4;

Em uso, parece com o seguinte

-- Create a table for the input
CREATE TABLE L (A INT, B INT, C INT,D INT);
INSERT INTO L VALUES(2, 1, 5, 0), (2, 1, 2, 7), (5, 0, 6, 6), (5, 0, 2, 7), (6, 6, 2, 1), (2, 7, 6, 6);

SELECT ST_AsText(D)FROM(SELECT(ST_Dump(ST_Polygonize(B))).geom D FROM(SELECT ST_Union(ST_MakeLine(ST_Point(A,B),ST_Point(C,D)))B FROM L)A)B WHERE ST_NPoints(D)=4;

-- Cleanup
DROP TABLE L;

A saída é a seguinte

POLYGON((5 0,2 1,3.67441860465116 3.09302325581395,5 0))
POLYGON((6 6,5 0,3.67441860465116 3.09302325581395,6 6))
POLYGON((3.67441860465116 3.09302325581395,2 7,6 6,3.67441860465116 3.09302325581395))
POLYGON((2 7,3.67441860465116 3.09302325581395,2 1,2 7))

Mathematica 915395 401 405

Atualizar

Esse desafio de programação é muito mais difícil do que parece à primeira vista.

A presente abordagem trabalha com casos simples, onde há apenas uma única interseção ao longo do comprimento de qualquer segmento de linha. Com vários cruzamentos ao longo de um segmento, é necessário acompanhar todos os pontos de interseção ao longo de cada linha e criar novos sub-segmentos (portanto, arestas gráficas adicionais) conectando a nova interseção a todos os pontos de interseção ao longo da linha de destino.

Apesar dessa limitação, pode valer a pena compartilhar a lógica subjacente à abordagem atual.

Os segmentos de linha de entrada são tratados como regiões. Se eles se cruzarem, o centróide será as coordenadas da interseção. Precisamos eliminar as interseções que ocorrem nos vértices dos segmentos de linha. Linhas que não se cruzam terão um centróide indeterminado.

Quatro novas arestas são criadas para cada ponto de interseção. Eles conectam o ponto de interseção aos quatro vértices das duas linhas de interseção.

Um gráfico como o abaixo, à direita, é gerado usando as arestas antiga e nova.

Os vértices são as coordenadas dos respectivos pontos. Ciclos, isto é, loops fechados de três vértices serão triângulos, desde que os três vértices não sejam colineares.

Atualmente, verificamos se algum "triângulo" tem uma área indeterminada. (Por algum motivo, ele não retorna uma área de 0 para três pontos colineares.)

Um exemplo simples

Abaixo estão (a) a figura plotada no plano de coordenadas e (b) o gráfico mostrando os nós fornecidos, bem como o nó de interseção {114/23, 314/69}. Neste último, os vértices não estão localizados nas respectivas coordenadas cartesianas.

Pode parecer que existem mais arestas na figura da direita do que na esquerda. Mas lembre-se de que existem arestas de gráficos sobrepostas à esquerda. Cada diagonal corresponde a 3 arestas do gráfico!

    f@w_ :=(h@{a_, b_, c_, d_} := (r = RegionCentroid@RegionIntersection[Line@{a, b}, Line@{c, d}];
     {r <-> a, r <-> b, r <-> c, r <-> d});
      Cases[FindCycle[Graph[Union@Join[w /. {{a_, b_Integer}, {c_, d_}} :> {a, b} <-> {c, d},
      Cases[Flatten[h /@ Cases[{Length[Union@#] < 4, #} & /@ (FlattenAt[#, {{1}, {2}}] & /@ 
      Subsets[w, {2}]),{False, c_} :> c]], Except[{Indeterminate, _} <-> _]]]], {3}, 50],
      x_ /; NumericQ[RegionMeasure@Triangle[x[[All, 1]]]]][[All, All, 1]]//N//Grid)

Cada linha abaixo é um triângulo.

f[{{{2,8},{8,1}},{{0,4},{8,1}},{{0,4},{9,5}},{{8,1},{9,5}},{{2,8},{0,4}},{{9,5},{2,8}}}]

Um exemplo mais complexo

f@{{{9, 5}, {0, -10}}, {{9, 5}, {0, 2}},  {{9, 5}, {2, -1}}, {{0, -10}, {2, -1}}, {{0, -10}, {-2, -1}}, {{-9, 5}, {0, -10}}, {{-9, 5}, {0, 2}}, {{-9, 5}, {-2, -1}}, {{0, 2}, {0, -10}}, {{-9, 5}, {2, -1}}, {{9, 5}, {-2, -1}}, {{-9, 5}, {9, 5}}}

Aqui está o gráfico correspondente às coordenadas de entrada . Os vértices estão nas coordenadas cartesianas esperadas. (Se você executar o código com golf, ele exibirá os vértices em outro lugar, respeitando os rótulos e as bordas dos vértices. Para facilitar a leitura, atribuai as coordenadas dos vértices usando um número adicional de códigos, não necessário para a solução.)

Aqui está o gráfico derivado.
Ele inclui o ponto de interseção derivado (0,1/11), onde algumas das linhas de entrada se cruzam.

O código encontrou 19 triângulos. Nove deles têm o ponto, (0,1/11)como um dos vértices.

Java, 1051 1004

(Programa totalmente funcional)

Eu pensei que este era um bom desafio não apenas para jogar golfe algum código, mas principalmente para praticar a escrita de funções matemáticas.

E para desenhar uma "linha de base", criei esta em Java * Espera que todos comecem a rir * .

Código

import java.util.*;class P{double x,y;static P l(double... i){double a=i[0],b=i[1],c=i[2],d=i[3],e=i[4],f=i[5],k,l,x=(k=i[7]-f)*(c-a)-(l=i[6]-e)*(d-b),n=(l*(b-f)-k*(a-e))/x,m=((c-a)*(b-f)-(d-b)*(a-e))/x;P p=new P();p.x=a+n*(c-a);p.y=b+n*(d-b);return(n>=0&n<=1&m>=0&m<=1&x!=0)?p:null;}public static void main(String[]p){Set<String>v=new HashSet();P q,w,e;Integer a,b,c,d,k,f,g,h,i,j,m,l,r,t,y,z;int[][]x=new int[l=p.length/4][4];for(c=0;c<l;c++){for(d=0;d<4;){x[c][d]=l.parseInt(p[c*4+d++]);}}z=x.length;for(r=0;r<z;r++){a=x[r][0];b=x[r][1];c=x[r][2];d=x[r][3];for(t=0;t<z;t++){if(t!=r){k=x[t][0];f=x[t][1];g=x[t][2];h=x[t][3];q=l(a,b,c,d,k,f,g,h);if(q!=null){for(y=0;y<z;y++){if(y!=r&y!=t){i=x[y][0];j=x[y][1];m=x[y][2];l=x[y][3];w=l(a,b,c,d,i,j,m,l);e=l(k,f,g,h,i,j,m,l);if(w!=null&&e!=null&&q.x!=e.x&q.y!=e.y&!v.contains(""+r+y+t)){v.add(""+r+t+y);v.add(""+r+y+t);v.add(""+t+r+y);v.add(""+t+y+r);v.add(""+y+r+t);v.add(""+y+t+r);System.out.printf("%s %s %s %s %s %s\n",q.x,q.y,w.x,w.y,e.x,e.y);}}}}}}}}}

Entrada

Inteiros separados por espaço. Em pares de 4 (x1, y1, x2, y2)

2 1 5 0 2 1 2 7 5 0 6 6 5 0 2 7 6 6 2 1 2 7 6 6

Saída (a saída real não arredonda para três casas decimais)

Cada linha contém um triângulo. Cada linha consiste em pontos flutuantes separados por espaço em pares de 2 (x1, y1, x2, y2, x3, y3). (Nota: a ordem dos 3 pontos que formam o triângulo é indefinida.)

5.0 0.0 2.0 1.0 6.0 6.0
5.0 0.0 2.0 1.0 2.0 7.0
5.0 0.0 2.0 1.0 3.674 3.093
2.0 7.0 2.0 1.0 3.674 3.093
2.0 1.0 2.0 7.0 6.0 6.0
5.0 0.0 6.0 6.0 3.674 3.093
5.0 0.0 6.0 6.0 2.0 7.0
3.674 3.093 2.0 7.0 6.0 6.0

Explicação

Comecei a escrever um método para encontrar a interseção entre duas linhas não infinitas. O método resultante é para um estilo Java bastante curto (246). Em vez de permitir que a entrada do método consista em 8 pontos duplos ou 2 (P), eu escolho usar um parâmetro arbitrário para proteger grandes quantidades de caracteres. Para minimizar o uso do operador de matriz, cada parâmetro usado mais de 2 vezes é colocado em sua própria variável.

static P l(double... i){double a=i[0],b=i[1],c=i[2],d=i[3],e=i[4],f=i[5],k,l,x=(k=i[7]-f)*(c-a)-(l=i[6]-e)*(d-b),n=(l*(b-f)-k*(a-e))/x,m=((c-a)*(b-f)-(d-b)*(a-e))/x;P p=new P();p.x=a+n*(c-a);p.y=b+n*(d-b);return(n>=0&n<=1&m>=0&m<=1&x!=0)?p:null;}

Mais explicações a serem adicionadas ... (esta resposta provavelmente pode ser ainda mais jogada)

BBC BASIC

Emulador em http://www.bbcbasic.co.uk/bbcwin/bbcwin.html

Eu estou esperando isso para jogar golfe nos anos 400.

Entrada / Saída

Sempre que o usuário entra em uma nova linha, o programa verifica se novos triângulos foram criados e os gera imediatamente, veja abaixo.

Um novo triângulo é criado sempre que a nova linha se cruza com duas linhas pré-existentes que também se cruzam mutuamente (exceto quando as três linhas se cruzam em um ponto, que é um caso especial que precisa ser tratado).

Código

O programa principal é o mais simples possível. No final, está a função, que executa a complexa tarefa de detectar interseções, de acordo com a fórmula em http://en.wikipedia.org/wiki/Line%E2%80%93line_intersection

A função retorna zero se não houver interseção e um número de ponto flutuante diferente de zero, se houver. Também tem um efeito colateral: as coordenadas da interseção são anexadas à string z $. Além disso, no básico da BBC, as variáveis ​​de uma função são visíveis para o programa principal, desde que o programa principal não tenha uma variável com o mesmo nome (mesmo após o término da função).

Portanto, o programa principal tem acesso às variáveis xe y, e me n, que armazenam as coordenadas das interseções atuais e anteriores. Isso é usado para detectar se realmente encontramos um triângulo e não apenas três linhas que se cruzam em um ponto.

  DIM a(99),b(99),c(99),d(99)                                                    :REM declare 4 arrays to hold the ata
  y=0                                                                            :REM x and y are only initialized
  x=0                                                                            :REM to avoid a no such varialbe error later
  FOR i=0 TO 99                                                                  :REM for each input line
    INPUT a(i),b(i),c(i),d(i)
    FOR j=0 TO i-1                                                               :REM iterate through all combinations of 2 previous lines
      FOR k=0 TO j-1
        z$=""                                                                    :REM clear z$, three function calls on next line will write the triangle (if found) to it
        IF i>j AND j>k AND FNf(i,j)*FNf(i,k)*FNf(j,k)<>0 IF x<>m OR y<>n PRINT z$:REM to avoid printing the same triangle twice, print only if j,k,i in lexicographic order. Also reject if x,y (3rd FNf call) and m,n (2nd FNf call) are the same: this means a point, not a triangle.
      NEXT
    NEXT
  NEXT

  DEF FNf(g,h)                                                                   :REM returns zero if no intersection found, otherwise a floating point value
  m=x                                                                            :REM backup previous x and y
  n=y                                                                            :REM to use in test for point versus triangle
  p=a(g)-c(g)
  q=b(g)-d(g)
  r=a(h)-c(h)
  s=b(h)-d(h)
  t=a(g)*d(g)-b(g)*c(g)
  u=a(h)*d(h)-b(h)*c(h)
  e=p*s-q*r                                                                      :REM following method in wikipedia, calculate denominator of expression
  IF e<>0 x=(t*r-u*p)/e : y=(t*s-u*q)/e: z$=z$+" "+STR$(x)+" "+STR$(y)           :REM if denominator not zero, calculate x and y and append a string copy to z$
  IF (a(g)-x)*(c(g)-x)>0 OR (b(g)-y)*(d(g)-x)>0 OR(a(h)-x)*(c(h)-x)>0 OR(b(h)-y)*(d(h)-y)>0 e=0
  =e          :REM return e                                                      :REM previous line sets e to zero if the intersection falls outside the line segment. This is detected when both are on the same side of the intersection, which yields a positive multiplication result.