Obliczanie liczby trójkątów na zdjęciu jest zadaniem często stosowanym w testach mózgu. Otrzymujesz zdjęcie, które zawiera kształty składające się z trójkątów. Następnie musisz znaleźć wszystkie możliwe trójkąty na obrazku.

Zadanie

Otrzymasz listę wierszy w wybranym formacie. Następnie musisz wygenerować listę znalezionych w nim trójkątów

Wejście

Otrzymujesz listę linii, każda podana przez cztery współrzędne całkowite (np. x1 y1 x2 y2). Możesz wybrać format wejściowy, o ile jest on wyraźnie udokumentowany. Przykłady:

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]]

Oto te same dane wejściowe co obraz:

Kolejny z przecięciami (tylko w jednym formacie, aby zaoszczędzić miejsce):

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

Wynik

Musisz wydrukować listę wszystkich trójkątów, każdy podany przez sześć współrzędnych zmiennoprzecinkowych (np. x1 y1 x2 y2 x3 y3), Na obrazie określonym przez dane wejściowe. Nie mogą to być liczby całkowite, ponieważ linie mogą się przecinać w dowolnym punkcie. Możesz wybrać format wyjściowy, o ile jest on wyraźnie udokumentowany. Przykładowe dane wyjściowe dla przykładowych danych wejściowych powyżej:

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]]

Możesz to założyć

• nie ma przypadków krawędzi, w których linia przecina przecięcie, ale żadnych linii, takich jak

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

• nie ma kątów powyżej 179 stopni

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

Zasady

• Możesz używać dowolnego języka.
• Nie wolno używać żadnych zasobów zewnętrznych.
• Obowiązują standardowe luki .

Punktacja

To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach .

PostGIS, 162

Myślę, że jest to zgodne z regułami. Jest to zapytanie do PostGIS, które jest rozszerzeniem PostgreSQL. Przyjmuje się, że dane wejściowe są tabelą współrzędnych dla każdej linii o nazwie L. Dane wyjściowe to zestaw wierszy z definicją wielokąta dla utworzonych trójkątów.

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;

W użyciu wygląda to następująco

-- 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;

Dane wyjściowe są następujące

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 915 395 401 405

Aktualizacja

To wyzwanie programistyczne jest znacznie trudniejsze, niż się wydaje.

Obecne podejście działa z prostymi przypadkami, w których występuje tylko jedno przecięcie wzdłuż dowolnego odcinka linii. Przy wielu skrzyżowaniach wzdłuż jednego segmentu konieczne jest śledzenie wszystkich punktów przecięcia wzdłuż każdej linii i tworzenie nowych podsegmentów (stąd dodatkowe krawędzie wykresu) łączących nowe skrzyżowanie ze wszystkimi punktami przecięcia wzdłuż linii docelowej.

Mimo tego ograniczenia warto podzielić logikę leżącą u podstaw obecnego podejścia.

Segmenty linii wejściowej są traktowane jako regiony. Jeśli się przecinają, środek ciężkości będzie współrzędnymi przecięcia. Musimy wyeliminować te przecięcia, które występują na wierzchołkach segmentów linii. Linie, które się nie przecinają, będą miały nieokreślony środek ciężkości.

Dla każdego punktu przecięcia tworzone są cztery nowe krawędzie. Łączą punkt przecięcia z czterema wierzchołkami dwóch przecinających się linii.

Wykres taki jak ten po prawej stronie jest generowany przy użyciu zarówno starych, jak i nowych krawędzi.

Wierzchołki są współrzędnymi odpowiednich punktów. Cykle, tj. Zamknięte pętle trzech wierzchołków będą trójkątami, pod warunkiem że trzy wierzchołki nie są współliniowe.

Obecnie sprawdzamy, czy jakikolwiek „trójkąt” ma nieokreślony obszar. (Z jakiegoś powodu nie zwraca obszaru 0 dla trzech punktów współliniowych.)

Prosty przykład

Poniżej są (a) wysokość wykreślono w płaszczyźnie współrzędnych oraz (b) wykres pokazujący podane węzłów oraz węzeł przecięcia linii {114/23, 314/69}. W tym ostatnim wierzchołki nie znajdują się na odpowiednich współrzędnych kartezjańskich.

