Leptonica  1.54
Файл src/ptafunc1.c
#include <math.h>
#include "allheaders.h"

Макросы

#define M_PI   3.14159265358979323846

Функции

static l_int32 l_dnaCopyUniquePts (L_DNA *da, PTA *ptas, PTA *ptad)
PTAptaSubsample (PTA *ptas, l_int32 subfactor)
l_int32 ptaJoin (PTA *ptad, PTA *ptas, l_int32 istart, l_int32 iend)
l_int32 ptaaJoin (PTAA *ptaad, PTAA *ptaas, l_int32 istart, l_int32 iend)
PTAptaReverse (PTA *ptas, l_int32 type)
PTAptaTranspose (PTA *ptas)
PTAptaCyclicPerm (PTA *ptas, l_int32 xs, l_int32 ys)
PTAptaSort (PTA *ptas, l_int32 sorttype, l_int32 sortorder, NUMA **pnaindex)
l_int32 ptaGetSortIndex (PTA *ptas, l_int32 sorttype, l_int32 sortorder, NUMA **pnaindex)
PTAptaSortByIndex (PTA *ptas, NUMA *naindex)
PTAAptaaSortByIndex (PTAA *ptaas, NUMA *naindex)
PTAptaUnionByAset (PTA *pta1, PTA *pta2)
PTAptaRemoveDupsByAset (PTA *ptas)
PTAptaIntersectionByAset (PTA *pta1, PTA *pta2)
L_ASETl_asetCreateFromPta (PTA *pta)
PTAptaUnionByHash (PTA *pta1, PTA *pta2)
l_int32 ptaRemoveDupsByHash (PTA *ptas, PTA **pptad, L_DNAHASH **pdahash)
PTAptaIntersectionByHash (PTA *pta1, PTA *pta2)
l_int32 ptaFindPtByHash (PTA *pta, L_DNAHASH *dahash, l_int32 x, l_int32 y, l_int32 *pindex)
L_DNAHASHl_dnaHashCreateFromPta (PTA *pta)
BOXptaGetBoundingRegion (PTA *pta)
l_int32 ptaGetRange (PTA *pta, l_float32 *pminx, l_float32 *pmaxx, l_float32 *pminy, l_float32 *pmaxy)
PTAptaGetInsideBox (PTA *ptas, BOX *box)
PTApixFindCornerPixels (PIX *pixs)
l_int32 ptaContainsPt (PTA *pta, l_int32 x, l_int32 y)
l_int32 ptaTestIntersection (PTA *pta1, PTA *pta2)
PTAptaTransform (PTA *ptas, l_int32 shiftx, l_int32 shifty, l_float32 scalex, l_float32 scaley)
l_int32 ptaPtInsidePolygon (PTA *pta, l_float32 x, l_float32 y, l_int32 *pinside)
l_float32 l_angleBetweenVectors (l_float32 x1, l_float32 y1, l_float32 x2, l_float32 y2)
l_int32 ptaGetLinearLSF (PTA *pta, l_float32 *pa, l_float32 *pb, NUMA **pnafit)
l_int32 ptaGetQuadraticLSF (PTA *pta, l_float32 *pa, l_float32 *pb, l_float32 *pc, NUMA **pnafit)
l_int32 ptaGetCubicLSF (PTA *pta, l_float32 *pa, l_float32 *pb, l_float32 *pc, l_float32 *pd, NUMA **pnafit)
l_int32 ptaGetQuarticLSF (PTA *pta, l_float32 *pa, l_float32 *pb, l_float32 *pc, l_float32 *pd, l_float32 *pe, NUMA **pnafit)
l_int32 ptaNoisyLinearLSF (PTA *pta, l_float32 factor, PTA **pptad, l_float32 *pa, l_float32 *pb, l_float32 *pmederr, NUMA **pnafit)
l_int32 ptaNoisyQuadraticLSF (PTA *pta, l_float32 factor, PTA **pptad, l_float32 *pa, l_float32 *pb, l_float32 *pc, l_float32 *pmederr, NUMA **pnafit)
l_int32 applyLinearFit (l_float32 a, l_float32 b, l_float32 x, l_float32 *py)
l_int32 applyQuadraticFit (l_float32 a, l_float32 b, l_float32 c, l_float32 x, l_float32 *py)
l_int32 applyCubicFit (l_float32 a, l_float32 b, l_float32 c, l_float32 d, l_float32 x, l_float32 *py)
l_int32 applyQuarticFit (l_float32 a, l_float32 b, l_float32 c, l_float32 d, l_float32 e, l_float32 x, l_float32 *py)
l_int32 pixPlotAlongPta (PIX *pixs, PTA *pta, l_int32 outformat, const char *title)
PTAptaGetPixelsFromPix (PIX *pixs, BOX *box)
PIXpixGenerateFromPta (PTA *pta, l_int32 w, l_int32 h)
PTAptaGetBoundaryPixels (PIX *pixs, l_int32 type)
PTAAptaaGetBoundaryPixels (PIX *pixs, l_int32 type, l_int32 connectivity, BOXA **pboxa, PIXA **ppixa)
PTAAptaaIndexLabelledPixels (PIX *pixs, l_int32 *pncc)
PTAptaGetNeighborPixLocs (PIX *pixs, l_int32 x, l_int32 y, l_int32 conn)
PIXpixDisplayPta (PIX *pixd, PIX *pixs, PTA *pta)
PIXpixDisplayPtaaPattern (PIX *pixd, PIX *pixs, PTAA *ptaa, PIX *pixp, l_int32 cx, l_int32 cy)
PIXpixDisplayPtaPattern (PIX *pixd, PIX *pixs, PTA *pta, PIX *pixp, l_int32 cx, l_int32 cy, l_uint32 color)
PTAptaReplicatePattern (PTA *ptas, PIX *pixp, PTA *ptap, l_int32 cx, l_int32 cy, l_int32 w, l_int32 h)
PIXpixDisplayPtaa (PIX *pixs, PTAA *ptaa)

