view release on metacpan or  search on metacpan

lib/Image/Bitmap2Paths.pm  view on Meta::CPAN

#   x CC
#  / x f
# c  Lxx
# E    v

# Input encodes a sequence of rectangles made of grid squares; rectangles share UR/LL corners:
#                â–¡	is encoded as 2,4,4,3,1 (all positive)
#             â–¡â–¡â–¡
#         â–¡â–¡â–¡â–¡
#     â–¡â–¡â–¡â–¡
#   â–¡â–¡
# We want to find a line which rasterizes to these squares, i.e., intersect the (“red”) vertical disector of every square.
#
# It is the same as intersecting a (“green”) horizontal line of length=1 centered at the shared corners, 
# plus intersecting the red lines of the leftmost and the rightmost square.  Suppose that non-on-edge rectanles
# are only of two sizes, s and s+1.  Swapping x and y axis, and subtracting y'=y-sx moves the green lines to a
# collection of red lines of a new configuration of rectanges.  This gives a step of recursion.  Above configuration is moved to
#     â–¡â–¡
#    â–¡
#   â–¡
# On this picture, the “old” red lines (“pink”, two at edges) become sloped lines with slope -s, with horizontal projection 1
# (ending on horizontal grid lines, below the center of first square, and below the center of the last square.  

# The right end of the left pink line is below the new-red line of the leftmost new square; hence it is below any fitting
# line.  One must only check that the left end of the left pink line is above the fitting line.  If this left end is on level 
# (or above) the top of the left square, everything is OK.  

# If it is on the level or below the bottom of the left square, then draw a new green line: horizontal line of lenght 1 going right
# from the left end of the pink like.  Obviously, the fitting line intersects the pink line iff it intersects the new green line.

# There are several cases when we may exclude the new green line being below the bottom of the left square:
#    • if all rectangles are actually squares, one could replace s by s+1 above, and have one rectangle instead; exclude this;
#    • if there is one rectangle longer than 2 (or two of length 2) the slope of the fitting line is < 1, so intersection with 
#      such green line is impossible;
#    • If there is one rectangle of length 2, and the rest are squares, the green line may be 1 unit below the bottom (and it
#      is unique; this may be repeated on both ends).

# Only two cases remain: the rectangles consist of 1 square (total), and that with a pink line which may be either forgotten,
# or replaced by an “additional” green line.  (The additional green lines have no associated red lines, so on the NEXT step of induction
# they would give no pink lines.)  

# In the first (“trivial”) case, the preceding step is of two rectangles with no added green lines.

# So induction step:  We start with n rectangles with k≤2 added green lines; coordinate change gives rectangles of total length 
# n-1+k with 2-k pink lines.  A pink line is either forgotten, or impossible, or gives a unique solution, or is convertible to
# a green line.  So either we exclude a configuration, or find a unique solution or a trivial case, or get rectangles with n-1+k 
# squares and ≤2-k added green lines.  The only cases when the number of squares did not decrease is:
#    All rectangles at start are squares except one of length 2; we had 2 added green lines.
# But then on the next step we have no added green lines, so the next step is the trivial one.

# (To avoid the trivial step [which is tricky] we ensure that we call recursively, there are at least two squares.
#  This means at least two green intervals on the previous stage.)
# Provided that this case is handled in the caller, the additional green lines appear when the length of the start/end rectangle
# is s+1; if it is above s+1, this is an impossible situation.

# In particular, every case is reduced to a “unique solution” one, or the “trivial” one.  The last one is equivalent to
# having 3 equidistant paralle lines with an an interval [AB] on the middle one (the preimage [AB] of the last red line), and
# opposite to each other rays XA' and YB' on the other two lines.  The fitting line must intersect all 3 of them. 
# Oone of ray may be the whole line).  It is easy to see that this is equivalent to the line intersecting intervals [XA], [AB] 
# and [BY].  If the quadrilateral XAYB is not convex, it may be decreased (so that X,A,B,Y are 3 vertices of a â–³, and a point
# on a side.  If it is convex, then intersecting [AB] is a corollary of other two.  ???

# Possibly unknown squares: the 2nd and 3rd row “share” a x-coordinate; assume that intersecting a red line in any of them is OK.
#                â–¡	This is equivalent to having the red line of double length, which is equivalent to
#             â–¡â–¡â–¡		the green line of double length at this position (assuming it is not at edge).
#         â–¡â–¡â–¡â–¡		Hence this allows the induction step as well.
#     â–¡â–¡â–¡â–¡â–¡		(Encode ignoring the extra square at second line, with second line marked as: $extended->{1}=1.)
#   â–¡â–¡

