/*=========================================================================

 Program:   Visualization Toolkit
 Module:    vtkConvexHull2D.cxx

 Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
 All rights reserved.
 See Copyright.txt or http://www.kitware.com/Copyright.htm for details.

 This software is distributed WITHOUT ANY WARRANTY; without even
 the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
 PURPOSE.  See the above copyright notice for more information.

 =========================================================================*/

#include "vtkConvexHull2D.h"

#include "vtkCellArray.h"
#include "vtkCellData.h"
#include "vtkCoordinate.h"
#include "vtkInformation.h"
#include "vtkInformationVector.h"
#include "vtkObjectFactory.h"
#include "vtkPointsProjectedHull.h"
#include "vtkPolyLine.h"
#include "vtkPolygon.h"
#include "vtkRenderer.h"
#include "vtkSmartPointer.h"
#include "vtkTransform.h"
#include "vtkTransformPolyDataFilter.h"

#include <algorithm>

vtkStandardNewMacro(vtkConvexHull2D);

//------------------------------------------------------------------------------
vtkConvexHull2D::vtkConvexHull2D()
{
  this->SetNumberOfOutputPorts(2);
  this->ScaleFactor = 1.0;
  this->Outline = false;
  this->MinHullSizeInWorld = 1.0;
  this->MinHullSizeInDisplay = 10;
  this->HullShape = vtkConvexHull2D::ConvexHull;
  this->Renderer = nullptr;

  this->Coordinate = vtkSmartPointer<vtkCoordinate>::New();
  this->Transform = vtkSmartPointer<vtkTransform>::New();
  this->OutputTransform = vtkSmartPointer<vtkTransform>::New();
  this->OutputTransformFilter = vtkSmartPointer<vtkTransformPolyDataFilter>::New();
  this->OutputTransformFilter->SetTransform(this->OutputTransform);
  this->OutlineSource = vtkSmartPointer<vtkPolyLine>::New();
  this->HullSource = vtkSmartPointer<vtkPolygon>::New();
}

//------------------------------------------------------------------------------
vtkConvexHull2D::~vtkConvexHull2D()
{
  this->SetRenderer(nullptr);
}

//------------------------------------------------------------------------------
void vtkConvexHull2D::CalculateBoundingRectangle(
  vtkPoints* inPoints, vtkPoints* outPoints, double minimumHullSize)
{
  minimumHullSize /= 2.0;
  inPoints->ComputeBounds();
  double bounds[6];
  inPoints->GetBounds(bounds);

  double xDeficit = minimumHullSize - (bounds[1] - bounds[0]);
  if (xDeficit > 0.0)
  {
    bounds[0] -= xDeficit;
    bounds[1] += xDeficit;
  }

  double yDeficit = minimumHullSize - (bounds[3] - bounds[2]);
  if (yDeficit > 0.0)
  {
    bounds[2] -= yDeficit;
    bounds[3] += yDeficit;
  }

  outPoints->SetNumberOfPoints(4);
  outPoints->SetPoint(0, bounds[0], bounds[2], 0.0);
  outPoints->SetPoint(1, bounds[1], bounds[2], 0.0);
  outPoints->SetPoint(2, bounds[1], bounds[3], 0.0);
  outPoints->SetPoint(3, bounds[0], bounds[3], 0.0);
}

//------------------------------------------------------------------------------
void vtkConvexHull2D::CalculateConvexHull(
  vtkPoints* inPoints, vtkPoints* outPoints, double minimumHullSize)
{
  if (inPoints->GetNumberOfPoints() == 1 || inPoints->GetNumberOfPoints() == 2)
  {
    vtkConvexHull2D::CalculateBoundingRectangle(inPoints, outPoints, minimumHullSize);
  }
  else if (inPoints->GetNumberOfPoints() >= 3)
  {
    vtkPointsProjectedHull* ppHull = vtkPointsProjectedHull::New();
    ppHull->ShallowCopy(inPoints);
    int numHullPoints = ppHull->GetSizeCCWHullZ();
    double* pts = new double[2 * numHullPoints];
    ppHull->GetCCWHullZ(pts, numHullPoints);

    vtkPoints* hullPoints = vtkPoints::New();
    hullPoints->SetNumberOfPoints(numHullPoints);
    for (vtkIdType i = 0; i < numHullPoints; ++i)
    {
      hullPoints->SetPoint(i, pts[2 * i], pts[2 * i + 1], 0.0);
    }
    ppHull->Delete();
    delete[] pts;

    if (numHullPoints < 3)
    {
      vtkConvexHull2D::CalculateBoundingRectangle(hullPoints, outPoints, minimumHullSize);
      return;
    }

    double bounds[6];
    hullPoints->GetBounds(bounds);
    double xScale = std::max(1.0, minimumHullSize / (bounds[1] - bounds[0]));
    double yScale = std::max(1.0, minimumHullSize / (bounds[3] - bounds[2]));
    if (xScale > 1.0 || yScale > 1.0)
    {
      double scale[3] = { xScale, yScale, 1.0 };
      double translate[3] = { (bounds[0] + (bounds[1] - bounds[0]) / 2.0),
        (bounds[2] + (bounds[3] - bounds[2]) / 2.0), 0.0 };

      vtkTransform* transform = vtkTransform::New();
      transform->Translate(translate);
      transform->Scale(scale);
      transform->Translate(-translate[0], -translate[1], -translate[2]);
      transform->TransformPoints(hullPoints, outPoints);
      transform->Delete();
    }
    else
    {
      outPoints->ShallowCopy(hullPoints);
    }
    hullPoints->Delete();
  }
}