Макросы

#define M_PI   3.14159265358979323846

Функции

applyCubicFit()

Input: a, b, c, d (cubic fit coefficients) x &y (<return> y = a * x^3 + b * x^2 + c * x + d) Return: 0 if OK, 1 on error

applyLinearFit()

Input: a, b (linear fit coefficients) x &y (<return> y = a * x + b) Return: 0 if OK, 1 on error

applyQuadraticFit()

Input: a, b, c (quadratic fit coefficients) x &y (<return> y = a * x^2 + b * x + c) Return: 0 if OK, 1 on error

applyQuarticFit()

Input: a, b, c, d, e (quartic fit coefficients) x &y (<return> y = a * x^4 + b * x^3 + c * x^2 + d * x + e) Return: 0 if OK, 1 on error

l_angleBetweenVectors()

Input: x1, y1 (end point of first vector) x2, y2 (end point of second vector) Return: angle (radians), or 0.0 on error

Notes: (1) This gives the angle between two vectors, going between vector1 (x1,y1) and vector2 (x2,y2). The angle is swept out from 1 --> 2. If this is clockwise, the angle is positive, but the result is folded into the interval [-pi, pi].

l_asetCreateFromPta()

Input: pta Return: set (using a 64-bit hash of (x,y) as the key)

static l_int32 l_dnaCopyUniquePts ( L_DNA da,
PTA ptas,
PTA ptad 
) [static]

l_dnaHashCreateFromPta()

Input: pta Return: dahash, or null on error

PIX* pixDisplayPta ( PIX pixd,
PIX pixs,
PTA pta 
)

pixDisplayPta()

Input: pixd (can be same as pixs or null; 32 bpp if in-place) pixs (1, 2, 4, 8, 16 or 32 bpp) pta (of path to be plotted) Return: pixd (32 bpp RGB version of pixs, with path in green).

Notes: (1) To write on an existing pixs, pixs must be 32 bpp and call with pixd == pixs: pixDisplayPta(pixs, pixs, pta); To write to a new pix, use pixd == NULL and call: pixd = pixDisplayPta(NULL, pixs, pta); (2) On error, returns pixd to avoid losing pixs if called as pixs = pixDisplayPta(pixs, pixs, pta);

