Identifying the triangles

Question

Counting the amount of triangles in a picture is a task commonly used in brain tests. You are given a picture that contains shapes consisting of triangles. You then must find all possible triangles in the picture.

Task

You are given a list of lines in a format of your choice. You must then output a list of triangles found in that

Input

You are given a list of lines, each given by four integer coordinates (eg. x1 y1 x2 y2). You may choose the input format, as long as it is clearly documented. Examples:

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

Here's the same input as an image:

Another one, with intersections (only in one format to save space):

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

Output

You must output a list of all triangles, each given by six floating-point coordinates (eg. x1 y1 x2 y2 x3 y3), in the picture specified by the input. These might not be integers, since the lines may cross at any point. You may choose the output format, as long as it is clearly documented. Example outputs for the example inputs above:

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

You may assume that

• there are no edge cases where a line crosses an intersection but not any lines, like

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

• there are no angles over 179 degrees, like

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

Rules

• You may use any language you want.
• No external resources must be used.
• Standard loopholes apply.

Scoring

This is code-golf, so the shortest answer in bytes wins.

Answer 1

Mathematica 915 395 401 405

Update

This programming challenge is much more difficult than it first appears to be.

The present approach works with simple cases, where there is but a single intersection along the length of any line segment. With multiple crossings along one segment, it is necessary to keep track of all of the intersection points along each line and create new sub-segments (hence additional graph edges) connecting the new intersection to all the intersection points along the target line.

Despite that limitation, it may be worth sharing the logic underlying the current approach.

---

The input line segments are treated as regions. If they intersect, the centroid will be the coordinates of the intersection. We need to eliminate those intersections that occur at the vertices of line segments. Lines that do not intersect will have an indeterminate centroid.

Four new edges are created for each intersection point. They connect the intersection point to the four vertices of the two intersecting lines.

A graph such as the one below on the right is generated using both the old and new edges.

The vertices are the coordinates of the respective points. Cycles, i.e., closed loops of three vertices will be triangles provided that the three vertices are not collinear.

Presently we check to see whether any "triangle" has an indeterminate area. (For some reason it does not return an area of 0 for three collinear points.)

---

A simple example

Below are (a) the figure plotted in the coordinate plane and (b) the graph showing the given nodes as well as the intersection node, {114/23, 314/69}. In the latter, the vertices are not located at the respective Cartesian coordinates.

It may appear that their are more edges in the right figure than in the left. But remember that there are overlapping graph edges on the left. Each diagonal actually corresponds to 3 graph edges!

---

    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)

Each row below is a triangle.

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

---

A more complex example

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

Here's the graph corresponding to the input coordinates. The vertices are at their expected Cartesian coordinates. (If you run the golfed code it will display the vertices elsewhere while respecting the vertex labels and edges. For readability, I assigned the vertex coordinates using a smattering of additional code, not necessary for the solution.)

---

Here's the derived graph.
It includes the derived point of intersection (0,1/11), where some of the input lines cross.

The code found 19 triangles. Nine of them have the point, (0,1/11) as one of the vertices.

Answer 2

Java, 1051 1004

(Fully working program)

I thought this is a nice challenge not just to golf some code, but mainly to practice writing mathematical functions.

And to draw a "baseline" I made this one in Java *Waits for everyone to start laughing*.

Code

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

---

Input

Space separated integers. In pairs of 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

---

Output (real output does not round to 3 decimals)

Each line contains one triangle Each line consist out of space separated floating points in pairs of 2 (x1, y1, x2, y2, x3, y3). (Note: the order of the 3 points that form the triangle is undefined.)

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

---

Explanation

I started to write a method to find the intersection between two not-infinite lines. The resulting method is for a Java style one pretty short (246). Instead of letting the method input consists out of 8 double's or two Points (P) I choose to use a arbitrary parameter to safe massive amounts of characters. To minimize the array operator usage each parameter used more than 2 times is placed in it's own variable.

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

More explanation to be added... (this answer can probably be golfed even more)

Answer 3

PostGIS, 162

I think this complies with the rules, It is a query for PostGIS, which is an extension of PostgreSQL. The input is assumed to be a table of coordinates for each line called L The output is a set of rows with the polygon definition for the triangles formed.

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;

In use it looks like the following

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

The output is as follows

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

Answer 4

BBC BASIC

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

I'm expecting this to golf down into the 400's.

Input / Output

Every time the user enters a new line, the program checks if any new triangles have been created, and outputs them immediately, see below.

A new triangle is created wherever the new line intersects with two pre-existing lines that are also mutually intersecting (except when all three lines intersect at a point, which is a special case that has to be dealt with.)

Code

The main program is about as simple as can be. At the end is the function, which performs the complex task of detecting intersections, according to the formula in http://en.wikipedia.org/wiki/Line%E2%80%93line_intersection

The function returns zero if there is no intersection and a nonzero floating point number if there is. It also has a side effect: the coordinates of the intersection are appended to the string z$. Additionally, in BBC basic the variables of a function are visible to the main program provided the main program does not have a variable of the same name (even after the function has finished.)

Therefore the main program has access to the variables x and y, and m and n, which store the coordinates of the current and previous intersections. This is used to detect if we have really found a triangle and not just three lines intersecting at a point.

  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.