require 'set' class TriangleFinder def initialize rays @rays = rays end def find find_line_segments find_point_connections find_triangles @triangles end # Find all (O, D) such that O and D are joined by a line segment. def find_line_segments @segments = Set.new @rays.each do |ray| ray.each do |origin| (ray - [origin]).each do |destination| @segments << [origin, destination].sort end end end end # For every point A, find all points that connect to A with a # line segment. def find_point_connections @connections = Hash.new @segments.each do |a, b| (@connections[a] ||= []) << b (@connections[b] ||= []) << a end @points = @connections.keys end # For every point A, find all points B and C that are both # connected to A with a line segment, but such that (A, B, C) # are not connected by a straight line. def find_triangles @triangles = Set.new @points.each do |a| @connections[a].each do |b| @connections[b].each do |c| if @connections[a].include? c unless connected_by_straight_line? a, b, c @triangles << [a, b, c].sort end end end end end end # Find whether a ray exists that intersects A, B, and C. def connected_by_straight_line? a, b, c @rays.any? do |ray| ray.include? a and ray.include? b and ray.include? c end end end rays = [ [0, 1], [0, 2, 4, 6], [0, 3, 7, 9], [0, 5, 8, 10], [1, 2, 3, 5], [1, 4, 7, 8], [1, 6, 9, 10] ] p TriangleFinder.new(rays).find