PIX* pixDisplayPtaa ( PIX pixs,
PTAA ptaa 
)

pixDisplayPtaa()

Input: pixs (1, 2, 4, 8, 16 or 32 bpp) ptaa (array of paths to be plotted) Return: pixd (32 bpp RGB version of pixs, with paths plotted in different colors), or null on error

PIX* pixDisplayPtaaPattern ( PIX pixd,
PIX pixs,
PTAA ptaa,
PIX pixp,
l_int32  cx,
l_int32  cy 
)

pixDisplayPtaaPattern()

Input: pixd (32 bpp) pixs (1, 2, 4, 8, 16 or 32 bpp; 32 bpp if in place) ptaa (giving locations at which the pattern is displayed) pixp (1 bpp pattern to be placed such that its reference point co-locates with each point in pta) cx, cy (reference point in pattern) Return: pixd (32 bpp RGB version of pixs).

Notes: (1) To write on an existing pixs, pixs must be 32 bpp and call with pixd == pixs: pixDisplayPtaPattern(pixs, pixs, pta, ...); To write to a new pix, use pixd == NULL and call: pixd = pixDisplayPtaPattern(NULL, pixs, pta, ...); (2) Puts a random color on each pattern associated with a pta. (3) On error, returns pixd to avoid losing pixs if called as pixs = pixDisplayPtaPattern(pixs, pixs, pta, ...); (4) A typical pattern to be used is a circle, generated with generatePtaFilledCircle()

PIX* pixDisplayPtaPattern ( PIX pixd,
PIX pixs,
PTA pta,
PIX pixp,
l_int32  cx,
l_int32  cy,
l_uint32  color 
)

pixDisplayPtaPattern()

Input: pixd (can be same as pixs or null; 32 bpp if in-place) pixs (1, 2, 4, 8, 16 or 32 bpp) pta (giving locations at which the pattern is displayed) pixp (1 bpp pattern to be placed such that its reference point co-locates with each point in pta) cx, cy (reference point in pattern) color (in 0xrrggbb00 format) Return: pixd (32 bpp RGB version of pixs).

Notes: (1) To write on an existing pixs, pixs must be 32 bpp and call with pixd == pixs: pixDisplayPtaPattern(pixs, pixs, pta, ...); To write to a new pix, use pixd == NULL and call: pixd = pixDisplayPtaPattern(NULL, pixs, pta, ...); (2) On error, returns pixd to avoid losing pixs if called as pixs = pixDisplayPtaPattern(pixs, pixs, pta, ...); (3) A typical pattern to be used is a circle, generated with generatePtaFilledCircle()

PTA* pixFindCornerPixels ( PIX pixs)

pixFindCornerPixels()

Input: pixs (1 bpp) Return: pta, or null on error

Notes: (1) Finds the 4 corner-most pixels, as defined by a search inward from each corner, using a 45 degree line.

PIX* pixGenerateFromPta ( PTA pta,
l_int32  w,
l_int32  h 
)

pixGenerateFromPta()

Input: pta w, h (of pix) Return: pix (1 bpp), or null on error

Notes: (1) Points are rounded to nearest ints. (2) Any points outside (w,h) are silently discarded. (3) Output 1 bpp pix has values 1 for each point in the pta.

l_int32 pixPlotAlongPta ( PIX pixs,
PTA pta,
l_int32  outformat,
const char *  title 
)

pixPlotAlongPta()

Input: pixs (any depth) pta (set of points on which to plot) outformat (GPLOT_PNG, GPLOT_PS, GPLOT_EPS, GPLOT_X11, GPLOT_LATEX) title (<optional> for plot; can be null) Return: 0 if OK, 1 on error

Notes: (1) We remove any existing colormap and clip the pta to the input pixs. (2) This is a debugging function, and does not remove temporary plotting files that it generates. (3) If the image is RGB, three separate plots are generated.

PTAA* ptaaGetBoundaryPixels ( PIX pixs,
l_int32  type,
l_int32  connectivity,
BOXA **  pboxa,
PIXA **  ppixa 
)

