src/textord/colpartitiongrid.cpp
ColPartition *ColPartitionGrid::BestMergeCandidate(
    const ColPartition *part, ColPartition_CLIST *candidates, bool debug,
    const std::function<bool(const ColPartition *, const ColPartition *)>
        &confirm_cb,
    int *overlap_increase) {
  if (overlap_increase != nullptr) {
    *overlap_increase = 0;
  }
  if (candidates->empty()) {
    return nullptr;
  }
  int ok_overlap =
      static_cast<int>(kTinyEnoughTextlineOverlapFraction * gridsize() + 0.5);
  // The best neighbour to merge with is the one that causes least
  // total pairwise overlap among all the neighbours.
  // If more than one offers the same total overlap, choose the one
  // with the least total area.
  const TBOX &part_box = part->bounding_box();
  ColPartition_C_IT it(candidates);
  ColPartition *best_candidate = nullptr;
  // Find the total combined box of all candidates and the original.
  TBOX full_box(part_box);
  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
    ColPartition *candidate = it.data();
    full_box += candidate->bounding_box();
  }
  // Keep valid neighbours in a list.
  ColPartition_CLIST neighbours;
  // Now run a rect search of the merged box for overlapping neighbours, as
  // we need anything that might be overlapped by the merged box.
  FindOverlappingPartitions(full_box, part, &neighbours);
  if (debug) {
    tprintf("Finding best merge candidate from %d, %d neighbours for box:",
            candidates->length(), neighbours.length());
    part_box.print();
  }
  // If the best increase in overlap is positive, then we also check the
  // worst non-candidate overlap. This catches the case of multiple good
  // candidates that overlap each other when merged. If the worst
  // non-candidate overlap is better than the best overlap, then return
  // the worst non-candidate overlap instead.
  ColPartition_CLIST non_candidate_neighbours;
  non_candidate_neighbours.set_subtract(SortByBoxLeft<ColPartition>, true,
                                        &neighbours, candidates);
  int worst_nc_increase = 0;
  int best_increase = INT32_MAX;
  int best_area = 0;
  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
    ColPartition *candidate = it.data();
    if (confirm_cb != nullptr && !confirm_cb(part, candidate)) {
      if (debug) {
        tprintf("Candidate not confirmed:");
        candidate->bounding_box().print();
      }
      continue;
    }
    int increase = IncreaseInOverlap(part, candidate, ok_overlap, &neighbours);
    const TBOX &cand_box = candidate->bounding_box();
    if (best_candidate == nullptr || increase < best_increase) {
      best_candidate = candidate;
      best_increase = increase;
      best_area = cand_box.bounding_union(part_box).area() - cand_box.area();
      if (debug) {
        tprintf("New best merge candidate has increase %d, area %d, over box:",
                increase, best_area);
        full_box.print();
        candidate->Print();
      }
    } else if (increase == best_increase) {
      int area = cand_box.bounding_union(part_box).area() - cand_box.area();
      if (area < best_area) {
        best_area = area;
        best_candidate = candidate;
      }
    }
    increase = IncreaseInOverlap(part, candidate, ok_overlap,
                                 &non_candidate_neighbours);
    if (increase > worst_nc_increase) {
      worst_nc_increase = increase;
    }
  }
  if (best_increase > 0) {
    // If the worst non-candidate increase is less than the best increase
    // including the candidates, then all the candidates can merge together
    // and the increase in outside overlap would be less, so use that result,
    // but only if each candidate is either a good diacritic merge with part,
    // or an ok merge candidate with all the others.
    // See TestCompatibleCandidates for more explanation and a picture.
    if (worst_nc_increase < best_increase &&
        TestCompatibleCandidates(*part, debug, candidates)) {
      best_increase = worst_nc_increase;
    }
  }
  if (overlap_increase != nullptr) {
    *overlap_increase = best_increase;
  }
  return best_candidate;
}
// Finds and returns the best candidate ColPartition to merge with part,
// selected from the candidates list, based on the minimum increase in
// pairwise overlap among all the partitions overlapped by the combined box.
// If overlap_increase is not nullptr then it returns the increase in overlap
// that would result from the merge.
// confirm_cb is a permanent callback that (if non-null) will be used to
// confirm the validity of a proposed merge candidate before selecting it.
//
// ======HOW MERGING WORKS======
// The problem:
// We want to merge all the parts of a textline together, but avoid merging
// separate textlines. Diacritics, i dots, punctuation, and broken characters
// are examples of small bits that need merging with the main textline.
// Drop-caps and descenders in one line that touch ascenders in the one below
// are examples of cases where we don't want to merge.
//
// The solution:
// Merges that increase overlap among other partitions are generally bad.
// Those that don't increase overlap (much) and minimize the total area
// seem to be good.
//
// Ascii art example:
// The text:
// groggy descenders
// minimum ascenders
// The boxes: The === represents a small box near or overlapping the lower box.
// -----------------
// |               |
// -----------------
// -===-------------
// |               |
// -----------------
// In considering what to do with the small === box, we find the 2 larger
// boxes as neighbours and possible merge candidates, but merging with the
// upper box increases overlap with the lower box, whereas merging with the
// lower box does not increase overlap.
// If the small === box didn't overlap either to start with, total area
// would be minimized by merging with the nearer (lower) box.
//
// This is a simple example. In reality, we have to allow some increase
// in overlap, or tightly spaced text would end up in bits.
Finds and returns the best candidate ColPartition to merge with part,
selected from the candidates list, based on the minimum increase in
pairwise overlap among all the partitions overlapped by the combined box.
If overlap_increase is not nullptr then it returns the increase in overlap
that would result from the merge.
confirm_cb is a permanent callback that (if non-null) will be used to
confirm the validity of a proposed merge candidate before selecting it.



