Daily Programming Challenge 345 Hard: 2D Triangle Mesh Generator (MIT License)

345h.rb

#!/usr/bin/env ruby
# Copyright 2018 Taylor C. Richberger
#
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
# 
# The above copyright notice and this permission notice shall be included in all
# copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
# SOFTWARE.

require 'optparse'
require 'matrix'
require 'set'

require 'nokogiri'

# Get convex hull, by individual points, in clockwise order
def quick_hull(points)
  # Don't change input
  points = points.dup

  # If too small for a triangle, return as array
  return points.to_a if points.size < 3

  # Add two points to the hull, being the extremes along the horizontal axis
  hull = points.minmax_by {|point| point[0]}
  points.subtract(hull)
  # Vec from a -> b
  linevec = hull[1] - hull[0]
  left, right = points.partition do |point|
    # Split into left and right elements
    linevec.cross.dot(point - hull[0]) > 0
  end.map(&Set.method(:new))

  [hull[0]] + find_hull(left, *hull) + [hull[1]] + find_hull(right, *hull.reverse)
end

# a and b must not be in points.  Finds left hull section from points, not
# including those points.
def find_hull(points, a, b)
  return [] if points.empty?

  ab = b - a

  # Get point farthest to the left of ab
  max = points.max_by do |point|
    ab.cross.dot(point - a)
  end

  a_max = max - a

  max_b = b - max

  leftpoints = Set.new(points.select do |point|
    a_max.cross.dot(point - a) > 0
  end)
  rightpoints = points.select do |point|
    max_b.cross.dot(point - max) > 0
  end
  return find_hull(leftpoints, a, max) + [max] + find_hull(rightpoints, max, b)
end

# Gets orientation of points, -1 for clockwise, 1 for counter, 0 for colinear
def orientation(a, b, c)
  (b - a).cross.dot(c - a) <=> 0
end

# Check if two edges intersect (endpoints may be the same)
# algorithm from https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/
# p -> x, q -> y, 1 -> a, 2 -> b
def intersect?(a, b)
  ax_ay_bx = orientation(a[0], a[1], b[0])
  ax_ay_by = orientation(a[0], a[1], b[1])
  bx_by_ax = orientation(b[0], b[1], a[0])
  bx_by_ay = orientation(b[0], b[1], a[1])
  if (ax_ay_bx != ax_ay_by) and
      (bx_by_ax != bx_by_ay) and
      # Two points may be shared without intersection
      (a + b).to_set.size > 3
    return true
  end

  # Fully colinear, bounding box determines intersection
  if ax_ay_bx == 0 &&
      ax_ay_by == 0 &&
      bx_by_ax == 0 &&
      bx_by_ay == 0
    min_x_a = a.map(&:first).min
    max_x_a = a.map(&:first).max
    min_y_a = a.map(&:to_a).map(&:last).min
    max_y_a = a.map(&:to_a).map(&:last).max

    min_x_b = b.map(&:first).min
    max_x_b = b.map(&:first).max
    min_y_b = b.map(&:to_a).map(&:last).min
    max_y_b = b.map(&:to_a).map(&:last).max

    # If they are colinear, bounding box determines intersection
    # They should be allowed to touch at endpoints
    if min_x_a >= max_x_b ||
      max_x_a <= min_x_b ||
      min_y_a >= max_y_b ||
      max_y_a <= min_y_b
      return false
    else
      return true
    end
  end

  return false
end

# find all edges between outer points and inner points, adding to and avoiding
# intersection with edges
def interhull_edges(outer, inner, edges)
  edges = edges.dup
  outer.each do |opoint|
    inner.each do |ipoint|
      unless opoint == ipoint
        testedge = [opoint, ipoint]
        unless edges.any? {|edge| intersect?(testedge, edge)}
          edges << testedge
        end
      end
    end
  end

  return edges
end

def main!
  options = {
    pointsize: 4,
    edgesize: 4,
    scale: 500,
    offset: 25,
  }
  OptionParser.new do |opts|
    opts.banner = "Usage: example.rb [options]"

    opts.on_tail("-h", "--help", "Show this help message") do
      puts opts
      exit
    end
    opts.on("-o", "--output FILE", "Set output svg file (default is stdout)") do |file|
      options[:output] = file
    end
    opts.on("-p", "--pointsize SIZE", Float, "Set radius of points") do |size|
      options[:pointsize] = size
    end
    opts.on("-e", "--edgesize SIZE", Float, "Set edge width") do |size|
      options[:edgesize] = size
    end
    opts.on("-s", "--scale SCALE", Float, "Pixel size of max canvas dimension, excluding offset") do |scale|
      options[:scale] = scale
    end
    opts.on("-O", "--offset OFFSET", Float, "Shift all point and edge positions by this amount in pixels") do |offset|
      options[:offset] = offset
    end
  end.parse!

  # Harvest stdin/file points into a map
  points = Set.new(ARGF.map do |line|
    line.strip!
    # Split on anything that can't be used to construct a number
    pair = line.split(/[^-+eE\.\d]+/)
    # We don't need the size of input, so discard it
    next if pair.length != 2
    Vector::elements pair.map(&method(:Float))
  end.compact)
  allpoints = points.dup

  hulls = []
  until points.empty?
    hull = quick_hull(points)
    hulls << hull
    points.subtract(hull)
  end

  edges = hulls.each_cons(2).map do |outer, inner|
    outeredges = []
    inneredges = []
    if outer.size > 2
      outeredges = outer.each_cons(2).map.to_a + [[outer.last, outer.first]]
    end
    if inner.size > 2
      inneredges = inner.each_cons(2).map.to_a + [[inner.last, inner.first]]
    end

    inter = interhull_edges(outer, inner, inneredges)
    outeredges + inter
  end.flatten(1).to_set

  # The innermost hull may be more than 3 points, so we need to check it against
  # itself as well
  inner = hulls.last
  if inner.size > 3
    inneredges = inner.each_cons(2).map.to_a + [[inner.last, inner.first]]
    edges.merge(interhull_edges(inner, inner, inneredges))
  end

  scale, offset = options.values_at(:scale, :offset)

  #calculate canvas size as well as shifts
  minx = allpoints.map(&:first).min
  miny = allpoints.map(&:to_a).map(&:last).min
  maxx = allpoints.map(&:first).max
  maxy = allpoints.map(&:to_a).map(&:last).max
  origwidth = maxx - minx
  origheight = maxy - miny
  origmax = [origwidth, origheight].max

  scale = scale / origmax

  builder = Nokogiri::XML::Builder.new(encoding: 'UTF-8') do |xml|
    xml.svg(
      xmlns: 'http://www.w3.org/2000/svg',
      version: '1.1',
      # Calculate canvas, with scale, and with offset on both sides
      width: (maxx - minx) * scale + offset * 2,
      height: (maxy - miny) * scale + offset * 2,
    ) do
      edges.each do |a, b|
        xml.line(
          x1: (a[0] - minx) * scale + offset,
          y1: (a[1] - miny) * scale + offset,
          x2: (b[0] - minx) * scale + offset,
          y2: (b[1] - miny) * scale + offset,
          stroke: 'black',
          'stroke-width': options[:edgesize],
        )
      end
      allpoints.each do |point|
        xml.circle(
          cx: (point[0] - minx) * scale + offset,
          cy: (point[1] - miny) * scale + offset,
          stroke: 'blue',
          fill: 'blue',
          r: options[:pointsize],
        )
      end
    end
  end
  if options.key? :output
    File::open(options[:output], 'w') do |file|
      file.puts builder.to_xml
    end
  else
    puts builder.to_xml
  end
end

main!