// --------------------------------------------------------------------
// Ipelet to clip to a polygon
// --------------------------------------------------------------------
/*

    This file is part of the extensible drawing editor Ipe.
    Copyright (C) 1993-2004  Otfried Cheong

    Ipe is free software; you can redistribute it and/or modify it
    under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    As a special exception, you have permission to link Ipe with the
    CGAL library and distribute executables, as long as you follow the
    requirements of the Gnu General Public License in regard to all of
    the software in the executable aside from CGAL.

    Ipe is distributed in the hope that it will be useful, but WITHOUT
    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
    License for more details.

    You should have received a copy of the GNU General Public License
    along with Ipe; if not, you can find it at
    "http://www.gnu.org/copyleft/gpl.html", or write to the Free
    Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

*/

#include "ipelib.h"
#include "ipepath.h"

// --------------------------------------------------------------------

class ClipIpelet : public Ipelet {
public:
  virtual int IpelibVersion() const { return IPELIB_VERSION; }
  virtual const char *Label() const { return "Clip to convex polygon"; }
  virtual void Run(int function, IpePage *page, IpeletHelper *helper);
};

// --------------------------------------------------------------------

class Polygon : public IpeVisitor {
public:
  bool Setup(const IpePath *obj);
  bool Inside(const IpeVector &pt) const;
  IpeGroup *Group() const { return new IpeGroup(iGroup); }

  // virtual void VisitGroup(const IpeGroup *obj);
  virtual void VisitPath(const IpePath *obj);
  virtual void VisitMark(const IpeMark *obj);

  void CutSegment(const IpePath *obj, const IpeVector &v0,
		  const IpeVector &v1);
  IpeVector ShootRay(const IpeVector &v0, const IpeVector &v1);
private:
  std::vector<IpeVector> iV;
  int iSign;
  IpeGroup iGroup;
};

bool Polygon::Setup(const IpePath *obj)
{
  if (!obj)
    return false;

  const IpeSegmentSubPath *sp = obj->SubPath(0)->AsSegs();
  if (!sp || !sp->Closed())
    return false;

  IpeMatrix m = obj->Matrix();
  for (int i = 0; i < sp->NumSegments(); ++i) {
    IpePathSegment s = sp->Segment(i);
    if (s.Type() != IpePathSegment::ESegment)
      return false;
    iV.push_back(m * s.CP(0));
  }
  iV.push_back(sp->Segment(-1).Last());
  iV.push_back(sp->Segment(0).CP(0));

  iSign = 1;
  if (IpeLine(iV[0], (iV[1] - iV[0]).Normalized()).Side(iV[2]) < 0)
    iSign = -1;

  for (uint i = 0; i < iV.size(); ++i)
    ipeDebug("(%g,%g)", iV[i].iX, iV[i].iY);
  ipeDebug("sign = %d", iSign);
  return true;
}

bool Polygon::Inside(const IpeVector &pt) const
{
  for (uint i = 0; i < iV.size() - 1; ++i) {
    IpeLine li(iV[i], (iV[i+1] - iV[i]).Normalized());
    if (iSign * li.Side(pt) < 0)
      return false;
  }
  return true;
}

inline double cross(const IpeVector &v1, const IpeVector &v2)
{
  return v1.iX * v2.iY - v1.iY * v2.iX;
}

static bool Intersect(double &lambda, const IpeLine &l,
		      const IpeLine &m)
{
  double denom = cross(m.Dir(), l.Dir());
  if (denom == 0.0)
    return false;
  lambda = cross(l.iP - m.iP, m.Dir()) / denom;
  return true;
}

IpeVector Polygon::ShootRay(const IpeVector &v0, const IpeVector &v1)
{
  IpeVector dir = (v1 - v0).Normalized();
  IpeLine l(v0, dir);
  double lambda;
  double minLambda = (v1 - v0).Len();
  for (uint i = 0; i < iV.size() - 1; ++i) {
    IpeLine m(iV[i], (iV[i+1] - iV[i]).Normalized());
    if (Intersect(lambda, l, m) && lambda > 0 && lambda < minLambda)
      minLambda = lambda;
  }
  return v0 + minLambda * dir;
}

void Polygon::CutSegment(const IpePath *obj, const IpeVector &v0,
			 const IpeVector &v1)
{
  IpeAllAttributes att;
  att.iStroke = obj->Stroke();
  att.iDashStyle = obj->DashStyle();
  att.iLineWidth = obj->LineWidth();
  // att.iStrokeStyle = obj->StrokeStyle();
  IpeSegment seg(v0, v1);
  iGroup.push_back(new IpePath(att, seg));
}

void Polygon::VisitPath(const IpePath *obj)
{
  if (obj->NumSubPaths() == 1) {
    const IpeSegmentSubPath *sp = obj->SubPath(0)->AsSegs();
    if (sp && sp->NumSegments() == 1) {
      IpePathSegment seg = sp->Segment(0);
      if (seg.Type() == IpePathSegment::ESegment) {
	IpeMatrix m = obj->Matrix();
	IpeVector v1 = m * seg.CP(0);
	IpeVector v2 = m * seg.Last();
	bool b1 = Inside(v1);
	bool b2 = Inside(v2);
	if (b1 && b2) {
	  iGroup.push_back(obj->Clone());
	} else if (b1) {
	  CutSegment(obj, v1, ShootRay(v1, v2));
	} else if (b2) {
	  CutSegment(obj, v2, ShootRay(v2, v1));
	}
      }
    }
  }
}

void Polygon::VisitMark(const IpeMark *obj)
{
  if (Inside(obj->Matrix() * obj->Position())) {
    iGroup.push_back(obj->Clone());
    ipeDebug("Adding mark");
  }
}

// clip all objects to the primary selection, which must be a convex polygon
void ClipIpelet::Run(int, IpePage *page, IpeletHelper *helper)
{
  Polygon pgn;
  IpePage::iterator prim = page->PrimarySelection();
  if (prim == page->end() || !pgn.Setup(prim->Object()->AsPath())) {
    helper->Message("Primary selection must be a polygon for clipping");
    return;
  }


  // now walk through selection, and do the clipping

  for (IpePage::const_iterator it = page->begin();
       it != page->end(); ++it) {
    // only treat secondary selection
    if (it->Select() == IpePgObject::ESecondary)
      pgn(*it);
  }

  prim->SetSelect(IpePgObject::ESecondary);
  page->push_back(IpePgObject(IpePgObject::EPrimary,
			      helper->CurrentLayer(),
			      pgn.Group()));
}

// --------------------------------------------------------------------

IPELET_DECLARE Ipelet *NewIpelet()
{
  return new ClipIpelet;
}

// --------------------------------------------------------------------