ptaaGetBoundaryPixels()

Input: pixs (1 bpp) type (L_BOUNDARY_FG, L_BOUNDARY_BG) connectivity (4 or 8) &boxa (<optional return>=""> bounding boxes of the c.c.) &pixa (<optional return>=""> pixa of the c.c.) Return: ptaa, or null on error

Notes: (1) This generates a ptaa of either fg or bg boundary pixels, where each pta has the boundary pixels for a connected component. (2) We can't simply find all the boundary pixels and then select those within the bounding box of each component, because bounding boxes can overlap. It is necessary to extract and dilate or erode each component separately. Note also that special handling is required for bg pixels when the component touches the pix boundary.

PTAA* ptaaIndexLabelledPixels ( PIX pixs,
l_int32 pncc 
)

ptaaIndexLabelledPixels()

Input: pixs (32 bpp, of indices of c.c.) &ncc (<optional return>=""> number of connected components) Return: ptaa, or null on error

Notes: (1) The pixel values in are the index of the connected component to which the pixel belongs; is typically generated from a 1 bpp pix by pixConnCompTransform(). Background pixels in the generating 1 bpp pix are represented in by 0. We do not check that the pixel values are correctly labelled. (2) Each pta in the returned ptaa gives the pixel locations correspnding to a connected component, with the label of each given by the index of the pta into the ptaa. (3) Initialize with the first pta in ptaa being empty and representing the background value (index 0) in the pix.

l_int32 ptaaJoin ( PTAA ptaad,
PTAA ptaas,
l_int32  istart,
l_int32  iend 
)

ptaaJoin()

Input: ptaad (dest ptaa; add to this one) ptaas (source ptaa; add from this one) istart (starting index in ptaas) iend (ending index in ptaas; use -1 to cat all) Return: 0 if OK, 1 on error

Notes: (1) istart < 0 is taken to mean 'read from the start' (istart = 0) (2) iend < 0 means 'read to the end' (3) if ptas == NULL, this is a no-op

PTAA* ptaaSortByIndex ( PTAA ptaas,
NUMA naindex 
)

ptaaSortByIndex()

Input: ptaas naindex (na that maps from the new ptaa to the input ptaa) Return: ptaad (sorted), or null on error

l_int32 ptaContainsPt ( PTA pta,
l_int32  x,
l_int32  y 
)

ptaContainsPt()

Input: pta x, y (point) Return: 1 if contained, 0 otherwise or on error

PTA* ptaCyclicPerm ( PTA ptas,
l_int32  xs,
l_int32  ys 
)

ptaCyclicPerm()