Może się wydawać, że mają więcej krawędzi na prawej figurze niż na lewej. Pamiętaj jednak, że po lewej stronie zachodzą na siebie krawędzie wykresu. Każda przekątna faktycznie odpowiada 3 krawędziom wykresu!

    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)

Każdy rząd poniżej to trójkąt.

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}}}]

Bardziej złożony przykład

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}}}

Oto wykres odpowiadający współrzędnym wejściowym . Wierzchołki mają swoje oczekiwane współrzędne kartezjańskie. (Jeśli uruchomisz kod do gry w golfa, wyświetli on wierzchołki gdzie indziej, jednocześnie przestrzegając etykiet i krawędzi wierzchołków. W celu zapewnienia czytelności przypisałem współrzędne wierzchołków za pomocą odrobiny dodatkowego kodu, który nie jest konieczny do rozwiązania.)

Oto wykres pochodny.
Obejmuje pochodny punkt przecięcia (0,1/11), w którym krzyżują się niektóre linie wejściowe.

Kod znalazł 19 trójkątów. Dziewięć z nich ma punkt, (0,1/11)jako jeden z wierzchołków.

Java, 1051 1004

(W pełni działający program)

Pomyślałem, że to fajne wyzwanie nie tylko do gry w golfa, ale przede wszystkim do ćwiczenia pisania funkcji matematycznych.

Aby narysować „linię bazową”, stworzyłem ją w Javie * Czeka, aż wszyscy zaczną się śmiać * .

Kod

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);}}}}}}}}}

Wejście

Liczby całkowite oddzielone spacją. W parach po 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

Wyjście (rzeczywista wydajność nie zaokrągla do 3 miejsc po przecinku)

Każda linia zawiera jeden trójkąt Każda linia składa się z rozdzielonych spacjami punktów zmiennoprzecinkowych w parach 2 (x1, y1, x2, y2, x3, y3). (Uwaga: kolejność 3 punktów tworzących trójkąt jest niezdefiniowana).

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

Wyjaśnienie

Zacząłem pisać metodę znajdowania przecięcia między dwiema nieskończonymi liniami. Powstała metoda jest bardzo krótka w stylu Java (246). Zamiast pozwolić, aby metoda zawierała 8 podwójnych lub dwóch Punktów (P), wybieram dowolny parametr, aby zabezpieczyć ogromne ilości znaków. Aby zminimalizować użycie operatora tablicy, każdy parametr użyty więcej niż 2 razy jest umieszczany we własnej zmiennej.

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;}

Więcej wyjaśnień do dodania ... (ta odpowiedź może być jeszcze bardziej golfa)

BBC BASIC

Emulator w http://www.bbcbasic.co.uk/bbcwin/bbcwin.html

Spodziewam się, że będzie to grało w golfa w latach 400-tych.

Wejście wyjście

Za każdym razem, gdy użytkownik wchodzi w nową linię, program sprawdza, czy zostały utworzone jakieś nowe trójkąty, i wysyła je natychmiast, patrz poniżej.

Nowy trójkąt jest tworzony wszędzie tam, gdzie nowa linia przecina się z dwiema wcześniej istniejącymi liniami, które również przecinają się wzajemnie (z wyjątkiem sytuacji, gdy wszystkie trzy linie przecinają się w punkcie, co jest szczególnym przypadkiem, z którym należy sobie poradzić.)

Kod

Główny program jest tak prosty, jak to tylko możliwe. Na końcu jest funkcja, która wykonuje złożone zadanie wykrywania skrzyżowań, zgodnie ze wzorem w http://en.wikipedia.org/wiki/Line%E2%80%93line_intersection

Funkcja zwraca zero, jeśli nie ma przecięcia, i niezerową liczbę zmiennoprzecinkową, jeśli istnieje. Ma również efekt uboczny: współrzędne skrzyżowania są dołączane do ciągu z $. Dodatkowo w BBC basic zmienne funkcji są widoczne dla programu głównego, pod warunkiem, że program główny nie ma zmiennej o tej samej nazwie (nawet po zakończeniu funkcji).

Dlatego główny program ma dostęp do zmiennych xi y, i, mi n, które przechowują współrzędne bieżącego i poprzednich skrzyżowań. Służy to do wykrycia, czy naprawdę znaleźliśmy trójkąt, a nie tylko trzy linie przecinające się w jednym punkcie.

  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.