The solution:
Merges that increase overlap among other partitions are generally bad.
Those that don't increase overlap (much) and minimize the total area
seem to be good.

Ascii art example:
The text:
groggy descenders
minimum ascenders
The boxes: The === represents a small box near or overlapping the lower box.





In considering what to do with the small === box, we find the 2 larger
boxes as neighbours and possible merge candidates, but merging with the
upper box increases overlap with the lower box, whereas merging with the
lower box does not increase overlap.
If the small === box didn't overlap either to start with, total area
would be minimized by merging with the nearer (lower) box.

This is a simple example. In reality, we have to allow some increase
in overlap, or tightly spaced text would end up in bits.
Finds and returns the best candidate ColPartition to merge with part selected from the candidates list based on the minimum increase in pairwise overlap among all the partitions overlapped by the combined box . If overlap_increase is not nullptr then it returns the increase in overlap that would result from the merge . confirm_cb is a permanent callback that ( if non - null ) will be used to confirm the validity of a proposed merge candidate before selecting it . The solution : Merges that increase overlap among other partitions are generally bad . Those that don ' t increase overlap ( much ) and minimize the total area seem to be good . Ascii art example : The text : groggy descenders minimum ascenders The boxes : The === represents a small box near or overlapping the lower box . In considering what to do with the small === box we find the 2 larger boxes as neighbours and possible merge candidates but merging with the upper box increases overlap with the lower box whereas merging with the lower box does not increase overlap . If the small === box didn ' t overlap either to start with total area would be minimized by merging with the nearer ( lower ) box . This is a simple example . In reality we have to allow some increase in overlap or tightly spaced text would end up in bits .
ColPartition *ColPartitionGrid::BestMergeCandidate(
    const ColPartition *part, ColPartition_CLIST *candidates, bool debug,
    const std::function<bool(const ColPartition *, const ColPartition *)>
        &confirm_cb,
    int *overlap_increase) {
  if (overlap_increase != nullptr) {
    *overlap_increase = 0;
  }
  if (candidates->empty()) {
    return nullptr;
  }
  int ok_overlap =
      static_cast<int>(kTinyEnoughTextlineOverlapFraction * gridsize() + 0.5);
  const TBOX &part_box = part->bounding_box();
  ColPartition_C_IT it(candidates);
  ColPartition *best_candidate = nullptr;
  TBOX full_box(part_box);
  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
    ColPartition *candidate = it.data();
    full_box += candidate->bounding_box();
  }
  ColPartition_CLIST neighbours;
  FindOverlappingPartitions(full_box, part, &neighbours);
  if (debug) {
    tprintf("Finding best merge candidate from %d, %d neighbours for box:",
            candidates->length(), neighbours.length());
    part_box.print();
  }
  ColPartition_CLIST non_candidate_neighbours;
  non_candidate_neighbours.set_subtract(SortByBoxLeft<ColPartition>, true,
                                        &neighbours, candidates);
  int worst_nc_increase = 0;
  int best_increase = INT32_MAX;
  int best_area = 0;
  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
    ColPartition *candidate = it.data();
    if (confirm_cb != nullptr && !confirm_cb(part, candidate)) {
      if (debug) {
        tprintf("Candidate not confirmed:");
        candidate->bounding_box().print();
      }
      continue;
    }
    int increase = IncreaseInOverlap(part, candidate, ok_overlap, &neighbours);
    const TBOX &cand_box = candidate->bounding_box();
    if (best_candidate == nullptr || increase < best_increase) {
      best_candidate = candidate;
      best_increase = increase;
      best_area = cand_box.bounding_union(part_box).area() - cand_box.area();
      if (debug) {
        tprintf("New best merge candidate has increase %d, area %d, over box:",
                increase, best_area);
        full_box.print();
        candidate->Print();
      }
    } else if (increase == best_increase) {
      int area = cand_box.bounding_union(part_box).area() - cand_box.area();
      if (area < best_area) {
        best_area = area;
        best_candidate = candidate;
      }
    }
    increase = IncreaseInOverlap(part, candidate, ok_overlap,
                                 &non_candidate_neighbours);
    if (increase > worst_nc_increase) {
      worst_nc_increase = increase;
    }
  }
  if (best_increase > 0) {
    if (worst_nc_increase < best_increase &&
        TestCompatibleCandidates(*part, debug, candidates)) {
      best_increase = worst_nc_increase;
    }
  }
  if (overlap_increase != nullptr) {
    *overlap_increase = best_increase;
  }
  return best_candidate;
}
ColPartition * ColPartitionGrid :: BestMergeCandidate ( const ColPartition * part , ColPartition_CLIST * candidates , bool debug , const std :: function < bool ( const ColPartition * , const ColPartition * ) > & confirm_cb , int * overlap_increase ) { if ( overlap_increase != nullptr ) { * overlap_increase = 0 ; } if ( candidates -> empty ( ) ) { return nullptr ; } int ok_overlap = static_cast < int > ( kTinyEnoughTextlineOverlapFraction * gridsize ( ) + 0.5 ) ; const TBOX & part_box = part -> bounding_box ( ) ; ColPartition_C_IT it ( candidates ) ; ColPartition * best_candidate = nullptr ; TBOX full_box ( part_box ) ; for ( it . mark_cycle_pt ( ) ; ! it . cycled_list ( ) ; it . forward ( ) ) { ColPartition * candidate = it . data ( ) ; full_box += candidate -> bounding_box ( ) ; } ColPartition_CLIST neighbours ; FindOverlappingPartitions ( full_box , part , & neighbours ) ; if ( debug ) { tprintf ( " " , candidates -> length ( ) , neighbours . length ( ) ) ; part_box . print ( ) ; } ColPartition_CLIST non_candidate_neighbours ; non_candidate_neighbours . set_subtract ( SortByBoxLeft < ColPartition > , true , & neighbours , candidates ) ; int worst_nc_increase = 0 ; int best_increase = INT32_MAX ; int best_area = 0 ; for ( it . mark_cycle_pt ( ) ; ! it . cycled_list ( ) ; it . forward ( ) ) { ColPartition * candidate = it . data ( ) ; if ( confirm_cb != nullptr && ! confirm_cb ( part , candidate ) ) { if ( debug ) { tprintf ( " " ) ; candidate -> bounding_box ( ) . print ( ) ; } continue ; } int increase = IncreaseInOverlap ( part , candidate , ok_overlap , & neighbours ) ; const TBOX & cand_box = candidate -> bounding_box ( ) ; if ( best_candidate == nullptr || increase < best_increase ) { best_candidate = candidate ; best_increase = increase ; best_area = cand_box . bounding_union ( part_box ) . area ( ) - cand_box . area ( ) ; if ( debug ) { tprintf ( " " , increase , best_area ) ; full_box . print ( ) ; candidate -> Print ( ) ; } } else if ( increase == best_increase ) { int area = cand_box . bounding_union ( part_box ) . area ( ) - cand_box . area ( ) ; if ( area < best_area ) { best_area = area ; best_candidate = candidate ; } } increase = IncreaseInOverlap ( part , candidate , ok_overlap , & non_candidate_neighbours ) ; if ( increase > worst_nc_increase ) { worst_nc_increase = increase ; } } if ( best_increase > 0 ) { if ( worst_nc_increase < best_increase && TestCompatibleCandidates ( * part , debug , candidates ) ) { best_increase = worst_nc_increase ; } } if ( overlap_increase != nullptr ) { * overlap_increase = best_increase ; } return best_candidate ; }
Finds and returns the best candidate ColPartition to merge with part,
selected from the candidates list, based on the minimum increase in
pairwise overlap among all the partitions overlapped by the combined box.
Finds and returns the best candidate ColPartition to merge with part selected from the candidates list based on the minimum increase in pairwise overlap among all the partitions overlapped by the combined box .
// The best neighbour to merge with is the one that causes least // total pairwise overlap among all the neighbours. // If more than one offers the same total overlap, choose the one // with the least total area. // Find the total combined box of all candidates and the original. // Keep valid neighbours in a list. // Now run a rect search of the merged box for overlapping neighbours, as // we need anything that might be overlapped by the merged box. // If the best increase in overlap is positive, then we also check the // worst non-candidate overlap. This catches the case of multiple good // candidates that overlap each other when merged. If the worst // non-candidate overlap is better than the best overlap, then return // the worst non-candidate overlap instead. // If the worst non-candidate increase is less than the best increase // including the candidates, then all the candidates can merge together // and the increase in outside overlap would be less, so use that result, // but only if each candidate is either a good diacritic merge with part, // or an ok merge candidate with all the others. // See TestCompatibleCandidates for more explanation and a picture.