Input: ptas xs, ys (start point; must be in ptas) Return: ptad (cyclic permutation, starting and ending at (xs, ys), or null on error

Notes: (1) Check to insure that (a) ptas is a closed path where the first and last points are identical, and (b) the resulting pta also starts and ends on the same point (which in this case is (xs, ys).

l_int32 ptaFindPtByHash ( PTA pta,
L_DNAHASH dahash,
l_int32  x,
l_int32  y,
l_int32 pindex 
)

ptaFindPtByHash()

Input: pta dahash (built from pta) x, y (arbitrary points) &index (<return> index into pta if (x,y) is in pta; -1 otherwise) Return: 0 if OK, 1 on error

Notes: (1) Fast lookup in dnaHash associated with a pta, to see if a random point (x,y) is already stored in the hash table.

PTA* ptaGetBoundaryPixels ( PIX pixs,
l_int32  type 
)

ptaGetBoundaryPixels()

Input: pixs (1 bpp) type (L_BOUNDARY_FG, L_BOUNDARY_BG) Return: pta, or null on error

Notes: (1) This generates a pta of either fg or bg boundary pixels. (2) See also pixGeneratePtaBoundary() for rendering of fg boundary pixels.

ptaGetBoundingRegion()

Input: pta Return: box, or null on error

Notes: (1) This is used when the pta represents a set of points in a two-dimensional image. It returns the box of minimum size containing the pts in the pta.

l_int32 ptaGetCubicLSF ( PTA pta,
l_float32 pa,
l_float32 pb,
l_float32 pc,
l_float32 pd,
NUMA **  pnafit 
)

ptaGetCubicLSF()

Input: pta &a (<optional return>=""> coeff a of LSF: y = ax^3 + bx^2 + cx + d) &b (<optional return>=""> coeff b of LSF) &c (<optional return>=""> coeff c of LSF) &d (<optional return>=""> coeff d of LSF) &nafit (<optional return>=""> numa of least square fit) Return: 0 if OK, 1 on error

Notes: (1) This does a cubic least square fit to the set of points in . That is, it finds coefficients a, b, c and d that minimize:

sum (yi - a*xi*xi*xi -b*xi*xi -c*xi - d)^2 i

Differentiate this expression w/rt a, b, c and d, and solve the resulting four equations for these coefficients in terms of various sums over the input data (xi, yi). The four equations are in the form: f[0][0]a + f[0][1]b + f[0][2]c + f[0][3] = g[0] f[1][0]a + f[1][1]b + f[1][2]c + f[1][3] = g[1] f[2][0]a + f[2][1]b + f[2][2]c + f[2][3] = g[2] f[3][0]a + f[3][1]b + f[3][2]c + f[3][3] = g[3] (2) If is defined, this returns an array of fitted values, corresponding to the two implicit Numa arrays (nax and nay) in pta. Thus, just as you can plot the data in pta as nay vs. nax, you can plot the linear least square fit as nafit vs. nax.

PTA* ptaGetInsideBox ( PTA ptas,
BOX box 
)

ptaGetInsideBox()

Input: ptas (input pts) box Return: ptad (of pts in ptas that are inside the box), or null on error

l_int32 ptaGetLinearLSF ( PTA pta,
l_float32 pa,
l_float32 pb,
NUMA **  pnafit 
)

ptaGetLinearLSF()

Input: pta &a (<optional return>=""> slope a of least square fit: y = ax + b) &b (<optional return>=""> intercept b of least square fit) &nafit (<optional return>=""> numa of least square fit) Return: 0 if OK, 1 on error

Notes: (1) Either or both &a and &b must be input. They determine the type of line that is fit. (2) If both &a and &b are defined, this returns a and b that minimize:

sum (yi - axi -b)^2 i

The method is simple: differentiate this expression w/rt a and b, and solve the resulting two equations for a and b in terms of various sums over the input data (xi, yi). (3) We also allow two special cases, where either a = 0 or b = 0: (a) If &a is given and &b = null, find the linear LSF that goes through the origin (b = 0). (b) If &b is given and &a = null, find the linear LSF with zero slope (a = 0). (4) If is defined, this returns an array of fitted values, corresponding to the two implicit Numa arrays (nax and nay) in pta. Thus, just as you can plot the data in pta as nay vs. nax, you can plot the linear least square fit as nafit vs. nax.

PTA* ptaGetNeighborPixLocs ( PIX pixs,
l_int32  x,
l_int32  y,
l_int32  conn 
)

ptaGetNeighborPixLocs()

Input: pixs (any depth) x, y (pixel from which we search for nearest neighbors conn (4 or 8 connectivity) Return: pta, or null on error

Notes: (1) Generates a pta of all valid neighbor pixel locations, or null on error.

PTA* ptaGetPixelsFromPix ( PIX pixs,
BOX box 
)

ptaGetPixelsFromPix()

Input: pixs (1 bpp) box (<optional> can be null) Return: pta, or null on error

Notes: (1) Generates a pta of fg pixels in the pix, within the box. If box == NULL, it uses the entire pix.

l_int32 ptaGetQuadraticLSF ( PTA pta,
l_float32 pa,
l_float32 pb,
l_float32 pc,
NUMA **  pnafit 
)

ptaGetQuadraticLSF()

Input: pta &a (<optional return>=""> coeff a of LSF: y = ax^2 + bx + c) &b (<optional return>=""> coeff b of LSF: y = ax^2 + bx + c) &c (<optional return>=""> coeff c of LSF: y = ax^2 + bx + c) &nafit (<optional return>=""> numa of least square fit) Return: 0 if OK, 1 on error

Notes: (1) This does a quadratic least square fit to the set of points in . That is, it finds coefficients a, b and c that minimize:

sum (yi - a*xi*xi -b*xi -c)^2 i

The method is simple: differentiate this expression w/rt a, b and c, and solve the resulting three equations for these coefficients in terms of various sums over the input data (xi, yi). The three equations are in the form: f[0][0]a + f[0][1]b + f[0][2]c = g[0] f[1][0]a + f[1][1]b + f[1][2]c = g[1] f[2][0]a + f[2][1]b + f[2][2]c = g[2] (2) If is defined, this returns an array of fitted values, corresponding to the two implicit Numa arrays (nax and nay) in pta. Thus, just as you can plot the data in pta as nay vs. nax, you can plot the linear least square fit as nafit vs. nax.

l_int32 ptaGetQuarticLSF ( PTA pta,
l_float32 pa,
l_float32 pb,
l_float32 pc,
l_float32 pd,
l_float32 pe,
NUMA **  pnafit 
)

ptaGetQuarticLSF()

Input: pta &a (<optional return>=""> coeff a of LSF: y = ax^4 + bx^3 + cx^2 + dx + e) &b (<optional return>=""> coeff b of LSF) &c (<optional return>=""> coeff c of LSF) &d (<optional return>=""> coeff d of LSF) &e (<optional return>=""> coeff e of LSF) &nafit (<optional return>=""> numa of least square fit) Return: 0 if OK, 1 on error

Notes: (1) This does a quartic least square fit to the set of points in . That is, it finds coefficients a, b, c, d and 3 that minimize:

sum (yi - a*xi*xi*xi*xi -b*xi*xi*xi -c*xi*xi - d*xi - e)^2 i

Differentiate this expression w/rt a, b, c, d and e, and solve the resulting five equations for these coefficients in terms of various sums over the input data (xi, yi). The five equations are in the form: f[0][0]a + f[0][1]b + f[0][2]c + f[0][3] + f[0][4] = g[0] f[1][0]a + f[1][1]b + f[1][2]c + f[1][3] + f[1][4] = g[1] f[2][0]a + f[2][1]b + f[2][2]c + f[2][3] + f[2][4] = g[2] f[3][0]a + f[3][1]b + f[3][2]c + f[3][3] + f[3][4] = g[3] f[4][0]a + f[4][1]b + f[4][2]c + f[4][3] + f[4][4] = g[4] (2) If is defined, this returns an array of fitted values, corresponding to the two implicit Numa arrays (nax and nay) in pta. Thus, just as you can plot the data in pta as nay vs. nax, you can plot the linear least square fit as nafit vs. nax.

l_int32 ptaGetRange ( PTA pta,
l_float32 pminx,
l_float32 pmaxx,
l_float32 pminy,
l_float32 pmaxy 
)

ptaGetRange()

Input: pta &minx (<optional return>=""> min value of x) &maxx (<optional return>=""> max value of x) &miny (<optional return>=""> min value of y) &maxy (<optional return>=""> max value of y) Return: 0 if OK, 1 on error

Notes: (1) We can use pts to represent pairs of floating values, that are not necessarily tied to a two-dimension region. For example, the pts can represent a general function y(x).

l_int32 ptaGetSortIndex ( PTA ptas,
l_int32  sorttype,
l_int32  sortorder,
NUMA **  pnaindex 
)

ptaGetSortIndex()

Input: ptas sorttype (L_SORT_BY_X, L_SORT_BY_Y) sortorder (L_SORT_INCREASING, L_SORT_DECREASING) &naindex (<return> index of sorted order into original array) Return: 0 if OK, 1 on error

PTA* ptaIntersectionByAset ( PTA pta1,
PTA pta2 
)

ptaIntersectionByAset()

Input: pta1, pta2 Return: ptad (intersection of the point sets), or null on error

Notes: (1) See sarrayIntersectionByAset() for the approach. (2) The key is a 64-bit hash from the (x,y) pair. (3) This is slower than ptaIntersectionByHash(), mostly because of the nlogn sort to build up the rbtree. Do not use for large numbers of points (say, > 1M).

PTA* ptaIntersectionByHash ( PTA pta1,
PTA pta2 
)

ptaIntersectionByHash()

Input: pta1, pta2 Return: ptad (intersection of the point sets), or null on error

Notes: (1) This is faster than ptaIntersectionByAset(), because the bucket lookup is O(n). It should be used if the pts are integers (e.g., representing pixel positions).

l_int32 ptaJoin ( PTA ptad,
PTA ptas,
l_int32  istart,
l_int32  iend 
)

ptaJoin()

Input: ptad (dest pta; add to this one) ptas (source pta; add from this one) istart (starting index in ptas) iend (ending index in ptas; use -1 to cat all) Return: 0 if OK, 1 on error

Notes: (1) istart < 0 is taken to mean 'read from the start' (istart = 0) (2) iend < 0 means 'read to the end' (3) if ptas == NULL, this is a no-op

l_int32 ptaNoisyLinearLSF ( PTA pta,
l_float32  factor,
PTA **  pptad,
l_float32 pa,
l_float32 pb,
l_float32 pmederr,
NUMA **  pnafit 
)

ptaNoisyLinearLSF()

Input: pta factor (reject outliers with error greater than this number of medians; typically ~ 3) &ptad (<optional return>=""> with outliers removed) &a (<optional return>=""> slope a of least square fit: y = ax + b) &b (<optional return>=""> intercept b of least square fit) &mederr (<optional return>=""> median error) &nafit (<optional return>=""> numa of least square fit to ptad) Return: 0 if OK, 1 on error

Notes: (1) This does a linear least square fit to the set of points in . It then evaluates the errors and removes points whose error is >= factor * median_error. It then re-runs the linear LSF on the resulting points. (2) Either or both &a and &b must be input. They determine the type of line that is fit. (3) The median error can give an indication of how good the fit is likely to be.

l_int32 ptaNoisyQuadraticLSF ( PTA pta,
l_float32  factor,
PTA **  pptad,
l_float32 pa,
l_float32 pb,
l_float32 pc,
l_float32 pmederr,
NUMA **  pnafit 
)

ptaNoisyQuadraticLSF()

Input: pta factor (reject outliers with error greater than this number of medians; typically ~ 3) &ptad (<optional return>=""> with outliers removed) &a (<optional return>=""> coeff a of LSF: y = ax^2 + bx + c) &b (<optional return>=""> coeff b of LSF: y = ax^2 + bx + c) &c (<optional return>=""> coeff c of LSF: y = ax^2 + bx + c) &mederr (<optional return>=""> median error) &nafit (<optional return>=""> numa of least square fit to ptad) Return: 0 if OK, 1 on error

Notes: (1) This does a quadratic least square fit to the set of points in . It then evaluates the errors and removes points whose error is >= factor * median_error. It then re-runs a quadratic LSF on the resulting points.

l_int32 ptaPtInsidePolygon ( PTA pta,
l_float32  x,
l_float32  y,
l_int32 pinside 
)

ptaPtInsidePolygon()

Input: pta (vertices of a polygon) x, y (point to be tested) &inside (<return> 1 if inside; 0 if outside or on boundary) Return: 1 if OK, 0 on error

The abs value of the sum of the angles subtended from a point by the sides of a polygon, when taken in order traversing the polygon, is 0 if the point is outside the polygon and 2*pi if inside. The sign will be positive if traversed cw and negative if ccw.

PTA* ptaRemoveDupsByAset ( PTA ptas)

ptaRemoveDupsByAset()

Input: ptas (assumed to be integer values) Return: ptad (with duplicates removed), or null on error

Notes: (1) This is slower than ptaRemoveDupsByHash(), mostly because of the nlogn sort to build up the rbtree. Do not use for large numbers of points (say, > 1M).

l_int32 ptaRemoveDupsByHash ( PTA ptas,
PTA **  pptad,
L_DNAHASH **  pdahash 
)

ptaRemoveDupsByHash()

Input: ptas (assumed to be integer values) &ptad (<return> unique set of pts; duplicates removed) &dahash (<optional return>=""> dnahash used for lookup) Return: 0 if OK, 1 on error

Notes: (1) Generates a pta with unique values. (2) The dnahash is built up with ptad to assure uniqueness. It can be used to find if a point is in the set: ptaFindPtByHash(ptad, dahash, x, y, &index) (3) The hash of the (x,y) location is simple and fast. It scales up with the number of buckets to insure a fairly random bucket selection for adjacent points. (4) A Dna is used rather than a Numa because we need accurate representation of 32-bit integers that are indices into ptas. Integer --> float --> integer conversion makes errors for integers larger than 10M. (5) This is faster than ptaRemoveDupsByAset(), because the bucket lookup is O(n), although there is a double-loop lookup within the dna in each bucket.

PTA* ptaReplicatePattern ( PTA ptas,
PIX pixp,
PTA ptap,
l_int32  cx,
l_int32  cy,
l_int32  w,
l_int32  h 
)

ptaReplicatePattern()

Input: ptas ("sparse" input pta) pixp (<optional> 1 bpp pattern, to be replicated in output pta) ptap (<optional> set of pts, to be replicated in output pta) cx, cy (reference point in pattern) w, h (clipping sizes for output pta) Return: ptad (with all points of replicated pattern), or null on error

Notes: (1) You can use either the image or the set of pts . (2) The pattern is placed with its reference point at each point in ptas, and all the fg pixels are colleced into ptad. For , this is equivalent to blitting pixp at each point in ptas, and then converting the resulting pix to a pta.

PTA* ptaReverse ( PTA ptas,
l_int32  type 
)

ptaReverse()

Input: ptas type (0 for float values; 1 for integer values) Return: ptad (reversed pta), or null on error

PTA* ptaSort ( PTA ptas,
l_int32  sorttype,
l_int32  sortorder,
NUMA **  pnaindex 
)

ptaSort()

Input: ptas sorttype (L_SORT_BY_X, L_SORT_BY_Y) sortorder (L_SORT_INCREASING, L_SORT_DECREASING) &naindex (<optional return>=""> index of sorted order into original array) Return: ptad (sorted version of ptas), or null on error

PTA* ptaSortByIndex ( PTA ptas,
NUMA naindex 
)

ptaSortByIndex()

Input: ptas naindex (na that maps from the new pta to the input pta) Return: ptad (sorted), or null on error

PTA* ptaSubsample ( PTA ptas,
l_int32  subfactor 
)

ptaSubsample()

Input: ptas subfactor (subsample factor, >= 1) Return: ptad (evenly sampled pt values from ptas, or null on error

l_int32 ptaTestIntersection ( PTA pta1,
PTA pta2 
)

ptaTestIntersection()

Input: pta1, pta2 Return: bval which is 1 if they have any elements in common; 0 otherwise or on error.

PTA* ptaTransform ( PTA ptas,
l_int32  shiftx,
l_int32  shifty,
l_float32  scalex,
l_float32  scaley 
)

ptaTransform()

Input: pta shiftx, shifty scalex, scaley Return: pta, or null on error

Notes: (1) Shift first, then scale.

PTA* ptaTranspose ( PTA ptas)

ptaTranspose()

Input: ptas Return: ptad (with x and y values swapped), or null on error

PTA* ptaUnionByAset ( PTA pta1,
PTA pta2 
)

ptaUnionByAset()

Input: pta1, pta2 Return: ptad (with the union of the set of points), or null on error

Notes: (1) See sarrayRemoveDupsByAset() for the approach. (2) The key is a 64-bit hash from the (x,y) pair. (3) This is slower than ptaUnionByHash(), mostly because of the nlogn sort to build up the rbtree. Do not use for large numbers of points (say, > 1M). (4) The *Aset() functions use the sorted l_Aset, which is just an rbtree in disguise.

PTA* ptaUnionByHash ( PTA pta1,
PTA pta2 
)

ptaUnionByHash()

Input: pta1, pta2 Return: ptad (with the union of the set of points), or null on error

Notes: (1) This is faster than ptaUnionByAset(), because the bucket lookup is O(n). It should be used if the pts are integers (e.g., representing pixel positions).