//------------------------------------------------------------------------------
void vtkConvexHull2D::ResizeHullToMinimumInDisplay(vtkPolyData* hullPolyData)
{
  if (this->Renderer && this->Renderer->IsActiveCameraCreated())
  {
    double bounds[6];
    hullPolyData->ComputeBounds();
    hullPolyData->GetBounds(bounds);

    double leftBottom[2];
    double rightTop[2];
    double* coord;
    this->Coordinate->SetCoordinateSystemToWorld();
    this->Coordinate->SetValue(bounds[0], bounds[2], 0.0);
    coord = this->Coordinate->GetComputedDoubleDisplayValue(this->Renderer);
    leftBottom[0] = coord[0];
    leftBottom[1] = coord[1];
    this->Coordinate->SetValue(bounds[1], bounds[3], 0.0);
    coord = this->Coordinate->GetComputedDoubleDisplayValue(this->Renderer);
    rightTop[0] = coord[0];
    rightTop[1] = coord[1];
    double currentDisplaySize[2] = { rightTop[0] - leftBottom[0], rightTop[1] - leftBottom[1] };

    if (currentDisplaySize[0] == 0.0 || currentDisplaySize[1] == 0.0)
    {
      vtkWarningMacro(<< "Can not scale a hull with zero display area.");
      return;
    }

    if (currentDisplaySize[0] < this->MinHullSizeInDisplay ||
      currentDisplaySize[1] < this->MinHullSizeInDisplay)
    {
      double scaleFx = std::max(1.0, this->MinHullSizeInDisplay / currentDisplaySize[0]);
      double scaleFy = std::max(1.0, this->MinHullSizeInDisplay / currentDisplaySize[1]);
      double scale[3] = { scaleFx, scaleFy, 1.0 };
      double translate[3] = { (bounds[0] + (bounds[1] - bounds[0]) / 2.0),
        (bounds[2] + (bounds[3] - bounds[2]) / 2.0), 0.0 };

      this->Transform->Identity();
      this->Transform->Translate(translate);
      this->Transform->Scale(scale);
      this->Transform->Translate(-translate[0], -translate[1], -translate[2]);

      vtkPoints* outPoints = vtkPoints::New();
      this->Transform->TransformPoints(hullPolyData->GetPoints(), outPoints);
      hullPolyData->SetPoints(outPoints);
      outPoints->Delete();
    }
  }
}

//------------------------------------------------------------------------------
void vtkConvexHull2D::SetRenderer(vtkRenderer* renderer)
{
  this->Renderer = renderer;
  this->Modified();
}

//------------------------------------------------------------------------------
vtkRenderer* vtkConvexHull2D::GetRenderer()
{
  return this->Renderer;
}

//------------------------------------------------------------------------------
vtkMTimeType vtkConvexHull2D::GetMTime()
{
  if (this->Renderer)
  {
    return this->Renderer->GetMTime();
  }
  else
  {
    return this->MTime;
  }
}

