/******************************************************************************

 ** Filename:    mfoutline.c

 ** Purpose:     Interface to outline struct used for extracting features

 ** Author:      Dan Johnson

 **

 ** (c) Copyright Hewlett-Packard Company, 1988.

 ** Licensed under the Apache License, Version 2.0 (the "License");

 ** you may not use this file except in compliance with the License.

 ** You may obtain a copy of the License at

 ** http://www.apache.org/licenses/LICENSE-2.0

 ** Unless required by applicable law or agreed to in writing, software

 ** distributed under the License is distributed on an "AS IS" BASIS,

 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

 ** See the License for the specific language governing permissions and

 ** limitations under the License.

 ******************************************************************************/

#include "mfoutline.h"

#include "blobs.h"

#include "classify.h"

#include "clusttool.h" //If remove you get caught in a loop somewhere

#include "mfx.h"

#include "params.h"

#include <cmath>

#include <cstdio>

namespace tesseract {

/*---------------------------------------------------------------------------*/

/** Convert a blob into a list of MFOUTLINEs (float-based microfeature format).

 */

LIST ConvertBlob(TBLOB *blob) {

  LIST outlines = NIL_LIST;

  return (blob == nullptr) ? NIL_LIST : ConvertOutlines(blob->outlines, outlines, outer);

}

/*---------------------------------------------------------------------------*/

/** Convert a TESSLINE into the float-based MFOUTLINE micro-feature format. */

MFOUTLINE ConvertOutline(TESSLINE *outline) {

  auto MFOutline = NIL_LIST;

  if (outline == nullptr || outline->loop == nullptr) {

    return MFOutline;

  }

  auto StartPoint = outline->loop;

  auto EdgePoint = StartPoint;

  do {

    auto NextPoint = EdgePoint->next;

    /* filter out duplicate points */

    if (EdgePoint->pos.x != NextPoint->pos.x || EdgePoint->pos.y != NextPoint->pos.y) {

      auto NewPoint = new MFEDGEPT;

      NewPoint->ClearMark();

      NewPoint->Hidden = EdgePoint->IsHidden();

      NewPoint->Point.x = EdgePoint->pos.x;

      NewPoint->Point.y = EdgePoint->pos.y;

      MFOutline = push(MFOutline, NewPoint);

    }

    EdgePoint = NextPoint;

  } while (EdgePoint != StartPoint);

  if (MFOutline != nullptr) {

    MakeOutlineCircular(MFOutline);

  }

  return MFOutline;

}

/*---------------------------------------------------------------------------*/

/**

 * Convert a tree of outlines to a list of MFOUTLINEs (lists of MFEDGEPTs).

 *

 * @param outline      first outline to be converted

 * @param mf_outlines  list to add converted outlines to

 * @param outline_type  are the outlines outer or holes?

 */

LIST ConvertOutlines(TESSLINE *outline, LIST mf_outlines, OUTLINETYPE outline_type) {

  MFOUTLINE mf_outline;

  while (outline != nullptr) {

    mf_outline = ConvertOutline(outline);

    if (mf_outline != nullptr) {

      mf_outlines = push(mf_outlines, mf_outline);

    }

    outline = outline->next;

  }

  return mf_outlines;

}

/*---------------------------------------------------------------------------*/

/**

 * This routine searches through the specified outline, computes

 * a slope for each vector in the outline, and marks each

 * vector as having one of the following directions:

 *   N, S, E, W, NE, NW, SE, SW

 * This information is then stored in the outline and the

 * outline is returned.

 * @param Outline   micro-feature outline to analyze

 * @param MinSlope  controls "snapping" of segments to horizontal

 * @param MaxSlope  controls "snapping" of segments to vertical

 */

void FindDirectionChanges(MFOUTLINE Outline, float MinSlope, float MaxSlope) {

  MFEDGEPT *Current;

  MFEDGEPT *Last;

  MFOUTLINE EdgePoint;

  if (DegenerateOutline(Outline)) {

    return;

  }

  Last = PointAt(Outline);

  Outline = NextPointAfter(Outline);

  EdgePoint = Outline;

  do {

    Current = PointAt(EdgePoint);

    ComputeDirection(Last, Current, MinSlope, MaxSlope);

    Last = Current;

    EdgePoint = NextPointAfter(EdgePoint);

  } while (EdgePoint != Outline);

} /* FindDirectionChanges */

/*---------------------------------------------------------------------------*/

/**

 * This routine deallocates all of the memory consumed by

 * a micro-feature outline.

 * @param arg   micro-feature outline to be freed

 */

void FreeMFOutline(void *arg) { // MFOUTLINE Outline)

  auto Outline = static_cast<MFOUTLINE>(arg);

  /* break the circular outline so we can use std. techniques to deallocate */

  MFOUTLINE Start = Outline->list_rest();

  set_rest(Outline, NIL_LIST);

  while (Start != nullptr) {

    delete reinterpret_cast<MFEDGEPT *>(Start->first_node());

    Start = pop(Start);

  }

} /* FreeMFOutline */

/*---------------------------------------------------------------------------*/

/**

 * Release all memory consumed by the specified list

 * of outlines.

 * @param Outlines  list of mf-outlines to be freed

 */

void FreeOutlines(LIST Outlines) {

  destroy_nodes(Outlines, FreeMFOutline);

} /* FreeOutlines */

/*---------------------------------------------------------------------------*/

/**

 * This routine searches through the specified outline and finds

 * the points at which the outline changes direction.  These

 * points are then marked as "extremities".  This routine is

 * used as an alternative to FindExtremities().  It forces the

 * endpoints of the microfeatures to be at the direction

 * changes rather than at the midpoint between direction

 * changes.

 * @param Outline   micro-feature outline to analyze

 */

void MarkDirectionChanges(MFOUTLINE Outline) {

  MFOUTLINE Current;

  MFOUTLINE Last;

  MFOUTLINE First;

  if (DegenerateOutline(Outline)) {

    return;

  }

  First = NextDirectionChange(Outline);

  Last = First;

  do {

    Current = NextDirectionChange(Last);

    PointAt(Current)->MarkPoint();

    Last = Current;

  } while (Last != First);

} /* MarkDirectionChanges */

/*---------------------------------------------------------------------------*/

/**

 * This routine returns the next point in the micro-feature

 * outline that is an extremity.  The search starts after

 * EdgePoint.  The routine assumes that the outline being

 * searched is not a degenerate outline (i.e. it must have

 * 2 or more edge points).

 * @param EdgePoint start search from this point

 * @return Next extremity in the outline after EdgePoint.

 * @note Globals: none

 */

MFOUTLINE NextExtremity(MFOUTLINE EdgePoint) {

  EdgePoint = NextPointAfter(EdgePoint);

  while (!PointAt(EdgePoint)->ExtremityMark) {

    EdgePoint = NextPointAfter(EdgePoint);

  }

  return (EdgePoint);

} /* NextExtremity */

/*---------------------------------------------------------------------------*/

/**

 * This routine normalizes the coordinates of the specified

 * outline so that the outline is deskewed down to the

 * baseline, translated so that x=0 is at XOrigin, and scaled

 * so that the height of a character cell from descender to

 * ascender is 1.  Of this height, 0.25 is for the descender,

 * 0.25 for the ascender, and 0.5 for the x-height.  The

 * y coordinate of the baseline is 0.

 * @param Outline   outline to be normalized

 * @param XOrigin   x-origin of text

 */

void NormalizeOutline(MFOUTLINE Outline, float XOrigin) {

  if (Outline == NIL_LIST) {

    return;

  }

  MFOUTLINE EdgePoint = Outline;

  do {

    MFEDGEPT *Current = PointAt(EdgePoint);

    Current->Point.y = MF_SCALE_FACTOR * (Current->Point.y - kBlnBaselineOffset);

    Current->Point.x = MF_SCALE_FACTOR * (Current->Point.x - XOrigin);

    EdgePoint = NextPointAfter(EdgePoint);

  } while (EdgePoint != Outline);

} /* NormalizeOutline */

/*---------------------------------------------------------------------------*/

/**

 * This routine normalizes every outline in Outlines

 * according to the currently selected normalization method.

 * It also returns the scale factors that it used to do this

 * scaling.  The scale factors returned represent the x and

 * y sizes in the normalized coordinate system that correspond

 * to 1 pixel in the original coordinate system.

 * Outlines are changed and XScale and YScale are updated.

 *

 * Globals:

 * - classify_norm_method  method being used for normalization

 * - classify_char_norm_range map radius of gyration to this value

 * @param Outlines  list of outlines to be normalized

 * @param XScale    x-direction scale factor used by routine

 * @param YScale    y-direction scale factor used by routine

 */

void Classify::NormalizeOutlines(LIST Outlines, float *XScale, float *YScale) {

  MFOUTLINE Outline;

  switch (classify_norm_method) {

    case character:

      ASSERT_HOST(!"How did NormalizeOutlines get called in character mode?");

      break;

    case baseline:

      iterate(Outlines) {

        Outline = static_cast<MFOUTLINE>(Outlines->first_node());

        NormalizeOutline(Outline, 0.0);

      }

      *XScale = *YScale = MF_SCALE_FACTOR;

      break;

  }

} /* NormalizeOutlines */

/*----------------------------------------------------------------------------

              Private Code

----------------------------------------------------------------------------*/

/**

 * Change the direction of every vector in the specified

 * outline segment to Direction.  The segment to be changed

 * starts at Start and ends at End.  Note that the previous

 * direction of End must also be changed to reflect the

 * change in direction of the point before it.

 * @param Start defines start of segment of outline to be modified

 * @param End defines end of segment of outline to be modified

 * @param Direction new direction to assign to segment

 */

void ChangeDirection(MFOUTLINE Start, MFOUTLINE End, DIRECTION Direction) {

  MFOUTLINE Current;

  for (Current = Start; Current != End; Current = NextPointAfter(Current)) {

    PointAt(Current)->Direction = Direction;

  }

  PointAt(End)->PreviousDirection = Direction;

} /* ChangeDirection */

/**

 * This routine normalizes each point in Outline by

 * translating it to the specified center and scaling it

 * anisotropically according to the given scale factors.

 * @param Outline     outline to be character normalized

 * @param cn_denorm

 */

void CharNormalizeOutline(MFOUTLINE Outline, const DENORM &cn_denorm) {

  MFOUTLINE First, Current;

  MFEDGEPT *CurrentPoint;

  if (Outline == NIL_LIST) {

    return;

  }

  First = Outline;

  Current = First;

  do {

    CurrentPoint = PointAt(Current);

    FCOORD pos(CurrentPoint->Point.x, CurrentPoint->Point.y);

    cn_denorm.LocalNormTransform(pos, &pos);

    CurrentPoint->Point.x = (pos.x() - UINT8_MAX / 2) * MF_SCALE_FACTOR;

    CurrentPoint->Point.y = (pos.y() - UINT8_MAX / 2) * MF_SCALE_FACTOR;

    Current = NextPointAfter(Current);

  } while (Current != First);

} /* CharNormalizeOutline */

/**

 * This routine computes the slope from Start to Finish and

 * and then computes the approximate direction of the line

 * segment from Start to Finish.  The direction is quantized

 * into 8 buckets:

 *  N, S, E, W, NE, NW, SE, SW

 * Both the slope and the direction are then stored into

 * the appropriate fields of the Start edge point.  The

 * direction is also stored into the PreviousDirection field

 * of the Finish edge point.

 * @param Start   starting point to compute direction from

 * @param Finish    finishing point to compute direction to

 * @param MinSlope  slope below which lines are horizontal

 * @param MaxSlope  slope above which lines are vertical

 */

void ComputeDirection(MFEDGEPT *Start, MFEDGEPT *Finish, float MinSlope, float MaxSlope) {

  FVECTOR Delta;

  Delta.x = Finish->Point.x - Start->Point.x;

  Delta.y = Finish->Point.y - Start->Point.y;

  if (Delta.x == 0) {

    if (Delta.y < 0) {

      Start->Slope = -FLT_MAX;

      Start->Direction = south;

    } else {

      Start->Slope = FLT_MAX;

      Start->Direction = north;

    }

  } else {

    Start->Slope = Delta.y / Delta.x;

    if (Delta.x > 0) {

      if (Delta.y > 0) {

        if (Start->Slope > MinSlope) {

          if (Start->Slope < MaxSlope) {

            Start->Direction = northeast;

          } else {

            Start->Direction = north;

          }

        } else {

          Start->Direction = east;

        }

      } else if (Start->Slope < -MinSlope) {

        if (Start->Slope > -MaxSlope) {

          Start->Direction = southeast;

        } else {

          Start->Direction = south;

        }

      } else {

        Start->Direction = east;

      }

    } else if (Delta.y > 0) {

      if (Start->Slope < -MinSlope) {

        if (Start->Slope > -MaxSlope) {

          Start->Direction = northwest;

        } else {

          Start->Direction = north;

        }

      } else {

        Start->Direction = west;

      }

    } else if (Start->Slope > MinSlope) {

      if (Start->Slope < MaxSlope) {

        Start->Direction = southwest;

      } else {

        Start->Direction = south;

      }

    } else {

      Start->Direction = west;

    }

  }

  Finish->PreviousDirection = Start->Direction;

}

/**

 * This routine returns the next point in the micro-feature

 * outline that has a direction different than EdgePoint.  The

 * routine assumes that the outline being searched is not a

 * degenerate outline (i.e. it must have 2 or more edge points).

 * @param EdgePoint start search from this point

 * @return Point of next direction change in micro-feature outline.

 * @note Globals: none

 */

MFOUTLINE NextDirectionChange(MFOUTLINE EdgePoint) {

  DIRECTION InitialDirection;

  InitialDirection = PointAt(EdgePoint)->Direction;

  MFOUTLINE next_pt = nullptr;

  do {

    EdgePoint = NextPointAfter(EdgePoint);

    next_pt = NextPointAfter(EdgePoint);

  } while (PointAt(EdgePoint)->Direction == InitialDirection && !PointAt(EdgePoint)->Hidden &&

           next_pt != nullptr && !PointAt(next_pt)->Hidden);

  return (EdgePoint);

}

} // namespace tesseract