require 'RMagick'
@top_intersects = [ ]
@all_intersects = { }
@just_ints = [ ]
@lines = [ ] #make a list of [[x1,y1],[x2,y2]], one for each line
def eq_maker( line)
slope = ( line[ 1 ] [ 1 ] - line[ 0 ] [ 1 ] ) / ( line[ 1 ] [ 0 ] - line[ 0 ] [ 0 ] )
y_intercept = line[ 0 ] [ 1 ] - ( slope * line[ 0 ] [ 0 ] )
return [ slope, y_intercept]
end
def intersection_finder( line1,line2) #finds the intersection point when given four points -- makes 2 lines, solves for x=y
line1 + = eq_maker( line1)
line2 + = eq_maker( line2)
if line1[ 2 ] == line2[ 2 ]
return [ line1,line2] .sort_by { | x| x[ 1 ] [ 0 ] } [ 0 ] [ 1 ] if line1[ 3 ] == line2[ 3 ] #ultra edge case: if they're the same line, return the endpoint with the minimum x
return [ - 10.0 ,- 10.0 ] #less edge, but still exceptionally unlikely: if they have the same slope, return a range that doesn't exist in our board
end
x_int = ( line2[ 3 ] - line1[ 3 ] ) / ( line1[ 2 ] - line2[ 2 ] ) #otherwise, return the intersection point (z2 - z1) /(m1 - m2)
y_int = ( line1[ 2 ] * x_int) + line1[ 3 ]
return [ x_int, y_int]
end
def on_both?( line1,line2,int) #.round(3) is necessary because floats suck dick
[ line1,line2] .each do | x|
return false unless int[ 0 ] .round ( 3 ) > = x[ 0 ] [ 0 ] .round ( 3 ) && int[ 0 ] .round ( 3 ) < = x[ 1 ] [ 0 ] .round ( 3 )
y_range = [ x[ 1 ] [ 1 ] .round ( 3 ) ,x[ 0 ] [ 1 ] .round ( 3 ) ] .sort
return false unless int[ 1 ] .round ( 3 ) > = y_range[ 0 ] && int[ 1 ] .round ( 3 ) < = y_range[ 1 ]
end
return true
end
def intersects( current_line) #todo: make floats not suck, and make sure it's selecting the right line (check to see if the intercept coordinates fall both on the current line and the new line length, not extended lengths
@all_intersects [ current_line] = [ ]
possibilities = @lines .select { | x| @all_intersects [ x] .nil ?} #check for intersections against all other lines that haven't already been checked for intersections (or self)
possibilities.each do | x|
int = intersection_finder( current_line,x)
if on_both?( current_line,x,int)
@just_ints .push int
@all_intersects [ int] = [ current_line,x] #every intersection has exactly 2 lines -- avoids some float problems
end
end
return true
end
def area_totaler( point1,point2) #totals area under any straight_line segment from x axis -- rectangle + triangle
x_range = [ point1[ 0 ] ,point2[ 0 ] ] .sort
y_range = [ point1[ 1 ] ,point2[ 1 ] ] .sort
width = x_range[ 1 ] - x_range[ 0 ]
rect_height = y_range[ 0 ]
triangle_height = ( y_range[ 1 ] - y_range[ 0 ] )
return ( rect_height * width) + ( 0.5 * width * triangle_height) #rect area + triangle area
end
#format: [center-pos,base-length,height]
triangles = [ ]
5 .times do #make random triangles
triangles.push [ ( rand ( 5000 ) + 2501 ) / 10.0 , ( rand ( 5000 ) + 1 ) / 10.0 , ( rand ( 5000 ) + 1001 ) / 10.0 ]
end
colors = [ 'red' ,'blue' ,'green' ,'purple' ,'orange' ,'yellow' ,'brown' ,'cyan' ,'magenta' ]
imgl = Magick::ImageList .new
imgl.new_image ( 1000 , 600 )
gc = Magick::Draw .new
triangles.each do | x| #draw triangles
gc.fill ( colors.sample ( 1 ) [ 0 ] )
gc.fill_opacity ( 0.5 )
coords = [ ( x[ 0 ] - ( x[ 1 ] / 2 ) ) ,0 , x[ 0 ] ,x[ 2 ] , ( x[ 0 ] + ( x[ 1 ] / 2 ) ) ,0 ]
@lines .push [ [ coords[ 0 ] ,coords[ 1 ] ] ,[ coords[ 2 ] ,coords[ 3 ] ] ]
@lines .push [ [ coords[ 2 ] ,coords[ 3 ] ] ,[ coords[ 4 ] ,coords[ 5 ] ] ]
eval "gc.polygon(#{coords.join(',')})"
end
@lines .sort_by ! { | x| x[ 0 ] [ 0 ] } #start at left -- first line = highest line
@lines .each { | x| intersects( x) } #build all real intersections
@just_ints .sort_by ! { | x| x[ 0 ] } #sort intercepts by x, move from left to right
@top_intersects .push @lines [ 0 ] [ 0 ] #first point on the line is the leftmost point
last_point = @lines .sort_by { | x| x[ 1 ] [ 0 ] } .last [ 1 ]
current_line = @lines [ 0 ] #start with leftmost line
@just_ints .each do | x| #iterate through intercepts, finding the top line
if current_line[ 1 ] [ 0 ] < x[ 0 ] && current_line[ 1 ] [ 1 ] .to_f == 0.0 #if the x of the next intercept is beyond the x of the end of our line, triangle hits the x axis, so add line endpoint and get the next line
@top_intersects .push current_line[ 1 ]
current_line = @lines [ @lines.index { | z| z[ 0 ] [ 0 ] > current_line[ 1 ] [ 0 ] } ]
@top_intersects .push current_line[ 0 ]
end
if @all_intersects [ x] .include ?( current_line) #if the next intersect includes our line, switch lines, push intersect to top_intersects
@top_intersects .push x
current_line = ( @all_intersects[ x] - [ current_line] ) [ 0 ]
end
#otherwise, if the int isn't on our line, do nothing (except draw a circle).
# Identify the intersections with gray circles
gc.stroke ( 'gray50' )
gc.stroke_width ( 1 )
gc.fill_opacity ( 0 )
coords = "gc.circle(#{x.join(',')},#{x.map {|y| y + 3}.join(',')})"
eval coords
end
@top_intersects .push last_point #add the last point after all intercepts =)
area = 0
( @top_intersects.length - 1 ) .times do | x| #count the total area under all sections
area + = area_totaler( @top_intersects[ x] ,@top_intersects[ x + 1 ] )
end
puts "Computed area is: #{area}"
sum = 0
triangles.each do | x| #sum all the triangles, for comparison
sum + = ( x[ 1 ] * x[ 2 ] * 0.5 )
end
puts "Area of all triangles, including overlap, is: #{sum}"
gc.stroke ( 'black' )
gc.stroke_width ( 3 )
eval "gc.polygon(#{@top_intersects.flatten.join(',')})" #draw a polygon which is @top_intersects.flatten -- trace tops of triangles
gc.draw ( imgl) #draw image
imgl.flip ! #flip it; we draw upside down =)
imgl.write ( "polygon.gif" )
cmVxdWlyZSAnUk1hZ2ljaycKQHRvcF9pbnRlcnNlY3RzID0gW10KQGFsbF9pbnRlcnNlY3RzID0ge30KQGp1c3RfaW50cyA9IFtdCkBsaW5lcyA9IFtdICNtYWtlIGEgbGlzdCBvZiBbW3gxLHkxXSxbeDIseTJdXSwgb25lIGZvciBlYWNoIGxpbmUKZGVmIGVxX21ha2VyKGxpbmUpCiAgICBzbG9wZSA9IChsaW5lWzFdWzFdIC0gbGluZVswXVsxXSkgLyAobGluZVsxXVswXSAtIGxpbmVbMF1bMF0pCgl5X2ludGVyY2VwdCA9IGxpbmVbMF1bMV0gLSAoc2xvcGUgKiBsaW5lWzBdWzBdKQoJcmV0dXJuIFtzbG9wZSwgeV9pbnRlcmNlcHRdCmVuZApkZWYgaW50ZXJzZWN0aW9uX2ZpbmRlcihsaW5lMSxsaW5lMikgI2ZpbmRzIHRoZSBpbnRlcnNlY3Rpb24gcG9pbnQgd2hlbiBnaXZlbiBmb3VyIHBvaW50cyAtLSBtYWtlcyAyIGxpbmVzLCBzb2x2ZXMgZm9yIHg9eQoJbGluZTEgKz0gZXFfbWFrZXIobGluZTEpCglsaW5lMiArPSBlcV9tYWtlcihsaW5lMikKCWlmIGxpbmUxWzJdID09ICBsaW5lMlsyXSAKCQlyZXR1cm4gW2xpbmUxLGxpbmUyXS5zb3J0X2J5IHt8eHwgeFsxXVswXX1bMF1bMV0gaWYgbGluZTFbM10gPT0gbGluZTJbM10gI3VsdHJhIGVkZ2UgY2FzZTogaWYgdGhleSdyZSB0aGUgc2FtZSBsaW5lLCByZXR1cm4gdGhlIGVuZHBvaW50IHdpdGggdGhlIG1pbmltdW0geAoJCXJldHVybiBbLTEwLjAsLTEwLjBdICNsZXNzIGVkZ2UsIGJ1dCBzdGlsbCBleGNlcHRpb25hbGx5IHVubGlrZWx5OiBpZiB0aGV5IGhhdmUgdGhlIHNhbWUgc2xvcGUsIHJldHVybiBhIHJhbmdlIHRoYXQgZG9lc24ndCBleGlzdCBpbiBvdXIgYm9hcmQKCWVuZAoJeF9pbnQgPSAobGluZTJbM10gLSBsaW5lMVszXSkgLyAobGluZTFbMl0gLSBsaW5lMlsyXSkgI290aGVyd2lzZSwgcmV0dXJuIHRoZSBpbnRlcnNlY3Rpb24gcG9pbnQgKHoyIC0gejEpIC8obTEgLSBtMikKCXlfaW50ID0gKGxpbmUxWzJdICogeF9pbnQpICsgbGluZTFbM10KCXJldHVybiBbeF9pbnQsIHlfaW50XQplbmQKZGVmIG9uX2JvdGg/KGxpbmUxLGxpbmUyLGludCkgICMucm91bmQoMykgaXMgbmVjZXNzYXJ5IGJlY2F1c2UgZmxvYXRzIHN1Y2sgZGljawoJW2xpbmUxLGxpbmUyXS5lYWNoIGRvIHx4fAoJCXJldHVybiBmYWxzZSB1bmxlc3MgaW50WzBdLnJvdW5kKDMpID49IHhbMF1bMF0ucm91bmQoMykgJiYgaW50WzBdLnJvdW5kKDMpIDw9IHhbMV1bMF0ucm91bmQoMykKCQl5X3JhbmdlID0gW3hbMV1bMV0ucm91bmQoMykseFswXVsxXS5yb3VuZCgzKV0uc29ydAoJCXJldHVybiBmYWxzZSB1bmxlc3MgaW50WzFdLnJvdW5kKDMpID49IHlfcmFuZ2VbMF0gJiYgaW50WzFdLnJvdW5kKDMpIDw9IHlfcmFuZ2VbMV0KCWVuZAoJcmV0dXJuIHRydWUKZW5kCmRlZiBpbnRlcnNlY3RzKGN1cnJlbnRfbGluZSkgI3RvZG86IG1ha2UgZmxvYXRzIG5vdCBzdWNrLCBhbmQgbWFrZSBzdXJlIGl0J3Mgc2VsZWN0aW5nIHRoZSByaWdodCBsaW5lIChjaGVjayB0byBzZWUgaWYgdGhlIGludGVyY2VwdCBjb29yZGluYXRlcyBmYWxsIGJvdGggb24gdGhlIGN1cnJlbnQgbGluZSBhbmQgdGhlIG5ldyBsaW5lIGxlbmd0aCwgbm90IGV4dGVuZGVkIGxlbmd0aHMgCglAYWxsX2ludGVyc2VjdHNbY3VycmVudF9saW5lXSA9IFtdCglwb3NzaWJpbGl0aWVzID0gQGxpbmVzLnNlbGVjdCB7fHh8IEBhbGxfaW50ZXJzZWN0c1t4XS5uaWw/fSAjY2hlY2sgZm9yIGludGVyc2VjdGlvbnMgYWdhaW5zdCBhbGwgb3RoZXIgbGluZXMgdGhhdCBoYXZlbid0IGFscmVhZHkgYmVlbiBjaGVja2VkIGZvciBpbnRlcnNlY3Rpb25zIChvciBzZWxmKQoJcG9zc2liaWxpdGllcy5lYWNoIGRvIHx4fAoJCWludCA9IGludGVyc2VjdGlvbl9maW5kZXIoY3VycmVudF9saW5lLHgpCgkJaWYgb25fYm90aD8oY3VycmVudF9saW5lLHgsaW50KQoJCQlAanVzdF9pbnRzLnB1c2ggaW50CgkJCUBhbGxfaW50ZXJzZWN0c1tpbnRdID0gW2N1cnJlbnRfbGluZSx4XSAjZXZlcnkgaW50ZXJzZWN0aW9uIGhhcyBleGFjdGx5IDIgbGluZXMgLS0gYXZvaWRzIHNvbWUgZmxvYXQgcHJvYmxlbXMKCQllbmQKCWVuZAoJcmV0dXJuIHRydWUKZW5kCmRlZiBhcmVhX3RvdGFsZXIocG9pbnQxLHBvaW50MikgI3RvdGFscyBhcmVhIHVuZGVyIGFueSBzdHJhaWdodF9saW5lIHNlZ21lbnQgZnJvbSB4IGF4aXMgLS0gcmVjdGFuZ2xlICsgdHJpYW5nbGUKCXhfcmFuZ2UgPSBbcG9pbnQxWzBdLHBvaW50MlswXV0uc29ydAoJeV9yYW5nZSA9IFtwb2ludDFbMV0scG9pbnQyWzFdXS5zb3J0Cgl3aWR0aCA9IHhfcmFuZ2VbMV0gLSB4X3JhbmdlWzBdCglyZWN0X2hlaWdodCA9IHlfcmFuZ2VbMF0KCXRyaWFuZ2xlX2hlaWdodCA9ICh5X3JhbmdlWzFdIC0geV9yYW5nZVswXSkKCXJldHVybiAocmVjdF9oZWlnaHQgKiB3aWR0aCkgKyAoMC41ICogd2lkdGggKiB0cmlhbmdsZV9oZWlnaHQpICNyZWN0IGFyZWEgKyB0cmlhbmdsZSBhcmVhCmVuZAoKI2Zvcm1hdDogW2NlbnRlci1wb3MsYmFzZS1sZW5ndGgsaGVpZ2h0XQp0cmlhbmdsZXMgPSBbXQo1LnRpbWVzIGRvICNtYWtlIHJhbmRvbSB0cmlhbmdsZXMKCXRyaWFuZ2xlcy5wdXNoIFsocmFuZCg1MDAwKSArIDI1MDEpIC8gMTAuMCAsIChyYW5kKDUwMDApICsgMSkgLyAxMC4wICwgKHJhbmQoNTAwMCkgKyAxMDAxKSAvIDEwLjBdCmVuZApjb2xvcnMgPSBbJ3JlZCcsJ2JsdWUnLCdncmVlbicsJ3B1cnBsZScsJ29yYW5nZScsJ3llbGxvdycsJ2Jyb3duJywnY3lhbicsJ21hZ2VudGEnXQppbWdsID0gTWFnaWNrOjpJbWFnZUxpc3QubmV3CmltZ2wubmV3X2ltYWdlKDEwMDAsIDYwMCkKZ2MgPSBNYWdpY2s6OkRyYXcubmV3Cgp0cmlhbmdsZXMuZWFjaCBkbyB8eHwjZHJhdyB0cmlhbmdsZXMKCWdjLmZpbGwoY29sb3JzLnNhbXBsZSgxKVswXSkKCWdjLmZpbGxfb3BhY2l0eSgwLjUpCgljb29yZHMgPSBbKHhbMF0gLSAoeFsxXSAvIDIpKSwwLAl4WzBdLHhbMl0sCSh4WzBdICsgKHhbMV0gLyAyKSksMF0KCUBsaW5lcy5wdXNoIFtbY29vcmRzWzBdLGNvb3Jkc1sxXV0sW2Nvb3Jkc1syXSxjb29yZHNbM11dXQoJQGxpbmVzLnB1c2ggW1tjb29yZHNbMl0sY29vcmRzWzNdXSxbY29vcmRzWzRdLGNvb3Jkc1s1XV1dCglldmFsICJnYy5wb2x5Z29uKCN7Y29vcmRzLmpvaW4oJywnKX0pIgplbmQKCkBsaW5lcy5zb3J0X2J5ISB7fHh8IHhbMF1bMF19ICNzdGFydCBhdCBsZWZ0IC0tIGZpcnN0IGxpbmUgPSBoaWdoZXN0IGxpbmUKQGxpbmVzLmVhY2ggeyB8eHwgaW50ZXJzZWN0cyh4KSB9ICNidWlsZCBhbGwgcmVhbCBpbnRlcnNlY3Rpb25zCkBqdXN0X2ludHMuc29ydF9ieSEge3x4fCB4WzBdfSAjc29ydCBpbnRlcmNlcHRzIGJ5IHgsIG1vdmUgZnJvbSBsZWZ0IHRvIHJpZ2h0CkB0b3BfaW50ZXJzZWN0cy5wdXNoIEBsaW5lc1swXVswXSAjZmlyc3QgcG9pbnQgb24gdGhlIGxpbmUgaXMgdGhlIGxlZnRtb3N0IHBvaW50Cmxhc3RfcG9pbnQgPSBAbGluZXMuc29ydF9ieSB7fHh8IHhbMV1bMF19Lmxhc3RbMV0KY3VycmVudF9saW5lID0gQGxpbmVzWzBdICNzdGFydCB3aXRoIGxlZnRtb3N0IGxpbmUKCkBqdXN0X2ludHMuZWFjaCBkbyB8eHwgI2l0ZXJhdGUgdGhyb3VnaCBpbnRlcmNlcHRzLCBmaW5kaW5nIHRoZSB0b3AgbGluZQoJaWYgY3VycmVudF9saW5lWzFdWzBdIDwgeFswXSAmJiBjdXJyZW50X2xpbmVbMV1bMV0udG9fZiA9PSAwLjAgICNpZiB0aGUgeCBvZiB0aGUgbmV4dCBpbnRlcmNlcHQgaXMgYmV5b25kIHRoZSB4IG9mIHRoZSBlbmQgb2Ygb3VyIGxpbmUsIHRyaWFuZ2xlIGhpdHMgdGhlIHggYXhpcywgc28gYWRkIGxpbmUgZW5kcG9pbnQgYW5kIGdldCB0aGUgbmV4dCBsaW5lCgkJQHRvcF9pbnRlcnNlY3RzLnB1c2ggY3VycmVudF9saW5lWzFdCgkJY3VycmVudF9saW5lID0gQGxpbmVzW0BsaW5lcy5pbmRleCB7fHp8IHpbMF1bMF0gPiBjdXJyZW50X2xpbmVbMV1bMF19XQoJCUB0b3BfaW50ZXJzZWN0cy5wdXNoIGN1cnJlbnRfbGluZVswXQoJZW5kCgkKCWlmIEBhbGxfaW50ZXJzZWN0c1t4XS5pbmNsdWRlPyhjdXJyZW50X2xpbmUpICNpZiB0aGUgbmV4dCBpbnRlcnNlY3QgaW5jbHVkZXMgb3VyIGxpbmUsIHN3aXRjaCBsaW5lcywgcHVzaCBpbnRlcnNlY3QgdG8gdG9wX2ludGVyc2VjdHMKCQlAdG9wX2ludGVyc2VjdHMucHVzaCB4CgkJY3VycmVudF9saW5lID0gKEBhbGxfaW50ZXJzZWN0c1t4XSAtIFtjdXJyZW50X2xpbmVdKVswXQoJZW5kCgkjb3RoZXJ3aXNlLCBpZiB0aGUgaW50IGlzbid0IG9uIG91ciBsaW5lLCBkbyBub3RoaW5nIChleGNlcHQgZHJhdyBhIGNpcmNsZSkuCgkKCSMgSWRlbnRpZnkgdGhlIGludGVyc2VjdGlvbnMgd2l0aCBncmF5IGNpcmNsZXMKCWdjLnN0cm9rZSgnZ3JheTUwJykKCWdjLnN0cm9rZV93aWR0aCgxKQoJZ2MuZmlsbF9vcGFjaXR5KDApCgljb29yZHMgPSAiZ2MuY2lyY2xlKCN7eC5qb2luKCcsJyl9LCN7eC5tYXAge3x5fCB5ICsgM30uam9pbignLCcpfSkiCglldmFsIGNvb3JkcwplbmQKCkB0b3BfaW50ZXJzZWN0cy5wdXNoIGxhc3RfcG9pbnQgI2FkZCB0aGUgbGFzdCBwb2ludCBhZnRlciBhbGwgaW50ZXJjZXB0cyA9KQoKYXJlYSA9IDAKKEB0b3BfaW50ZXJzZWN0cy5sZW5ndGggLSAxKS50aW1lcyBkbyB8eHwgI2NvdW50IHRoZSB0b3RhbCBhcmVhIHVuZGVyIGFsbCBzZWN0aW9ucwoJYXJlYSArPSBhcmVhX3RvdGFsZXIoQHRvcF9pbnRlcnNlY3RzW3hdLEB0b3BfaW50ZXJzZWN0c1t4ICsgMV0pCmVuZApwdXRzICJDb21wdXRlZCBhcmVhIGlzOiAje2FyZWF9IgoKc3VtID0gMAp0cmlhbmdsZXMuZWFjaCBkbyB8eHwgI3N1bSBhbGwgdGhlIHRyaWFuZ2xlcywgZm9yIGNvbXBhcmlzb24KCXN1bSArPSAoeFsxXSAqIHhbMl0gKiAwLjUpCmVuZApwdXRzICJBcmVhIG9mIGFsbCB0cmlhbmdsZXMsIGluY2x1ZGluZyBvdmVybGFwLCBpczogI3tzdW19IgoKCmdjLnN0cm9rZSgnYmxhY2snKQpnYy5zdHJva2Vfd2lkdGgoMykKZXZhbCAiZ2MucG9seWdvbigje0B0b3BfaW50ZXJzZWN0cy5mbGF0dGVuLmpvaW4oJywnKX0pIiAjZHJhdyBhIHBvbHlnb24gd2hpY2ggaXMgQHRvcF9pbnRlcnNlY3RzLmZsYXR0ZW4gLS0gdHJhY2UgdG9wcyBvZiB0cmlhbmdsZXMKCmdjLmRyYXcoaW1nbCkgI2RyYXcgaW1hZ2UKaW1nbC5mbGlwISAjZmxpcCBpdDsgd2UgZHJhdyB1cHNpZGUgZG93biA9KQppbWdsLndyaXRlKCJwb2x5Z29uLmdpZiIp