# Returns empty or a,b,db of the line y=ax+b-db which rasterizes to the rectangles of widths @$CC (connected UR ↔ LL corners);
# The other two arguments as as above.  LL corner of the leftmost of bottom squares is at 0,0.
sub encodes_line ($;$$$);		# Refused degenerated cases when there is a unique solution — with choices in rasterization
sub encodes_line ($;$$$) { 		# %$extended should not have negative keys
  my ($CC, $green_at_left, $green_at_right, $extended) = (shift, shift, shift, shift||{}); # Every elt encodes delta between cells
  # A horrible mess of special-cases before we can recognize "runs", and flip axes...
#  warn "Got: [@$CC], $green_at_left, $green_at_right";
  # Banal case: one rectangle
  return 0, 1/2 if 1 >= @$CC and not ($green_at_left or $green_at_right);		# No greens at all; one rectangle
  my(@jumps, $left_red, $right_red, %seen) = @$CC;	# jumps between greens
  if ($green_at_left) { $left_red = $CC->[0] - 1 }
  else { shift @jumps }
  if ($green_at_right) { $right_red = $CC->[-1] - 1 }
  else { pop @jumps }
  # Need to exclude a trivial case
  unless (@jumps) {					# Only one green
    if ($green_at_left or $green_at_right) {		# Maximize some metric (∑distances to mid-red points)
      	my $sl = 3/(4*$CC->[0] - 1);			#    ==> intersects right at height ≈¾.
      	return ($green_at_left ? ($sl, $sl/4) : ($sl, 1/4 - $sl/2)) # Cut the green interval in the same proportion
    } else {						# Two rectangles; likewise: if ratio of lengths is t≤1, use ¾(1+t²)/(1+t³)
      my $addHalf = 0;
      if ($extended->{0} and $CC->[0] < $CC->[1] - 1) {
        $CC = [$CC->[0] + 1, $CC->[1] - 1];
      } elsif ($extended->{0} and $CC->[0] == $CC->[1] - 1) {
        $addHalf = 1;
      }
      if ($CC->[0] + $addHalf == $CC->[1]) {	# Go through the center of symmetry, with intersection of edge red lines as above:
        my $sl = 3/(4*$CC->[0] + 2*$addHalf - 2);
        return($sl, 1/4 - $sl/2);
      } elsif ($CC->[0] < $CC->[1]) {		# One strategy is to continue periodically, then make a best fit; this joints
        # midpoints of rectangles.  If differ by one, this breaks the green line 1:3 (with 1 on the side of longer rectangle).
        #    On the other hand, to avoid close-to pathological rasterizations, we should divide the green line in the middle!
        # The best derasterization of 1+2 cuts the red lines at heights ¾,¼,¾ (the last ¾ makes it also good-in-L²-norm).
        #    (It is also better since there are two ways to treat it: one can consider the main direction to be horizontal,
        #     or to be diagonal.  This “best” approximation is the same in these two approaches.)
        my $t = $CC->[0] / ($CC->[1] - 1);		# Break green as 1:3, but use the slope as above with t-correction
        my $sl = 3*(1+$t*$t)/(1+$t*$t*$t)/(4*$CC->[1] - 2);
        return($sl, 1 - $sl*$CC->[0]);
      } else {				# Likewise
        my $t = $CC->[1] / ($CC->[0] - 1); # If differ by 1, the distances to red lines are ¼, ¾, ⁵⁄₄,... exactly as ½,3/3 for equal lengths
        my $sl = 3*(1+$t*$t)/(1+$t*$t*$t)/(4*$CC->[0] - 2);
        return($sl, 1 - $sl*$CC->[0]);
      }
    }
  }
  # Up to this moment, always successfully return; below, unsuccessful returns indented (the only successful is the last one):
  my %jump_pre_ext = map { ($_ + !!$green_at_left, $extended->{$_}) } keys %$extended;	# shift keys of extended to be pre-jump
  my $tot_jumps = 0;
  $tot_jumps += $_ for @jumps;
  my($slope_min, $slope_max) = (($tot_jumps - !!$jump_pre_ext{0})/@jumps, ($tot_jumps + !!$jump_pre_ext{@jumps})/@jumps);
  if (int($slope_min) != int $slope_max) {	# differ by ≤1 unless @jumps = 1
    # There is a chance that after shear transformation with slope = int $slope_max, we have both increasing and decreasing paths.