Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#include "tcenterlinevectP.h"
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//==========================================================================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//************************
Toshihiro Shimizu 890ddd
//*    Polygonization    *
Toshihiro Shimizu 890ddd
//************************
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//===============================
Toshihiro Shimizu 890ddd
//    Raw Borders Extraction
Toshihiro Shimizu 890ddd
//===============================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//Raw contour class definition
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
class RawBorderPoint
Toshihiro Shimizu 890ddd
{
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	TPoint m_position;
Toshihiro Shimizu 890ddd
	int m_ambiguousTurn; //used to remember cases of multiple turning directions
Toshihiro Shimizu 890ddd
						 //in a RawBorder extraction.
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
public:
Toshihiro Shimizu 890ddd
	RawBorderPoint() : m_ambiguousTurn(0) {}
Toshihiro Shimizu 890ddd
	RawBorderPoint(int i, int j) : m_position(i, j), m_ambiguousTurn(0) {}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	inline TPoint pos() const { return m_position; }
Toshihiro Shimizu 890ddd
	inline int x() const { return m_position.x; }
Toshihiro Shimizu 890ddd
	inline int y() const { return m_position.y; }
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	enum { left = 1,
Toshihiro Shimizu 890ddd
		   right = 2 }; //Direction taken at ambiguous turning point
Toshihiro Shimizu 890ddd
	inline int getAmbiguous() const { return m_ambiguousTurn; }
Toshihiro Shimizu 890ddd
	inline void setAmbiguous(int direction) { m_ambiguousTurn = direction; }
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
class RawBorder : public std::vector<rawborderpoint></rawborderpoint>
Toshihiro Shimizu 890ddd
{
Toshihiro Shimizu 890ddd
	int m_xExternal; //x coordinate of a specific vertex in the outer
Toshihiro Shimizu 890ddd
					 //RawBorder which contains this inner one.
Toshihiro Shimizu 890ddd
	TPointD *m_coordinateSums;
Toshihiro Shimizu 890ddd
	TPointD *m_coordinateSquareSums;
Toshihiro Shimizu 890ddd
	double *m_coordinateMixedSums;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
public:
Toshihiro Shimizu 890ddd
	RawBorder() {}
Toshihiro Shimizu 890ddd
	~RawBorder() {}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	void setXExternalPixel(int a) { m_xExternal = a; }
Toshihiro Shimizu 890ddd
	int xExternalPixel() { return m_xExternal; }
Toshihiro Shimizu 890ddd
	TPointD *&sums() { return m_coordinateSums; }
Toshihiro Shimizu 890ddd
	TPointD *&sums2() { return m_coordinateSquareSums; }
Toshihiro Shimizu 890ddd
	double *&sumsMix() { return m_coordinateMixedSums; }
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//Of course we don't want RawBorders to be entirely copied whenever STL
Toshihiro Shimizu 890ddd
//requires to resize a BorderFamily...
Toshihiro Shimizu 890ddd
typedef std::vector<rawborder *=""> BorderFamily;</rawborder>
Toshihiro Shimizu 890ddd
typedef std::vector<borderfamily> BorderList;</borderfamily>
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//==========================================================================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//============================
Toshihiro Shimizu 890ddd
//    Polygonizer Locals
Toshihiro Shimizu 890ddd
//============================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
namespace
Toshihiro Shimizu 890ddd
{
Toshihiro Shimizu 890ddd
//Const names
Toshihiro Shimizu 890ddd
enum { white = 0,
Toshihiro Shimizu 890ddd
	   black = 1 };
Toshihiro Shimizu 890ddd
enum { inner = 0,
Toshihiro Shimizu 890ddd
	   outer = 1,
Toshihiro Shimizu 890ddd
	   none = 2,
Toshihiro Shimizu 890ddd
	   invalid = 3 };
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//=======================================================================================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//-------------------------------
Toshihiro Shimizu 890ddd
//    Raster Data Functions
Toshihiro Shimizu 890ddd
//-------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//NOTA: Il tono di un TPixelCM32 rappresenta la transizione tra colore ink e colore paint.
Toshihiro Shimizu 890ddd
//      di solito, se il tono e' basso abbiamo un colore ink - che puo' anche essere bianco,
Toshihiro Shimizu 890ddd
//      in teoria...
Toshihiro Shimizu 890ddd
//      Sarebbe opportuno che il vettorizzatore riconoscesse - per colormap - il colore
Toshihiro Shimizu 890ddd
//      delle strokes.
Toshihiro Shimizu 890ddd
//      Approcci: a)  la Signaturemap diventa *piu'* di una bitmap e si seguono le outline
Toshihiro Shimizu 890ddd
//                    dei singoli colori.
Toshihiro Shimizu 890ddd
//                 => Sconnessioni tra i colori adiacenti. Bisogna introdurre la distanza tra
Toshihiro Shimizu 890ddd
//                    colori per seguire l'outline (ossia, i pixel tenuti a dx della outline
Toshihiro Shimizu 890ddd
//                    devono essere simili).
Toshihiro Shimizu 890ddd
//
Toshihiro Shimizu 890ddd
//                b)  Una volta vettorizzato tutto, si sceglie il colore della stroke.
Toshihiro Shimizu 890ddd
//                    E' possibile controllare il colore sui vertici delle sequenze semplificate
Toshihiro Shimizu 890ddd
//                    e fare una media.
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//NOTE: Transparency makes colors fade to white. Full transparent black pixels are considered white.
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
template <typename t=""></typename>
Toshihiro Shimizu 890ddd
class PixelEvaluator
Toshihiro Shimizu 890ddd
{
Toshihiro Shimizu 890ddd
	TRasterPT<t> m_ras;</t>
Toshihiro Shimizu 890ddd
	int m_threshold;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
public:
Toshihiro Shimizu 890ddd
	PixelEvaluator(const TRasterPT<t> &ras, int threshold)</t>
Toshihiro Shimizu 890ddd
		: m_ras(ras), m_threshold(threshold) {}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	inline unsigned char getBlackOrWhite(int x, int y);
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
template <>
Toshihiro Shimizu 890ddd
inline unsigned char PixelEvaluator<tpixel32>::getBlackOrWhite(int x, int y)</tpixel32>
Toshihiro Shimizu 890ddd
{
Toshihiro Shimizu 890ddd
	//return ras->pixels(y)[x].r + 2 * ras->pixels(y)[x].g + ras->pixels(y)[x].b <
Toshihiro Shimizu 890ddd
	//   threshold * (ras->pixels(y)[x].m / 255.0);
Toshihiro Shimizu 890ddd
	//NOTE: Green is considered twice brighter than red or blue channel.
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	//Using Value of HSV color model
Shinya Kitaoka 12c444
	return std::max(m_ras->pixels(y)[x].r, std::max(m_ras->pixels(y)[x].g, m_ras->pixels(y)[x].b)) <
Toshihiro Shimizu 890ddd
		   m_threshold * (m_ras->pixels(y)[x].m / 255.0);
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	//Using Lightness of HSV color model
Toshihiro Shimizu 890ddd
	//return (max(ras->pixels(y)[x].r, max(ras->pixels(y)[x].g, ras->pixels(y)[x].b)) +
Toshihiro Shimizu 890ddd
	//       min(ras->pixels(y)[x].r, min(ras->pixels(y)[x].g, ras->pixels(y)[x].b))) / 2.0 <
Toshihiro Shimizu 890ddd
	//  threshold * (ras->pixels(y)[x].m / 255.0);
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	//Using (relative) Luminance
Toshihiro Shimizu 890ddd
	//return 0.2126 * ras->pixels(y)[x].r + 0.7152 * ras->pixels(y)[x].g + 0.0722 * ras->pixels(y)[x].b <
Toshihiro Shimizu 890ddd
	//  threshold * (ras->pixels(y)[x].m / 255.0);
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
template <>
Toshihiro Shimizu 890ddd
inline unsigned char PixelEvaluator<tpixelgr8>::getBlackOrWhite(int x, int y)</tpixelgr8>
Toshihiro Shimizu 890ddd
{
Toshihiro Shimizu 890ddd
	return m_ras->pixels(y)[x].value < m_threshold;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
template <>
Toshihiro Shimizu 890ddd
inline unsigned char PixelEvaluator<tpixelcm32>::getBlackOrWhite(int x, int y)</tpixelcm32>
Toshihiro Shimizu 890ddd
{
Toshihiro Shimizu 890ddd
	return m_ras->pixels(y)[x].getTone() < m_threshold;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//Signaturemap format:
Toshihiro Shimizu 890ddd
//  stores a map of bytes, whose first bit represents the color (black/white) of corresponding pixel, and
Toshihiro Shimizu 890ddd
//  the rest its 'signature', used as an int to store information.
Toshihiro Shimizu 890ddd
//NOTE: given a TRaster32, the corresponding Signaturemap constructed is intended 0(white)-padded
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
class Signaturemap
Toshihiro Shimizu 890ddd
{
Shinya Kitaoka 79e39b
	std::unique_ptr<unsigned char[]=""> m_array;</unsigned>
Toshihiro Shimizu 890ddd
	int m_rowSize;
Toshihiro Shimizu 890ddd
	int m_colSize;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
public:
Toshihiro Shimizu 890ddd
	Signaturemap(const TRasterP &ras, int threshold);
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	template <typename t=""></typename>
Toshihiro Shimizu 890ddd
	void readRasterData(const TRasterPT<t> &ras, int threshold);</t>
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	inline int getRowSize() const { return m_rowSize; }
Toshihiro Shimizu 890ddd
	inline int getColSize() const { return m_colSize; }
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	unsigned char *pixelByte(int x, int y) { return &m_array[(y + 1) * m_rowSize + x + 1]; }
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	bool getBitmapColor(int x, int y) const
Toshihiro Shimizu 890ddd
	{
Toshihiro Shimizu 890ddd
		return m_array[(y + 1) * m_rowSize + x + 1] & 1;
Toshihiro Shimizu 890ddd
	}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	inline unsigned char getSignature(int x, int y) const
Toshihiro Shimizu 890ddd
	{
Toshihiro Shimizu 890ddd
		return m_array[(y + 1) * m_rowSize + x + 1] >> 1;
Toshihiro Shimizu 890ddd
	}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	void setSignature(int x, int y, int val)
Toshihiro Shimizu 890ddd
	{
Toshihiro Shimizu 890ddd
		unsigned char *pixel = pixelByte(x, y);
Toshihiro Shimizu 890ddd
		*pixel &= 1;
Toshihiro Shimizu 890ddd
		*pixel |= (val << 1); //Si puo' fare meglio??
Toshihiro Shimizu 890ddd
	}
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
Signaturemap::Signaturemap(const TRasterP &ras, int threshold)
Toshihiro Shimizu 890ddd
{
Toshihiro Shimizu 890ddd
	//Extrapolate raster type
Toshihiro Shimizu 890ddd
	TRaster32P rr = (TRaster32P)ras;
Toshihiro Shimizu 890ddd
	TRasterGR8P rgr = (TRasterGR8P)ras;
Toshihiro Shimizu 890ddd
	TRasterCM32P rt = (TRasterCM32P)ras;
Toshihiro Shimizu 890ddd
	assert(rr || rgr || rt);
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	//Read raster data
Toshihiro Shimizu 890ddd
	if (rr) {
Toshihiro Shimizu 890ddd
		rr->lock();
Toshihiro Shimizu 890ddd
		readRasterData(rr, threshold);
Toshihiro Shimizu 890ddd
		rr->unlock();
Toshihiro Shimizu 890ddd
	} else if (rgr) {
Toshihiro Shimizu 890ddd
		rgr->lock();
Toshihiro Shimizu 890ddd
		readRasterData(rgr, threshold);
Toshihiro Shimizu 890ddd
		rgr->unlock();
Toshihiro Shimizu 890ddd
	} else {
Toshihiro Shimizu 890ddd
		rt->lock();
Toshihiro Shimizu 890ddd
		readRasterData(rt, threshold);
Toshihiro Shimizu 890ddd
		rt->unlock();
Toshihiro Shimizu 890ddd
	}
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
template <typename t=""></typename>
Toshihiro Shimizu 890ddd
void Signaturemap::readRasterData(const TRasterPT<t> &ras, int threshold)</t>
Toshihiro Shimizu 890ddd
{
Toshihiro Shimizu 890ddd
	unsigned char *currByte;
Toshihiro Shimizu 890ddd
	int x, y;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	PixelEvaluator<t> evaluator(ras, threshold);</t>
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	m_rowSize = ras->getLx() + 2;
Toshihiro Shimizu 890ddd
	m_colSize = ras->getLy() + 2;
Shinya Kitaoka 79e39b
	m_array.reset(new unsigned char[m_rowSize * m_colSize]);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 79e39b
	memset(m_array.get(), none << 1, m_rowSize);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 79e39b
	currByte = m_array.get() + m_rowSize;
Toshihiro Shimizu 890ddd
	for (y = 0; y < ras->getLy(); ++y) {
Toshihiro Shimizu 890ddd
		*currByte = none << 1;
Toshihiro Shimizu 890ddd
		currByte++;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
		for (x = 0; x < ras->getLx(); ++x, ++currByte)
Toshihiro Shimizu 890ddd
			*currByte = evaluator.getBlackOrWhite(x, y) | (none << 1);
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
		*currByte = none << 1;
Toshihiro Shimizu 890ddd
		currByte++;
Toshihiro Shimizu 890ddd
	}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	memset(currByte, none << 1, m_rowSize);
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//Minority check for amiguous turning directions
Toshihiro Shimizu 890ddd
inline bool getMinorityCheck(const Signaturemap &ras, int x, int y)
Toshihiro Shimizu 890ddd
{
Toshihiro Shimizu 890ddd
	//Assumes (x,y) is ambiguous case: 2 immediate surrounding pixels are white and 2 black
Toshihiro Shimizu 890ddd
	return (ras.getBitmapColor(x + 1, y) +
Toshihiro Shimizu 890ddd
			ras.getBitmapColor(x + 1, y - 1) +
Toshihiro Shimizu 890ddd
			ras.getBitmapColor(x - 2, y) +
Toshihiro Shimizu 890ddd
			ras.getBitmapColor(x - 2, y - 1) +
Toshihiro Shimizu 890ddd
			ras.getBitmapColor(x - 1, y + 1) +
Toshihiro Shimizu 890ddd
			ras.getBitmapColor(x - 1, y - 2) +
Toshihiro Shimizu 890ddd
			ras.getBitmapColor(x, y + 1) +
Toshihiro Shimizu 890ddd
			ras.getBitmapColor(x, y - 2)) > 4;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//Sets signature of a given border
Toshihiro Shimizu 890ddd
inline void setSignature(Signaturemap &ras, const RawBorder &border, int val)
Toshihiro Shimizu 890ddd
{
Toshihiro Shimizu 890ddd
	unsigned int j;
Toshihiro Shimizu 890ddd
	int yOld;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	//Set border's alpha channel
Toshihiro Shimizu 890ddd
	yOld = border.back().y();
Toshihiro Shimizu 890ddd
	for (j = 0; j < border.size(); ++j) {
Toshihiro Shimizu 890ddd
		if (border[j].y() < yOld) {
Toshihiro Shimizu 890ddd
			ras.setSignature(border[j].x(), border[j].y(), val);
Toshihiro Shimizu 890ddd
		} else if (border[j].y() > yOld) {
Toshihiro Shimizu 890ddd
			ras.setSignature(border[j].x(), yOld, val);
Toshihiro Shimizu 890ddd
		}
Toshihiro Shimizu 890ddd
		yOld = border[j].y();
Toshihiro Shimizu 890ddd
	}
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//==========================================================================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//-------------------------------
Toshihiro Shimizu 890ddd
//    Raw Borders Extraction
Toshihiro Shimizu 890ddd
//-------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//RawBorderPoints correspond to lower-left pixel corners.
Toshihiro Shimizu 890ddd
//EXAMPLE: (0,0) is the lower-left *corner* of the image, whereas (0,0) also
Toshihiro Shimizu 890ddd
// represents coordinates of the lower-left *pixel*.
Toshihiro Shimizu 890ddd
//NOTE: 'Ambiguous turning' vertices are those of kind:
Toshihiro Shimizu 890ddd
//
Toshihiro Shimizu 890ddd
//    B|W           W|B
Toshihiro Shimizu 890ddd
//    -x-    -or-   -x-
Toshihiro Shimizu 890ddd
//    W|B           B|W
Toshihiro Shimizu 890ddd
//
Toshihiro Shimizu 890ddd
//Keeping B on the right of our path-seeking direction, we may either turn
Toshihiro Shimizu 890ddd
//left or right at these points.
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
RawBorder *extractPath(Signaturemap &ras, int x0, int y0,
Toshihiro Shimizu 890ddd
					   int pathType, int xOuterPixel, int despeckling)
Toshihiro Shimizu 890ddd
{
Toshihiro Shimizu 890ddd
	RawBorder *path = new RawBorder;
Toshihiro Shimizu 890ddd
	int x, y;
Toshihiro Shimizu 890ddd
	short dirX, dirY;
Toshihiro Shimizu 890ddd
	long int area = 0;
Toshihiro Shimizu 890ddd
	bool nextLeftPixel, nextRightPixel;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	if (pathType == outer) {
Toshihiro Shimizu 890ddd
		dirX = 0;
Toshihiro Shimizu 890ddd
		dirY = 1;
Toshihiro Shimizu 890ddd
	} else {
Toshihiro Shimizu 890ddd
		dirX = 1;
Toshihiro Shimizu 890ddd
		dirY = 0;
Toshihiro Shimizu 890ddd
		area += y0;
Toshihiro Shimizu 890ddd
		path->setXExternalPixel(xOuterPixel);
Toshihiro Shimizu 890ddd
	}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	path->push_back(RawBorderPoint(x0, y0));
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	//Check here if (x0, y0) is an ambiguous-direction point
Toshihiro Shimizu 890ddd
	nextLeftPixel = ras.getBitmapColor(x0 + (dirY - dirX - 1) / 2, y0 + (-dirY - dirX - 1) / 2);
Toshihiro Shimizu 890ddd
	nextRightPixel = ras.getBitmapColor(x0 + (-dirX - dirY - 1) / 2, y0 + (dirX - dirY - 1) / 2);
Toshihiro Shimizu 890ddd
	if ((nextRightPixel == black) && (nextLeftPixel == white))
Toshihiro Shimizu 890ddd
		path->back().setAmbiguous(dirX ? RawBorderPoint::left : RawBorderPoint::right);
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	//Begin path extraction
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	for (x = x0 + dirX, y = y0 + dirY; !(x == x0 && y == y0); x += dirX, y += dirY) {
Toshihiro Shimizu 890ddd
		path->push_back(RawBorderPoint(x, y));
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
		//Calculate next direction
Toshihiro Shimizu 890ddd
		nextLeftPixel = ras.getBitmapColor(x + (dirX - dirY - 1) / 2, y + (dirY + dirX - 1) / 2);
Toshihiro Shimizu 890ddd
		nextRightPixel = ras.getBitmapColor(x + (dirX + dirY - 1) / 2, y + (dirY - dirX - 1) / 2);
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
		if ((nextRightPixel == black) && (nextLeftPixel == black)) {
Toshihiro Shimizu 890ddd
			//Left Turn
Toshihiro Shimizu 890ddd
			std::swap(dirY, dirX);
Toshihiro Shimizu 890ddd
			dirX = -dirX;
Toshihiro Shimizu 890ddd
		} else if ((nextRightPixel == white) && (nextLeftPixel == white)) {
Toshihiro Shimizu 890ddd
			//Right Turn
Toshihiro Shimizu 890ddd
			std::swap(dirY, dirX);
Toshihiro Shimizu 890ddd
			dirY = -dirY;
Toshihiro Shimizu 890ddd
		} else if ((nextRightPixel == white) && (nextLeftPixel == black)) {
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
			//path->back().setAmbiguous();
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
			//Do a surrounding check and connect minority color
Toshihiro Shimizu 890ddd
			if (getMinorityCheck(ras, x, y) == black) {
Toshihiro Shimizu 890ddd
				std::swap(dirY, dirX);
Toshihiro Shimizu 890ddd
				dirY = -dirY;
Toshihiro Shimizu 890ddd
				path->back().setAmbiguous(RawBorderPoint::right);
Toshihiro Shimizu 890ddd
			} //right turn
Toshihiro Shimizu 890ddd
			else {
Toshihiro Shimizu 890ddd
				std::swap(dirY, dirX);
Toshihiro Shimizu 890ddd
				dirX = -dirX;
Toshihiro Shimizu 890ddd
				path->back().setAmbiguous(RawBorderPoint::left);
Toshihiro Shimizu 890ddd
			} //left turn
Toshihiro Shimizu 890ddd
		}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
		//Also calculate border area
Toshihiro Shimizu 890ddd
		area += y * dirX;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
		//And sign treated pixel
Toshihiro Shimizu 890ddd
		if (dirY != 0)
Toshihiro Shimizu 890ddd
			ras.setSignature(x, y + (dirY - 1) / 2, pathType);
Toshihiro Shimizu 890ddd
	}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	//If the inner region's overall area is under a given threshold,
Toshihiro Shimizu 890ddd
	//then erase it (intended as image noise).
Toshihiro Shimizu 890ddd
	if (abs(area) < despeckling) {
Toshihiro Shimizu 890ddd
		setSignature(ras, *path, invalid);
Toshihiro Shimizu 890ddd
		delete path;
Toshihiro Shimizu 890ddd
		path = 0;
Toshihiro Shimizu 890ddd
	}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	return path;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
BorderList *extractBorders(const TRasterP &ras, int threshold, int despeckling)
Toshihiro Shimizu 890ddd
{
Toshihiro Shimizu 890ddd
	Signaturemap byteImage(ras, threshold);
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	BorderList *borderHierarchy = new BorderList;
Shinya Kitaoka 3bfa54
	std::vector<rawborder *=""> outerBorders;</rawborder>
Shinya Kitaoka 3bfa54
	std::list<rawborder *=""> innerBorders;</rawborder>
Toshihiro Shimizu 890ddd
	RawBorder *foundPath;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	int x, y;
Toshihiro Shimizu 890ddd
	bool Color, oldColor;
Toshihiro Shimizu 890ddd
	int xOuterPixel = 0;
Toshihiro Shimizu 890ddd
	bool enteredRegionType;
Toshihiro Shimizu 890ddd
	unsigned char signature;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	//Traverse image to extract raw borders
Toshihiro Shimizu 890ddd
	for (y = 0; y < ras->getLy(); ++y) {
Toshihiro Shimizu 890ddd
		oldColor = white;
Toshihiro Shimizu 890ddd
		enteredRegionType = outer;
Toshihiro Shimizu 890ddd
		for (x = 0; x < ras->getLx(); ++x) {
Toshihiro Shimizu 890ddd
			if (oldColor ^ (Color = byteImage.getBitmapColor(x, y))) {
Toshihiro Shimizu 890ddd
				//Region type changes
Toshihiro Shimizu 890ddd
				enteredRegionType = !enteredRegionType;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
				if ((signature = byteImage.getSignature(x, y)) == none) {
Toshihiro Shimizu 890ddd
					//We've found a border
Campbell Barton 5ea53c
					if ((foundPath = extractPath(byteImage, x, y, !enteredRegionType, xOuterPixel, despeckling)))
Toshihiro Shimizu 890ddd
						if (enteredRegionType == outer)
Toshihiro Shimizu 890ddd
							innerBorders.push_back(foundPath);
Toshihiro Shimizu 890ddd
						else
Toshihiro Shimizu 890ddd
							outerBorders.push_back(foundPath);
Toshihiro Shimizu 890ddd
				}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
				//If leaving a white region, remember it - in order to establish
Toshihiro Shimizu 890ddd
				//border hierarchy in the future
Toshihiro Shimizu 890ddd
				if (enteredRegionType == inner && signature != invalid)
Toshihiro Shimizu 890ddd
					xOuterPixel = x;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
				//Invalid pixels got signed by a cut-out path, due to insufficient area
Toshihiro Shimizu 890ddd
				if (signature == invalid)
Toshihiro Shimizu 890ddd
					byteImage.setSignature(x, y, none); //Restore them now
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
				oldColor = Color;
Toshihiro Shimizu 890ddd
			}
Toshihiro Shimizu 890ddd
		}
Toshihiro Shimizu 890ddd
	}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	//Now, we have all borders found, but no hierarchy between them.
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	unsigned int i;
Shinya Kitaoka 3bfa54
	std::list<rawborder *="">::iterator l;</rawborder>
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	//Build hierarchy
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	innerBorders.push_front(0); //Just to keep a fixed list head
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	for (i = 0; i < outerBorders.size(); ++i) {
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
		//Initialize a border family
Toshihiro Shimizu 890ddd
		borderHierarchy->push_back(BorderFamily());
Toshihiro Shimizu 890ddd
		borderHierarchy->back().push_back(outerBorders[i]);
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
		//Reset outerBorders[i]'s signature
Toshihiro Shimizu 890ddd
		setSignature(byteImage, *outerBorders[i], none);
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
		//Now check inner borders for insideness - check if the outerPixel
Toshihiro Shimizu 890ddd
		//remembered in path extraction has been cleared
Toshihiro Shimizu 890ddd
		for (l = innerBorders.begin(), ++l; l != innerBorders.end(); ++l) {
Toshihiro Shimizu 890ddd
			if (byteImage.getSignature((*l)->xExternalPixel(), (**l)[0].y()) == none) {
Toshihiro Shimizu 890ddd
				borderHierarchy->back().push_back(*l);
Toshihiro Shimizu 890ddd
				setSignature(byteImage, **l, none);
Toshihiro Shimizu 890ddd
				l = innerBorders.erase(l);
Toshihiro Shimizu 890ddd
				--l;
Toshihiro Shimizu 890ddd
			}
Toshihiro Shimizu 890ddd
		}
Toshihiro Shimizu 890ddd
	}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	return borderHierarchy;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//==================================
Toshihiro Shimizu 890ddd
//    Calculate optimal polygons
Toshihiro Shimizu 890ddd
//==================================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//The optimal polygon for a given original border is found like:
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
// 1) Find couples (i,k(i)), so that k(i) be the largest k:
Toshihiro Shimizu 890ddd
//        d(j,ik) <= 1;  for *all* i
Toshihiro Shimizu 890ddd
//    It can be shown that such a condition is equivalent to:
Toshihiro Shimizu 890ddd
//      exists line l : d(l,j)<=1/2, for all i<=j<=k(i).
Toshihiro Shimizu 890ddd
// 2) Clean the above couples - find couples (i,l(i)):
Toshihiro Shimizu 890ddd
//        l(i)=min{k(j)},  j=i..n.
Toshihiro Shimizu 890ddd
// 3) Calculate clipped couples (i',l'); where i'=i+1, l'=l(i)-1.
Toshihiro Shimizu 890ddd
// 4) Calculate sums for path penalties.
Toshihiro Shimizu 890ddd
// 5) Apply optimality algorithm.
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//NOTE: Weak simpleness reads like: a set of polygons is weak-simple if no edge
Toshihiro Shimizu 890ddd
//      *crosses* another edge. Superposition and collision of edges with vertices
Toshihiro Shimizu 890ddd
//      are still admitted.
Toshihiro Shimizu 890ddd
//        =>  It can be shown that due to 1) and special conditions on ambiguous
Toshihiro Shimizu 890ddd
//            turnings applied in both 1) and 3), weak simpleness is insured in
Toshihiro Shimizu 890ddd
//            our polygonization.
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//Helper functions/classes: circular-indexed vectors
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//returns 1 whenever the triple (a,b,c) is 'circular' mod n.
Toshihiro Shimizu 890ddd
//NOTE: We'll find useful taking (i,i,j) as 1 and (i,j,j) as 0.
Toshihiro Shimizu 890ddd
inline bool isCircular(int a, int b, int c)
Toshihiro Shimizu 890ddd
{
Toshihiro Shimizu 890ddd
	return a <= c ? a <= b && b < c : c > b || b >= a;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//Extracts a 'next corner' array - helps improving overall speed
Shinya Kitaoka 79e39b
inline std::unique_ptr<int[]> findNextCorners(RawBorder &path)</int[]>
Toshihiro Shimizu 890ddd
{
Shinya Kitaoka 79e39b
	std::unique_ptr<int[]> corners(new int[path.size()]);</int[]>
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	//NOTE: 0 is a corner, due to the path extraction procedure.
Shinya Kitaoka 79e39b
	int currentCorner = 0;
Shinya Kitaoka 79e39b
	for (int i = path.size() - 1; i >= 0; --i) {
Toshihiro Shimizu 890ddd
		if (path[currentCorner].x() != path[i].x() &&
Toshihiro Shimizu 890ddd
			path[currentCorner].y() != path[i].y())
Toshihiro Shimizu 890ddd
			currentCorner = i + 1;
Toshihiro Shimizu 890ddd
		corners[i] = currentCorner;
Toshihiro Shimizu 890ddd
	}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	return corners;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//Calculate furthest k satisfying 1) for all fixed i.
Shinya Kitaoka 79e39b
inline std::unique_ptr<int[]> furthestKs(RawBorder &path, std::unique_ptr<int[]>& nextCorners)</int[]></int[]>
Toshihiro Shimizu 890ddd
{
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	int n = path.size();
Shinya Kitaoka 79e39b
	std::unique_ptr<int[]> kVector(new int[n]);</int[]>
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	enum { left,
Toshihiro Shimizu 890ddd
		   up,
Toshihiro Shimizu 890ddd
		   right,
Toshihiro Shimizu 890ddd
		   down };
Toshihiro Shimizu 890ddd
	int directionsOccurred[4];
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	nextCorners = findNextCorners(path);
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	int i, j, k;
Toshihiro Shimizu 890ddd
	TPoint shift;
Toshihiro Shimizu 890ddd
	TPoint leftConstraint, rightConstraint, violatedConstraint;
Toshihiro Shimizu 890ddd
	TPoint newLeftConstraint, newRightConstraint;
Toshihiro Shimizu 890ddd
	TPoint jPoint, jNextPoint, iPoint, direction;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	int directionSignature;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	for (i = 0; i < n; ++i) {
Toshihiro Shimizu 890ddd
		//Initialize search
Toshihiro Shimizu 890ddd
		leftConstraint = rightConstraint = TPoint();
Toshihiro Shimizu 890ddd
		directionsOccurred[0] = directionsOccurred[1] = directionsOccurred[2] =
Toshihiro Shimizu 890ddd
			directionsOccurred[3] = 0;
Toshihiro Shimizu 890ddd
		j = i;
Toshihiro Shimizu 890ddd
		jNextPoint = iPoint = path[i].pos();
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
		//Search for k(i)
Toshihiro Shimizu 890ddd
		while (1) {
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
			//NOTE: Here using TPoint::operator= is less effective than setting
Toshihiro Shimizu 890ddd
			//its x and y components directly...
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
			jPoint = jNextPoint;
Toshihiro Shimizu 890ddd
			jNextPoint = path[nextCorners[j]].pos();
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
			//Update directions count
Toshihiro Shimizu 890ddd
			directionSignature = jNextPoint.x > jPoint.x ? right : jNextPoint.x < jPoint.x ? left
Toshihiro Shimizu 890ddd
																						   : jNextPoint.y > jPoint.y ? up : down;
Toshihiro Shimizu 890ddd
			directionsOccurred[directionSignature] = 1;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
			//If all 4 axis directions occurred, quit
Toshihiro Shimizu 890ddd
			if (directionsOccurred[left] && directionsOccurred[right] &&
Toshihiro Shimizu 890ddd
				directionsOccurred[up] && directionsOccurred[down]) {
Toshihiro Shimizu 890ddd
				k = j;
Toshihiro Shimizu 890ddd
				goto foundK;
Toshihiro Shimizu 890ddd
			}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
			//Update displacement from i
Toshihiro Shimizu 890ddd
			shift = jNextPoint - iPoint;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
			//Test j against constraints
Toshihiro Shimizu 890ddd
			//if(cross(shift, leftConstraint)<0 || cross(shift, rightConstraint)>0)
Toshihiro Shimizu 890ddd
			if (cross(shift, leftConstraint) < 0) {
Toshihiro Shimizu 890ddd
				violatedConstraint = leftConstraint;
Toshihiro Shimizu 890ddd
				break;
Toshihiro Shimizu 890ddd
			}
Toshihiro Shimizu 890ddd
			if (cross(shift, rightConstraint) > 0) {
Toshihiro Shimizu 890ddd
				violatedConstraint = rightConstraint;
Toshihiro Shimizu 890ddd
				break;
Toshihiro Shimizu 890ddd
			}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
			//Update constraints
Toshihiro Shimizu 890ddd
			if (abs(shift.x) > 1 || abs(shift.y) > 1) {
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
				newLeftConstraint.x = shift.x +
Toshihiro Shimizu 890ddd
									  (shift.y < 0 || (shift.y == 0 && shift.x < 0) ? 1 : -1);
Toshihiro Shimizu 890ddd
				newLeftConstraint.y = shift.y +
Toshihiro Shimizu 890ddd
									  (shift.x > 0 || (shift.x == 0 && shift.y < 0) ? 1 : -1);
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
				if (cross(newLeftConstraint, leftConstraint) >= 0)
Toshihiro Shimizu 890ddd
					leftConstraint = newLeftConstraint;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
				newRightConstraint.x = shift.x +
Toshihiro Shimizu 890ddd
									   (shift.y > 0 || (shift.y == 0 && shift.x < 0) ? 1 : -1);
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
				newRightConstraint.y = shift.y +
Toshihiro Shimizu 890ddd
									   (shift.x < 0 || (shift.x == 0 && shift.y < 0) ? 1 : -1);
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
				if (cross(newRightConstraint, rightConstraint) <= 0)
Toshihiro Shimizu 890ddd
					rightConstraint = newRightConstraint;
Toshihiro Shimizu 890ddd
			}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
			//Imposing strict constraint for ambiguous turnings, to ensure polygons' weak simpleness.
Toshihiro Shimizu 890ddd
			//Has to be defined *outside* abs checks.
Toshihiro Shimizu 890ddd
			if (path[nextCorners[j]].getAmbiguous()) {
Toshihiro Shimizu 890ddd
				if (path[nextCorners[j]].getAmbiguous() == RawBorderPoint::left)
Toshihiro Shimizu 890ddd
					rightConstraint = shift;
Toshihiro Shimizu 890ddd
				else
Toshihiro Shimizu 890ddd
					leftConstraint = shift;
Toshihiro Shimizu 890ddd
			}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
			j = nextCorners[j];
Toshihiro Shimizu 890ddd
		}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
		//At this point, constraints are violated by the next corner.
Toshihiro Shimizu 890ddd
		//Then, search for the last k between j and corners[j] not violating them.
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
		direction = convert(normalize(convert(jNextPoint - jPoint)));
Toshihiro Shimizu 890ddd
		k = (j + cross(jPoint - iPoint, violatedConstraint) / cross(violatedConstraint, direction)) % n;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	foundK:
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
		kVector[i] = k;
Toshihiro Shimizu 890ddd
	}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	return kVector;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
// Now find the effective intervals inside which we can define possible
Toshihiro Shimizu 890ddd
// arcs approximating the given raw border:
Toshihiro Shimizu 890ddd
//    for every a in [i,res[i]], the arc connecting border[i] and
Toshihiro Shimizu 890ddd
//    border[a] will be a possible one.
Shinya Kitaoka 79e39b
inline std::unique_ptr<int[]> calculateForwardArcs(RawBorder &border, bool ambiguitiesCheck)</int[]>
Toshihiro Shimizu 890ddd
{
Shinya Kitaoka 79e39b
	int const n = (int)border.size();
Toshihiro Shimizu 890ddd
Shinya Kitaoka 79e39b
	std::unique_ptr<int[]> nextCorners;</int[]>
Shinya Kitaoka 79e39b
	std::unique_ptr<int[]> k = furthestKs(border, nextCorners);</int[]>
Shinya Kitaoka 79e39b
	std::unique_ptr<int[]> K(new int[n]);</int[]>
Shinya Kitaoka 79e39b
	std::unique_ptr<int[]> res(new int[n]);</int[]>
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	//find K[i]= min {k[j]}, j=i..n-1.
Shinya Kitaoka 79e39b
	for (int i = 0; i < n; ++i) {
Shinya Kitaoka 79e39b
		int j;
Toshihiro Shimizu 890ddd
		for (j = i, K[i] = k[i]; isCircular(i, j, K[i]); j = (j + 1) % n)
Toshihiro Shimizu 890ddd
			if (isCircular(j, k[j], K[i]))
Toshihiro Shimizu 890ddd
				K[i] = k[j];
Toshihiro Shimizu 890ddd
	}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	//Finally, we perform the following clean-up operations:
Toshihiro Shimizu 890ddd
	//  first, extremities of [i,K[i]] are clipped away, to obtain a
Toshihiro Shimizu 890ddd
	//    smoother optimal polygon (and deal with cases like the unitary
Toshihiro Shimizu 890ddd
	//    square);
Toshihiro Shimizu 890ddd
	//  second, arcs of the kind [i,j] with j
Toshihiro Shimizu 890ddd
Shinya Kitaoka 79e39b
	for (int i = n - 1, j = 0; j < n; i = j, ++j) {
Toshihiro Shimizu 890ddd
		res[j] = K[i] < j ? (K[i] == 0 ? n - 1 : n) : K[i] - 1;
Toshihiro Shimizu 890ddd
	}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	//Amibiguities check for vertex and edge superpositions. Prevent problems in the forecoming
Toshihiro Shimizu 890ddd
	//straight-skeleton thinning process.
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	if (ambiguitiesCheck) {
Shinya Kitaoka 79e39b
		for (int i = 1; nextCorners[i] > 0; i = nextCorners[i]) {
Toshihiro Shimizu 890ddd
			if (border[i].getAmbiguous() == RawBorderPoint::right) {
Toshihiro Shimizu 890ddd
				//Check vertices from i (excluded) to res[res[i]]; if in it there exists vertex k so that pos(k)==pos(i)...
Toshihiro Shimizu 890ddd
				//This prevents the existence of 0 degree angles in the optimal polygon.
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
				int rrPlus1 = (res[res[i] % n] + 1) % n;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 79e39b
				for (int j = nextCorners[i];
Toshihiro Shimizu 890ddd
					 isCircular(i, j, rrPlus1) && j != i; //remember that isCircular(a,a,b) == 1 ...
Toshihiro Shimizu 890ddd
					 j = nextCorners[j]) {
Toshihiro Shimizu 890ddd
					if (border[j].getAmbiguous() && (border[j].pos() == border[i].pos())) {
Toshihiro Shimizu 890ddd
						res[res[i] % n] = j - 1;
Toshihiro Shimizu 890ddd
						assert((res[i] % n) != j - 1);
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
						//Further, ensure res is increasing
Toshihiro Shimizu 890ddd
						for (int k = res[i] % n; res[k] >= j - 1 && k >= 0; --k) {
Toshihiro Shimizu 890ddd
							res[k] = j - 1;
Toshihiro Shimizu 890ddd
							assert(k != j - 1);
Toshihiro Shimizu 890ddd
						}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
						break;
Toshihiro Shimizu 890ddd
					}
Toshihiro Shimizu 890ddd
				}
Toshihiro Shimizu 890ddd
			}
Toshihiro Shimizu 890ddd
		}
Toshihiro Shimizu 890ddd
	}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	return res;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//Let sum[i] and sum2[i] be respectively the sums of vertex coordinates
Toshihiro Shimizu 890ddd
//from 0 to i, and the sums of their squares; sumsMix contain sums of
Toshihiro Shimizu 890ddd
//xy terms.
Toshihiro Shimizu 890ddd
inline void calculateSums(RawBorder &path)
Toshihiro Shimizu 890ddd
{
Toshihiro Shimizu 890ddd
	unsigned int i, n = path.size();
Toshihiro Shimizu 890ddd
	TPointD currentRelativePos;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	path.sums() = new TPointD[n + 1];
Toshihiro Shimizu 890ddd
	path.sums2() = new TPointD[n + 1];
Toshihiro Shimizu 890ddd
	path.sumsMix() = new double[n + 1];
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	path.sums()[0].x = path.sums()[0].y = path.sums2()[0].x = path.sums2()[0].y = 0;
Toshihiro Shimizu 890ddd
	for (i = 1; i < path.size(); ++i) {
Toshihiro Shimizu 890ddd
		currentRelativePos = convert(path[i].pos() - path[0].pos());
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
		path.sums()[i] = path.sums()[i - 1] + currentRelativePos;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
		path.sums2()[i].x = path.sums2()[i - 1].x + currentRelativePos.x * currentRelativePos.x;
Toshihiro Shimizu 890ddd
		path.sums2()[i].y = path.sums2()[i - 1].y + currentRelativePos.y * currentRelativePos.y;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
		path.sumsMix()[i] = path.sumsMix()[i - 1] + currentRelativePos.x * currentRelativePos.y;
Toshihiro Shimizu 890ddd
	}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	// path[n] is virtually intended as path[0], but we prefer to introduce
Toshihiro Shimizu 890ddd
	// it in the optimality algorithm's count
Toshihiro Shimizu 890ddd
	path.sums()[n].x = path.sums()[n].y = path.sums2()[n].x = path.sums2()[n].y = 0;
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//Let a,b the index-extremities of an arc of this path.
Toshihiro Shimizu 890ddd
//Then return its penalty.
Toshihiro Shimizu 890ddd
inline double penalty(RawBorder &path, int a, int b)
Toshihiro Shimizu 890ddd
{
Toshihiro Shimizu 890ddd
	int n = b - a + 1;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	TPointD v = convert(rotate90(path[b == path.size() ? 0 : b].pos() - path[a].pos()));
Toshihiro Shimizu 890ddd
	TPointD sum = path.sums()[b] - path.sums()[a];
Toshihiro Shimizu 890ddd
	TPointD sum2 = path.sums2()[b] - path.sums2()[a];
Toshihiro Shimizu 890ddd
	double sumMix = path.sumsMix()[b] - path.sumsMix()[a];
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	double F1 = sum2.x - 2 * sum.x * path[a].x() + n * path[a].x() * path[a].x();
Toshihiro Shimizu 890ddd
	double F2 = sum2.y - 2 * sum.y * path[a].y() + n * path[a].y() * path[a].y();
Toshihiro Shimizu 890ddd
	double F3 = sumMix - sum.x * path[a].y() - sum.y * path[a].x() + n * path[a].x() * path[a].y();
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	return sqrt((v.y * v.y * F1 + v.x * v.x * F2 - 2 * v.x * v.y * F3) / n);
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//NOTA: Il seguente algoritmo di riduzione assicura la semplicita' (debole) dei poligoni prodotti.
Toshihiro Shimizu 890ddd
//
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
inline void reduceBorder(RawBorder &border, Contour &res, bool ambiguitiesCheck)
Toshihiro Shimizu 890ddd
{
Shinya Kitaoka 79e39b
	int n = border.size();
Toshihiro Shimizu 890ddd
	int minPenaltyNext;
Shinya Kitaoka 79e39b
	std::unique_ptr<int[]> minPenaltyNextArray(new int[n]);</int[]>
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	//Calculate preliminary infos
Shinya Kitaoka 79e39b
	std::unique_ptr<int[]> longestArcFrom = calculateForwardArcs(border, ambiguitiesCheck);</int[]>
Toshihiro Shimizu 890ddd
	calculateSums(border);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 79e39b
	std::unique_ptr<double[]> penaltyToEnd(new double[n + 1]);</double[]>
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	//EXPLANATION:
Toshihiro Shimizu 890ddd
	//The fastest way to extract the optimal reduced border is based on the
Toshihiro Shimizu 890ddd
	//weakly monotonic property of longestArc[].
Toshihiro Shimizu 890ddd
	//The minimal number of its vertices 'm' is easily found by
Toshihiro Shimizu 890ddd
	//traversing the path with the longest step allowed. Let b[] be that
Toshihiro Shimizu 890ddd
	//succession; then, given res[i], it has to be reached by a vertex in
Toshihiro Shimizu 890ddd
	//the interval: {a[i-1], .. , b[i-1]}, where longestArc[a[i-1]]=a[i],
Toshihiro Shimizu 890ddd
	//longestArc[a[i-1]-1]
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	//Calculate m
Shinya Kitaoka 79e39b
	int m = 0;
Shinya Kitaoka 79e39b
	for (int i = 0; i < n; i = longestArcFrom[i])
Toshihiro Shimizu 890ddd
		++m;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	//Calculate b[]
Shinya Kitaoka 79e39b
	std::unique_ptr<int[]> b(new int[m + 1]);</int[]>
Toshihiro Shimizu 890ddd
	b[m] = n;
Shinya Kitaoka 79e39b
	for (int i = 0, j = 0; j < m; i = longestArcFrom[i], ++j)
Toshihiro Shimizu 890ddd
		b[j] = i;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	//NOTE: a[] need not be completely found - we just remember the
Toshihiro Shimizu 890ddd
	//a=a[j+1] currently needed.
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	//Now, build the optimal polygon
Shinya Kitaoka 79e39b
	for (int j = m - 1, a = n; j >= 0; --j) {
Shinya Kitaoka 79e39b
		int k;
Toshihiro Shimizu 890ddd
		for (k = b[j]; k >= 0 && longestArcFrom[k] >= a; --k) {
Toshihiro Shimizu 890ddd
			penaltyToEnd[k] = infinity;
Shinya Kitaoka 79e39b
			for (int i = a; i <= longestArcFrom[k]; ++i) {
Shinya Kitaoka 79e39b
				double newPenalty = penaltyToEnd[i] + penalty(border, k, i);
Toshihiro Shimizu 890ddd
				if (newPenalty < penaltyToEnd[k])
Toshihiro Shimizu 890ddd
					penaltyToEnd[k] = newPenalty;
Toshihiro Shimizu 890ddd
				minPenaltyNext = i;
Toshihiro Shimizu 890ddd
			}
Toshihiro Shimizu 890ddd
			minPenaltyNextArray[k] = minPenaltyNext;
Toshihiro Shimizu 890ddd
		}
Toshihiro Shimizu 890ddd
		a = k + 1;
Toshihiro Shimizu 890ddd
	}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	//Finally, read off the optimal polygon
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	res.resize(m);
Shinya Kitaoka 79e39b
	for (int i = 0, j = 0; i < n; i = minPenaltyNextArray[i], ++j) {
Toshihiro Shimizu 890ddd
		res[j] = ContourNode(border[i].x(), border[i].y());
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
		//Ambiguities are still remembered in the output polygon.
Toshihiro Shimizu 890ddd
		if (border[i].getAmbiguous() == RawBorderPoint::left)
Toshihiro Shimizu 890ddd
			res[j].setAttribute(ContourNode::AMBIGUOUS_LEFT);
Toshihiro Shimizu 890ddd
		if (border[i].getAmbiguous() == RawBorderPoint::right)
Toshihiro Shimizu 890ddd
			res[j].setAttribute(ContourNode::AMBIGUOUS_RIGHT);
Toshihiro Shimizu 890ddd
	}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	delete[] border.sums();
Toshihiro Shimizu 890ddd
	delete[] border.sums2();
Toshihiro Shimizu 890ddd
	delete[] border.sumsMix();
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//Reduction caller and list copier.
Toshihiro Shimizu 890ddd
inline void reduceBorders(BorderList &borders, Contours &result, bool ambiguitiesCheck)
Toshihiro Shimizu 890ddd
{
Toshihiro Shimizu 890ddd
	unsigned int i, j;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	//Initialize output container
Toshihiro Shimizu 890ddd
	result.resize(borders.size());
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	//Copy results
Toshihiro Shimizu 890ddd
	for (i = 0; i < borders.size(); ++i) {
Toshihiro Shimizu 890ddd
		result[i].resize(borders[i].size());
Toshihiro Shimizu 890ddd
		for (j = 0; j < borders[i].size(); ++j) {
Toshihiro Shimizu 890ddd
			reduceBorder(*borders[i][j], result[i][j], ambiguitiesCheck);
Toshihiro Shimizu 890ddd
			delete borders[i][j];
Toshihiro Shimizu 890ddd
		}
Toshihiro Shimizu 890ddd
	}
Toshihiro Shimizu 890ddd
}
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//--------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//===========================
Toshihiro Shimizu 890ddd
//    Polygonization Main
Toshihiro Shimizu 890ddd
//===========================
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//Extracts a polygonal, minimal yet faithful representation of image contours
Toshihiro Shimizu 890ddd
//Contours* polygonize(const TRasterP &ras){
Toshihiro Shimizu 890ddd
void polygonize(const TRasterP &ras, Contours &polygons, VectorizerCoreGlobals &g)
Toshihiro Shimizu 890ddd
{
Toshihiro Shimizu 890ddd
	BorderList *borders;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
	borders = extractBorders(ras, g.currConfig->m_threshold, g.currConfig->m_despeckling);
Toshihiro Shimizu 890ddd
	reduceBorders(*borders, polygons, g.currConfig->m_maxThickness > 0.0);
Toshihiro Shimizu 890ddd
}