Подсчет количества треугольников на изображении является задачей, обычно используемой в тестах мозга. Вам дана картинка, которая содержит фигуры, состоящие из треугольников. Затем вы должны найти все возможные треугольники на картинке.

задача

Вам предоставляется список строк в формате по вашему выбору. Затем вы должны вывести список треугольников, найденных в этом

вход

Вам предоставляется список строк, каждая из которых имеет четыре целочисленных координаты (например, x1 y1 x2 y2). Вы можете выбрать формат ввода, если он четко задокументирован. Примеры:

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

Вот такой же ввод как изображение:

Еще один, с пересечениями (только в одном формате для экономии места):

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

Выход

Вы должны вывести список всех треугольников, каждый из которых задан шестью координатами с плавающей точкой (например, x1 y1 x2 y2 x3 y3), на рисунке, указанном входными данными . Это могут быть не целые числа, поскольку линии могут пересекаться в любой точке. Вы можете выбрать выходной формат, если он четко задокументирован. Пример выходов для примера входов выше:

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

Вы можете предположить, что

• не существует краевых случаев, когда прямая пересекает пересечение, но нет линий, например

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

• нет углов больше 179 градусов, вроде

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

правила

• Вы можете использовать любой язык, который хотите.
• Внешние ресурсы не должны использоваться.
• Применяются стандартные лазейки .

счет

Это код-гольф , поэтому выигрывает самый короткий ответ в байтах .

ПостГИС, 162

Я думаю, что это соответствует правилам. Это запрос к PostGIS, который является расширением PostgreSQL. Предполагается, что входные данные представляют собой таблицу координат для каждой строки с именем L. Выходные данные представляют собой набор строк с определением полигонов для сформированных треугольников.

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;

В использовании это выглядит следующим образом

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

Выход выглядит следующим образом

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

Обновить

Эта задача программирования гораздо сложнее, чем кажется на первый взгляд.

Настоящий подход работает с простыми случаями, когда существует только одно пересечение по длине любого отрезка. При наличии нескольких пересечений вдоль одного сегмента необходимо отслеживать все точки пересечения вдоль каждой линии и создавать новые подсегменты (следовательно, дополнительные ребра графа), соединяющие новое пересечение со всеми точками пересечения вдоль целевой линии.

Несмотря на это ограничение, возможно, стоит поделиться логикой, лежащей в основе нынешнего подхода.

Сегменты входных линий обрабатываются как регионы. Если они пересекаются, центр тяжести будет координатами пересечения. Нам нужно устранить те пересечения, которые встречаются в вершинах отрезков. Линии, которые не пересекаются, будут иметь неопределенный центроид.

Для каждой точки пересечения создаются четыре новых ребра. Они соединяют точку пересечения с четырьмя вершинами двух пересекающихся линий.

График, такой как приведенный ниже справа, создается с использованием как старых, так и новых ребер.

Вершины - это координаты соответствующих точек. Циклы, т. Е. Замкнутые петли из трех вершин, будут треугольниками при условии, что эти три вершины не коллинеарны.

В настоящее время мы проверяем, имеет ли какой-либо «треугольник» неопределенную область. (По некоторым причинам он не возвращает область 0 для трех коллинеарных точек.)

Простой пример

Ниже (а) фигура изображена на координатной плоскости и (б) график , показывающий данные узлы, а также узел пересечения, {114/23, 314/69}. В последнем случае вершины не расположены в соответствующих декартовых координатах.

Может показаться, что на правом рисунке их больше, чем на левом. Но помните, что слева есть перекрывающиеся ребра графа. Каждая диагональ на самом деле соответствует 3 ребрам графа!

    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)

Каждая строка ниже представляет собой треугольник.

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

Более сложный пример

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

Вот график, соответствующий входным координатам. Вершины находятся в ожидаемых декартовых координатах. (Если вы запустите гольф-код, он покажет вершины в другом месте, при этом соблюдая метки и ребра вершин. Для удобства чтения я назначил координаты вершин, используя дополнительный код, не необходимый для решения.)

Вот полученный график.
Он включает в себя производную точку пересечения (0,1/11), где некоторые входные линии пересекаются.

В коде найдено 19 треугольников. Девять из них имеют точку, (0,1/11)как одну из вершин.

Ява, 1051 1004

(Полностью рабочая программа)

Я подумал, что это хорошая задача не только для игры в гольф, но и для практики написания математических функций.

И чтобы нарисовать «базовую линию», я сделал это на Java * Ждет, когда все начнут смеяться * .

Код

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

вход

Целые числа через пробел В парах по 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

Вывод (реальный вывод не округляется до 3 десятичных знаков)

Каждая строка содержит один треугольник. Каждая строка состоит из разделенных пробелами плавающих точек в парах по 2 (x1, y1, x2, y2, x3, y3). (Примечание: порядок 3 точек, которые образуют треугольник, не определен.)

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

объяснение

Я начал писать метод, чтобы найти пересечение между двумя бесконечными линиями. Результирующий метод для стиля Java довольно короткий (246). Вместо того, чтобы позволить вводу метода состоять из 8 двойных или двух точек (P), я выбираю использовать произвольный параметр для сохранения большого количества символов. Чтобы минимизировать использование оператора массива, каждый параметр, используемый более 2 раз, помещается в собственную переменную.

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

Дополнительные пояснения будут добавлены ... (этот ответ, вероятно, может быть еще больше в гольфе)

BBC BASIC

Эмулятор на http://www.bbcbasic.co.uk/bbcwin/bbcwin.html

Я ожидаю, что это в гольф в 400-х годов.

Ввод, вывод

Каждый раз, когда пользователь вводит новую строку, программа проверяет, были ли созданы новые треугольники, и немедленно выводит их, см. Ниже.

Новый треугольник создается везде, где новая линия пересекается с двумя ранее существующими линиями, которые также взаимно пересекаются (за исключением случаев, когда все три линии пересекаются в точке, что является особым случаем, с которым нужно иметь дело.)

Код

Основная программа настолько проста, насколько это возможно. В конце находится функция, которая выполняет сложную задачу обнаружения пересечений, по формуле в http://en.wikipedia.org/wiki/Line%E2%80%93line_intersection

Функция возвращает ноль, если пересечения нет, и ненулевое число с плавающей точкой, если оно есть. Это также имеет побочный эффект: координаты пересечения добавляются к строке z $. Кроме того, в BBC basic переменные функции видны основной программе при условии, что основная программа не имеет переменной с тем же именем (даже после завершения функции).

Поэтому основная программа имеет доступ к переменным xи y, и, mи n, которые хранят координаты текущего и предыдущего пересечений. Это используется для определения, действительно ли мы нашли треугольник, а не только три линии, пересекающиеся в точке.

  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.