//------------------------------------------------------------------------------
int vtkConvexHull2D::RequestData(vtkInformation* vtkNotUsed(request),
  vtkInformationVector** inputVector, vtkInformationVector* outputVector)
{
  // Get the input and output.
  vtkInformation* inInfo = inputVector[0]->GetInformationObject(0);

  vtkPolyData* input = vtkPolyData::SafeDownCast(inInfo->Get(vtkDataObject::DATA_OBJECT()));
  vtkPoints* inputPoints = input->GetPoints();
  if (!inputPoints)
  {
    vtkErrorMacro("Input points needed");
    return 0;
  }

  vtkInformation* outInfo0 = outputVector->GetInformationObject(0);
  vtkInformation* outInfo1 = outputVector->GetInformationObject(1);

  vtkPolyData* outputHull = vtkPolyData::SafeDownCast(outInfo0->Get(vtkDataObject::DATA_OBJECT()));
  vtkPolyData* outputOutline =
    vtkPolyData::SafeDownCast(outInfo1->Get(vtkDataObject::DATA_OBJECT()));

  // Create filled polygon
  vtkPoints* hullPoints = vtkPoints::New();
  switch (this->HullShape)
  {
    case vtkConvexHull2D::BoundingRectangle:
      this->CalculateBoundingRectangle(inputPoints, hullPoints, this->MinHullSizeInWorld);
      break;
    default: // vtkConvexHull2D::ConvexHull
      this->CalculateConvexHull(inputPoints, hullPoints, this->MinHullSizeInWorld);
      break;
  }

  vtkIdType numHullPoints = hullPoints->GetNumberOfPoints();
  vtkIdType* hullPts = new vtkIdType[numHullPoints];
  for (int i = 0; i < numHullPoints; ++i)
  {
    hullPts[i] = i;
  }
  this->HullSource->Initialize(numHullPoints, hullPts, hullPoints);
  delete[] hullPts;

  vtkCellArray* hullCells = vtkCellArray::New();
  hullCells->InsertNextCell(this->HullSource);
  vtkSmartPointer<vtkPolyData> hullPolyData = vtkSmartPointer<vtkPolyData>::New();
  hullPolyData->SetPoints(hullPoints);
  hullPolyData->SetPolys(hullCells);
  hullPoints->Delete();
  hullCells->Delete();

  // Adjust for the scale-factor
  double* centre = hullPolyData->GetCenter();
  this->OutputTransform->Identity();
  this->OutputTransform->Translate(centre);
  this->OutputTransform->Scale(this->ScaleFactor, this->ScaleFactor, this->ScaleFactor);
  this->OutputTransform->Translate(-centre[0], -centre[1], -centre[2]);
  this->OutputTransformFilter->SetInputData(hullPolyData);
  this->OutputTransformFilter->Update();
  hullPolyData = this->OutputTransformFilter->GetOutput();

  // Account for current camera zoom level
  this->ResizeHullToMinimumInDisplay(hullPolyData);

  // Copy hull to output
  outputHull->ShallowCopy(hullPolyData);

  if (this->Outline)
  {
    vtkIdType numOutlinePoints = outputHull->GetNumberOfPoints();
    vtkIdType* outlinePts = new vtkIdType[numOutlinePoints + 1];
    for (int i = 0; i < numOutlinePoints; ++i)
    {
      outlinePts[i] = i;
    }
    outlinePts[numOutlinePoints] = outlinePts[0];

    this->OutlineSource->Initialize(numOutlinePoints + 1, outlinePts, outputHull->GetPoints());

    vtkSmartPointer<vtkPolyData> outlinePolyData = vtkSmartPointer<vtkPolyData>::New();
    vtkCellArray* outlineCells = vtkCellArray::New();
    outlineCells->InsertNextCell(this->OutlineSource);
    outlinePolyData->SetPoints(outputHull->GetPoints());
    outlinePolyData->SetLines(outlineCells);
    outlineCells->Delete();
    delete[] outlinePts;

    // Copy outline to output
    outputOutline->ShallowCopy(outlinePolyData);
  }
  return 1;
}

//------------------------------------------------------------------------------
void vtkConvexHull2D::PrintSelf(ostream& os, vtkIndent indent)
{
  this->Superclass::PrintSelf(os, indent);
  os << indent << "ScaleFactor: " << this->ScaleFactor << "\n";
  os << indent << "Outline: " << (this->Outline ? "On" : "Off") << "\n";
  os << indent << "HullShape: ";
  switch (this->HullShape)
  {
    case ConvexHull:
      os << "ConvexHull\n";
      break;
    case BoundingRectangle:
      os << "BoundingRectangle\n";
      break;
    default:
      os << "Unknown\n";
      break;
  }
  os << indent << "MinHullSizeInDisplay: " << this->MinHullSizeInDisplay << "\n";
  os << indent << "MinHullSizeInWorld: " << this->MinHullSizeInWorld << "\n";
  os << indent << "Renderer: ";
  if (this->Renderer)
  {
    os << endl;
    this->Renderer->PrintSelf(os, indent.GetNextIndent());
  }
  else
  {
    os << "(none)" << endl;
  }
}