[gegl/soc-2011-seamless-clone: 1/17] Introduce work in progress code of the Seamless Clone Operation
- From: Barak Itkin <barakitkin src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gegl/soc-2011-seamless-clone: 1/17] Introduce work in progress code of the Seamless Clone Operation
- Date: Sat, 17 Mar 2012 19:19:11 +0000 (UTC)
commit 760ba2b1c087663a0b4663fdcad6b1647eb90454
Author: Barak Itkin <lightningismyname gmail com>
Date: Mon Aug 1 23:08:51 2011 +0300
Introduce work in progress code of the Seamless Clone Operation
This commit also includes the code of the poly2tri-c library.
operations/common/seamless-clone/Makefile.am | 9 +
operations/common/seamless-clone/find-outline.c | 220 +++
operations/common/seamless-clone/find-outline.h | 40 +
operations/common/seamless-clone/make-mesh.c | 228 +++
operations/common/seamless-clone/make-mesh.h | 43 +
.../seamless-clone/poly2tri-c/common/cutils.h | 39 +
.../poly2tri-c/common/poly2tri-private.h | 34 +
.../seamless-clone/poly2tri-c/common/shapes.c | 736 ++++++++++
.../seamless-clone/poly2tri-c/common/shapes.h | 262 ++++
.../seamless-clone/poly2tri-c/common/utils.c | 95 ++
.../seamless-clone/poly2tri-c/common/utils.h | 63 +
operations/common/seamless-clone/poly2tri-c/main.c | 250 ++++
.../common/seamless-clone/poly2tri-c/poly2tri.h | 39 +
.../seamless-clone/poly2tri-c/refine/refine.c | 703 ++++++++++
.../seamless-clone/poly2tri-c/refine/refine.h | 29 +
.../poly2tri-c/refine/triangulation.c | 1458 ++++++++++++++++++++
.../poly2tri-c/refine/triangulation.h | 330 +++++
.../seamless-clone/poly2tri-c/refine/utils.h | 71 +
.../seamless-clone/poly2tri-c/render/mesh-render.c | 290 ++++
.../seamless-clone/poly2tri-c/render/mesh-render.h | 47 +
.../seamless-clone/poly2tri-c/render/svg-plot.c | 330 +++++
.../seamless-clone/poly2tri-c/render/svg-plot.h | 98 ++
.../poly2tri-c/sweep/advancing_front.c | 224 +++
.../poly2tri-c/sweep/advancing_front.h | 88 ++
.../common/seamless-clone/poly2tri-c/sweep/cdt.c | 90 ++
.../common/seamless-clone/poly2tri-c/sweep/cdt.h | 101 ++
.../common/seamless-clone/poly2tri-c/sweep/sweep.c | 932 +++++++++++++
.../common/seamless-clone/poly2tri-c/sweep/sweep.h | 270 ++++
.../poly2tri-c/sweep/sweep_context.c | 313 +++++
.../poly2tri-c/sweep/sweep_context.h | 133 ++
operations/common/seamless-clone/seamless-clone.c | 330 +++++
operations/common/seamless-clone/seamless-clone.h | 34 +
32 files changed, 7929 insertions(+), 0 deletions(-)
---
diff --git a/operations/common/seamless-clone/Makefile.am b/operations/common/seamless-clone/Makefile.am
new file mode 100644
index 0000000..6abd459
--- /dev/null
+++ b/operations/common/seamless-clone/Makefile.am
@@ -0,0 +1,9 @@
+SUBDIRS = poly2tri-c
+
+EXTRA_DIST = \
+ find-outline.c \
+ find-outline.h \
+ make-mesh.c \
+ make-mesh.h \
+ seamless-clone.c \
+ seamless-clone.h
diff --git a/operations/common/seamless-clone/find-outline.c b/operations/common/seamless-clone/find-outline.c
new file mode 100644
index 0000000..280ebbe
--- /dev/null
+++ b/operations/common/seamless-clone/find-outline.c
@@ -0,0 +1,220 @@
+/* This file is an image processing operation for GEGL
+ *
+ * find-outline.c
+ * Copyright (C) 2011 Barak Itkin <lightningismyname gmail com>
+ *
+ * This program 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 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program 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 this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/* This file is part 1 of 3 in the seamless clone operation. The logic
+ * in this file allows to find the outline of a given image. A pixel is
+ * considered an outline pixel, if it's alpha is larger than 0.5 and one
+ * of it's neighbors has alpha lower than that.
+ *
+ * Currently, the logic in this file allows for finding one outline with
+ * no holes, and it currently assumse that only one "island" of high
+ * alpha exists
+ */
+
+#include <cairo.h>
+#include <gegl.h>
+#include <stdio.h> /* TODO: get rid of this debugging way! */
+
+#include "seamless-clone.h"
+#include "poly2tri-c/poly2tri.h"
+#include "poly2tri-c/refine/triangulation.h"
+
+/* Define the directions
+ *
+ * 0
+ *
+ * 7 N 1
+ * ^
+ * |
+ * |
+ * 6 W<----+---->E 2
+ * | =====>X
+ * | ||
+ * v ||
+ * 5 S 3 ||
+ * vv
+ * 4 Y
+ */
+typedef enum {
+ D_N = 0, /* 000 */
+ D_NE = 1, /* 001 */
+ D_E = 2, /* 010 */
+ D_SE = 3, /* 011 */
+ D_S = 4, /* 100 */
+ D_SW = 5, /* 101 */
+ D_W = 6, /* 110 */
+ D_NW = 7 /* 111 */
+} OUTLINE_DIRECTION;
+
+#define cwdirection(t) (((t)+1)%8)
+#define ccwdirection(t) (((t)+7)%8)
+#define oppositedirection(t) (((t)+4)%8)
+
+#define isSouth(s) (((s) == D_S) || ((s) == D_SE) || ((s) == D_SW))
+#define isNorth(s) (((s) == D_N) || ((s) == D_NE) || ((s) == D_NW))
+
+#define isEast(s) (((s) == D_NE) || ((s) == D_E) || ((s) == D_SE))
+#define isWest(s) (((s) == D_NW) || ((s) == D_W) || ((s) == D_SW))
+
+/**
+ * Add a COPY of the given point into the array pts. The original point CAN
+ * be freed later!
+ */
+static void
+add_point (GPtrArray* pts, ScPoint *pt)
+{
+ ScPoint *cpy = g_slice_new (ScPoint);
+ cpy->x = pt->x;
+ cpy->y = pt->y;
+
+ g_ptr_array_add (pts, cpy);
+}
+
+static void
+spoint_move (ScPoint *pt, OUTLINE_DIRECTION t, ScPoint *dest)
+{
+ dest->x = pt->x + (isEast(t) ? 1 : (isWest(t) ? -1 : 0));
+ dest->y = pt->y + (isSouth(t) ? 1 : (isNorth(t) ? -1 : 0));
+}
+
+static gboolean
+in_range(gint val,gint min,gint max)
+{
+ return (((min) <= (val)) && ((val) <= (max)));
+}
+
+#define buf_offset(rect,x0,y0) (((y0) - (rect)->y) * (rect)->width + (x0))
+#define buf_offset_PT(rect,pt) buf_offset((rect),(pt)->x,(pt)->y)
+
+static gboolean
+is_opaque (GeglRectangle *rect,
+ gfloat *pixels,
+ ScPoint *pt)
+{
+ g_assert (pt != NULL);
+ g_assert (rect != NULL);
+
+ return in_range(pt->x, rect->x, rect->x + rect->width - 1)
+ && in_range(pt->y, rect->y, rect->y + rect->height - 1)
+ && (pixels[buf_offset_PT(rect,pt)*4+3] >= 0.5f);
+}
+
+/* This function receives a white pixel (pt) and the direction of the movement
+ * that lead to it (prevdirection). It will return the direction leading to the
+ * next white pixel (while following the edges in CW order), and the pixel
+ * itself would be stored in dest.
+ *
+ * The logic is simple:
+ * 1. Try to continue in the same direction that lead us to the current pixel
+ * 2. Dprev = oppposite(prevdirection)
+ * 3. Dnow = cw(Dprev)
+ * 4. While moving to Dnow is white:
+ * 4.1. Dprev = Dnow
+ * 4.2. Dnow = cw(D)
+ * 5. Return the result - moving by Dprev
+ */
+static inline OUTLINE_DIRECTION
+outline_walk_cw (GeglRectangle *rect,
+ gfloat *pixels,
+ OUTLINE_DIRECTION prevdirection,
+ ScPoint *pt,
+ ScPoint *dest)
+{
+ OUTLINE_DIRECTION Dprev = oppositedirection(prevdirection);
+ OUTLINE_DIRECTION Dnow = cwdirection (Dprev);
+
+ ScPoint ptN, ptP;
+
+ spoint_move (pt, Dprev, &ptP);
+ spoint_move (pt, Dnow, &ptN);
+
+ while (is_opaque (rect, pixels, &ptN))
+ {
+ Dprev = Dnow;
+ ptP.x = ptN.x;
+ ptP.y = ptN.y;
+ Dnow = cwdirection (Dprev);
+ spoint_move (pt, Dnow, &ptN);
+ }
+
+ dest->x = ptP.x;
+ dest->y = ptP.y;
+ return Dprev;
+}
+
+#define pteq(pt1,pt2) (((pt1)->x == (pt2)->x) && ((pt1)->y == (pt2)->y))
+
+GPtrArray*
+outline_find_ccw (GeglRectangle *rect,
+ gfloat *pixels)
+{
+ GPtrArray *points = g_ptr_array_new ();
+
+ gint x = rect->x, y;
+
+ gboolean found = FALSE;
+ ScPoint START, pt, ptN;
+ OUTLINE_DIRECTION DIR, DIRN;
+
+ /* First of all try to find a white pixel */
+ for (y = rect->y; y < rect->y + rect->height; y++)
+ {
+ for (x = rect->x; x < rect->x + rect->width; x++)
+ {
+ if (pixels[buf_offset(rect,x,y)*4+3] >= 0.5f)
+ {
+ found = TRUE;
+ break;
+ }
+ }
+ if (found) break;
+ }
+
+ if (!found)
+ return points;
+
+ pt.x = START.x = x;
+ pt.y = START.y = y;
+ DIR = D_NW;
+
+ add_point (points, &START);
+
+ DIRN = outline_walk_cw (rect, pixels, DIR,&pt,&ptN);
+
+ while (! pteq(&ptN,&START))
+ {
+ add_point (points, &ptN);
+ pt.x = ptN.x;
+ pt.y = ptN.y;
+ DIR = DIRN;
+ DIRN = outline_walk_cw (rect, pixels, DIR,&pt,&ptN);
+ }
+
+ return points;
+}
+
+void
+sc_outline_free (ScOutline *self)
+{
+ GPtrArray *real = (GPtrArray*) self;
+ gint i;
+ for (i = 0; i < real->len; i++)
+ g_slice_free (ScPoint, g_ptr_array_index (self, i));
+ g_ptr_array_free (real, TRUE);
+}
diff --git a/operations/common/seamless-clone/find-outline.h b/operations/common/seamless-clone/find-outline.h
new file mode 100644
index 0000000..2fd7155
--- /dev/null
+++ b/operations/common/seamless-clone/find-outline.h
@@ -0,0 +1,40 @@
+/* This file is an image processing operation for GEGL
+ *
+ * find-outline.h
+ * Copyright (C) 2011 Barak Itkin <lightningismyname gmail com>
+ *
+ * This program 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 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program 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 this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef __SEAMLESS_CLONE_FIND_OUTLINE_H__
+#define __SEAMLESS_CLONE_FIND_OUTLINE_H__
+
+#include <gegl.h>
+
+typedef struct {
+ gint x, y;
+} ScPoint;
+
+/* Define a type for the outline to distinguish it from all the other
+ * pointer arrays in the code of the seamless cloning. Also allow later
+ * to pass it transparently to other places and free it, without
+ * depending on the actual representation of this type.
+ */
+typedef GPtrArray ScOutline;
+
+ScOutline* outline_find_ccw (GeglRectangle *rect, gfloat *pixels);
+
+void sc_outline_free (ScOutline *self);
+
+#endif
diff --git a/operations/common/seamless-clone/make-mesh.c b/operations/common/seamless-clone/make-mesh.c
new file mode 100644
index 0000000..12b559f
--- /dev/null
+++ b/operations/common/seamless-clone/make-mesh.c
@@ -0,0 +1,228 @@
+/* This file is an image processing operation for GEGL
+ *
+ * seamless-clone.c
+ * Copyright (C) 2011 Barak Itkin <lightningismyname gmail com>
+ *
+ * This program 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 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program 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 this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/* This file is part 2 of 3 in the seamless clone operation. The logic in this
+ * file takes an outline as returned from find-outline.c, and makes a fine mesh
+ * out of it. After generating the mesh, the list of sample points for each
+ * inner point of the mesh will be defined.
+ */
+
+#include <cairo.h>
+#include <gegl.h>
+#include <stdio.h> /* TODO: get rid of this debugging way! */
+
+#include "seamless-clone.h"
+#include "poly2tri-c/poly2tri.h"
+#include "poly2tri-c/refine/triangulation.h"
+
+#define g_ptr_array_index_cyclic(array,index_) g_ptr_array_index(array,(index_)%((array)->len))
+
+#define basePointCount 16
+
+/* This won't add the point in the second index, to allow avoiding
+ * insertion of a points twice from two adjacent segments. The caller
+ * must do that
+ */
+static void
+sc_compute_sample_list_part (ScOutline *outline,
+ gint index1,
+ gint index2,
+ gdouble Px,
+ gdouble Py,
+ ScSampleList *sl,
+ gint k)
+{
+ GPtrArray *real = (GPtrArray*) outline;
+
+ ScPoint *pt1 = g_ptr_array_index_cyclic (real, index1);
+ ScPoint *pt2 = g_ptr_array_index_cyclic (real, index2);
+
+ /* Compute the angle pt1-x-pt2 */
+ gdouble dx1 = Px - pt1->x, dy1 = Py - pt1->y;
+ gdouble dx2 = Px - pt2->x, dy2 = Py - pt2->y;
+ gdouble norm1 = sqrt (dx1 * dx1 + dy1 * dy1);
+ gdouble norm2 = sqrt (dx2 * dx2 + dy2 * dy2);
+ gdouble angle = acos ((dx1 * dx2 + dy1 * dy2) / (norm1 * norm2));
+
+ gdouble div = real->len / (gdouble) basePointCount;
+ gint d = index2 - index1;
+
+ gdouble edist = real->len / (basePointCount * pow (2.5, k));
+ gdouble eang = 0.75 * pow (0.8, k);
+ gboolean needsMore = !(norm1 > edist && norm2 > edist && angle < eang);
+
+ /* Check if inserting more would help, and if there are actually
+ * points in the middle. */
+
+ if (!needsMore || d >= 1)
+ {
+ g_ptr_array_add (sl->points, pt1);
+ return;
+ }
+ else
+ {
+ gint index12 = (index1 + index2) / 2;
+ sc_compute_sample_list_part (outline, index1, index12, Px, Py, sl, k + 1);
+ sc_compute_sample_list_part (outline, index12, index2, Px, Py, sl, k + 1);
+ return;
+ }
+}
+
+static void
+sc_compute_sample_list_weights (gdouble Px,
+ gdouble Py,
+ ScSampleList *sl)
+{
+ gint N = sl->points->len;
+ gdouble *tan_as_half = g_new (gdouble, N);
+ gdouble *norms = g_new (gdouble, N);
+ gdouble *weights = g_new (gdouble, N);
+
+ gint i;
+
+ gdouble weightTotal = 0, weightTemp;
+ gint special = -1;
+
+ for (i = 0; i < N; i++)
+ {
+ ScPoint *pt1 = g_ptr_array_index_cyclic (sl->points, i);
+ ScPoint *pt2 = g_ptr_array_index_cyclic (sl->points, i + 1);
+
+ gdouble dx1 = Px - pt1->x, dy1 = Py - pt1->y;
+ gdouble dx2 = Px - pt2->x, dy2 = Py - pt2->y;
+ gdouble norm1 = sqrt (dx1 * dx1 + dy1 * dy1);
+ gdouble norm2 = sqrt (dx2 * dx2 + dy2 * dy2);
+ gdouble ang, temp;
+
+ norms[i] = norm1;
+
+ /* Did the point match one of the outline points? */
+ if (norm1 == 0)
+ {
+ gdouble temp = 1;
+ g_ptr_array_remove_range (sl->points, 0 N);
+ g_array_remove_range (sl->weights, 0 N);
+
+ g_ptr_array_add (sl->points, pt1);
+ g_array_append_val (sl->weights, temp);
+ return;
+ }
+
+ temp = (dx1 * dx2 + dy1 * dy2) / (norm1 * norm2);
+
+ if (temp > 1)
+ {
+ /* Result is in the range of 0 to PI */
+ ang = acos (temp);
+ }
+ else
+ {
+ ang = 0;
+ }
+
+ tan_as_half[i] = tan (ang / 2);
+ tan_as_half[i] = ABS (tan_as_half[i]);
+ }
+
+ weightTemp = (tan_as_half[0] + tan_as_half[N-1]) / pow (norms[0], 2);
+ g_array_append_val (sl->weights, weightTemp);
+
+ for (i = 1; i < N; i++)
+ {
+ weightTemp = (tan_as_half[i - 1] + tan_as_half[i % N]) / pow (norms[i % N], 2);
+ g_array_append_val (sl->weights, weightTemp);
+ }
+}
+
+static ScSampleList*
+sc_compute_sample_list (ScOutline *outline,
+ gdouble Px,
+ gdouble Py)
+{
+ ScSampleList *sl = g_slice_new (ScSampleList);
+ GPtrArray *real = (GPtrArray*) outline;
+ gdouble div = real->len / ((gdouble) basePointCount);
+ gint i, index1, index2;
+
+ sl->points = g_ptr_array_new ();
+ sl->weight = g_array_new (FALSE, TRUE, sizeof (gdouble));
+
+ for (i = 0; i < basePointCount; i++)
+ {
+ k = 0;
+ index1 = (gint) (i * div);
+ index2 = (gint) ((i + 1) * div);
+
+ sc_compute_sample_list_part (outline, index1, index2, Px, Py, sl, k);
+ }
+
+ sc_compute_sample_list_weights (Px, Py, sl);
+
+ return sl;
+}
+
+/**
+ * sc_make_fine_mesh:
+ * @outline: An ScOutline object describing the PSLG of the mesh
+ * @mesh_bounds: A rectangle in which the bounds of the mesh should be
+ * stored
+ */
+static P2tRTriangulation*
+sc_make_fine_mesh (ScOutline *outline,
+ GeglRectangle *mesh_bounds)
+{
+ GPtrArray *realOutline = (GPtrArray*) outline;
+ gint i, N = ptList->len;
+ gint min_x = G_MAXINT, max_x = -G_MAXINT, min_y = G_MAXINT, max_y = -G_MAXINT;
+
+ /* An array of P2tRPoint*, holding the outline points */
+ GPtrArray *mesh_points = g_ptr_array_new ();
+
+ P2tRTriangulation *T;
+
+ for (i = 0; i < N; i++)
+ {
+ SPoint *pt = (SPoint*) g_ptr_array_index (realOutline, i);
+
+ min_x = MIN (pt->x, min_x);
+ min_y = MIN (pt->y, min_y);
+ max_x = MAX (pt->x, max_x);
+ max_y = MAX (pt->y, max_y);
+
+ /* No one should care if the points are given in reverse order,
+ * and prepending to the GList is more efficient */
+ mesh_points = g_ptr_array_add (mesh_points, p2tr_point_new (pt->x, pt->y));
+ }
+
+ mesh_bounds->x = min_x;
+ mesh_bounds->y = min_y;
+ mesh_bounds->width = max_x + 1 - min_x;
+ mesh_bounds->height = max_y + 1 - min_y;
+
+ T = p2tr_triangulate_and_refine (mesh_points);
+
+ for (i = 0; i < N; i++)
+ {
+ p2tr_point_unref (g_ptr_array_index (mesh_points, i));
+ }
+
+ g_ptr_array_free (mesh_points);
+
+ return T;
+}
diff --git a/operations/common/seamless-clone/make-mesh.h b/operations/common/seamless-clone/make-mesh.h
new file mode 100644
index 0000000..43af30b
--- /dev/null
+++ b/operations/common/seamless-clone/make-mesh.h
@@ -0,0 +1,43 @@
+/* This file is an image processing operation for GEGL
+ *
+ * make-mesh.h
+ * Copyright (C) 2011 Barak Itkin <lightningismyname gmail com>
+ *
+ * This program 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 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program 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 this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef __SEAMLESS_CLONE_MAKE_MESH_H__
+#define __SEAMLESS_CLONE_MAKE_MESH_H__
+
+typedef struct {
+ GPtrArray *points; /* An array of ScPoint* objects */
+ GArray *weights; /* An array of gdouble values */
+ gdouble total_weight;
+} ScSampleList;
+
+void sc_free_sample_list (ScSampleList *self);
+
+void
+ComputeSampling (P2tRTriangulation *T,
+ P2tRHashSet **edgePts,
+ GHashTable **sampling);
+
+void
+ComputeInnerSample (P2tRPoint *X,
+ gpointer *sampleData, /* the value of the key X in sampling */
+ GeglBuffer *input,
+ GeglBuffer *aux,
+ gfloat dest[3]);
+
+#endif
diff --git a/operations/common/seamless-clone/poly2tri-c/common/cutils.h b/operations/common/seamless-clone/poly2tri-c/common/cutils.h
new file mode 100755
index 0000000..1fcb2cd
--- /dev/null
+++ b/operations/common/seamless-clone/poly2tri-c/common/cutils.h
@@ -0,0 +1,39 @@
+/*
+ * File: cutils.h
+ * Author: user
+ *
+ * Created on 28 ××× 2011, 02:24
+ */
+
+#ifndef CUTILS_H
+#define CUTILS_H
+
+#include <glib.h>
+#include "poly2tri-private.h"
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif
+
+#define DEBUG FALSE
+
+ typedef GPtrArray* P2tEdgePtrArray;
+#define edge_index(array,index_) ((P2tEdge*)g_ptr_array_index(array,index_))
+ typedef GPtrArray* P2tPointPtrArray;
+#define point_index(array,index_) ((P2tPoint*)g_ptr_array_index(array,index_))
+ typedef GPtrArray* P2tTrianglePtrArray;
+#define triangle_index(array,index_) ((P2tTriangle*)g_ptr_array_index(array,index_))
+ typedef GPtrArray* P2tNodePtrArray;
+#define node_index(array,index_) ((P2tNode*)g_ptr_array_index(array,index_))
+ typedef GList* P2tTrianglePtrList;
+#define triangle_val(list) ((P2tTriangle*)((list)->data))
+
+#define g_ptr_array_index_cyclic(array,index_) g_ptr_array_index(array,(index_)%((array)->len))
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* CUTILS_H */
+
diff --git a/operations/common/seamless-clone/poly2tri-c/common/poly2tri-private.h b/operations/common/seamless-clone/poly2tri-c/common/poly2tri-private.h
new file mode 100755
index 0000000..abdb29b
--- /dev/null
+++ b/operations/common/seamless-clone/poly2tri-c/common/poly2tri-private.h
@@ -0,0 +1,34 @@
+/*
+ * File: poly2tri-private.h
+ * Author: user
+ *
+ * Created on 4 ×××× 2011, 13:22
+ */
+
+#ifndef POLY2TRI_PRIVATE_H
+#define POLY2TRI_PRIVATE_H
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif
+
+typedef struct _P2tNode P2tNode;
+typedef struct AdvancingFront_ P2tAdvancingFront;
+typedef struct CDT_ P2tCDT;
+typedef struct _P2tEdge P2tEdge;
+typedef struct _P2tPoint P2tPoint;
+typedef struct _P2tTriangle P2tTriangle;
+typedef struct SweepContext_ P2tSweepContext;
+typedef struct Sweep_ P2tSweep;
+
+typedef struct P2tSweepContextBasin_ P2tSweepContextBasin;
+typedef struct P2tSweepContextEdgeEvent_ P2tSweepContextEdgeEvent;
+
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* POLY2TRI_PRIVATE_H */
+
diff --git a/operations/common/seamless-clone/poly2tri-c/common/shapes.c b/operations/common/seamless-clone/poly2tri-c/common/shapes.c
new file mode 100755
index 0000000..f211148
--- /dev/null
+++ b/operations/common/seamless-clone/poly2tri-c/common/shapes.c
@@ -0,0 +1,736 @@
+/*
+ * This file is a part of Poly2Tri-C - The C port of the Poly2Tri library
+ * Porting to C done by (c) Barak Itkin <lightningismyname gmail com>
+ * http://code.google.com/p/poly2tri-c/
+ *
+ * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
+ * http://code.google.com/p/poly2tri/
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without modification,
+ * are permitted provided that the following conditions are met:
+ *
+ * * Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright notice,
+ * this list of conditions and the following disclaimer in the documentation
+ * and/or other materials provided with the distribution.
+ * * Neither the name of Poly2Tri nor the names of its contributors may be
+ * used to endorse or promote products derived from this software without specific
+ * prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+#include "shapes.h"
+#include <stdio.h>
+#include <stdlib.h>
+
+/// Default constructor does nothing (for performance).
+
+void
+p2t_point_init (P2tPoint* THIS)
+{
+ THIS->x = 0;
+ THIS->y = 0;
+ THIS->edge_list = g_ptr_array_new ();
+}
+
+P2tPoint*
+p2t_point_new ()
+{
+ P2tPoint* THIS = g_slice_new (P2tPoint);
+ p2t_point_init (THIS);
+ return THIS;
+}
+
+/// Construct using coordinates.
+
+void
+p2t_point_init_dd (P2tPoint* THIS, double x, double y)
+{
+ THIS->x = x;
+ THIS->y = y;
+ THIS->edge_list = g_ptr_array_new ();
+}
+
+P2tPoint*
+p2t_point_new_dd (double x, double y)
+{
+ P2tPoint* THIS = g_slice_new (P2tPoint);
+ p2t_point_init_dd (THIS, x, y);
+ return THIS;
+}
+
+void
+p2t_point_destroy (P2tPoint* THIS)
+{
+ g_ptr_array_free (THIS->edge_list, TRUE);
+}
+
+void
+p2t_point_free (P2tPoint* THIS)
+{
+ p2t_point_destroy (THIS);
+ g_slice_free (P2tPoint, THIS);
+}
+
+/// Constructor
+
+void
+p2t_edge_init (P2tEdge* THIS, P2tPoint* p1, P2tPoint* p2)
+{
+ THIS->p = p1;
+ THIS->q = p2;
+ if (p1->y > p2->y)
+ {
+ THIS->q = p1;
+ THIS->p = p2;
+ }
+ else if (p1->y == p2->y)
+ {
+ if (p1->x > p2->x)
+ {
+ THIS->q = p1;
+ THIS->p = p2;
+ }
+ else if (p1->x == p2->x)
+ {
+ // Repeat points
+ assert (FALSE);
+ }
+ }
+
+ g_ptr_array_add (THIS->q->edge_list, THIS);
+}
+
+P2tEdge*
+p2t_edge_new (P2tPoint* p1, P2tPoint* p2)
+{
+ P2tEdge* THIS = g_slice_new (P2tEdge);
+ p2t_edge_init (THIS, p1, p2);
+ return THIS;
+}
+
+void
+p2t_edge_destroy (P2tEdge* THIS) { }
+
+void
+p2t_edge_free (P2tEdge* THIS)
+{
+ p2t_edge_destroy (THIS);
+ g_slice_free (P2tEdge, THIS);
+}
+
+P2tTriangle*
+p2t_triangle_new (P2tPoint* a, P2tPoint* b, P2tPoint* c)
+{
+ P2tTriangle *tr = g_new (P2tTriangle, 1);
+ p2t_triangle_init (tr, a, b, c);
+ return tr;
+}
+
+void
+p2t_triangle_init (P2tTriangle* THIS, P2tPoint* a, P2tPoint* b, P2tPoint* c)
+{
+ THIS->points_[0] = a;
+ THIS->points_[1] = b;
+ THIS->points_[2] = c;
+ THIS->neighbors_[0] = NULL;
+ THIS->neighbors_[1] = NULL;
+ THIS->neighbors_[2] = NULL;
+ THIS->constrained_edge[0] = THIS->constrained_edge[1] = THIS->constrained_edge[2] = FALSE;
+ THIS->delaunay_edge[0] = THIS->delaunay_edge[1] = THIS->delaunay_edge[2] = FALSE;
+ THIS->interior_ = FALSE;
+
+}
+// Update neighbor pointers
+
+void
+p2t_triangle_mark_neighbor_pt_pt_tr (P2tTriangle* THIS, P2tPoint* p1, P2tPoint* p2, P2tTriangle* t)
+{
+ if ((p1 == THIS->points_[2] && p2 == THIS->points_[1]) || (p1 == THIS->points_[1] && p2 == THIS->points_[2]))
+ THIS->neighbors_[0] = t;
+ else if ((p1 == THIS->points_[0] && p2 == THIS->points_[2]) || (p1 == THIS->points_[2] && p2 == THIS->points_[0]))
+ THIS->neighbors_[1] = t;
+ else if ((p1 == THIS->points_[0] && p2 == THIS->points_[1]) || (p1 == THIS->points_[1] && p2 == THIS->points_[0]))
+ THIS->neighbors_[2] = t;
+ else
+ assert (0);
+}
+
+// Exhaustive search to update neighbor pointers
+
+void
+p2t_triangle_mark_neighbor_tr (P2tTriangle* THIS, P2tTriangle *t)
+{
+ if (p2t_triangle_contains_pt_pt (t, THIS->points_[1], THIS->points_[2]))
+ {
+ THIS->neighbors_[0] = t;
+ p2t_triangle_mark_neighbor_pt_pt_tr (t, THIS->points_[1], THIS->points_[2], THIS);
+ }
+ else if (p2t_triangle_contains_pt_pt (t, THIS->points_[0], THIS->points_[2]))
+ {
+ THIS->neighbors_[1] = t;
+ p2t_triangle_mark_neighbor_pt_pt_tr (t, THIS->points_[0], THIS->points_[2], THIS);
+ }
+ else if (p2t_triangle_contains_pt_pt (t, THIS->points_[0], THIS->points_[1]))
+ {
+ THIS->neighbors_[2] = t;
+ p2t_triangle_mark_neighbor_pt_pt_tr (t, THIS->points_[0], THIS->points_[1], THIS);
+ }
+}
+
+/**
+ * Clears all references to all other triangles and points
+ */
+void
+p2t_triangle_clear (P2tTriangle* THIS)
+{
+ int i;
+ P2tTriangle *t;
+ for (i = 0; i < 3; i++)
+ {
+ t = THIS->neighbors_[i];
+ if (t != NULL)
+ {
+ p2t_triangle_clear_neighbor_tr (t, THIS);
+ }
+ }
+ p2t_triangle_clear_neighbors (THIS);
+ THIS->points_[0] = THIS->points_[1] = THIS->points_[2] = NULL;
+}
+
+void
+p2t_triangle_clear_neighbor_tr (P2tTriangle* THIS, P2tTriangle *triangle)
+{
+ if (THIS->neighbors_[0] == triangle)
+ {
+ THIS->neighbors_[0] = NULL;
+ }
+ else if (THIS->neighbors_[1] == triangle)
+ {
+ THIS->neighbors_[1] = NULL;
+ }
+ else
+ {
+ THIS->neighbors_[2] = NULL;
+ }
+}
+
+void
+p2t_triangle_clear_neighbors (P2tTriangle* THIS)
+{
+ THIS->neighbors_[0] = NULL;
+ THIS->neighbors_[1] = NULL;
+ THIS->neighbors_[2] = NULL;
+}
+
+void
+p2t_triangle_clear_delunay_edges (P2tTriangle* THIS)
+{
+ THIS->delaunay_edge[0] = THIS->delaunay_edge[1] = THIS->delaunay_edge[2] = FALSE;
+}
+
+P2tPoint*
+p2t_triangle_opposite_point (P2tTriangle* THIS, P2tTriangle* t, P2tPoint* p)
+{
+ P2tPoint *cw = p2t_triangle_point_cw (t, p);
+ double x = cw->x;
+ double y = cw->y;
+ x = p->x;
+ y = p->y;
+ P2tPoint* ham = p2t_triangle_point_cw (THIS, cw);
+ return p2t_triangle_point_cw (THIS, cw);
+}
+
+// Legalized triangle by rotating clockwise around point(0)
+
+void
+p2t_triangle_legalize_pt (P2tTriangle* THIS, P2tPoint *point)
+{
+ THIS->points_[1] = THIS->points_[0];
+ THIS->points_[0] = THIS->points_[2];
+ THIS->points_[2] = point;
+}
+
+// Legalize triagnle by rotating clockwise around oPoint
+
+void
+p2t_triangle_legalize_pt_pt (P2tTriangle* THIS, P2tPoint *opoint, P2tPoint *npoint)
+{
+ if (opoint == THIS->points_[0])
+ {
+ THIS->points_[1] = THIS->points_[0];
+ THIS->points_[0] = THIS->points_[2];
+ THIS->points_[2] = npoint;
+ }
+ else if (opoint == THIS->points_[1])
+ {
+ THIS->points_[2] = THIS->points_[1];
+ THIS->points_[1] = THIS->points_[0];
+ THIS->points_[0] = npoint;
+ }
+ else if (opoint == THIS->points_[2])
+ {
+ THIS->points_[0] = THIS->points_[2];
+ THIS->points_[2] = THIS->points_[1];
+ THIS->points_[1] = npoint;
+ }
+ else
+ {
+ assert (0);
+ }
+}
+
+int
+p2t_triangle_index (P2tTriangle* THIS, const P2tPoint* p)
+{
+ if (p == THIS->points_[0])
+ {
+ return 0;
+ }
+ else if (p == THIS->points_[1])
+ {
+ return 1;
+ }
+ else if (p == THIS->points_[2])
+ {
+ return 2;
+ }
+ assert (0);
+}
+
+int
+p2t_triangle_edge_index (P2tTriangle* THIS, const P2tPoint* p1, const P2tPoint* p2)
+{
+ if (THIS->points_[0] == p1)
+ {
+ if (THIS->points_[1] == p2)
+ {
+ return 2;
+ }
+ else if (THIS->points_[2] == p2)
+ {
+ return 1;
+ }
+ }
+ else if (THIS->points_[1] == p1)
+ {
+ if (THIS->points_[2] == p2)
+ {
+ return 0;
+ }
+ else if (THIS->points_[0] == p2)
+ {
+ return 2;
+ }
+ }
+ else if (THIS->points_[2] == p1)
+ {
+ if (THIS->points_[0] == p2)
+ {
+ return 1;
+ }
+ else if (THIS->points_[1] == p2)
+ {
+ return 0;
+ }
+ }
+ return -1;
+}
+
+void
+p2t_triangle_mark_constrained_edge_i (P2tTriangle* THIS, const int index)
+{
+ THIS->constrained_edge[index] = TRUE;
+}
+
+void
+p2t_triangle_mark_constrained_edge_ed (P2tTriangle* THIS, P2tEdge* edge)
+{
+ p2t_triangle_mark_constrained_edge_pt_pt (THIS, edge->p, edge->q);
+}
+
+// Mark edge as constrained
+
+void
+p2t_triangle_mark_constrained_edge_pt_pt (P2tTriangle* THIS, P2tPoint* p, P2tPoint* q)
+{
+ if ((q == THIS->points_[0] && p == THIS->points_[1]) || (q == THIS->points_[1] && p == THIS->points_[0]))
+ {
+ THIS->constrained_edge[2] = TRUE;
+ }
+ else if ((q == THIS->points_[0] && p == THIS->points_[2]) || (q == THIS->points_[2] && p == THIS->points_[0]))
+ {
+ THIS->constrained_edge[1] = TRUE;
+ }
+ else if ((q == THIS->points_[1] && p == THIS->points_[2]) || (q == THIS->points_[2] && p == THIS->points_[1]))
+ {
+ THIS->constrained_edge[0] = TRUE;
+ }
+}
+
+// The point counter-clockwise to given point
+
+P2tPoint*
+p2t_triangle_point_cw (P2tTriangle* THIS, P2tPoint* point)
+{
+ if (point == THIS->points_[0])
+ {
+ return THIS->points_[2];
+ }
+ else if (point == THIS->points_[1])
+ {
+ return THIS->points_[0];
+ }
+ else if (point == THIS->points_[2])
+ {
+ return THIS->points_[1];
+ }
+ assert (0);
+}
+
+// The point counter-clockwise to given point
+
+P2tPoint*
+p2t_triangle_point_ccw (P2tTriangle* THIS, P2tPoint* point)
+{
+ if (point == THIS->points_[0])
+ {
+ return THIS->points_[1];
+ }
+ else if (point == THIS->points_[1])
+ {
+ return THIS->points_[2];
+ }
+ else if (point == THIS->points_[2])
+ {
+ return THIS->points_[0];
+ }
+ assert (0);
+}
+
+// The neighbor clockwise to given point
+
+P2tTriangle*
+p2t_triangle_neighbor_cw (P2tTriangle* THIS, P2tPoint* point)
+{
+ if (point == THIS->points_[0])
+ {
+ return THIS->neighbors_[1];
+ }
+ else if (point == THIS->points_[1])
+ {
+ return THIS->neighbors_[2];
+ }
+ return THIS->neighbors_[0];
+}
+
+// The neighbor counter-clockwise to given point
+
+P2tTriangle*
+p2t_triangle_neighbor_ccw (P2tTriangle* THIS, P2tPoint* point)
+{
+ if (point == THIS->points_[0])
+ {
+ return THIS->neighbors_[2];
+ }
+ else if (point == THIS->points_[1])
+ {
+ return THIS->neighbors_[0];
+ }
+ return THIS->neighbors_[1];
+}
+
+gboolean
+p2t_triangle_get_constrained_edge_ccw (P2tTriangle* THIS, P2tPoint* p)
+{
+ if (p == THIS->points_[0])
+ {
+ return THIS->constrained_edge[2];
+ }
+ else if (p == THIS->points_[1])
+ {
+ return THIS->constrained_edge[0];
+ }
+ return THIS->constrained_edge[1];
+}
+
+gboolean
+p2t_triangle_get_constrained_edge_cw (P2tTriangle* THIS, P2tPoint* p)
+{
+ if (p == THIS->points_[0])
+ {
+ return THIS->constrained_edge[1];
+ }
+ else if (p == THIS->points_[1])
+ {
+ return THIS->constrained_edge[2];
+ }
+ return THIS->constrained_edge[0];
+}
+
+void
+p2t_triangle_set_constrained_edge_ccw (P2tTriangle* THIS, P2tPoint* p, gboolean ce)
+{
+ if (p == THIS->points_[0])
+ {
+ THIS->constrained_edge[2] = ce;
+ }
+ else if (p == THIS->points_[1])
+ {
+ THIS->constrained_edge[0] = ce;
+ }
+ else
+ {
+ THIS->constrained_edge[1] = ce;
+ }
+}
+
+void
+p2t_triangle_set_constrained_edge_cw (P2tTriangle* THIS, P2tPoint* p, gboolean ce)
+{
+ if (p == THIS->points_[0])
+ {
+ THIS->constrained_edge[1] = ce;
+ }
+ else if (p == THIS->points_[1])
+ {
+ THIS->constrained_edge[2] = ce;
+ }
+ else
+ {
+ THIS->constrained_edge[0] = ce;
+ }
+}
+
+gboolean
+p2t_triangle_get_delunay_edge_ccw (P2tTriangle* THIS, P2tPoint* p)
+{
+ if (p == THIS->points_[0])
+ {
+ return THIS->delaunay_edge[2];
+ }
+ else if (p == THIS->points_[1])
+ {
+ return THIS->delaunay_edge[0];
+ }
+ return THIS->delaunay_edge[1];
+}
+
+gboolean
+p2t_triangle_get_delunay_edge_cw (P2tTriangle* THIS, P2tPoint* p)
+{
+ if (p == THIS->points_[0])
+ {
+ return THIS->delaunay_edge[1];
+ }
+ else if (p == THIS->points_[1])
+ {
+ return THIS->delaunay_edge[2];
+ }
+ return THIS->delaunay_edge[0];
+}
+
+void
+p2t_triangle_set_delunay_edge_ccw (P2tTriangle* THIS, P2tPoint* p, gboolean e)
+{
+ if (p == THIS->points_[0])
+ {
+ THIS->delaunay_edge[2] = e;
+ }
+ else if (p == THIS->points_[1])
+ {
+ THIS->delaunay_edge[0] = e;
+ }
+ else
+ {
+ THIS->delaunay_edge[1] = e;
+ }
+}
+
+void
+p2t_triangle_set_delunay_edge_cw (P2tTriangle* THIS, P2tPoint* p, gboolean e)
+{
+ if (p == THIS->points_[0])
+ {
+ THIS->delaunay_edge[1] = e;
+ }
+ else if (p == THIS->points_[1])
+ {
+ THIS->delaunay_edge[2] = e;
+ }
+ else
+ {
+ THIS->delaunay_edge[0] = e;
+ }
+}
+
+// The neighbor across to given point
+
+P2tTriangle*
+p2t_triangle_neighbor_across (P2tTriangle* THIS, P2tPoint* opoint)
+{
+ if (opoint == THIS->points_[0])
+ {
+ return THIS->neighbors_[0];
+ }
+ else if (opoint == THIS->points_[1])
+ {
+ return THIS->neighbors_[1];
+ }
+ return THIS->neighbors_[2];
+}
+
+void
+p2t_triangle_debug_print (P2tTriangle* THIS)
+{
+ printf ("%f,%f ", THIS->points_[0]->x, THIS->points_[0]->y);
+ printf ("%f,%f ", THIS->points_[1]->x, THIS->points_[1]->y);
+ printf ("%f,%f\n", THIS->points_[2]->x, THIS->points_[2]->y);
+}
+
+// WARNING! the function for sorting a g_ptr_array expects to recieve
+// pointers to the pointers (double indirection)!
+
+gint
+p2t_point_cmp (gconstpointer a, gconstpointer b)
+{
+ P2tPoint *ap = *((P2tPoint**) a), *bp = *((P2tPoint**) b);
+ if (ap->y < bp->y)
+ {
+ return -1;
+ }
+ else if (ap->y == bp->y)
+ {
+ // Make sure q is point with greater x value
+ if (ap->x < bp->x)
+ {
+ return -1;
+ }
+ else if (ap->x == bp->x)
+ return 0;
+ }
+ return 1;
+}
+
+// /// Add two points_ component-wise.
+//
+// Point operator + (const Point& a, const Point& b)
+// {
+// return Point (a.x + b.x, a.y + b.y);
+// }
+//
+// /// Subtract two points_ component-wise.
+//
+// Point operator - (const Point& a, const Point& b)
+// {
+// return Point (a.x - b.x, a.y - b.y);
+// }
+//
+// /// Multiply point by scalar
+//
+// Point operator * (double s, const Point& a)
+// {
+// return Point (s * a.x, s * a.y);
+// }
+
+// gboolean operator == (const Point& a, const Point& b)
+
+gboolean
+p2t_point_equals (const P2tPoint* a, const P2tPoint* b)
+{
+ return a->x == b->x && a->y == b->y;
+}
+//
+// gboolean operator != (const Point& a, const Point& b)
+// {
+// return a.x != b.x && a.y != b.y;
+// }
+
+// /// Peform the dot product on two vectors.
+//
+// double
+// Dot (const Point& a, const Point& b)
+// {
+// return a.x * b.x + a.y * b.y;
+// }
+//
+// /// Perform the cross product on two vectors. In 2D this produces a scalar.
+//
+// double
+// Cross (const Point& a, const Point& b)
+// {
+// return a.x * b.y - a.y * b.x;
+// }
+//
+// /// Perform the cross product on a point and a scalar. In 2D this produces
+// /// a point.
+//
+// Point
+// Cross (const Point& a, double s)
+// {
+// return Point (s * a.y, -s * a.x);
+// }
+//
+// /// Perform the cross product on a scalar and a point. In 2D this produces
+// /// a point.
+//
+// Point
+// Cross (const double s, const Point& a)
+// {
+// return Point (-s * a.y, s * a.x);
+// }
+
+P2tPoint*
+p2t_triangle_get_point (P2tTriangle* THIS, const int index)
+{
+ return THIS->points_[index];
+}
+
+P2tTriangle*
+p2t_triangle_get_neighbor (P2tTriangle* THIS, const int index)
+{
+ return THIS->neighbors_[index];
+}
+
+gboolean
+p2t_triangle_contains_pt (P2tTriangle* THIS, P2tPoint* p)
+{
+ return p == THIS->points_[0] || p == THIS->points_[1] || p == THIS->points_[2];
+}
+
+gboolean
+p2t_triangle_contains_ed (P2tTriangle* THIS, const P2tEdge* e)
+{
+ return p2t_triangle_contains_pt (THIS, e->p) && p2t_triangle_contains_pt (THIS, e->q);
+}
+
+gboolean
+p2t_triangle_contains_pt_pt (P2tTriangle* THIS, P2tPoint* p, P2tPoint* q)
+{
+ return p2t_triangle_contains_pt (THIS, p) && p2t_triangle_contains_pt (THIS, q);
+}
+
+gboolean
+p2t_triangle_is_interior (P2tTriangle* THIS)
+{
+ return THIS->interior_;
+}
+
+void
+p2t_triangle_is_interior_b (P2tTriangle* THIS, gboolean b)
+{
+ THIS->interior_ = b;
+}
diff --git a/operations/common/seamless-clone/poly2tri-c/common/shapes.h b/operations/common/seamless-clone/poly2tri-c/common/shapes.h
new file mode 100755
index 0000000..6287e9a
--- /dev/null
+++ b/operations/common/seamless-clone/poly2tri-c/common/shapes.h
@@ -0,0 +1,262 @@
+/*
+ * This file is a part of Poly2Tri-C - The C port of the Poly2Tri library
+ * Porting to C done by (c) Barak Itkin <lightningismyname gmail com>
+ * http://code.google.com/p/poly2tri-c/
+ *
+ * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
+ * http://code.google.com/p/poly2tri/
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without modification,
+ * are permitted provided that the following conditions are met:
+ *
+ * * Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright notice,
+ * this list of conditions and the following disclaimer in the documentation
+ * and/or other materials provided with the distribution.
+ * * Neither the name of Poly2Tri nor the names of its contributors may be
+ * used to endorse or promote products derived from this software without specific
+ * prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef __SHAPES_H__
+#define __SHAPES_H__
+
+#include <stddef.h>
+#include <assert.h>
+#include <math.h>
+#include "poly2tri-private.h"
+#include "cutils.h"
+
+/**
+ * P2tPoint:
+ * @x: The x coordinate of the point
+ * @y: The y coordinate of the point
+ * @edge_list: The edges this point constitutes an upper ending point
+ *
+ * A struct to represent 2D points with double precision, and to keep track
+ * of the edges this point constitutes an upper ending point
+ */
+struct _P2tPoint
+{
+ /*< public >*/
+ P2tEdgePtrArray edge_list;
+ double x, y;
+};
+
+/**
+ * p2t_point_init_dd:
+ * @THIS: The #P2tPoint to initialize
+ * @x: The desired x coordinate of the point
+ * @y: The desired y coordinate of the point
+ *
+ * A function to initialize a #P2tPoint struct with the given coordinates. The
+ * struct must later be finalized by a call to #p2t_point_destroy
+ */
+void p2t_point_init_dd (P2tPoint* THIS, double x, double y);
+
+/**
+ * p2t_point_new_dd:
+ * @x: The desired x coordinate of the point
+ * @y: The desired y coordinate of the point
+ *
+ * A utility function to alloacte and initialize a #P2tPoint.
+ * See #p2t_point_init_dd. Note that when finished using the point, it must be
+ * freed by a call to #p2t_point_free and can not be freed like regular memory.
+ *
+ * Returns: The allocated and initialized point
+ */
+P2tPoint* p2t_point_new_dd (double x, double y);
+
+/**
+ * p2t_point_init:
+ * @THIS: The #P2tPoint to initialize
+ *
+ * A function to initialize a #P2tPoint struct to (0,0). The struct must later
+ * be finalized by a call to #p2t_point_destroy
+ */
+void p2t_point_init (P2tPoint* THIS);
+
+/**
+ * p2t_point_new:
+ *
+ * A utility function to alloacte and initialize a #P2tPoint.
+ * See #p2t_point_init. Note that when finished using the point, it must be
+ * freed by a call to #p2t_point_free and can not be freed like regular memory.
+ */
+P2tPoint* p2t_point_new ();
+
+/**
+ * p2t_point_destroy:
+ * @THIS: The #P2tPoint whose resources should be freed
+ *
+ * This function will free all the resources allocated by a #P2tPoint, without
+ * freeing the #P2tPoint pointed by @THIS
+ */
+void p2t_point_destroy (P2tPoint* THIS);
+
+/**
+ * p2t_point_free:
+ * @THIS: The #P2tPoint to free
+ *
+ * This function will free all the resources allocated by a #P2tPoint, and will
+ * also free the #P2tPoint pointed by @THIS
+ */
+void p2t_point_free (P2tPoint* THIS);
+
+/**
+ * P2tEdge:
+ * @p: The top right point of the edge
+ * @q: The bottom left point of the edge
+ *
+ * Represents a simple polygon's edge
+ */
+struct _P2tEdge
+{
+ P2tPoint *p, *q;
+};
+
+/**
+ * p2t_edge_init:
+ * @THIS: The #P2tEdge to initialize
+ * @p1: One of the two points that form the edge
+ * @p2: The other point of the two points that form the edge
+ *
+ * A function to initialize a #P2tEdge struct from the given points. The
+ * struct must later be finalized by a call to #p2t_point_destroy.
+ *
+ * Warning: The points must be geometrically not-equal! This means that they
+ * must differ by at least one of their coordinates. Otherwise, a runtime error
+ * would be raised!
+ */
+void p2t_edge_init (P2tEdge* THIS, P2tPoint* p1, P2tPoint* p2);
+
+/**
+ * p2t_edge_new:
+ *
+ * A utility function to alloacte and initialize a #P2tEdge.
+ * See #p2t_edge_init. Note that when finished using the point, it must be freed
+ * by a call to #p2t_point_free and can not be freed like regular memory.
+ *
+ * Returns: The allocated and initialized edge
+ */
+P2tEdge* p2t_edge_new (P2tPoint* p1, P2tPoint* p2);
+
+/**
+ * p2t_edge_destroy:
+ * @THIS: The #P2tEdge whose resources should be freed
+ *
+ * This function will free all the resources allocated by a #P2tEdge, without
+ * freeing the #P2tPoint pointed by @THIS
+ */
+void p2t_edge_destroy (P2tEdge* THIS);
+
+/**
+ * p2t_edge_free:
+ * @THIS: The #P2tEdge to free
+ *
+ * This function will free all the resources allocated by a #P2tEdge, and will
+ * also free the #P2tEdge pointed by @THIS
+ */
+void p2t_edge_free (P2tEdge* THIS);
+
+
+/* Triangle-based data structures are know to have better performance than quad-edge structures
+ * See: J. Shewchuk, "Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator"
+ * "Triangulations in CGAL"
+ */
+
+/**
+ * P2tTriangle:
+ * @constrained_edge: Flags to determine if an edge is a Constrained edge
+ * @delaunay_edg: Flags to determine if an edge is a Delauney edge
+ * @points_: Triangle points
+ * @neighbors_: Neighbor list
+ * @interior_: Has this triangle been marked as an interior triangle?
+ *
+ * A data structure for representing a triangle, while keeping information about
+ * neighbor triangles, etc.
+ */
+struct _P2tTriangle
+{
+ /*< public >*/
+ gboolean constrained_edge[3];
+ gboolean delaunay_edge[3];
+
+ /*< private >*/
+ P2tPoint * points_[3];
+ struct _P2tTriangle * neighbors_[3];
+ gboolean interior_;
+};
+
+P2tTriangle* p2t_triangle_new (P2tPoint* a, P2tPoint* b, P2tPoint* c);
+void p2t_triangle_init (P2tTriangle* THIS, P2tPoint* a, P2tPoint* b, P2tPoint* c);
+P2tPoint* p2t_triangle_get_point (P2tTriangle* THIS, const int index);
+P2tPoint* p2t_triangle_point_cw (P2tTriangle* THIS, P2tPoint* point);
+P2tPoint* p2t_triangle_point_ccw (P2tTriangle* THIS, P2tPoint* point);
+P2tPoint* p2t_triangle_opposite_point (P2tTriangle* THIS, P2tTriangle* t, P2tPoint* p);
+
+P2tTriangle* p2t_triangle_get_neighbor (P2tTriangle* THIS, const int index);
+void p2t_triangle_mark_neighbor_pt_pt_tr (P2tTriangle* THIS, P2tPoint* p1, P2tPoint* p2, P2tTriangle* t);
+void p2t_triangle_mark_neighbor_tr (P2tTriangle* THIS, P2tTriangle *t);
+
+void p2t_triangle_mark_constrained_edge_i (P2tTriangle* THIS, const int index);
+void p2t_triangle_mark_constrained_edge_ed (P2tTriangle* THIS, P2tEdge* edge);
+void p2t_triangle_mark_constrained_edge_pt_pt (P2tTriangle* THIS, P2tPoint* p, P2tPoint* q);
+
+int p2t_triangle_index (P2tTriangle* THIS, const P2tPoint* p);
+int p2t_triangle_edge_index (P2tTriangle* THIS, const P2tPoint* p1, const P2tPoint* p2);
+
+P2tTriangle* p2t_triangle_neighbor_cw (P2tTriangle* THIS, P2tPoint* point);
+P2tTriangle* p2t_triangle_neighbor_ccw (P2tTriangle* THIS, P2tPoint* point);
+gboolean p2t_triangle_get_constrained_edge_ccw (P2tTriangle* THIS, P2tPoint* p);
+gboolean p2t_triangle_get_constrained_edge_cw (P2tTriangle* THIS, P2tPoint* p);
+void p2t_triangle_set_constrained_edge_ccw (P2tTriangle* THIS, P2tPoint* p, gboolean ce);
+void p2t_triangle_set_constrained_edge_cw (P2tTriangle* THIS, P2tPoint* p, gboolean ce);
+gboolean p2t_triangle_get_delunay_edge_ccw (P2tTriangle* THIS, P2tPoint* p);
+gboolean p2t_triangle_get_delunay_edge_cw (P2tTriangle* THIS, P2tPoint* p);
+void p2t_triangle_set_delunay_edge_ccw (P2tTriangle* THIS, P2tPoint* p, gboolean e);
+void p2t_triangle_set_delunay_edge_cw (P2tTriangle* THIS, P2tPoint* p, gboolean e);
+
+gboolean p2t_triangle_contains_pt (P2tTriangle* THIS, P2tPoint* p);
+gboolean p2t_triangle_contains_ed (P2tTriangle* THIS, const P2tEdge* e);
+gboolean p2t_triangle_contains_pt_pt (P2tTriangle* THIS, P2tPoint* p, P2tPoint* q);
+void p2t_triangle_legalize_pt (P2tTriangle* THIS, P2tPoint* point);
+void p2t_triangle_legalize_pt_pt (P2tTriangle* THIS, P2tPoint* opoint, P2tPoint* npoint);
+/**
+ * Clears all references to all other triangles and points
+ */
+void p2t_triangle_clear (P2tTriangle* THIS);
+void p2t_triangle_clear_neighbor_tr (P2tTriangle* THIS, P2tTriangle *triangle);
+void p2t_triangle_clear_neighbors (P2tTriangle* THIS);
+void p2t_triangle_clear_delunay_edges (P2tTriangle* THIS);
+
+gboolean p2t_triangle_is_interior (P2tTriangle* THIS);
+void p2t_triangle_is_interior_b (P2tTriangle* THIS, gboolean b);
+
+P2tTriangle* p2t_triangle_neighbor_across (P2tTriangle* THIS, P2tPoint* opoint);
+
+void p2t_triangle_debug_print (P2tTriangle* THIS);
+
+gint p2t_point_cmp (gconstpointer a, gconstpointer b);
+
+// gboolean operator == (const Point& a, const Point& b);
+gboolean p2t_point_equals (const P2tPoint* a, const P2tPoint* b);
+
+#endif
+
+
diff --git a/operations/common/seamless-clone/poly2tri-c/common/utils.c b/operations/common/seamless-clone/poly2tri-c/common/utils.c
new file mode 100755
index 0000000..24ce71b
--- /dev/null
+++ b/operations/common/seamless-clone/poly2tri-c/common/utils.c
@@ -0,0 +1,95 @@
+
+/*
+ * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
+ * http://code.google.com/p/poly2tri/
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without modification,
+ * are permitted provided that the following conditions are met:
+ *
+ * * Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright notice,
+ * this list of conditions and the following disclaimer in the documentation
+ * and/or other materials provided with the distribution.
+ * * Neither the name of Poly2Tri nor the names of its contributors may be
+ * used to endorse or promote products derived from this software without specific
+ * prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <math.h>
+#include "utils.h"
+
+/**
+ * Forumla to calculate signed area<br>
+ * Positive if CCW<br>
+ * Negative if CW<br>
+ * 0 if collinear<br>
+ * <pre>
+ * A[P1,P2,P3] = (x1*y2 - y1*x2) + (x2*y3 - y2*x3) + (x3*y1 - y3*x1)
+ * = (x1-x3)*(y2-y3) - (y1-y3)*(x2-x3)
+ * </pre>
+ */
+P2tOrientation
+p2t_orient2d (P2tPoint* pa, P2tPoint* pb, P2tPoint* pc)
+{
+ double detleft = (pa->x - pc->x) * (pb->y - pc->y);
+ double detright = (pa->y - pc->y) * (pb->x - pc->x);
+ double val = detleft - detright;
+ if (val > -EPSILON && val < EPSILON)
+ {
+ return COLLINEAR;
+ }
+ else if (val > 0)
+ {
+ return CCW;
+ }
+ return CW;
+}
+
+gboolean
+p2t_utils_in_scan_area (P2tPoint* pa, P2tPoint* pb, P2tPoint* pc, P2tPoint* pd)
+{
+ double pdx = pd->x;
+ double pdy = pd->y;
+ double adx = pa->x - pdx;
+ double ady = pa->y - pdy;
+ double bdx = pb->x - pdx;
+ double bdy = pb->y - pdy;
+
+ double adxbdy = adx * bdy;
+ double bdxady = bdx * ady;
+ double oabd = adxbdy - bdxady;
+
+ if (oabd <= EPSILON)
+ {
+ return FALSE;
+ }
+
+ double cdx = pc->x - pdx;
+ double cdy = pc->y - pdy;
+
+ double cdxady = cdx * ady;
+ double adxcdy = adx * cdy;
+ double ocad = cdxady - adxcdy;
+
+ if (ocad <= EPSILON)
+ {
+ return FALSE;
+ }
+
+ return TRUE;
+}
diff --git a/operations/common/seamless-clone/poly2tri-c/common/utils.h b/operations/common/seamless-clone/poly2tri-c/common/utils.h
new file mode 100755
index 0000000..18d42b9
--- /dev/null
+++ b/operations/common/seamless-clone/poly2tri-c/common/utils.h
@@ -0,0 +1,63 @@
+/*
+ * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
+ * http://code.google.com/p/poly2tri/
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without modification,
+ * are permitted provided that the following conditions are met:
+ *
+ * * Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright notice,
+ * this list of conditions and the following disclaimer in the documentation
+ * and/or other materials provided with the distribution.
+ * * Neither the name of Poly2Tri nor the names of its contributors may be
+ * used to endorse or promote products derived from this software without specific
+ * prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef UTILS_H
+#define UTILS_H
+
+#include <glib.h>
+#include "poly2tri-private.h"
+#include "cutils.h"
+#include "shapes.h"
+
+#define PI_3div4 (3 * M_PI / 4)
+#define EPSILON (1e-6)
+
+typedef enum
+{
+ CW, CCW, COLLINEAR
+} P2tOrientation;
+
+/**
+ * Forumla to calculate signed area<br>
+ * Positive if CCW<br>
+ * Negative if CW<br>
+ * 0 if collinear<br>
+ * <pre>
+ * A[P1,P2,P3] = (x1*y2 - y1*x2) + (x2*y3 - y2*x3) + (x3*y1 - y3*x1)
+ * = (x1-x3)*(y2-y3) - (y1-y3)*(x2-x3)
+ * </pre>
+ */
+P2tOrientation p2t_orient2d (P2tPoint* pa, P2tPoint* pb, P2tPoint* pc);
+
+gboolean p2t_utils_in_scan_area (P2tPoint* pa, P2tPoint* pb, P2tPoint* pc, P2tPoint* pd);
+
+#endif
+
diff --git a/operations/common/seamless-clone/poly2tri-c/main.c b/operations/common/seamless-clone/poly2tri-c/main.c
new file mode 100755
index 0000000..001a276
--- /dev/null
+++ b/operations/common/seamless-clone/poly2tri-c/main.c
@@ -0,0 +1,250 @@
+/*
+ * Poly2Tri Copyright (c) 2009-2011, Poly2Tri Contributors
+ * http://code.google.com/p/poly2tri/
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without modification,
+ * are permitted provided that the following conditions are met:
+ *
+ * * Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright notice,
+ * this list of conditions and the following disclaimer in the documentation
+ * and/or other materials provided with the distribution.
+ * * Neither the name of Poly2Tri nor the names of its contributors may be
+ * used to endorse or promote products derived from this software without specific
+ * prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <glib.h>
+
+#include "poly2tri.h"
+
+#include "refine/triangulation.h"
+#include "render/svg-plot.h"
+#include "refine/refine.h"
+
+#include "render/mesh-render.h"
+
+#include <string.h>
+
+
+static gint refine_max_steps = 1000;
+static gboolean debug_print = TRUE;
+static gboolean verbose = TRUE;
+static gchar *input_file = NULL;
+static gchar *output_file = NULL;
+
+static GOptionEntry entries[] =
+{
+ { "refine-max-steps", 'r', 0, G_OPTION_ARG_INT, &refine_max_steps, "Set maximal refinement steps to N", "N" },
+ { "verbose", 'v', 0, G_OPTION_ARG_NONE, &verbose, "Print output?", NULL },
+ { "debug", 'd', 0, G_OPTION_ARG_NONE, &debug_print, "Enable debug printing", NULL },
+ { "input", 'i', 0, G_OPTION_ARG_FILENAME, &input_file, "Use input file at FILE_IN", "FILE_IN" },
+ { "output", 'o', 0, G_OPTION_ARG_FILENAME, &output_file, "Use output file at FILE_IN", "FILE_OUT" },
+ { NULL }
+};
+
+typedef gfloat Color3f[3];
+typedef gfloat Point2f[2];
+
+/**
+ * read_points_file:
+ * @path: The path to the points & colors file
+ * @points: An pointer to an array of pointers to #P2RrPoint will be returned
+ * here. NULL can be passed.
+ * @colors: An pointer to an array of colors will be returned here. NULL can be
+ * passed.
+ *
+ *
+ */
+void
+read_points_file (const gchar *path,
+ GPtrArray **points,
+ GArray **colors)
+{
+ FILE *f = fopen (path, "r");
+ gint countPts = 0, countCls = 0;
+
+ if (f == NULL)
+ {
+ g_print ("Error! Could not read input file!");
+ exit (1);
+ }
+
+ if (verbose)
+ g_print ("Now parsing \"%s\"\n", path);
+
+ if (points != NULL) *points = g_ptr_array_new ();
+ if (colors != NULL) *colors = g_array_new (FALSE, FALSE, sizeof (Color3f));
+
+ if (debug_print && points == NULL) g_print ("Points will not be kept\n");
+ if (debug_print && colors == NULL) g_print ("Colors will not be kept\n");
+
+ while (! feof (f))
+ {
+ Color3f col = { 0, 0, 0 };
+ Point2f ptc = { 0, 0 };
+ gboolean foundCol = FALSE, foundPt = FALSE;
+
+ /* Read only while we have valid points */
+ gint readSize = fscanf (f, "@ %f %f ", &ptc[0], &ptc[1]);
+
+ if (readSize > 0)
+ {
+ if (readSize != 2)
+ {
+ g_error ("Error! %d is an unexpected number of floats after point '@' declaration!\n", readSize);
+ exit (1);
+ }
+
+ foundPt = TRUE;
+
+ if (points != NULL)
+ {
+ g_ptr_array_add (*points, p2tr_point_new (ptc[0], ptc[1]));
+ countPts++;
+ }
+ }
+
+ readSize = fscanf (f, "# %f %f %f ", &col[0], &col[1], &col[2]);
+
+ if (readSize > 0)
+ {
+ if (readSize != 1 && readSize != 3)
+ {
+ g_error ("Error! %d is an unexpected number of floats after color '#' declaration!\n", readSize);
+ exit (1);
+ }
+
+ foundCol = TRUE;
+
+ /* Did we read Gray color information? */
+ if (readSize == 1)
+ col[1] = col[2] = col[0];
+
+ if (colors != NULL)
+ {
+ g_array_append_val (*colors, ptc);
+ countCls++;
+ }
+ }
+
+ if (!foundCol && !foundPt)
+ break;
+ }
+
+ fclose (f);
+
+ if (verbose)
+ g_print ("Read %d points and %d colors\n", countPts, countCls);
+}
+
+gint main (int argc, char *argv[])
+{
+ FILE *out;
+ GError *error = NULL;
+ GOptionContext *context;
+
+ GPtrArray *pts;
+ GArray *colors;
+
+ P2tRTriangulation *T;
+
+ gint i;
+ gchar buf[MAX_PATH+1];
+ gfloat *im;
+
+ context = g_option_context_new ("- Create a fine mesh from a given PSLG");
+ g_option_context_add_main_entries (context, entries, NULL);
+
+// g_option_context_add_group (context, gtk_get_option_group (TRUE));
+
+ if (!g_option_context_parse (context, &argc, &argv, &error))
+ {
+ g_print ("option parsing failed: %s\n", error->message);
+ exit (1);
+ }
+
+ if (input_file == NULL)
+ {
+ g_print ("No input file given. Stop.");
+ exit (1);
+ }
+
+ if (! g_file_test (input_file, G_FILE_TEST_EXISTS))
+ {
+ g_print ("Input file does not exist. Stop.");
+ exit (1);
+ }
+
+ if (output_file == NULL)
+ {
+ g_print ("No output file given. Stop.");
+ exit (1);
+ }
+
+ if ((out = fopen (output_file, "w")) == NULL)
+ {
+ g_print ("Can't open the output file. Stop.");
+ exit (1);
+ }
+
+ read_points_file (input_file, &pts, &colors);
+
+ T = p2tr_triangulate_and_refine (pts);
+
+ p2tr_plot_svg (T,out);
+
+ fclose (out);
+
+ sprintf (buf, "%s.ppm", output_file);
+
+ if ((out = fopen (buf, "w")) == NULL)
+ {
+ g_print ("Can't open the output ppm file. Stop.");
+ exit (1);
+ }
+
+ P2tRImageConfig imc;
+
+ imc.cpp = 4;
+ imc.min_x = imc.min_y = 0;
+ imc.step_x = imc.step_y = 0.2;
+ imc.x_samples = imc.y_samples = 500;
+
+ im = g_new (gfloat, imc.cpp * imc.x_samples * imc.y_samples);
+
+ p2tr_mesh_render_scanline (T, im, &imc, p2tr_test_point_to_color, NULL);
+
+ p2tr_write_ppm (out, im, &imc);
+ fclose (out);
+
+ g_free (im);
+
+ p2tr_triangulation_free (T);
+
+ for (i = 0; i < pts->len; i++)
+ {
+ p2tr_point_unref ((P2tRPoint*) g_ptr_array_index (pts, i));
+ }
+
+ g_ptr_array_free (pts, TRUE);
+ g_array_free (colors, TRUE);
+
+}
\ No newline at end of file
diff --git a/operations/common/seamless-clone/poly2tri-c/poly2tri.h b/operations/common/seamless-clone/poly2tri-c/poly2tri.h
new file mode 100755
index 0000000..487755e
--- /dev/null
+++ b/operations/common/seamless-clone/poly2tri-c/poly2tri.h
@@ -0,0 +1,39 @@
+/*
+ * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
+ * http://code.google.com/p/poly2tri/
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without modification,
+ * are permitted provided that the following conditions are met:
+ *
+ * * Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright notice,
+ * this list of conditions and the following disclaimer in the documentation
+ * and/or other materials provided with the distribution.
+ * * Neither the name of Poly2Tri nor the names of its contributors may be
+ * used to endorse or promote products derived from this software without specific
+ * prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef POLY2TRI_H
+#define POLY2TRI_H
+
+#include "common/shapes.h"
+#include "sweep/cdt.h"
+
+#endif
+
diff --git a/operations/common/seamless-clone/poly2tri-c/refine/refine.c b/operations/common/seamless-clone/poly2tri-c/refine/refine.c
new file mode 100755
index 0000000..b4d991a
--- /dev/null
+++ b/operations/common/seamless-clone/poly2tri-c/refine/refine.c
@@ -0,0 +1,703 @@
+#include <stdlib.h>
+
+#include "triangulation.h"
+
+/* Place holder function. In the future, this should be replaced by some search
+ * tree, such as a quad tree.
+ */
+P2tRTriangle *
+p2tr_triangulation_locate_point (P2tRTriangulation *T, P2tRPoint *X)
+{
+ P2trHashSetIter iter;
+ P2tRTriangle *result;
+
+ p2tr_hash_set_iter_init (&iter, T->tris);
+
+ while (p2tr_hash_set_iter_next(&iter, (gpointer*)&result))
+ {
+ if (p2tr_triangle_contains_pt (result, X))
+ return result;
+ }
+
+ return NULL;
+}
+
+gboolean
+p2tr_points_are_same (P2tRPoint *pt1, P2tRPoint *pt2)
+{
+ return p2tr_math_edge_len_sq (pt1->x, pt1->y, pt2->x, pt2->y) < EPSILON2;
+}
+
+/* As the algorithm paper states, an edge can only be encroached by the
+ * point opposite to it in one of the triangles it's a part of.
+ * We can deduce from that that a point may only encroach upon edges that form
+ * the triangle in/on which it is located.
+ * which are opposite to it in some triangle, and that it may encroach free
+ * points (points which are not a part of any triangles)
+ * We can find the list of triangles in which a point it a part, by iterating
+ * over the .tri property of the out going edges.
+ * NOTE: If there is a triangle formed by edges, but without a real triangle
+ * there, then we are dealing with the edges of the domain which have to
+ * be constrained! Therefore, we can ignore these edges and not return them
+ */
+P2tRHashSet *
+p2tr_triangulation_get_encroaches_upon (P2tRPoint *pt, P2tRTriangulation *T)
+{
+ GList *iter;
+ P2tRTriangle *Tri = p2tr_triangulation_locate_point (T, pt);
+ P2tRPoint *p;
+ P2tRHashSet *E = p2tr_hash_set_set_new (g_direct_hash, g_direct_equal, NULL);
+ gint i;
+
+ if (Tri == NULL)
+ return E;
+
+ for (i = 0; i < 3; i++)
+ {
+ /* If the point is the same as any of the points of the triangle, then it
+ * is inside the diametral circle of all the edges that connect to that
+ * point. In that case, add all the edges of the point to the list of
+ * encroahced edges.
+ * TODO: check if you can break after finding one in this case
+ */
+ if (p2tr_points_are_same (pt, p = p2tr_edge_get_end (Tri->edges[i])))
+ foreach (iter, p->edges)
+ p2tr_hash_set_insert (E, (P2tREdge*) iter->data);
+
+ /* Now, check if any of the edges contains the point inside it's diametral
+ * circle */
+ if (p2tr_edge_diametral_circle_contains (Tri->edges[i], pt))
+ p2tr_hash_set_insert (E, Tri->edges[i]);
+
+ /* TODO: add a check for the case where the point is actually on one of the
+ * edges */
+ }
+
+ return E;
+}
+
+
+/**
+ * Split an edge at a given point. If the point is at the same location as one
+ * of the sides, the edge will not be split in order to avoid zero lengthed edges.
+ *
+ * @param e the edge to split
+ * @param pt the point to add
+ * @param T the triangulation to maintain
+ * @param patchHoles Whethe the holes created by removing the original edge
+ * should be patched
+ * @param dest An array where the results of the split are to be stored. The
+ * array should be of size 2, and it will contain one edge if no split
+ * occured or two edges if a split did in fact occur.
+ *
+ * @return The amount of edges resulting from the split - 1 if no split, 2 if a
+ * split occured
+ */
+gint
+p2tr_split_edge (P2tREdge *e,
+ P2tRPoint *pt,
+ P2tRTriangulation *T,
+ gboolean patchHoles,
+ P2tREdge *dest[2],
+ gboolean flipFix)
+{
+ /* A
+ * / \
+ * / | \
+ * / \
+ * / | \
+ * / \
+ * S---- pt----E ===> This is edge e, and pt is the point we insert
+ * \ | /
+ * \ /
+ * \ | /
+ * \ /
+ * \ | /
+ * \ /
+ * B
+ *
+ * Each of these edges may need flip fixing!
+ */
+ P2tRPoint *S = p2tr_edge_get_start (e);
+ P2tRPoint *E = p2tr_edge_get_end (e);
+ P2tRPoint *A = NULL, *B = NULL;
+
+ P2tRTriangle *SptA = NULL, *ptEA = NULL, *SptB = NULL, *ptEB = NULL;
+
+ gboolean constrained = e->constrained;
+ /* TODO: T remove me */
+ p2tr_validate_edge (e);
+
+ P2tREdge *Spt, *ptE;
+
+ p2tr_debug ("Checking if can split\n");
+
+ if (p2tr_points_are_same (pt, S) || p2tr_points_are_same (pt, E))
+ {
+ dest[0] = e;
+ dest[1] = NULL;
+ return 1;
+ }
+
+ p2tr_debug ("Splitting!\nAdding (%f,%f) between (%f,%f) and (%f,%f)\n", pt->x,pt->y,S->x,S->y,E->x,E->y);
+
+ if (patchHoles)
+ {
+ if (e->tri != NULL)
+ A = p2tr_triangle_opposite_point (e->tri, e);
+
+ if (e->mirror->tri != NULL)
+ B = p2tr_triangle_opposite_point (e->mirror->tri, e);
+ }
+
+ p2tr_edge_remove (e, T);
+
+ Spt = p2tr_edge_new (S, pt);
+ ptE = p2tr_edge_new (pt,E);
+
+ p2tr_edge_set_constrained (Spt, constrained);
+ p2tr_edge_set_constrained (ptE, constrained);
+
+ if (patchHoles)
+ {
+ if (A != NULL)
+ {
+ P2tREdge *ptA = p2tr_point_edge_to (pt, A);
+ P2tRTriangle *SptA = p2tr_triangle_new (Spt, ptA, p2tr_point_edge_to (A, S), T);
+ P2tRTriangle *ptEA = p2tr_triangle_new (ptE, p2tr_point_edge_to (E, A), ptA->mirror,T);
+ }
+
+ if (B != NULL)
+ {
+ P2tREdge* ptB = p2tr_point_edge_to (pt, B);
+ P2tRTriangle *SptB = p2tr_triangle_new (Spt, ptB, p2tr_point_edge_to (B, S), T);
+ P2tRTriangle *ptEB = p2tr_triangle_new (ptE, p2tr_point_edge_to (E, B), ptB->mirror,T);
+ }
+ }
+
+ if (flipFix)
+ {
+ P2tREdge *temp;
+
+ /* We do not want the edges resulting from the split to be flipped! */
+ p2tr_edge_set_delaunay (Spt, TRUE);
+ p2tr_edge_set_delaunay (ptE, TRUE);
+
+ if (A != NULL)
+ {
+ p2tr_triangulation_legalize (T, SptA);
+ p2tr_triangulation_legalize (T, ptEA);
+ }
+ if (B != NULL)
+ {
+ p2tr_triangulation_legalize (T, SptB);
+ p2tr_triangulation_legalize (T, ptEB);
+ }
+
+ p2tr_edge_set_delaunay (Spt, FALSE);
+ p2tr_edge_set_delaunay (ptE, FALSE);
+ }
+
+ // Error - if the triangles were remove, unreffing them would cause problems
+ // So for now, I'm commenting these out
+ // TODO: FIXME!
+// p2tr_triangle_unref (SptA);
+// p2tr_triangle_unref (ptEA);
+
+// p2tr_triangle_unref (SptB);
+// p2tr_triangle_unref (ptEB);
+
+ if (dest != NULL)
+ {
+ /* We shouldn't decrese the reference to Spt and ptE, since it's 1
+ * right now, and we pass the reference to them back to the caller through
+ * dest */
+ dest[0] = Spt;
+ dest[1] = ptE;
+ }
+ else
+ {
+ p2tr_edge_unref (Spt);
+ p2tr_edge_unref (ptE);
+ }
+ return 2;
+}
+
+/**
+ * Insert a point into a triangulation. If it's outside of the triangulation or
+ * if it merges with an existing point it will not be inserted. If it's on an
+ * existing edge, the edge will be split and then there will be a flipfix to
+ * make the triangulation CDT again. If it's inside a triangle, the triangle
+ * will be subdivided and flipfixing will be applied to maintain the CDT
+ * property.
+ *
+ * @param pt the point to insert
+ * @param T the triangulation to insert into
+ *
+ * @return TRUE if the point was inserted, FALSE otherwise
+ */
+gboolean
+p2tr_triangulation_insert_pt (P2tRPoint *pt, P2tRTriangulation *T)
+{
+ p2tr_debug ("@insertPt\n");
+ P2tRTriangle *Tri = p2tr_triangulation_locate_point (T, pt);
+
+ gint i;
+ P2tREdge *temp;
+
+ p2tr_validate_triangulation (T);
+ if (Tri == NULL)
+ {
+ p2tr_debug ("Warning - tried to insert point outside of domain\n");
+ return FALSE;
+ }
+
+ P2tREdge *ab = Tri->edges[0];
+ P2tREdge *bc = Tri->edges[1];
+ P2tREdge *ca = Tri->edges[2];
+
+ P2tRPoint *a = p2tr_edge_get_end (ca);
+ P2tRPoint *b = p2tr_edge_get_end (ab);
+ P2tRPoint *c = p2tr_edge_get_end (bc);
+
+ if (p2tr_points_are_same (pt, a)
+ || p2tr_points_are_same (pt, b)
+ || p2tr_points_are_same (pt, c))
+ {
+ p2tr_debug ("Not inserting point on existing point!\n");
+ return FALSE;
+ }
+
+ p2tr_validate_triangulation (T);
+ /* Check if the point is on any of the edges */
+ for (i = 0; i < 3; i++)
+ {
+ P2tRPoint *S = p2tr_edge_get_start (Tri->edges[i]);
+ P2tRPoint *E = p2tr_edge_get_end (Tri->edges[i]);
+
+ /* Is the point on the edge? */
+ if (p2tr_math_orient2d (pt,S,E) == COLLINEAR)
+ {
+ gint j;
+ gint splitCount;
+ P2tREdge *splits[2];
+
+ /* If so, flip the edge */
+ p2tr_validate_triangulation (T);
+ splitCount = p2tr_split_edge (Tri->edges[i], pt, T, TRUE, splits, TRUE);
+ p2tr_validate_triangulation (T);
+ /* Then, flipfix each of the resulting edges */
+ for (j = 0; j < splitCount; j++)
+ {
+ p2tr_triangulation_flip_fix (splits[j], T);
+ /* We don't use the edge after this point, so unref */
+ p2tr_edge_unref (splits[j]);
+ }
+
+ /* If the point is on one edge then it's not on any other edge (unless
+ * it is in fact one of the triangle vertices but we already fixed
+ * that case earlier). So by splitting the edge and flipfixing the
+ * result, we are in fact done. */
+ return TRUE;
+ }
+ }
+
+ /* If reached here, then the point was not on any of the edges. So just
+ * insert it into the triangle */
+
+ p2tr_validate_triangulation (T);
+ p2tr_triangle_subdivide (Tri, pt, T, NULL);
+ p2tr_validate_triangulation (T);
+
+ /* IMPORTANT: YOU CAN NOT FLIP AB/BC/CA BECAUSE THEY MAY NOT EXIST!
+ * Even if there is an edge from a to b for example, it may not be ab we got
+ * earlier! It can be there as a result of different flip fixing which
+ * deleted and then created it! So, take the edge returned from has_edge_to
+ * (which is the updated one) and flip-fix if it exists.
+ */
+ if ((temp = p2tr_point_has_edge_to (a,b)) != NULL)
+ p2tr_triangulation_flip_fix (temp, T);
+ p2tr_validate_triangulation (T);
+
+ if ((temp = p2tr_point_has_edge_to (b,c)) != NULL)
+ p2tr_triangulation_flip_fix (temp, T);
+ p2tr_validate_triangulation (T);
+
+ if ((temp = p2tr_point_has_edge_to (c,a)) != NULL)
+ p2tr_triangulation_flip_fix (temp, T);
+ p2tr_validate_triangulation (T);
+
+ return TRUE;
+}
+
+typedef gboolean (*deltafunc) (P2tRTriangle *);
+
+
+/*
+ * This function returns negative if triangle a is uglier than b, 0 if same, and
+ * 1 if b is uglier
+ */
+gint
+ugliness_comparision (gconstpointer a,
+ gconstpointer b,
+ gpointer ignored)
+{
+ if (a == b)
+ return 0; // Fast path exit
+
+ gdouble shortestA = p2tr_triangle_shortest_edge_len ((P2tRTriangle*)a);
+ gdouble shortestB = p2tr_triangle_shortest_edge_len ((P2tRTriangle*)b);
+
+ gdouble longestA = p2tr_triangle_longest_edge_len ((P2tRTriangle*)a);
+ gdouble longestB = p2tr_triangle_longest_edge_len ((P2tRTriangle*)b);
+
+ gdouble smallestA = p2tr_triangle_smallest_non_seperating_angle ((P2tRTriangle*)a);
+ gdouble smallestB = p2tr_triangle_smallest_non_seperating_angle ((P2tRTriangle*)b);
+
+// Bad
+// return (gint) ((smallestA - smallestB) / M_PI) ;//+ (longestA - longestB) / MAX (longestA, longestB);
+
+// Seems Good
+ return (gint) (1 - longestA/longestB + ((smallestA - smallestB) / M_PI));
+
+// Not sure?
+// return (gint) (longestB/shortestB - longestA/shortestA);
+
+// Trivial, reasonable
+// return (gint) (smallestA - smallestB);
+}
+
+
+void
+NewVertex (P2tRPoint *v, gdouble theta, deltafunc delta,
+ GQueue *Qs, GSequence *Qt)
+{
+ GList *iter;
+
+ p2tr_debug ("NewVertex: After inserting ");
+ p2tr_debug_point (v, TRUE);
+
+ foreach (iter, v->edges)
+ {
+ P2tREdge *ed = (P2tREdge*) iter->data;
+ P2tRTriangle *t = ed->tri;
+
+ if (t != NULL)
+ {
+ p2tr_debug ("NewVertex: Checking tri ");
+ p2tr_debug_tri (t, TRUE);
+
+ P2tREdge *e = p2tr_triangle_opposite_edge (t, v);
+ if (e->mirror->tri == NULL && p2tr_edge_is_encroached_by (e, v))
+ g_queue_push_tail (Qs, e);
+ else if (delta (t) || p2tr_triangle_smallest_non_seperating_angle (t) < theta)
+ g_sequence_insert_sorted (Qt, t, ugliness_comparision, NULL);
+ }
+ }
+}
+
+void
+SplitEncroachedSubsegments (gdouble theta,
+ deltafunc delta,
+ P2tRTriangulation *T,
+ GQueue *Qs,
+ GSequence *Qt)
+{
+ while (! g_queue_is_empty (Qs))
+ {
+ p2tr_debug ("Handling edge\n");
+ P2tREdge *s = g_queue_pop_head (Qs);
+ gboolean isin = FALSE;
+
+ P2trHashSetIter iter;
+ P2tRTriangle *t;
+ p2tr_hash_set_iter_init (&iter, T->tris);
+
+ while (p2tr_hash_set_iter_next (&iter, (gpointer*)&t))
+ {
+ if (t->edges[0] == s || t->edges[1] == s || t->edges[2] == s)
+ {
+ isin = TRUE;
+ break;
+ }
+ }
+
+ if (isin)
+ {
+ if (p2tr_edge_len_sq (s) >= 1)
+ {
+ P2tRPoint *v = p2tr_edge_concentric_center (s);
+ P2tREdge *splits[2];
+ gint splitCount = p2tr_split_edge (s, v, T, TRUE, splits, TRUE), i;
+
+ for (i = 0; i < splitCount; i++)
+ {
+ p2tr_triangulation_flip_fix (splits[i], T);
+ }
+
+ NewVertex (v, theta, delta, Qs, Qt);
+ for (i = 0; i < splitCount; i++)
+ {
+ if (p2tr_edge_is_encroached (splits[i]))
+ g_queue_push_tail (Qs, splits[i]);
+ }
+ }
+ }
+ }
+}
+
+
+gboolean
+p2tr_false_delta (P2tRTriangle *t)
+{
+ return FALSE;
+}
+
+const gdouble POW2_EPS = 0;
+const gdouble LENGTHSQ_EPS = 0;
+
+gboolean
+SplitPermitted (P2tREdge *s, gdouble d)
+{
+ p2tr_debug ("@SplitPermitted\n");
+ if (! (p2tr_point_is_in_cluster (p2tr_edge_get_start(s), s) ^ p2tr_point_is_in_cluster (p2tr_edge_get_end(s), s->mirror)))
+ {
+ p2tr_debug ("Criteria 1\n");
+ return TRUE;
+ }
+ gdouble l = p2tr_edge_len_sq (s);
+ gdouble temp = log2 (l) / 2;
+ if (ABS (round (temp) - temp) < POW2_EPS)
+ {
+ p2tr_debug ("Criteria 2\n");
+ return TRUE;
+ }
+
+ gdouble phi_min;
+ GList *S = p2tr_point_get_cluster (p2tr_edge_get_start (s), s, &phi_min);
+ GList *s1;
+
+ foreach(s1, S)
+ {
+ if (p2tr_edge_len_sq ((P2tREdge*)s1->data) < 1 * (1 + LENGTHSQ_EPS))
+ {
+ p2tr_debug ("Criteria 3\n");
+ return TRUE;
+ }
+ }
+
+ gdouble r_min = sqrt(l) * sin (phi_min / 2);
+
+ if (r_min >= d)
+ {
+ p2tr_debug ("Criteria 4\n");
+ return TRUE;
+ }
+
+ p2tr_debug ("Split not permitted\n");
+ return FALSE;
+}
+
+#define MIN_MAX_EDGE_LEN 0
+
+void
+DelaunayTerminator (P2tRTriangulation *T, GList *XEs, gdouble theta, deltafunc delta)
+{
+ const gint STEPS = atoi (g_getenv ("p2t_refine_steps"));
+
+ GSequence *Qt;
+ GQueue Qs;
+
+ GList *Liter, Liter2;
+ P2trHashSetIter Hiter;
+
+ p2tr_validate_triangulation (T);
+
+ P2tRTriangle *t;
+
+ g_queue_init (&Qs);
+ Qt = g_sequence_new (NULL);
+
+ p2tr_debug ("Now we have %d triangles\n", g_hash_table_size (T->tris));
+
+ if (STEPS == 0)
+ return;
+
+ foreach (Liter, XEs)
+ {
+ P2tREdge *s = (P2tREdge*) (Liter->data);
+ if (p2tr_edge_is_encroached (s))
+ {
+ g_queue_push_tail (&Qs, s);
+ }
+ }
+
+ SplitEncroachedSubsegments(0, p2tr_false_delta,T,&Qs,Qt);
+
+ p2tr_validate_triangulation (T);
+
+ p2tr_hash_set_iter_init (&Hiter, T->tris);
+ while (p2tr_hash_set_iter_next (&Hiter, (gpointer*)&t))
+ if (delta (t) || p2tr_triangle_smallest_non_seperating_angle (t) < theta)
+ g_sequence_insert_sorted (Qt, t, ugliness_comparision, NULL);
+
+ gint STOP = STEPS - 1; /* The above split was a step */
+
+ while (g_sequence_get_length (Qt) > 0 && STOP > 0)
+ {
+ p2tr_validate_triangulation (T);
+ p2tr_debug ("Restarting main loop\n");
+ STOP--;
+
+ do
+ {
+ GSequenceIter *siter = g_sequence_get_begin_iter (Qt);
+ t = g_sequence_get (siter);
+ g_sequence_remove (siter);
+ if (g_sequence_get_length (Qt) == 0) break;
+ }
+ while (! p2tr_hash_set_contains (T->tris, t));
+ if (g_sequence_get_length (Qt) == 0) break;
+
+ if (p2tr_triangle_longest_edge_len (t) < MIN_MAX_EDGE_LEN)
+ {
+ continue;
+ }
+
+ /* Possibly make more efficient by adding an "erased" field */
+ if (p2tr_hash_set_contains (T->tris, t))
+ {
+ P2tRCircle cc;
+ P2tRPoint *c;
+ P2tRHashSet *E;
+
+ p2tr_debug ("Found a triangle that still needs fixing\n");
+
+ p2tr_triangle_circumcircle (t, &cc);
+ c = p2tr_point_new (cc.x,cc.y);
+
+ E = p2tr_triangulation_get_encroaches_upon (c, T);
+ p2tr_validate_triangulation (T);
+
+ if (g_hash_table_size (E) == 0)
+ {
+ p2tr_debug ("It's circumcircle encraoches upon nothing!\n");
+ /* Check if the point is in the domain and inserted OK */
+ if (p2tr_triangulation_insert_pt (c, T))
+ {
+ p2tr_validate_triangulation (T);
+ NewVertex (c,theta,delta,&Qs,Qt);
+ p2tr_validate_triangulation (T);
+ }
+ else
+ {
+ int k;
+ /* In the other cases, split the edge crossing the
+ * line to the point
+ */
+ g_assert (! p2tr_triangle_contains_pt (t, c));
+ P2tRPoint *M = p2tr_triangle_median_pt (t);
+ P2tREdge *MC = p2tr_point_edge_to (M, c);
+ p2tr_validate_triangulation (T);
+ for (k = 0; k < 3; k++)
+ {
+ P2tREdge *e = t->edges[k];
+ if (p2tr_edges_intersect (e, MC))
+ {
+ P2tREdge *splits[2];
+ P2tRPoint *splitPoint = p2tr_edge_concentric_center (e);
+ gint count = p2tr_split_edge (e, splitPoint, T, TRUE, splits, TRUE);
+ p2tr_validate_triangulation (T);
+ gint j;
+
+ for (j = 0; j < count; j++)
+ {
+ p2tr_triangulation_flip_fix (splits[j], T);
+ p2tr_validate_triangulation (T);
+ }
+
+ p2tr_point_unref (splitPoint);
+ break;
+ }
+ }
+ }
+ }
+ else
+ {
+ P2tREdge *s;
+ p2tr_debug ("It's circumcircle encraoches %d edges\n", g_hash_table_size (E));
+ gdouble d = p2tr_triangle_shortest_edge_len (t);
+
+ p2tr_hash_set_iter_init (&Hiter, E);
+ while (p2tr_hash_set_iter_next (&Hiter, (gpointer*)&s))
+ {
+ if (delta (t) || SplitPermitted(s,d))
+ {
+ p2tr_debug ("Appending an edge for splitting\n");
+ g_queue_push_tail (&Qs, s);
+ }
+ }
+ if (! g_queue_is_empty (&Qs))
+ {
+ g_sequence_insert_sorted (Qt, t, ugliness_comparision, NULL);
+ p2tr_debug ("Will now try splitting\n");
+ SplitEncroachedSubsegments(theta,delta,T,&Qs,Qt);
+ }
+ }
+
+ p2tr_point_unref (c);
+ }
+
+ // Why not to legalize here:
+ // 1. Because it should have no effect if we did maintain the CDT
+ // 2. Because if it does have an effect, since legalizations checks only
+ // vialoations with adjacent neighbours, it may simply violate the CDT
+ // property with remote ones!
+
+ // Flip fixing actually adds more triangles that may have to be fixed.
+ // Untill we do it preoperly, add them here:
+ /*
+ P2trHashSetIter triter;
+ P2tRTriangle *trit;
+
+ p2tr_hash_set_iter_init (&triter,T->tris);
+ while (p2tr_hash_set_iter_next (&triter, (gpointer*)&trit))
+ {
+ if (p2tr_triangle_smallest_non_seperating_angle (trit) < theta)
+ g_sequence_insert_sorted (Qt, t, ugliness_comparision, NULL);
+ }
+ */
+ }
+}
+
+/*
+ * Input must be a GPtrArray of P2tRPoint*
+ */
+P2tRTriangulation*
+p2tr_triangulate_and_refine (GPtrArray *pts)
+{
+ gint i, N = pts->len;
+ GList *XEs = NULL, *iter;
+ P2tRTriangulation *T;
+
+ for (i = 0; i < pts->len; i++)
+ {
+ P2tREdge *E = p2tr_point_edge_to ((P2tRPoint*)g_ptr_array_index_cyclic (pts, i),
+ (P2tRPoint*)g_ptr_array_index_cyclic (pts, i+1));
+ p2tr_edge_set_constrained (E, TRUE);
+ XEs = g_list_prepend (XEs, E);
+ }
+
+ T = p2tr_triangulateA ((P2tRPoint**)pts->pdata ,pts->len);
+ DelaunayTerminator (T,XEs,M_PI/6,p2tr_false_delta);
+
+ foreach (iter, XEs)
+ {
+ P2tREdge *E = (P2tREdge*) iter->data;
+ p2tr_edge_unref (E);
+ }
+
+ g_list_free (XEs);
+
+ return T;
+}
\ No newline at end of file
diff --git a/operations/common/seamless-clone/poly2tri-c/refine/refine.h b/operations/common/seamless-clone/poly2tri-c/refine/refine.h
new file mode 100755
index 0000000..91fe871
--- /dev/null
+++ b/operations/common/seamless-clone/poly2tri-c/refine/refine.h
@@ -0,0 +1,29 @@
+/*
+ * File: refine.h
+ * Author: Barak
+ *
+ * Created on 29 ×××× 2011, 04:52
+ */
+
+#ifndef REFINE_H
+#define REFINE_H
+
+#include <glib.h>
+#include "triangulation.h"
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif
+
+P2tRTriangulation*
+p2tr_triangulate_and_refine (GPtrArray *pts);
+
+
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* REFINE_H */
+
diff --git a/operations/common/seamless-clone/poly2tri-c/refine/triangulation.c b/operations/common/seamless-clone/poly2tri-c/refine/triangulation.c
new file mode 100755
index 0000000..fa09578
--- /dev/null
+++ b/operations/common/seamless-clone/poly2tri-c/refine/triangulation.c
@@ -0,0 +1,1458 @@
+#include <math.h>
+
+#include "../common/utils.h"
+#include "triangulation.h"
+#include "../poly2tri.h"
+
+/* ########################################################################## */
+/* Common math */
+/* ########################################################################## */
+gdouble
+p2tr_math_normalize_angle (gdouble angle)
+{
+ while (angle < -M_PI)
+ angle += 2 * M_PI_2;
+ while (angle > M_PI)
+ angle -= 2 * M_PI;
+ return angle;
+}
+
+/* NOTE: exact copy of p2t_orient2d, with different EPSILON2
+ * TODO: merge somehow
+ */
+P2tROrientation
+p2tr_math_orient2d (P2tRPoint* pa,
+ P2tRPoint* pb,
+ P2tRPoint* pc)
+{
+ double detleft = (pa->x - pc->x) * (pb->y - pc->y);
+ double detright = (pa->y - pc->y) * (pb->x - pc->x);
+ double val = detleft - detright;
+// p2tr_debug ("orient2d val is %f\n",val);
+ if (val > -EPSILON2 && val < EPSILON2)
+ {
+// p2tr_debug ("COLLINEAR!\n");
+ return COLLINEAR;
+ }
+ else if (val > 0)
+ {
+// p2tr_debug ("CCW!\n");
+ return CCW;
+ }
+// p2tr_debug ("CW!\n");
+ return CW;
+}
+
+/* TODO: check relation with p2t_utils_in_scan_area */
+/* This function is based on an article by Jonathan Richard Shewchuk
+ * "Robust Adaptive Floating-Point Geometric Predicates"
+ *
+ * | ax-dx ay-dy (ax-dx)^2+(ay-dy)^2 |
+ * | bx-dx by-dy (bx-dx)^2+(by-dy)^2 |
+ * | cx-dx cy-dy (cx-dx)^2+(cy-dy)^2 |
+ *
+ * A, B AND C MUST BE IN CCW ORDER!
+ */
+P2tRInCircle
+p2tr_math_incircle (P2tRPoint* a,
+ P2tRPoint* b,
+ P2tRPoint* c,
+ P2tRPoint* d)
+{
+ gdouble ad_dx = a->x - d->x;
+ gdouble ad_dy = a->y - d->y;
+ gdouble ad_dsq = ad_dx * ad_dx + ad_dy * ad_dy;
+
+ gdouble bd_dx = b->x - d->x;
+ gdouble bd_dy = b->y - d->y;
+ gdouble bd_dsq = bd_dx * bd_dx + bd_dy * bd_dy;
+
+ gdouble cd_dx = c->x - d->x;
+ gdouble cd_dy = c->y - d->y;
+ gdouble cd_dsq = cd_dx * cd_dx + cd_dy * cd_dy;
+
+ gdouble calc = + ad_dx * (bd_dy * cd_dsq - cd_dy * bd_dsq)
+ - ad_dy * (bd_dx * cd_dsq - cd_dx * bd_dsq)
+ + ad_dsq * (bd_dx * cd_dy - cd_dx * bd_dy);
+
+ if (calc > EPSILON2)
+ return INCIRCLE_INSIDE;
+ else if (calc < EPSILON2)
+ return INCIRCLE_OUTSIDE;
+ else
+ return INCIRCLE_ON;
+}
+
+gdouble
+p2tr_math_edge_len_sq (gdouble x1, gdouble y1, gdouble x2, gdouble y2)
+{
+ gdouble dx = x2 - x1;
+ gdouble dy = y2 - y1;
+ return dx * dx + dy * dy;
+}
+
+/* ########################################################################## */
+/* Triangulation struct */
+/* ########################################################################## */
+
+void
+p2tr_triangulation_remove_pt (P2tRTriangulation *self, P2tRPoint *pt)
+{
+ if (p2tr_hash_set_remove (self->pts, pt))
+ p2tr_point_unref (pt);
+}
+
+void
+p2tr_triangulation_remove_ed (P2tRTriangulation *self, P2tREdge *ed)
+{
+ if (p2tr_hash_set_remove (self->edges, ed))
+ p2tr_edge_unref (ed);
+}
+
+void
+p2tr_triangulation_remove_tr (P2tRTriangulation *self, P2tRTriangle *tr)
+{
+ if (p2tr_hash_set_remove (self->tris, tr))
+ p2tr_triangle_unref (tr);
+}
+
+void
+p2tr_triangulation_add_pt (P2tRTriangulation *self, P2tRPoint *pt)
+{
+ if (p2tr_hash_set_contains (self->pts, pt))
+ return;
+
+ p2tr_hash_set_insert (self->pts, pt);
+ p2tr_point_ref (pt);
+}
+void
+p2tr_triangulation_add_ed (P2tRTriangulation *self, P2tREdge *ed)
+{
+ if (p2tr_hash_set_contains (self->edges, ed))
+ return;
+
+ p2tr_hash_set_insert (self->edges, ed);
+ p2tr_edge_ref (ed);
+}
+void
+p2tr_triangulation_add_tr (P2tRTriangulation *self, P2tRTriangle *tr)
+{
+ if (p2tr_hash_set_contains (self->tris, tr))
+ return;
+
+ p2tr_hash_set_insert (self->tris, tr);
+ p2tr_triangle_ref (tr);
+}
+
+/* ########################################################################## */
+/* Point struct */
+/* ########################################################################## */
+
+static void
+p2tr_point_init (P2tRPoint *self,
+ gdouble x,
+ gdouble y)
+{
+ self->x = x;
+ self->y = y;
+ self->edges = NULL;
+ self->_refcount = 1;
+}
+
+P2tRPoint*
+p2tr_point_new (gdouble x,
+ gdouble y)
+{
+ P2tRPoint *self = g_slice_new (P2tRPoint);
+ p2tr_point_init (self, x, y);
+ return self;
+}
+
+static void
+p2tr_point_destroy (P2tRPoint *self)
+{
+ GList *iter;
+
+ g_assert (self->_refcount == 0);
+
+ foreach (iter, self->edges)
+ {
+ P2tREdge *e = (P2tREdge*) iter->data;
+ p2tr_edge_unref (e);
+ }
+
+ g_list_free (self->edges);
+}
+
+void
+p2tr_point_free (P2tRPoint *self)
+{
+ p2tr_point_destroy (self);
+ g_slice_free (P2tRPoint, self);
+}
+/* DBG: Differs from original
+ *
+ * THIS FUNCTION SHOULD NOT BE USED DIRECTLY! IT IS JUST A CONVINIENCE FUNCTION
+ * USED BY THE CONSTRUCTOR OF THE EDGE OBJECT TO ACTUALLY REFERENCE THE EDGE
+ * FROM THE POINT!
+ */
+static void
+p2tr_point_add_edge (P2tRPoint *self,
+ P2tREdge *edge)
+{
+ GList *iter = self->edges;
+ for (iter = self->edges; iter != NULL; iter = iter->next)
+ {
+ if (!(P2TR_EDGE(iter->data)->angle < edge->angle))
+ break;
+ }
+
+ /* Inserting before NULL will insert at the end of the list */
+ self->edges = g_list_insert_before (self->edges, iter, edge);
+
+ /* We now hold a reference to the edge! */
+ p2tr_edge_ref (edge);
+}
+
+void
+p2tr_point_remove_edge (P2tRPoint *self,
+ P2tREdge *edge)
+{
+ p2tr_assert_and_explain (g_list_find (self->edges, edge) != NULL, "can't remove non existing edge");
+ self->edges = g_list_remove (self->edges, edge);
+ p2tr_edge_unref (edge);
+}
+
+void
+p2tr_point_remove (P2tRPoint *self,
+ P2tRTriangulation *T)
+{
+ GList *iter = self->edges;
+ for (iter = self->edges; iter != NULL; iter = iter->next)
+ {
+ p2tr_edge_remove (P2TR_EDGE(iter->data), T);
+ }
+ p2tr_triangulation_remove_pt (T, self);
+}
+
+/* This function will return an edge from the current
+ * point to a given other point. If no such edge exists,
+ * it will be created
+ */
+P2tREdge*
+p2tr_point_edge_to (P2tRPoint *self, P2tRPoint *end)
+{
+ GList *iter = self->edges;
+
+ for (iter = self->edges; iter != NULL; iter = iter->next)
+ if (P2TR_EDGE(iter->data)->end == end)
+ {
+ p2tr_edge_ref (P2TR_EDGE(iter->data));
+ return P2TR_EDGE (iter->data);
+ }
+
+ /* Don't decrease reference - this is returned to someone else */
+ return p2tr_edge_new (self, end);
+}
+
+P2tREdge*
+p2tr_point_has_edge_to (P2tRPoint *self, P2tRPoint *end)
+{
+ GList *iter = self->edges;
+
+ for (iter = self->edges; iter != NULL; iter = iter->next)
+ if (P2TR_EDGE(iter->data)->end == end)
+ return P2TR_EDGE(iter->data);
+
+ return NULL;
+}
+
+P2tREdge*
+p2tr_point_edgeccw (P2tRPoint *self, P2tREdge *edge)
+{
+ GList *index = g_list_find (self->edges, edge);
+ return p2tr_edgelist_ccw (self->edges, index);
+}
+
+P2tREdge*
+p2tr_point_edgecw (P2tRPoint *self, P2tREdge *edge)
+{
+ GList *index = g_list_find (self->edges, edge);
+ return p2tr_edgelist_cw (self->edges, index);
+}
+
+/*
+ * ^ e1 = CCW Neighbor of e
+ * /
+ * / e1.tri
+ * /
+ * P *------> e
+ * \
+ * \ e.tri
+ * \
+ * v e2 = CW Neighbor of e
+ *
+ * e is in a cluster defined by P, if any of the
+ * following conditions hold:
+ * - The angle between e and e2 is less than 60 degrees,
+ * and the triangle of e1 is not None (i.e. the area
+ * between the edges is in the triangulation domain)
+ * - Same with e and e1
+ */
+gboolean
+p2tr_point_is_in_cluster (P2tRPoint *self, P2tREdge *e)
+{
+ /* TODO: make more efficient instead of two searches */
+ GList *eL = g_list_find (self->edges, e);
+ P2tREdge *e1 = p2tr_edgelist_ccw (self->edges, eL);
+ P2tREdge *e2 = p2tr_edgelist_cw (self->edges, eL);
+
+ gdouble Ae1e = p2tr_math_normalize_angle (e1->angle - e->angle);
+ gdouble Aee2 = p2tr_math_normalize_angle (e->angle - e2->angle);
+
+ return (e1->tri != NULL && ABS (Ae1e) <= M_PI/3)
+ || (e->tri != NULL && ABS (Aee2) <= M_PI/3);
+}
+
+/*
+ * DBG: different from original
+ */
+GList*
+p2tr_point_get_cluster (P2tRPoint *self, P2tREdge *e, gdouble *angle)
+{
+ gdouble A = M_PI, a;
+ GList *eI = g_list_find (self->edges, e);
+ GList *temp;
+
+ GList *S = g_list_append (NULL, e);
+
+ GList *ePrev = g_list_cyclic_prev (self->edges,eI);
+ GList *eNext = g_list_cyclic_next (self->edges,eI);
+
+ a = p2tr_math_normalize_angle (e->angle - P2TR_EDGE (ePrev->data)->angle);
+ while (a <= M_PI / 3 && ePrev != eI)
+ {
+ A = MIN(a, A);
+ S = g_list_prepend (S, P2TR_EDGE (ePrev->data));
+ temp = ePrev;
+ ePrev = g_list_cyclic_prev (self->edges, ePrev);
+ a = p2tr_math_normalize_angle (P2TR_EDGE (temp->data)->angle - P2TR_EDGE (ePrev->data)->angle);
+ }
+
+ a = p2tr_math_normalize_angle (P2TR_EDGE (eNext->data)->angle - e->angle);
+ while (a <= M_PI / 3 && eNext->data != S->data)
+ {
+ A = MIN(a, A);
+ S = g_list_append (S, P2TR_EDGE (eNext->data));
+ temp = eNext;
+ eNext = g_list_cyclic_next (self->edges, eNext);
+ a = p2tr_math_normalize_angle (P2TR_EDGE (eNext->data)->angle - P2TR_EDGE (temp->data)->angle);
+ }
+
+ if (angle != NULL)
+ *angle = A;
+
+ return S;
+}
+
+gboolean
+p2tr_point_is_fully_in_domain (P2tRPoint *self)
+{
+ GList *iter = self->edges;
+
+ for (iter = self->edges; iter != NULL; iter = iter->next)
+ if (P2TR_EDGE(iter->data)->end == NULL)
+ return FALSE;
+
+ return TRUE;
+}
+
+/* ########################################################################## */
+/* Edge struct */
+/* ########################################################################## */
+
+P2tREdge*
+p2tr_edge_new (P2tRPoint *start, P2tRPoint *end)
+{
+ return p2tr_edge_new_private (start, end, FALSE);
+}
+
+P2tREdge*
+p2tr_edge_new_private (P2tRPoint *start, P2tRPoint *end, gboolean mirror)
+{
+ P2tREdge *self = g_slice_new (P2tREdge);
+ p2tr_edge_init_private (self, start, end, mirror);
+ return self;
+}
+
+static void
+p2tr_edge_init (P2tREdge *self, P2tRPoint *start, P2tRPoint *end)
+{
+ p2tr_edge_init_private (self, start, end, FALSE);
+}
+
+static void
+p2tr_edge_init_private (P2tREdge *self, P2tRPoint *start, P2tRPoint *end, gboolean mirror)
+{
+ self->_refcount = 0;
+ self->removed = FALSE;
+ self->end = end;
+ self->tri = NULL;
+
+ self->angle = atan2 (end->y - start->y, end->x - start->x);
+
+ self->delaunay = FALSE;
+ self->constrained = FALSE;
+
+ /* Important! Add the edge only once we have an angle!
+ * This function also adds a reference to the edge, since the point now points
+ * at the edge. */
+ p2tr_point_add_edge (start, self);
+
+ if (!mirror)
+ {
+ self->mirror = p2tr_edge_new_private (end, start, TRUE);
+ self->mirror->mirror = self;
+ }
+
+ /* The edge that was created should have it's reference count increased by 1,
+ * since it will be returned (so mark the person who gets it holds a ref).
+ * Note that we don't count the reference loop between two mirror edges */
+ if (!mirror)
+ p2tr_edge_ref (self);
+
+ /* Finally, the edge now references it's end point */
+ p2tr_point_ref (self->end);
+
+ p2tr_assert_and_explain (p2tr_point_has_edge_to (start, end), "edge connectivity");
+ p2tr_assert_and_explain (p2tr_point_has_edge_to (end, start), "edge connectivity");
+}
+
+/* Note that you can't really free one edge - since the edge and it's mirror are
+ * tightly coupled. By freeing one of them, you will also free the other - so
+ * beware of double freeing!
+ *
+ * The best way is not to free directly, but to use the unref function.
+ *
+ * TODO: Merge some logic and fill in missing part with the edge_remove function
+ */
+void
+p2tr_edge_free (P2tREdge *self)
+{
+ g_assert (self->_refcount == 0);
+
+ if (self->mirror->_refcount != 0)
+ return;
+
+ self->removed = self->mirror->removed = TRUE;
+
+ p2tr_point_unref (self->mirror->end);
+ p2tr_point_unref (self->end);
+
+ p2tr_triangle_unref (self->mirror->tri);
+ p2tr_triangle_unref (self->tri);
+
+ g_slice_free (P2tREdge, self->mirror);
+ g_slice_free (P2tREdge, self);
+}
+
+/* You can't remove just one edge from a triangulation. When you remove an edge,
+ * it's mirror is also removed! Calling this will also remove the edge from the
+ * points that form the edge.
+ *
+ * TODO: Merge some logic and fill in missing part with the edge_free function
+ */
+void
+p2tr_edge_remove (P2tREdge *self, P2tRTriangulation *T)
+{
+ p2tr_edge_remove_private (self, T);
+ p2tr_validate_triangulation (T);
+}
+
+static void
+p2tr_edge_remove_private (P2tREdge *self, P2tRTriangulation *T)
+{
+ P2tREdge *mir = self->mirror;
+
+ if (self->removed)
+ return;
+
+ if (self->tri != NULL)
+ p2tr_triangle_remove (self->tri, T);
+ p2tr_validate_triangulation (T);
+
+ if (mir->tri != NULL)
+ p2tr_triangle_remove (mir->tri, T);
+ p2tr_validate_triangulation (T);
+
+ self->removed = mir->removed = TRUE;
+
+ p2tr_validate_triangulation (T);
+ p2tr_point_remove_edge (p2tr_edge_get_start (self), self);
+ p2tr_validate_triangulation (T);
+ p2tr_point_remove_edge (p2tr_edge_get_start (mir), mir);
+ p2tr_validate_triangulation (T);
+
+ p2tr_triangulation_remove_ed (T, self);
+ p2tr_triangulation_remove_ed (T, mir);
+}
+
+/*
+ * DBG: different from source
+ */
+gboolean
+p2tr_edge_is_encroached_by (P2tREdge *self, P2tRPoint *other)
+{
+ if (p2tr_edge_diametral_circle_contains (self, other))
+ {
+ p2tr_debug ("The point ");
+ p2tr_debug_point (other, FALSE);
+ p2tr_debug (" encroaches ");
+ p2tr_debug_edge (self, TRUE);
+ return TRUE;
+ }
+ return FALSE;
+}
+
+/*
+ * DBG: different from source
+ */
+gboolean
+p2tr_edge_is_encroached (P2tREdge *self)
+{
+ if (self->tri != NULL)
+ {
+ P2tRPoint *w = p2tr_triangle_opposite_point (self->tri, self);
+ if (p2tr_edge_is_encroached_by (self, w))
+ return TRUE;
+ }
+
+ if (self->mirror->tri != NULL)
+ {
+ P2tRPoint *w = p2tr_triangle_opposite_point (self->mirror->tri, self);
+ if (p2tr_edge_is_encroached_by (self, w))
+ return TRUE;
+ }
+
+ p2tr_debug ("The edge ");
+ p2tr_debug_edge (self, FALSE);
+ p2tr_debug (" is not encroached!\n");
+
+ return FALSE;
+}
+
+gboolean
+p2tr_edge_diametral_circle_contains (P2tREdge *self, P2tRPoint *pt)
+{
+ /* a-----O-----b
+ * /
+ * /
+ * pt
+ *
+ * pt is in the diametral circle only if it's distance from O (the center of
+ * a and b) is equal/less than a's distance from O (that's the radius).
+ */
+ P2tRPoint *a = p2tr_edge_get_start (self);
+ P2tRPoint *b = p2tr_edge_get_end (self);
+
+ gdouble Ox = (a->x + b->x) / 2;
+ gdouble Oy = (a->y + b->y) / 2;
+
+ return (Ox - a->x) * (Ox - a->x) + (Oy - a->y) * (Oy - a->y)
+ >= (Ox - pt->x) * (Ox - pt->x) + (Oy - pt->y) * (Oy - pt->y);
+ /*
+ return (pt->y - a->y) * (pt->x - a->x)
+ * (pt->y - b->y) * (pt->x - b->x) <= 0;
+ */
+}
+
+gboolean
+p2tr_edge_diametral_lens_contains (P2tREdge *self, P2tRPoint *W)
+{
+ /*
+ * W
+ * /|\
+ * / | \
+ * /60|60\
+ * / | \
+ * /30 | 30\
+ * X-----O-----Y
+ * L L
+ *
+ * Non-Efficient: Calculate XW, and XO=YO
+ *
+ * |XO| ===> |XO| sqrt(3) ===> |XO|^2 3
+ * Make sure asin (----) >= 60Â ===> ---- >= ------- ===> ------ >= -
+ * |XW| ===> |XW| 2 ===> |XW|^2 4
+ *
+ * |YO| ===> |YO| sqrt(3) ===> |YO|^2 3
+ * Make sure asin (----) >= 60Â ===> ---- >= ------- ===> ------ >= -
+ * |YW| ===> |YW| 2 ===> |YW|^2 4
+ */
+
+ P2tRPoint *X = p2tr_edge_get_start (self);
+ P2tRPoint *Y = p2tr_edge_get_end (self);
+
+ gdouble XO2 = p2tr_edge_len_sq (self) / 4, YO2 = XO2;
+
+ gdouble XW2 = p2tr_math_edge_len_sq (X->x, X->y, W->x, W->y);
+ gdouble YW2 = p2tr_math_edge_len_sq (Y->x, Y->y, W->x, W->y);
+
+ return (XO2 / XW2 >= 0.75) && (YO2 / YW2 >= 0.75);
+}
+
+gdouble
+p2tr_edge_len_sq (P2tREdge *self)
+{
+ P2tRPoint *S = p2tr_edge_get_start (self);
+ P2tRPoint *E = p2tr_edge_get_end (self);
+ return p2tr_math_edge_len_sq (S->x,S->y,E->x,E->y);
+}
+
+void
+p2tr_edge_set_constrained (P2tREdge *self, gboolean b)
+{
+ self->constrained = self->mirror->constrained = b;
+}
+
+void
+p2tr_edge_set_delaunay (P2tREdge *self, gboolean b)
+{
+ self->delaunay = self->mirror->delaunay = b;
+}
+
+/* a = abs(E1.angle)
+ * b = abs(E2.angle)
+ *
+ * A is the angle we wish to find. Note the fact that we want
+ * to find the angle so that the edges go CLOCKWISE around it.
+ *
+ * Case 1: Signs of E1.angle and | Case 2: Signs of E1.angle and
+ * E2.angle agree | E2.angle disagree
+ * |
+ * A=a'+b=180-a+b | A=180-a-b
+ *
+ * ^^ |
+ * E2 // | *
+ * // | ^^ \\
+ * // \ | // A \\
+ * * A| | E1 // \_/ \\ E2
+ * /^^ / | // \\
+ * / || | //a vv
+ * / || E1 | ------------------
+ * / || | \b
+ * /b a'||a | \
+ * -------------- | \
+ * PRECONDITION: e1.getEnd() == e2.getStart()
+ */
+gdouble
+p2tr_angle_between (P2tREdge *e1, P2tREdge *e2)
+{
+ gdouble RET;
+
+ g_assert (p2tr_edge_get_end (e1) == p2tr_edge_get_start (e2));
+
+ if (e1->angle < 0)
+ {
+ if (e2->angle > 0)
+ return ABS (e1->angle) + ABS (e2->angle) - M_PI;
+ else
+ return ABS (e1->angle) - (ABS (e2->angle) - M_PI);
+ }
+ else
+ {
+ if (e2->angle > 0)
+ return M_PI - ABS (e1->angle) + ABS (e2->angle);
+ else
+ return M_PI - ABS (e1->angle) - ABS (e2->angle);
+ }
+
+ /* g_assert (RET + EPSILON2 >= 0 && RET <= M_PI + EPSILON2); */
+
+ return RET;
+}
+
+void
+p2tr_triangle_init (P2tRTriangle *self, P2tREdge *e1, P2tREdge *e2, P2tREdge *e3, P2tRTriangulation *T)
+{
+ P2tRPoint *A = p2tr_edge_get_end (e1);
+ P2tRPoint *B = p2tr_edge_get_end (e2);
+ P2tRPoint *C = p2tr_edge_get_end (e3);
+
+ /* Assert that edges do form a loop! */
+ p2tr_assert_and_explain (A == p2tr_edge_get_start (e2)
+ && B == p2tr_edge_get_start (e3)
+ && C == p2tr_edge_get_start (e1), "Edges form a loop!");
+
+ P2tROrientation o = p2tr_math_orient2d (A, B, C);
+
+ /*
+ * ^
+ * | \ | ^ \
+ * a | \ c ==> | a' | \ c'
+ * v \ | | \
+ * -----> | <--- v
+ * b | b'
+ *
+ * When found a CCW triangle with edges a-b-c, change it to
+ * a'-c'-b' and not a'-b'-c' !!!
+ */
+
+ p2tr_assert_and_explain (o != COLLINEAR, "No support for collinear points!");
+
+ if (o == CCW)
+ {
+ self->edges[0] = e1->mirror;
+ self->edges[1] = e3->mirror;
+ self->edges[2] = e2->mirror;
+ }
+ else
+ {
+ self->edges[0] = e1;
+ self->edges[1] = e2;
+ self->edges[2] = e3;
+ }
+
+ /* The triangle is now referenced by the person who requested it, and also by
+ * 3 edges. Also, the 3 edges are now referenced by the triangle.
+ */
+ self->edges[0]->tri = self->edges[1]->tri = self->edges[2]->tri = self;
+ self->_refcount = 4;
+ p2tr_edge_ref (self->edges[0]);
+ p2tr_edge_ref (self->edges[1]);
+ p2tr_edge_ref (self->edges[2]);
+
+ if (T != NULL)
+ {
+ p2tr_triangulation_add_tr (T, self);
+ }
+}
+
+P2tRTriangle*
+p2tr_triangle_new (P2tREdge *e1, P2tREdge *e2, P2tREdge *e3, P2tRTriangulation *T)
+{
+ P2tRTriangle *self = g_slice_new (P2tRTriangle);
+ p2tr_triangle_init (self, e1, e2, e3, T);
+ return self;
+}
+
+/* TODO: merge logic with the remove function */
+void
+p2tr_triangle_free (P2tRTriangle *self)
+{
+ g_assert (self->_refcount == 0);
+
+ p2tr_edge_unref (self->edges[0]);
+ p2tr_edge_unref (self->edges[1]);
+ p2tr_edge_unref (self->edges[2]);
+
+ g_slice_free (P2tRTriangle, self);
+}
+
+/*
+ * e0.end
+ * ^
+ * | \
+ * | \ e0 <=> e1.end
+ * e0 | \ e1 e1 <=> e2.end
+ * | \ e2 <=> e0.end
+ * <---- v
+ * e2.end e2 e1.end
+ */
+P2tRPoint*
+p2tr_triangle_opposite_point (P2tRTriangle *self, P2tREdge *e)
+{
+ if (self->edges[0] == e || self->edges[0] == e->mirror)
+ return p2tr_edge_get_end (self->edges[1]);
+ else if (self->edges[1] == e || self->edges[1] == e->mirror)
+ return p2tr_edge_get_end (self->edges[2]);
+ else if (self->edges[2] == e || self->edges[2] == e->mirror)
+ return p2tr_edge_get_end (self->edges[0]);
+
+ p2tr_assert_and_explain (FALSE, "Edge not in in triangle!");
+}
+
+P2tREdge*
+p2tr_triangle_opposite_edge (P2tRTriangle *self, P2tRPoint *pt)
+{
+ if (p2tr_edge_get_end (self->edges[0]) == pt)
+ return self->edges[2];
+ else if (p2tr_edge_get_end (self->edges[1]) == pt)
+ return self->edges[0];
+ else if (p2tr_edge_get_end (self->edges[2]) == pt)
+ return self->edges[1];
+
+ p2tr_assert_and_explain (FALSE, "Point not in in triangle!");
+}
+
+/* Return the smallest angle not seperating two input segments (Input segments
+ * can not be disconnected, so we can't fix a small angle between them)
+ */
+gdouble
+p2tr_triangle_smallest_non_seperating_angle (P2tRTriangle *self)
+{
+ gdouble minA = M_PI;
+
+ P2tREdge *e0 = self->edges[0];
+ P2tREdge *e1 = self->edges[1];
+ P2tREdge *e2 = self->edges[2];
+
+ if (! e0->mirror->constrained && ! e1->mirror->constrained)
+ minA = MIN (minA, p2tr_angle_between(self->edges[0], self->edges[1]));
+
+ if (! e1->mirror->constrained && ! e2->mirror->constrained)
+ minA = MIN (minA, p2tr_angle_between(self->edges[1], self->edges[2]));
+
+ if (! e2->mirror->constrained && ! e0->mirror->constrained)
+ minA = MIN (minA, p2tr_angle_between(self->edges[2], self->edges[0]));
+
+ return minA;
+}
+
+gdouble
+p2tr_triangle_shortest_edge_len (P2tRTriangle *self)
+{
+ gdouble l0 = p2tr_edge_len_sq (self->edges[0]);
+ gdouble l1 = p2tr_edge_len_sq (self->edges[1]);
+ gdouble l2 = p2tr_edge_len_sq (self->edges[2]);
+
+ return sqrt (MIN (l0, MIN (l1, l2)));
+}
+
+gdouble
+p2tr_triangle_longest_edge_len (P2tRTriangle *self)
+{
+ gdouble l0 = p2tr_edge_len_sq (self->edges[0]);
+ gdouble l1 = p2tr_edge_len_sq (self->edges[1]);
+ gdouble l2 = p2tr_edge_len_sq (self->edges[2]);
+
+ return sqrt (MAX (l0, MAX (l1, l2)));
+}
+
+void
+p2tr_triangle_angles (P2tRTriangle *self, gdouble dest[3])
+{
+ dest[0] = p2tr_angle_between(self->edges[0], self->edges[1]);
+ dest[1] = p2tr_angle_between(self->edges[1], self->edges[2]);
+ dest[2] = p2tr_angle_between(self->edges[2], self->edges[0]);
+}
+
+gdouble
+p2tr_triangle_get_angle_at (P2tRTriangle *self, P2tRPoint* pt)
+{
+ if (pt == self->edges[0]->end)
+ return p2tr_angle_between(self->edges[0], self->edges[1]);
+ else if (pt == self->edges[1]->end)
+ return p2tr_angle_between(self->edges[1], self->edges[2]);
+ else if (pt == self->edges[2]->end)
+ return p2tr_angle_between(self->edges[2], self->edges[0]);
+ else
+ p2tr_assert_and_explain (FALSE, "Trying to get the angle at a point not in the tri!\n");
+}
+
+/*
+ * TODO: merge logic with the free function
+ */
+void
+p2tr_triangle_remove (P2tRTriangle *self, P2tRTriangulation *T)
+{
+ p2tr_debug ("Removing a triangle\n");
+
+ if (T != NULL)
+ p2tr_triangulation_remove_tr (T, self);
+
+ self->edges[0]->tri = NULL;
+ p2tr_triangle_unref (self);
+
+ self->edges[1]->tri = NULL;
+ p2tr_triangle_unref (self);
+
+ self->edges[2]->tri = NULL;
+ p2tr_triangle_unref (self);
+
+}
+
+void
+p2tr_triangle_circumcircle (P2tRTriangle *self, P2tRCircle *dest)
+{
+ P2tRPoint *A = p2tr_edge_get_end (self->edges[2]);
+ P2tRPoint *B = p2tr_edge_get_end (self->edges[0]);
+ P2tRPoint *C = p2tr_edge_get_end (self->edges[1]);
+
+ gdouble Anorm = A->x * A->x + A->y * A->y;
+ gdouble Bnorm = B->x * B->x + B->y * B->y;
+ gdouble Cnorm = C->x * C->x + C->y * C->y;
+
+ gdouble D = 2*(A->x * (B->y - C->y) + B->x * (C->y - A->y) + C->x * (A->y - B->y));
+
+ dest->x = (Anorm * (B->y - C->y) + Bnorm * (C->y - A->y) + Cnorm * (A->y - B->y)) / D;
+ dest->y = -(Anorm * (B->x - C->x) + Bnorm * (C->x - A->x) + Cnorm * (A->x - B->x)) / D;
+
+ dest->radius = sqrt (p2tr_math_edge_len_sq (A->x, A->y, dest->x, dest->y));
+}
+
+gboolean
+p2tr_triangle_is_circumcenter_inside (P2tRTriangle *self)
+{
+ gdouble angles[3];
+
+ p2tr_triangle_angles (self, angles);
+
+ return MAX (angles[0], MAX (angles[1], angles[2])) < M_PI / 2;
+}
+
+
+/*
+ * P0
+ * ^ \
+ * / \
+ * e2/ \e0
+ * / *C \
+ * / v
+ * P2 <------- P1
+ * e1
+ *
+ * DBG: different from source
+ */
+void
+p2tr_triangle_subdivide (P2tRTriangle *self, P2tRPoint *C, P2tRTriangulation *T, P2tRTriangle *dest_new[3])
+{
+ P2tREdge *e0 = self->edges[0];
+ P2tREdge *e1 = self->edges[1];
+ P2tREdge *e2 = self->edges[2];
+
+ P2tREdge *CP0, *CP1, *CP2;
+
+ P2tRPoint *P0 = p2tr_edge_get_end (e2);
+ P2tRPoint *P1 = p2tr_edge_get_end (e0);
+ P2tRPoint *P2 = p2tr_edge_get_end (e1);
+
+ P2tRTriangle *t0, *t1, *t2;
+
+ if (C == NULL)
+ {
+ P2tRCircle cc;
+ p2tr_triangle_circumcircle (self, &cc);
+ C = p2tr_point_new (cc.x, cc.y);
+ }
+
+ g_assert (p2tr_triangle_contains_pt (self, C));
+
+ p2tr_validate_triangulation (T);
+ p2tr_triangle_remove (self, T);
+ p2tr_validate_triangulation (T);
+
+ CP0 = p2tr_point_edge_to (C, P0);
+ CP1 = p2tr_point_edge_to (C, P1);
+ CP2 = p2tr_point_edge_to (C, P2);
+
+ t0 = p2tr_triangle_new (CP0, e0, CP1->mirror, T);
+ p2tr_validate_triangulation (T);
+ t1 = p2tr_triangle_new (CP1, e1, CP2->mirror, T);
+ p2tr_validate_triangulation (T);
+ t2 = p2tr_triangle_new (CP2, e2, CP0->mirror, T);
+ p2tr_validate_triangulation (T);
+
+ if (dest_new != NULL)
+ {
+ dest_new[0] = t0;
+ dest_new[1] = t1;
+ dest_new[2] = t2;
+ }
+ else
+ {
+ p2tr_triangle_unref (t0);
+ p2tr_triangle_unref (t1);
+ p2tr_triangle_unref (t2);
+ }
+}
+
+/* Based on http://www.blackpawn.com/texts/pointinpoly/default.html */
+gboolean
+p2tr_triangle_contains_pt (P2tRTriangle *self, P2tRPoint *P)
+{
+ P2tRPoint *A = p2tr_edge_get_end (self->edges[2]);
+ P2tRPoint *B = p2tr_edge_get_end (self->edges[0]);
+ P2tRPoint *C = p2tr_edge_get_end (self->edges[1]);
+
+ gdouble v0x = C->x - A->x;
+ gdouble v0y = C->y - A->y;
+ gdouble v1x = B->x - A->x;
+ gdouble v1y = B->y - A->y;
+ gdouble v2x = P->x - A->x;
+ gdouble v2y = P->y - A->y;
+
+ /* Compute dot products */
+ gdouble dot00 = v0x * v0x + v0y * v0y;
+ gdouble dot01 = v0x * v1x + v0y * v1y;
+ gdouble dot02 = v0x * v2x + v0y * v2y;
+ gdouble dot11 = v1x * v1x + v1y * v1y;
+ gdouble dot12 = v1x * v2x + v1y * v2y;
+
+ /* Compute barycentric coordinates */
+ gdouble invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
+ gdouble u = (dot11 * dot02 - dot01 * dot12) * invDenom;
+ gdouble v = (dot00 * dot12 - dot01 * dot02) * invDenom;
+
+ /* Check if point is in triangle */
+ return (u > -EPSILON2) && (v > -EPSILON2) && (u + v < 1 + EPSILON2);
+}
+
+
+gboolean
+p2tr_triangulation_legalize (P2tRTriangulation *T,
+ P2tRTriangle *tr)
+{
+ /* Remember! Edges in each triangle are ordered counter clockwise!
+ * q
+ * *-----------*a shared_tr = p->q = tr->edges[i]
+ * |\ / shared_ot = q->p = tr->edges[i]->mirror
+ * | \ / ot = shared_ot->tri
+ * | \ tr /
+ * | \ /
+ * | ot \ /
+ * *-----*
+ * b p
+ *
+ * Also note that we can not flip in cases of concave quads! We must check
+ * that the angles at p and at q are both smaller than 180Â.
+ */
+ gint i;
+
+ /* First, make sure this triangle still exists */
+ if (! p2tr_hash_set_contains (T->tris, tr))
+ return FALSE;
+
+ /* To legalize a triangle we start by finding if any of the three edges
+ * violate the Delaunay condition
+ */
+ for (i = 0; i < 3; i++)
+ {
+ P2tREdge *shared_tr = tr->edges[i];
+ P2tREdge *shared_ot = shared_tr->mirror;
+ P2tRTriangle* ot = shared_ot->tri;
+
+ // If this is a Constrained Edge or a Delaunay Edge (only during
+ // recursive legalization) then we should not try to legalize
+ if (shared_tr->delaunay || shared_tr->constrained)
+ continue;
+
+ if (ot)
+ {
+ P2tRPoint* p = p2tr_edge_get_end (shared_ot);
+ P2tRPoint* q = p2tr_edge_get_end (shared_tr);
+ P2tRPoint* a = p2tr_triangle_opposite_point (tr, shared_tr);
+ P2tRPoint* b = p2tr_triangle_opposite_point (ot, shared_ot);
+ // We already checked if it's constrained or delaunay for the case of
+ // skipping this tri
+
+ // Check for concave quads
+ if (p2tr_triangle_get_angle_at (tr, p) + p2tr_triangle_get_angle_at (ot, p) >= M_PI
+ || p2tr_triangle_get_angle_at (tr, q) + p2tr_triangle_get_angle_at (ot, q) >= M_PI)
+ continue;
+
+ gboolean inside = p2tr_math_incircle (p, a, q, b);
+
+ if (inside)
+ {
+ P2tREdge *ab;
+ P2tREdge *bq, *qa, *pb, *ap;
+ P2tRTriangle *abq, *pba;
+
+ // First of all, remove the edge
+ p2tr_edge_remove (shared_tr, T);
+
+ // Create a new matching rotated edge
+ ab = p2tr_edge_new (a, b);
+
+ // Mark it as Delaunay
+ p2tr_edge_set_delaunay (ab, TRUE);
+
+ // Create the triangles
+ bq = p2tr_point_edge_to (b,q);
+ qa = p2tr_point_edge_to (q,a);
+ abq = p2tr_triangle_new (ab, bq, qa, T);
+
+ pb = p2tr_point_edge_to (p,b);
+ ap = p2tr_point_edge_to (a,p);
+ pba = p2tr_triangle_new (pb, ab->mirror, ap, T);
+
+ // Unref stuff
+ p2tr_edge_unref (bq);
+ p2tr_edge_unref (qa);
+
+ p2tr_edge_unref (pb);
+ p2tr_edge_unref (ap);
+
+ // Now, legalize these two triangles:
+ p2tr_triangulation_legalize (T, abq);
+ p2tr_triangle_unref (abq);
+
+ // Legalization may have killed the other triangle, but that's OK
+ // since legalization makes sure the triangle exists
+ p2tr_triangulation_legalize (T, pba);
+ p2tr_triangle_unref (pba);
+
+ // Reset the Delaunay edges, since they only are valid Delaunay edges
+ // until we add a new triangle or point.
+ // XXX: need to think about this. Can these edges be tried after we
+ // return to previous recursive level?
+ p2tr_edge_set_delaunay (ab, FALSE);
+
+ // If triangle have been legalized no need to check the other edges since
+ // the recursive legalization will handles those so we can end here.
+ return TRUE;
+ }
+ }
+ }
+ return FALSE;
+}
+
+/* * A2
+ * / \
+ * / \
+ * / T2 \
+ * B *------>* C e = B->C
+ * ^ T1 /
+ * \ /
+ * \ v
+ * * A1
+ */
+void
+p2tr_triangulation_flip_fix (P2tREdge *e, P2tRTriangulation *T)
+{
+ P2tRTriangle *T1 = e->tri;
+ P2tRTriangle *T2 = e->mirror->tri;
+
+ /* Removed edges do not need fixing, constrained edges can not be flipped, and
+ * edges that were already flipped should not be flipped again.
+ *
+ * Finally, edges must have a triangle on both sides of them (such a situation
+ * can occur during the execution of the algorithms, without the edge being
+ * constrained) in order to be flipped
+ */
+ if (e->removed || e->constrained || e->delaunay || T1 == NULL || T2 == NULL)
+ return;
+
+ P2tRPoint *A1 = p2tr_triangle_opposite_point (T1, e);
+ P2tRPoint *A2 = p2tr_triangle_opposite_point (T2, e);
+ P2tRPoint *B = p2tr_edge_get_start (e);
+ P2tRPoint *C = p2tr_edge_get_end (e);
+
+ /* We can't do a flip fix in cases where the two triangles form together a
+ * concave quad!
+ *
+ * To check this, see if the sum of the two angles at any of the edges is
+ * larger than 180 degress.
+ */
+ P2tREdge *BC = p2tr_point_edge_to (B, C);
+
+ p2tr_validate_triangulation (T);
+ P2tREdge *CA2 = p2tr_point_edge_to (C, A2);
+ p2tr_validate_triangulation (T);
+ P2tREdge *CA1 = p2tr_point_edge_to (C, A1);
+ p2tr_validate_triangulation (T);
+
+ P2tREdge *BA2 = p2tr_point_edge_to (B, A2);
+ p2tr_validate_triangulation (T);
+ P2tREdge *BA1 = p2tr_point_edge_to (B, A1);
+ p2tr_validate_triangulation (T);
+
+ gdouble BCA2 = p2tr_angle_between (CA2->mirror,BC->mirror);
+ gdouble BCA1 = p2tr_angle_between (BC,CA1);
+
+ gdouble CBA2 = p2tr_angle_between (BC->mirror,BA2);
+ gdouble CBA1 = p2tr_angle_between (BA1->mirror,BC);
+
+ if (BCA2 + BCA1 > M_PI - EPSILON2 || CBA2 + CBA1 > M_PI - EPSILON2)
+ {
+ p2tr_debug ("Won't fix concave quads!\n");
+
+ /* In the case of concave quads, mark the edge as non flip-able */
+ p2tr_edge_set_delaunay (BC, TRUE);
+
+ /* Now fix the other edges */
+ p2tr_triangulation_flip_fix (BA2,T);
+ p2tr_triangulation_flip_fix (BA1,T);
+ p2tr_triangulation_flip_fix (CA2,T);
+ p2tr_triangulation_flip_fix (CA1,T);
+
+ /* Restore */
+ p2tr_edge_set_delaunay (BC, FALSE);
+ }
+
+ /* Check if empty circle property does not hold */
+ else if (p2tr_math_incircle (A1,C,B,A2) != INCIRCLE_OUTSIDE
+ || p2tr_math_incircle (A2,B,C,A1) != INCIRCLE_OUTSIDE)
+ {
+ P2tREdge *A2A1;
+ P2tRTriangle *Tn1, *Tn2;
+
+ p2tr_validate_triangulation (T);
+ p2tr_edge_remove (e, T);
+ p2tr_validate_triangulation (T);
+
+ A2A1 = p2tr_point_edge_to (A2, A1);
+ p2tr_validate_triangulation (T);
+
+ Tn1 = p2tr_triangle_new (A2A1, BA1->mirror, BA2, T);
+ p2tr_validate_triangulation (T);
+ Tn2 = p2tr_triangle_new (A2A1, CA1->mirror, CA2, T);
+ p2tr_validate_triangulation (T);
+
+ p2tr_edge_set_delaunay (A2A1, TRUE);
+
+ p2tr_triangulation_flip_fix (BA2,T);
+ p2tr_triangulation_flip_fix (CA2,T);
+
+ p2tr_triangulation_flip_fix (BA1->mirror,T);
+ p2tr_triangulation_flip_fix (CA1->mirror,T);
+
+ p2tr_edge_set_delaunay (A2A1, FALSE);
+ }
+}
+
+/* TODO: UNEFFICIENT LIKE HELL! */
+gboolean
+p2tr_edges_intersect (P2tREdge *e1, P2tREdge *e2)
+{
+ P2tRPoint *e1S = p2tr_edge_get_start (e1);
+ P2tRPoint *e1E = p2tr_edge_get_end (e1);
+ P2tRPoint *e2S = p2tr_edge_get_start (e1);
+ P2tRPoint *e2E = p2tr_edge_get_end (e1);
+
+ return p2tr_math_orient2d (e1S,e1E,e2S) != p2tr_math_orient2d (e1S,e1E,e2E)
+ && p2tr_math_orient2d (e2S,e2E,e1S) != p2tr_math_orient2d (e2S,e2E,e1E);
+}
+
+P2tRPoint *
+p2tr_triangle_median_pt (P2tRTriangle *self)
+{
+ P2tRPoint *A = p2tr_edge_get_end (self->edges[2]);
+ P2tRPoint *B = p2tr_edge_get_end (self->edges[0]);
+ P2tRPoint *C = p2tr_edge_get_end (self->edges[1]);
+
+ return p2tr_point_new ((A->x+B->x+C->x)/3,(A->y+B->y+C->y)/3);
+}
+
+/* TODO: this computation can be much optimized using math rules! */
+P2tRPoint *
+p2tr_edge_concentric_center (P2tREdge *e)
+{
+ gdouble x0 = p2tr_edge_get_start(e)->x, y0 = p2tr_edge_get_start(e)->y;
+ gdouble x1 = p2tr_edge_get_end(e)->x, y1 = p2tr_edge_get_end(e)->y;
+ gdouble fraction;
+
+ gdouble l = sqrt (p2tr_edge_len_sq (e));
+ /* Note that in the braces below, it's L and not 1 */
+ gdouble lPart = pow (2, round (log2 (l/2)));
+
+ while (lPart >= l)
+ lPart /= 2
+ ;
+ fraction = lPart / l;
+
+ return p2tr_point_new (x0 + fraction * (x1 - x0), y0 + fraction * (y1 - y0));
+}
+
+P2tRTriangulation*
+p2tr_triangulate (GList *p2trpoints)
+{
+ P2tPointPtrArray D = g_ptr_array_new ();
+ GList *iter;
+
+ P2tRTriangulation *T = p2tr_triangulation_new ();
+
+ GHashTable *map = g_hash_table_new_full (g_direct_hash, g_direct_equal, NULL, NULL);
+
+ foreach (iter, p2trpoints)
+ {
+ P2tRPoint *pt = (P2tRPoint*) iter->data;
+ P2tPoint *opt = p2t_point_new_dd (pt->x, pt->y);
+
+ g_hash_table_insert (map, opt, pt);
+ g_ptr_array_add (D, opt);
+ }
+
+ P2tCDT *cdt = p2t_cdt_new (D);
+ p2t_cdt_triangulate (cdt);
+
+ P2tTrianglePtrArray pt = p2t_cdt_get_triangles (cdt);
+ int i;
+ for (i = 0; i < pt->len; i++)
+ {
+ P2tTriangle *t = triangle_index (pt,i);
+ P2tRPoint *p0 = g_hash_table_lookup (map, p2t_triangle_get_point (t, 0));
+ P2tRPoint *p1 = g_hash_table_lookup (map, p2t_triangle_get_point (t, 1));
+ P2tRPoint *p2 = g_hash_table_lookup (map, p2t_triangle_get_point (t, 2));
+ p2tr_triangle_new (p2tr_point_edge_to (p0, p1),
+ p2tr_point_edge_to (p1, p2),
+ p2tr_point_edge_to (p2, p0), T);
+ }
+
+ p2t_cdt_free (cdt);
+
+ for (i = 0; i < D->len; i++)
+ p2t_point_free (point_index (D, i));
+
+ g_ptr_array_free (D, TRUE);
+
+ g_hash_table_destroy (map);
+
+ return T;
+
+}
+
+P2tRTriangulation *
+p2tr_triangulation_new ()
+{
+ P2tRTriangulation *self = g_slice_new (P2tRTriangulation);
+ self->tris = p2tr_hash_set_set_new (g_direct_hash, g_direct_equal, NULL);
+ self->pts = p2tr_hash_set_set_new (g_direct_hash, g_direct_equal, NULL);
+ self->edges = p2tr_hash_set_set_new (g_direct_hash, g_direct_equal, NULL);
+ return self;
+}
+
+P2tRTriangulation*
+p2tr_triangulation_free (P2tRTriangulation *self)
+{
+ P2trHashSetIter siter;
+
+ P2tRTriangle *tr;
+ P2tREdge *ed;
+ P2tRPoint *pt;
+
+ p2tr_hash_set_iter_init (&siter, self->tris);
+ while (p2tr_hash_set_iter_next (&siter, (gpointer*) &tr))
+ {
+ p2tr_triangle_unref (tr);
+ }
+
+ p2tr_hash_set_iter_init (&siter, self->edges);
+ while (p2tr_hash_set_iter_next (&siter, (gpointer*) &ed))
+ {
+ p2tr_edge_unref (ed);
+ }
+
+ p2tr_hash_set_iter_init (&siter, self->pts);
+ while (p2tr_hash_set_iter_next (&siter, (gpointer*) &pt))
+ {
+ p2tr_point_unref (pt);
+ }
+
+ g_hash_table_destroy (self->tris);
+ g_hash_table_destroy (self->edges);
+ g_hash_table_destroy (self->pts);
+
+ g_slice_free (P2tRTriangulation, self);
+}
+
+P2tRTriangulation*
+p2tr_triangulateA (P2tRPoint **p2trpoints, gint count)
+{
+ GList *A = NULL;
+ P2tRTriangulation *T;
+ int i;
+ for (i = 0; i < count; i++)
+ {
+ A = g_list_prepend (A, p2trpoints[count-i-1]);
+ }
+
+ T = p2tr_triangulate (A);
+
+ g_list_free (A);
+
+ return T;
+
+}
+
+#define DEBUG FALSE
+gboolean
+p2tr_validate_triangulation (P2tRTriangulation* T)
+{
+#if DEBUG
+ P2trHashSetIter iter;
+ GList *L;
+ P2tRTriangle *t;
+
+ p2tr_hash_set_iter_init (&iter, T->tris);
+
+ while (p2tr_hash_set_iter_next (&iter, (gpointer*)&t))
+ {
+ int i;
+ for (i = 0; i < 3; i++)
+ {
+ P2tRPoint *S = p2tr_edge_get_start (t->edges[i]);
+ P2tRPoint *E = p2tr_edge_get_end (t->edges[i]);
+
+ p2tr_assert_and_explain (p2tr_point_has_edge_to (S, E), "edge connectivity");
+ p2tr_assert_and_explain (p2tr_point_has_edge_to (E, S), "edge connectivity");
+ p2tr_assert_and_explain (t->edges[i]->tri == t, "triangle <-> edge");
+ }
+ }
+#endif
+ return TRUE;
+
+}
+
+gboolean
+p2tr_validate_edge (P2tREdge* e)
+{
+ if (e->constrained != e->mirror->constrained)
+ {
+ G_BREAKPOINT();
+ g_assert (FALSE);
+ }
+ if (e->tri == NULL && ! e->constrained)
+ {
+ G_BREAKPOINT();
+ g_assert (FALSE);
+ }
+
+ if (e->mirror->constrained != e->mirror->mirror->constrained)
+ {
+ G_BREAKPOINT();
+ g_assert (FALSE);
+ }
+ if (e->mirror->tri == NULL && ! e->mirror->constrained)
+ {
+ G_BREAKPOINT();
+ g_assert (FALSE);
+ }
+
+ return TRUE;
+
+}
+
+
+void
+p2tr_debug_point (P2tRPoint* pt, gboolean newline)
+{
+ p2tr_debug ("@PT(%g,%g)", pt->x, pt->y);
+ if (newline) p2tr_debug ("\n");
+}
+
+void
+p2tr_debug_edge (P2tREdge* ed, gboolean newline)
+{
+ p2tr_debug ("@ED(");
+ p2tr_debug_point (p2tr_edge_get_start (ed), FALSE);
+ p2tr_debug ("->");
+ p2tr_debug_point (p2tr_edge_get_end (ed), FALSE);
+ p2tr_debug (")");
+ if (newline) p2tr_debug ("\n");
+}
+
+void
+p2tr_debug_tri (P2tRTriangle* tr, gboolean newline)
+{
+ p2tr_debug ("@TR(");
+ p2tr_debug_edge (tr->edges[0], FALSE);
+ p2tr_debug ("~");
+ p2tr_debug_edge (tr->edges[1], FALSE);
+ p2tr_debug ("~");
+ p2tr_debug_edge (tr->edges[2], FALSE);
+ p2tr_debug (")");
+ if (newline) p2tr_debug ("\n");
+}
+
diff --git a/operations/common/seamless-clone/poly2tri-c/refine/triangulation.h b/operations/common/seamless-clone/poly2tri-c/refine/triangulation.h
new file mode 100755
index 0000000..8dd56c9
--- /dev/null
+++ b/operations/common/seamless-clone/poly2tri-c/refine/triangulation.h
@@ -0,0 +1,330 @@
+/*
+ * This file is a part of Poly2Tri-C - The C port of the Poly2Tri library
+ * Porting to C done by (c) Barak Itkin <lightningismyname gmail com>
+ * http://code.google.com/p/poly2tri-c/
+ *
+ * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
+ * http://code.google.com/p/poly2tri/
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without modification,
+ * are permitted provided that the following conditions are met:
+ *
+ * * Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright notice,
+ * this list of conditions and the following disclaimer in the documentation
+ * and/or other materials provided with the distribution.
+ * * Neither the name of Poly2Tri nor the names of its contributors may be
+ * used to endorse or promote products derived from this software without specific
+ * prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+#ifndef __POLY2TRI_C_REFINE_TRIANGULATION_H__
+#define __POLY2TRI_C_REFINE_TRIANGULATION_H__
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif
+
+#include <glib.h>
+#include "../common/utils.h"
+#include "utils.h"
+#include <stdio.h>
+
+#define EPSILON2 (1e-6)
+
+#define p2tr_debug //g_printerr
+
+#define p2tr_assert_and_explain(expr,err) \
+do { \
+ if (!(expr)) \
+ { \
+ g_warning (err); \
+ g_assert (FALSE); \
+ } \
+} while (FALSE)
+
+
+typedef struct P2tRTriangle_ P2tRTriangle;
+typedef struct P2tREdge_ P2tREdge;
+typedef struct P2tRPoint_ P2tRPoint;
+typedef struct P2tRTriangulation_ P2tRTriangulation;
+typedef struct P2tRCircle_ P2tRCircle;
+
+/* ########################################################################## */
+/* Common math */
+/* ########################################################################## */
+
+gdouble p2tr_math_normalize_angle (gdouble angle);
+
+/* TODO: try to somehow merge with the matching functions in utils.c */
+typedef P2tOrientation P2tROrientation;
+
+typedef enum
+{
+ INCIRCLE_ON,
+ INCIRCLE_INSIDE,
+ INCIRCLE_OUTSIDE
+} P2tRInCircle;
+
+P2tROrientation p2tr_math_orient2d (P2tRPoint* pa, P2tRPoint* pb, P2tRPoint* pc);
+
+P2tRInCircle p2tr_math_incircle (P2tRPoint* a, P2tRPoint* b, P2tRPoint* c, P2tRPoint* d);
+
+gdouble p2tr_math_edge_len_sq (gdouble x1, gdouble y1, gdouble x2, gdouble y2);
+
+/* ########################################################################## */
+/* Triangulation struct */
+/* ########################################################################## */
+
+struct P2tRTriangulation_
+{
+ P2tRHashSet *pts;
+ P2tRHashSet *edges;
+ P2tRHashSet *tris;
+};
+
+void p2tr_triangulation_remove_pt (P2tRTriangulation *self, P2tRPoint *pt);
+void p2tr_triangulation_remove_ed (P2tRTriangulation *self, P2tREdge *ed);
+void p2tr_triangulation_remove_tr (P2tRTriangulation *self, P2tRTriangle *tr);
+
+void p2tr_triangulation_add_pt (P2tRTriangulation *self, P2tRPoint *pt);
+void p2tr_triangulation_add_ed (P2tRTriangulation *self, P2tREdge *ed);
+void p2tr_triangulation_add_tr (P2tRTriangulation *self, P2tRTriangle *tr);
+
+/* ########################################################################## */
+/* Point struct */
+/* ########################################################################## */
+
+struct P2tRPoint_
+{
+ gdouble x;
+ gdouble y;
+ GList *edges;
+ guint _refcount;
+};
+
+static void p2tr_point_init (P2tRPoint *self, gdouble x, gdouble y);
+
+P2tRPoint* p2tr_point_new (gdouble x, gdouble y);
+
+static void p2tr_point_add_edge (P2tRPoint *self, P2tREdge *edge);
+
+void p2tr_point_remove_edge (P2tRPoint *self, P2tREdge *edge);
+
+void p2tr_point_remove (P2tRPoint *self, P2tRTriangulation *T);
+
+P2tREdge* p2tr_point_edge_to (P2tRPoint *self, P2tRPoint *end);
+
+P2tREdge* p2tr_point_has_edge_to (P2tRPoint *self, P2tRPoint *end);
+
+P2tREdge* p2tr_point_edgeccw (P2tRPoint *self, P2tREdge *edge);
+
+P2tREdge* p2tr_point_edgecw (P2tRPoint *self, P2tREdge *edge);
+
+gboolean p2tr_point_is_in_cluster (P2tRPoint *self, P2tREdge *e);
+
+GList* p2tr_point_get_cluster (P2tRPoint *self, P2tREdge *e, gdouble *angle);
+
+gboolean p2tr_point_is_fully_in_domain (P2tRPoint *self);
+
+void p2tr_point_free (P2tRPoint *self);
+
+#define p2tr_point_ref(pt) ((pt)->_refcount++)
+
+#define p2tr_point_unref(pt) \
+do { \
+ if ((--(pt)->_refcount) == 0) \
+ { \
+ p2tr_point_free ((pt)); \
+ } \
+} while (FALSE)
+
+
+/* ########################################################################## */
+/* Edge struct */
+/* ########################################################################## */
+
+#define P2TR_EDGE(e) ((P2tREdge*)(e))
+
+struct P2tREdge_
+{
+ P2tRPoint *end;
+ gdouble angle;
+
+ P2tREdge *mirror;
+ P2tRTriangle *tri;
+
+ gboolean delaunay;
+ gboolean constrained;
+
+ gboolean removed;
+
+ /* Note that this count does not include the pointing from the mirror edge */
+ guint _refcount;
+};
+
+P2tREdge* p2tr_edge_new (P2tRPoint *start, P2tRPoint *end);
+
+P2tREdge* p2tr_edge_new_private (P2tRPoint *start, P2tRPoint *end, gboolean mirror);
+
+static void p2tr_edge_init (P2tREdge *self, P2tRPoint *start, P2tRPoint *end);
+
+static void p2tr_edge_init_private (P2tREdge *self, P2tRPoint *start, P2tRPoint *end, gboolean mirror);
+
+void p2tr_edge_remove (P2tREdge *self, P2tRTriangulation *T);
+
+static void p2tr_edge_remove_private (P2tREdge *self, P2tRTriangulation *T);
+
+gboolean p2tr_edge_is_encroached_by (P2tREdge *self, P2tRPoint *other);
+
+gboolean p2tr_edge_is_encroached (P2tREdge *self);
+
+gboolean p2tr_edge_diametral_lens_contains (P2tREdge *self, P2tRPoint *W);
+
+gboolean p2tr_edge_diametral_circle_contains (P2tREdge *self, P2tRPoint *pt);
+
+gdouble p2tr_edge_len_sq (P2tREdge *self);
+
+void p2tr_edge_set_constrained (P2tREdge *self, gboolean b);
+
+void p2tr_edge_set_delaunay (P2tREdge *self, gboolean b);
+
+/* Note that you can't really free one edge; Freeing will happen when both
+ * have no references to
+ */
+void p2tr_edge_free (P2tREdge *self);
+
+#define p2tr_edge_ref(ed) ((ed)->_refcount++)
+
+#define p2tr_edge_unref(ed) \
+do { \
+ if ((--(ed)->_refcount) == 0) \
+ { \
+ p2tr_edge_free ((ed)); \
+ } \
+} while (FALSE)
+
+#define p2tr_edgelist_ccw(elist,e) P2TR_EDGE(g_list_cyclic_next((elist),(e))->data)
+#define p2tr_edgelist_cw(elist,e) P2TR_EDGE(g_list_cyclic_prev((elist),(e))->data)
+
+#define p2tr_edge_get_start(e) ((e)->mirror->end)
+#define p2tr_edge_get_end(e) ((e)->end)
+
+/* ########################################################################## */
+/* Triangle struct */
+/* ########################################################################## */
+
+struct P2tRTriangle_
+{
+ P2tREdge *edges[3];
+ guint _refcount;
+};
+
+struct P2tRCircle_
+{
+ gdouble x;
+ gdouble y;
+
+ gdouble radius;
+};
+
+gdouble p2tr_angle_between (P2tREdge *e1, P2tREdge *e2);
+
+void p2tr_triangle_init (P2tRTriangle *self, P2tREdge *e1, P2tREdge *e2, P2tREdge *e3, P2tRTriangulation *T);
+
+P2tRTriangle* p2tr_triangle_new (P2tREdge *e1, P2tREdge *e2, P2tREdge *e3, P2tRTriangulation *T);
+
+void p2tr_triangle_free (P2tRTriangle *self);
+
+P2tRPoint* p2tr_triangle_opposite_point (P2tRTriangle *self, P2tREdge *e);
+
+P2tREdge* p2tr_triangle_opposite_edge (P2tRTriangle *self, P2tRPoint *pt);
+
+gdouble p2tr_triangle_smallest_non_seperating_angle (P2tRTriangle *self);
+
+gdouble p2tr_triangle_shortest_edge_len (P2tRTriangle *self);
+
+gdouble p2tr_triangle_longest_edge_len (P2tRTriangle *self);
+
+void p2tr_triangle_angles (P2tRTriangle *self, gdouble dest[3]);
+
+gdouble p2tr_triangle_get_angle_at (P2tRTriangle *self, P2tRPoint* pt);
+
+void p2tr_triangle_remove (P2tRTriangle *self, P2tRTriangulation *T);
+
+void p2tr_triangle_circumcircle (P2tRTriangle *self, P2tRCircle *dest);
+
+gboolean p2tr_triangle_is_circumcenter_inside (P2tRTriangle *self);
+
+void p2tr_triangle_subdivide (P2tRTriangle *self, P2tRPoint *C, P2tRTriangulation *T, P2tRTriangle *dest_new[3]);
+
+gboolean p2tr_triangle_contains_pt (P2tRTriangle *self, P2tRPoint *P);
+
+void p2tr_triangulation_flip_fix (P2tREdge *e, P2tRTriangulation *T);
+
+gboolean p2tr_edges_intersect (P2tREdge *e1, P2tREdge *e2);
+
+P2tRPoint *p2tr_triangle_median_pt (P2tRTriangle *self);
+
+P2tRPoint *p2tr_edge_concentric_center (P2tREdge *e);
+
+P2tRTriangulation* p2tr_triangulate (GList *p2trpoints);
+
+P2tRTriangulation* p2tr_triangulateA (P2tRPoint **p2trpoints, gint count);
+
+gboolean p2tr_validate_triangulation (P2tRTriangulation* T);
+
+gboolean p2tr_validate_edge (P2tREdge* e);
+
+gboolean p2tr_false_delta (P2tRTriangle *t);
+
+#define p2tr_triangle_ref(tr) ((tr)->_refcount++)
+
+#define p2tr_triangle_unref(tr) \
+do { \
+ if ((--(tr)->_refcount) == 0) \
+ { \
+ p2tr_triangle_free ((tr)); \
+ } \
+} while (FALSE)
+
+
+
+
+
+P2tRTriangulation*
+p2tr_triangulation_free (P2tRTriangulation *self);
+
+P2tRTriangulation*
+p2tr_triangulation_new ();
+
+
+
+
+void p2tr_debug_point (P2tRPoint* pt, gboolean newline);
+
+void p2tr_debug_edge (P2tREdge* ed, gboolean newline);
+
+void p2tr_debug_tri (P2tRTriangle* tr, gboolean newline);
+
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* TRIANGULATION_H */
\ No newline at end of file
diff --git a/operations/common/seamless-clone/poly2tri-c/refine/utils.h b/operations/common/seamless-clone/poly2tri-c/refine/utils.h
new file mode 100755
index 0000000..a846155
--- /dev/null
+++ b/operations/common/seamless-clone/poly2tri-c/refine/utils.h
@@ -0,0 +1,71 @@
+/*
+ * This file is a part of Poly2Tri-C - The C port of the Poly2Tri library
+ * Porting to C done by (c) Barak Itkin <lightningismyname gmail com>
+ * http://code.google.com/p/poly2tri-c/
+ *
+ * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
+ * http://code.google.com/p/poly2tri/
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without modification,
+ * are permitted provided that the following conditions are met:
+ *
+ * * Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright notice,
+ * this list of conditions and the following disclaimer in the documentation
+ * and/or other materials provided with the distribution.
+ * * Neither the name of Poly2Tri nor the names of its contributors may be
+ * used to endorse or promote products derived from this software without specific
+ * prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef __POLY2TRI_C_REFINE_UTILS_H__
+#define __POLY2TRI_C_REFINE_UTILS_H__
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif
+
+#include <glib.h>
+
+ /* The code for the Hash Set is partially based on the example given at
+ * http://developer.gnome.org/glib/2.29/glib-Hash-Tables.html
+ */
+
+ typedef GHashTable P2tRHashSet;
+ typedef GHashTableIter P2trHashSetIter;
+
+#define p2tr_hash_set_set_new(hash_func, equal_func, destroy) g_hash_table_new_full ((hash_func), (equal_func), (destroy),NULL)
+#define p2tr_hash_set_insert(set,element) g_hash_table_insert ((set), (element), (element))
+#define p2tr_hash_set_contains(set,element) g_hash_table_lookup_extended ((set), (element), NULL, NULL)
+#define p2tr_hash_set_remove(set,element) g_hash_table_remove ((set), (element))
+
+#define p2tr_hash_set_iter_init(iter,hash_set) g_hash_table_iter_init ((iter),(hash_set))
+#define p2tr_hash_set_iter_next(iter,val) g_hash_table_iter_next ((iter),(val),NULL)
+#define p2tr_hash_set_iter_remove(iter) g_hash_table_iter_remove ((iter))
+
+#define g_list_cyclic_prev(list,elem) (((elem)->prev != NULL) ? (elem)->prev : g_list_last ((elem)))
+#define g_list_cyclic_next(list,elem) (((elem)->next != NULL) ? (elem)->next : g_list_first ((elem)))
+
+#define foreach(iter,list) for ((iter) = (list); (iter) != NULL; (iter) = (iter)->next)
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* UTILS_H */
diff --git a/operations/common/seamless-clone/poly2tri-c/render/mesh-render.c b/operations/common/seamless-clone/poly2tri-c/render/mesh-render.c
new file mode 100755
index 0000000..1785059
--- /dev/null
+++ b/operations/common/seamless-clone/poly2tri-c/render/mesh-render.c
@@ -0,0 +1,290 @@
+#include <glib.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include "../refine/triangulation.h"
+#include "mesh-render.h"
+
+/* Most computations using the Barycentric Coordinates are Based on
+ * http://www.blackpawn.com/texts/pointinpoly/default.html */
+
+/* This function is simply to make sure the code is consitant */
+void
+p2tr_triangle_barycentric_get_points (P2tRTriangle *self,
+ P2tRPoint **A,
+ P2tRPoint **B,
+ P2tRPoint **C)
+{
+ *A = p2tr_edge_get_end (self->edges[2]);
+ *B = p2tr_edge_get_end (self->edges[0]);
+ *C = p2tr_edge_get_end (self->edges[1]);
+}
+
+#define USE_BARYCENTRIC(u,v,A,B,C) ((A) + (v)*((B)-(A)) + (u)*((C)-(A)))
+
+gboolean
+p2tr_triangle_compute_barycentric_coords (P2tRTriangle *tr,
+ gdouble Px,
+ gdouble Py,
+ gdouble *u_out,
+ gdouble *v_out)
+{
+ P2tRPoint *A, *B, *C;
+
+ gdouble u, v;
+ gdouble v0x, v0y, v1x, v1y, v2x, v2y;
+ gdouble dot00, dot01, dot02, dot11, dot12;
+ gdouble invDenom;
+
+ p2tr_triangle_barycentric_get_points (tr, &A, &B, &C);
+
+ /* v0 = C-A */
+ v0x = C->x - A->x;
+ v0y = C->y - A->y;
+ /* v1 = B-A */
+ v1x = B->x - A->x;
+ v1y = B->y - A->y;
+ /* v2 = P-A */
+ v2x = Px - A->x;
+ v2y = Py - A->y;
+
+ /* Compute dot products */
+ dot00 = v0x * v0x + v0y * v0y;
+ dot01 = v0x * v1x + v0y * v1y;
+ dot02 = v0x * v2x + v0y * v2y;
+ dot11 = v1x * v1x + v1y * v1y;
+ dot12 = v1x * v2x + v1y * v2y;
+
+ /* Compute barycentric coordinates */
+ invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
+
+ /* P = A + v*(B-A) + u*(C-A) */
+ *u_out = u = (dot11 * dot02 - dot01 * dot12) * invDenom;
+ *v_out = v = (dot00 * dot12 - dot01 * dot02) * invDenom;
+
+ /* Check if point is in triangle */
+ return (u > -EPSILON2) && (v > -EPSILON2) && (u + v < 1 + EPSILON2);
+
+}
+
+/* This function implements box logic to see if a point is contained in a
+ * triangles bounding box. This is very useful for cases where there are many
+ * triangles to test against a single point, and most of them aren't even near
+ * it.
+ *
+ * Instead of finding the Xmin, Xmax, Ymin, Ymax and checking if the the point
+ * is outside, just check if the point is on the SAME SIDE compared to all the
+ * points of the triangle.
+ * See http://lightningismyname.blogspot.com/2011/08/quickboxa-quick-point-in-triangle-test.html
+ */
+gboolean
+p2tr_triangule_quick_box_test (P2tRTriangle *self,
+ gdouble Px,
+ gdouble Py)
+{
+ P2tRPoint *A = p2tr_edge_get_end (self->edges[2]);
+ P2tRPoint *B = p2tr_edge_get_end (self->edges[0]);
+ P2tRPoint *C = p2tr_edge_get_end (self->edges[1]);
+
+ register gboolean xPBorder = B->x <= Px;
+ register gboolean yPBorder = B->y <= Py;
+
+ return (((A->x <= Px) == xPBorder) && (xPBorder == (C->x <= Px)))
+ || (((A->y <= Py) == yPBorder) && (yPBorder == (C->y <= Py)));
+}
+/**
+ * p2tr_triangulation_locate_point2:
+ * @T: A triangulation object
+ * @X: The point to locate
+ * @guess: Some triangle near the point, or NULL if not known.
+ * WARNING! The triangle must be inside the same continuos region as the
+ * point! If not, this function may return wrong values!
+ *
+ * Returns: A triangle containing the point, or NULL if the point is outside the
+ * triangulation domain.
+ */
+P2tRTriangle*
+p2tr_triangulation_locate_point2 (P2tRTriangulation *T,
+ gdouble Px,
+ gdouble Py,
+ P2tRTriangle *guess,
+ gdouble *u,
+ gdouble *v)
+{
+ if (guess == NULL || ! p2tr_hash_set_contains (T->tris, guess))
+ {
+ /* If we have nothing, check all the triangles.
+ * TODO: This can probably be improved by sampling several triangles at
+ * random, picking the closest and using it as a guess.*/
+ P2tRTriangle *tr = NULL;
+ P2trHashSetIter iter;
+ p2tr_hash_set_iter_init (&iter, T->tris);
+ while (p2tr_hash_set_iter_next (&iter, (gpointer*)&tr))
+ if (p2tr_triangle_compute_barycentric_coords (tr, Px, Py, u, v))
+ return tr;
+ return NULL;
+ }
+ else
+ {
+ /* Maintain a set of checked triangles, and a queue of ones to check.
+ * For each triangle in the queue, check if it has the point, and if not
+ * then add it's neighbors at the end of the queue. This also gaurantess
+ * to some level a search that starts local around the triangles and only
+ * goes farther if needed. */
+ P2tRHashSet *checked = p2tr_hash_set_set_new (g_direct_hash, g_direct_equal, NULL);
+ P2tRTriangle *result = NULL, *current = NULL;
+ GQueue tris;
+ gint i;
+
+ g_queue_init (&tris);
+ g_queue_push_tail (&tris, guess);
+
+ while (! g_queue_is_empty (&tris))
+ {
+ current = (P2tRTriangle*) g_queue_pop_head (&tris);
+ if (p2tr_triangle_compute_barycentric_coords (current, Px, Py, u, v))
+ {
+ result = current;
+ break;
+ }
+ else for (i = 0; i < 3; i++)
+ {
+ P2tRTriangle *neighbor = current->edges[i]->mirror->tri;
+ if (neighbor != NULL && ! p2tr_hash_set_contains (checked, neighbor))
+ g_queue_push_tail (&tris, current->edges[i]->mirror->tri);
+ }
+
+ p2tr_hash_set_insert (checked, current);
+ }
+
+ /* If the queue is empty, then we have nothing to free. It's struct is
+ * allocated directly on the stack and it has nothing dynamic in it. */
+
+ g_hash_table_destroy (checked);
+
+ return result;
+ }
+}
+
+void p2tr_test_point_to_color (P2tRPoint* point, gfloat *dest, gpointer user_data)
+{
+/*
+ GRand* sr = g_rand_new_with_seed ((*((guchar*)&point->x)) ^ (*((guchar*)&point->y)));
+ gfloat temp;
+
+ temp = (gfloat) g_rand_double (sr);
+ dest[0] = ABS (temp);
+
+ temp = (gfloat) g_rand_double (sr);
+ dest[1] = ABS (temp);
+
+ temp = (gfloat) g_rand_double (sr);
+ dest[2] = ABS (temp);
+
+ dest[3] = 1;
+*/
+ dest[0] = 0;
+ dest[1] = 0.5;
+ dest[2] = 1;
+}
+
+void
+p2tr_mesh_render_scanline (P2tRTriangulation *T,
+ gfloat *dest,
+ P2tRImageConfig *config,
+ P2tRPointToColorFunc pt2col,
+ gpointer pt2col_user_data)
+{
+ gdouble *uvbuf = g_new (gdouble, 2 * config->x_samples * config->y_samples), *Puv = uvbuf;
+ P2tRTriangle **tribuf = g_new (P2tRTriangle*, config->x_samples * config->y_samples), **Ptri = tribuf;
+ P2tRTriangle *tr_prev = NULL, *tr_now;
+
+ gint x, y;
+
+ tribuf[0] = p2tr_triangulation_locate_point2 (T, config->min_x, config->min_y, NULL, &uvbuf[0], &uvbuf[1]);
+
+ for (x = 0; x < config->x_samples; x++)
+ for (y = 0; y < config->y_samples; y++)
+ {
+ gdouble Px = config->min_x + x * config->step_x;
+ gdouble Py = config->min_y + y * config->step_y;
+ *Ptri++ = p2tr_triangulation_locate_point2 (T, Px, Py, *Ptri, &Puv[0], &Puv[1]);
+ Puv+=2;
+ }
+
+ Puv = uvbuf;
+ Ptri = tribuf;
+
+ P2tRPoint *A = NULL, *B = NULL, *C = NULL;
+
+ gfloat *col = g_new (gfloat, config->cpp);
+ gfloat *colA = g_new (gfloat, config->cpp);
+ gfloat *colB = g_new (gfloat, config->cpp);
+ gfloat *colC = g_new (gfloat, config->cpp);
+
+ gfloat *pixel = dest;
+
+ GTimer *timer = g_timer_new ();
+ g_timer_start (timer);
+
+ for (x = 0; x < config->x_samples; x++)
+ for (y = 0; y < config->y_samples; y++)
+ {
+ gdouble u = Puv[0], v = Puv[1];
+ tr_now = *Ptri++;
+ uvbuf++;
+
+ if (tr_now == NULL)
+ {
+ pixel[3] = 0;
+ pixel += 4;
+ }
+ else
+ {
+ if (tr_now != tr_prev)
+ {
+ p2tr_triangle_barycentric_get_points (tr_now, &A, &B, &C);
+ pt2col (A, colA, pt2col_user_data);
+ pt2col (B, colB, pt2col_user_data);
+ pt2col (C, colC, pt2col_user_data);
+ tr_now = tr_prev;
+ }
+
+ *pixel++ = USE_BARYCENTRIC (u,v,colA[0],colB[0],colC[0]);
+ *pixel++ = USE_BARYCENTRIC (u,v,colA[1],colB[1],colC[1]);
+ *pixel++ = USE_BARYCENTRIC (u,v,colA[2],colB[2],colC[2]);
+ *pixel++ = 1;
+ }
+ }
+ g_timer_stop (timer);
+ p2tr_debug ("Mesh rendering took %f seconds\n", g_timer_elapsed (timer, NULL));
+}
+
+void
+p2tr_write_ppm (FILE *f,
+ gfloat *dest,
+ P2tRImageConfig *config)
+{
+ gint x, y;
+ fprintf (f, "P3\n");
+ fprintf (f, "%d %d\n", config->x_samples, config->y_samples);
+ fprintf (f, "255\n");
+
+ gfloat *pixel = dest;
+
+ for (y = 0; y < config->y_samples; y++)
+ {
+ for (x = 0; x < config->x_samples; x++)
+ {
+ if (pixel[3] <= 0.5)
+ fprintf (f, " 0 0 0");
+ else
+ fprintf (f, "%3d %3d %3d", (guchar)(pixel[0] * 255), (guchar)(pixel[1] * 255), (guchar)(pixel[2] * 255));
+
+ if (x != config->x_samples - 1)
+ fprintf (f, " ");
+
+ pixel += 4;
+ }
+ fprintf (f, "\n");
+ }
+}
\ No newline at end of file
diff --git a/operations/common/seamless-clone/poly2tri-c/render/mesh-render.h b/operations/common/seamless-clone/poly2tri-c/render/mesh-render.h
new file mode 100755
index 0000000..6d86985
--- /dev/null
+++ b/operations/common/seamless-clone/poly2tri-c/render/mesh-render.h
@@ -0,0 +1,47 @@
+/*
+ * File: mesh-render.h
+ * Author: Barak
+ *
+ * Created on 1 ×××××× 2011, 15:37
+ */
+
+#ifndef MESH_RENDER_H
+#define MESH_RENDER_H
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif
+
+typedef struct {
+ /* Minimal X and Y coordinates to start sampling at */
+ gdouble min_x, min_y;
+ /* Size of a step in each axis */
+ gdouble step_x, step_y;
+ /* The amount of samples desired in each axis */
+ guint x_samples, y_samples;
+ /* The amount of channels per pixel, both in destination buffer and in the
+ * colors returned from the matching point-to-color function */
+ guint cpp;
+} P2tRImageConfig;
+
+typedef void (*P2tRPointToColorFunc) (P2tRPoint* point, gfloat *dest, gpointer user_data);
+
+void p2tr_test_point_to_color (P2tRPoint* point, gfloat *dest, gpointer user_data);
+
+void
+p2tr_mesh_render_scanline (P2tRTriangulation *T,
+ gfloat *dest,
+ P2tRImageConfig *config,
+ P2tRPointToColorFunc pt2col,
+ gpointer pt2col_user_data);
+
+
+
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* MESH_RENDER_H */
+
diff --git a/operations/common/seamless-clone/poly2tri-c/render/svg-plot.c b/operations/common/seamless-clone/poly2tri-c/render/svg-plot.c
new file mode 100755
index 0000000..d716ace
--- /dev/null
+++ b/operations/common/seamless-clone/poly2tri-c/render/svg-plot.c
@@ -0,0 +1,330 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <math.h>
+#include <glib.h>
+
+#include "../refine/triangulation.h"
+
+#include "svg-plot.h"
+
+void
+p2tr_plot_svg_plot_group_start (const gchar *Name, FILE *outfile)
+{
+ if (Name == NULL)
+ fprintf (outfile, "<g>" "\n");
+ else
+ fprintf (outfile, "<g name=\"%s\">" "\n", Name);
+}
+
+void
+p2tr_plot_svg_plot_group_end (FILE *outfile)
+{
+ fprintf (outfile, "</g>" "\n");
+}
+
+void
+p2tr_plot_svg_plot_line (gdouble x1, gdouble y1, gdouble x2, gdouble y2, const gchar *color, FILE *outfile)
+{
+ fprintf (outfile, "<line x1=\"%f\" y1=\"%f\" x2=\"%f\" y2=\"%f\"" "\n", x1, y1, x2, y2);
+ fprintf (outfile, "style=\"stroke: %s; stroke-width: %f\" />" "\n", color, PLOT_LINE_WIDTH);
+ fprintf (outfile, "" "\n");
+}
+
+void
+p2tr_plot_svg_plot_arrow (gdouble x1, gdouble y1, gdouble x2, gdouble y2, const gchar* color, FILE *outfile)
+{
+ p2tr_plot_svg_plot_line (x1, y1, x2, y2, color, outfile);
+
+ gdouble dy = y2 - y1;
+ gdouble dx = x2 - x1;
+ gdouble angle = atan2 (dy, dx);
+
+ gdouble temp = angle - ARROW_SIDE_ANGLE;
+ p2tr_plot_svg_plot_line (x2, y2, x2 - ARROW_HEAD_SIZE * cos (temp), y2 - ARROW_HEAD_SIZE * sin (temp), color, outfile);
+
+ temp = angle + ARROW_SIDE_ANGLE;
+ p2tr_plot_svg_plot_line (x2, y2, x2 - ARROW_HEAD_SIZE * cos (temp), y2 - ARROW_HEAD_SIZE * sin (temp), color, outfile);
+}
+
+void
+p2tr_plot_svg_fill_triangle (gdouble x1, gdouble y1, gdouble x2, gdouble y2, gdouble x3, gdouble y3, const gchar *color, FILE *outfile)
+{
+ fprintf (outfile, "<polyline points=\"%f,%f %f,%f %f,%f\"" "\n", x1, y1, x2, y2, x3, y3);
+ fprintf (outfile, "style=\"fill: %s\" />" "\n", color);
+ fprintf (outfile, "" "\n");
+}
+
+void
+p2tr_plot_svg_fill_point (gdouble x1, gdouble y1, const gchar* color, FILE *outfile)
+{
+ fprintf (outfile, "<circle cx=\"%f\" cy=\"%f\" r=\"%f\"" "\n", x1, y1, MAX (1, PLOT_LINE_WIDTH));
+ fprintf (outfile, "style=\"fill: %s; stroke: none\" />" "\n", color);
+ fprintf (outfile, "" "\n");
+}
+
+void
+p2tr_plot_svg_plot_circle (gdouble xc, gdouble yc, gdouble R, const gchar* color, FILE *outfile)
+{
+ fprintf (outfile, "<circle cx=\"%f\" cy=\"%f\" r=\"%f\"" "\n", xc, yc, R);
+ fprintf (outfile, "style=\"stroke: %s; stroke-width: %f; fill: none\" />" "\n", color, PLOT_LINE_WIDTH);
+ fprintf (outfile, "" "\n");
+}
+
+void
+p2tr_plot_svg_plot_end (FILE *outfile)
+{
+ fprintf (outfile, "</g>" "\n");
+ fprintf (outfile, "</svg>" "\n");
+}
+
+void
+p2tr_plot_svg_plot_init (FILE *outfile)
+{
+ fprintf (outfile, "<?xml version=\"1.0\" standalone=\"no\"?>" "\n");
+ fprintf (outfile, "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"" "\n");
+ fprintf (outfile, "\"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\";>" "\n");
+ fprintf (outfile, "<svg width=\"100%%\" height=\"100%%\" version=\"1.1\"" "\n");
+ fprintf (outfile, "xmlns=\"http://www.w3.org/2000/svg\";>" "\n");
+ fprintf (outfile, "" "\n");
+ fprintf (outfile, "<defs>" "\n");
+ fprintf (outfile, " <marker id=\"arrow\" viewBox=\"0 0 10 10\" refX=\"10\" refY=\"5\"" "\n");
+ fprintf (outfile, " markerUnits=\"strokeWidth\" orient=\"auto\"" "\n");
+ fprintf (outfile, " markerWidth=\"12\" markerHeight=\"9\">" "\n");
+ fprintf (outfile, "" "\n");
+ fprintf (outfile, " <polyline points=\"0,0 10,5 0,10\" fill=\"none\" stroke-width=\"2px\" stroke=\"inherit\" />" "\n");
+ fprintf (outfile, " </marker>" "\n");
+ fprintf (outfile, "</defs>" "\n");
+ fprintf (outfile, "" "\n");
+ fprintf (outfile, "<g transform=\"translate(%f,%f) scale(%f,-%f)\">" "\n", X_TRANSLATE, Y_TRANSLATE, X_SCALE, Y_SCALE);
+
+ p2tr_plot_svg_plot_arrow (-20, 0, 100, 0, "black", outfile);
+ p2tr_plot_svg_plot_arrow (0, -20, 0, 100, "black", outfile);
+}
+
+void
+p2tr_plot_svg_plot_edge (P2tREdge *self, const gchar* color, FILE* outfile)
+{
+ gdouble x1 = p2tr_edge_get_start (self)->x;
+ gdouble y1 = p2tr_edge_get_start (self)->y;
+ gdouble x2 = p2tr_edge_get_end (self)->x;
+ gdouble y2 = p2tr_edge_get_end (self)->y;
+ gdouble R = sqrt ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) / 2;
+
+ p2tr_plot_svg_plot_line (x1, y1, x2, y2, color, outfile);
+
+
+// if (p2tr_edge_is_encroached (self))
+// p2tr_plot_svg_plot_circle ((x1 + x2) / 2, (y1 + y2) / 2, R, "red", outfile);
+}
+
+void
+p2tr_plot_svg_plot_triangle (P2tRTriangle *self, const gchar* color, FILE* outfile)
+{
+ P2tRCircle c;
+ p2tr_triangle_circumcircle (self, &c);
+ p2tr_plot_svg_plot_edge (self->edges[0], color, outfile);
+ p2tr_plot_svg_plot_edge (self->edges[1], color, outfile);
+ p2tr_plot_svg_plot_edge (self->edges[2], color, outfile);
+ p2tr_plot_svg_plot_circle (c.x, c.y, c.radius, "green", outfile);
+ p2tr_plot_svg_fill_point (self->edges[0]->end->x, self->edges[0]->end->y, "blue", outfile);
+ p2tr_plot_svg_fill_point (self->edges[1]->end->x, self->edges[1]->end->y, "blue", outfile);
+ p2tr_plot_svg_fill_point (self->edges[2]->end->x, self->edges[2]->end->y, "blue", outfile);
+}
+
+void
+CCWTest (FILE* outfile)
+{
+ P2tRPoint *A = p2tr_point_new (50, 50);
+ gdouble C[8][2] = {
+ {0, 0},
+ {50, 0},
+ {100, 0},
+ {100, 50},
+ {100, 100},
+ {50, 100},
+ {0, 100},
+ {0, 50}
+ };
+
+ gint lenC = sizeof (C) / (2 * sizeof (gdouble));
+
+ gint j;
+ for (j = 0; j < lenC; j++)
+ {
+ gint k;
+ do
+ {
+ k = rand () % lenC;
+ }
+ while (C[k][0] == INFINITY && C[k][1] == INFINITY);
+
+ gdouble *h = C[k];
+
+ p2tr_point_edge_to (A, p2tr_point_new (h[0], h[1]));
+
+ h[0] = h[1] = INFINITY;
+ }
+
+ gint i = 0;
+ GList *iter;
+
+ foreach (iter, A->edges)
+ {
+ gchar color[18];
+ P2tREdge *e = (P2tREdge*) iter->data;
+ gint val = i * 255 / lenC;
+
+ sprintf (color, "#%02x%02x%02x", val, val, val);
+ p2tr_plot_svg_plot_edge (e, color, outfile);
+ i++;
+ }
+}
+
+void
+TriangleClockwiseTest (FILE* outfile)
+{
+
+ const gchar * ecolors[3] = {"#ff0000", "#00ff00", "#0000ff"};
+ const gchar * mecolors[3] = {"#770000", "#007700", "#000077"};
+ const gchar * ptcolors[3] = {"#ff00ff", "#ffff00", "#00ffff"};
+
+ const gchar * names[3] = {"A", "B", "C"};
+
+ P2tRPoint * pts[3];
+ int i;
+ for (i = 0; i < 3; i++)
+ {
+ pts[i] = p2tr_point_new (r (), r ());
+ }
+
+ P2tREdge * edges[3];
+ for (i = 0; i < 3; i++)
+ {
+ edges[i] = p2tr_edge_new (pts[i], pts[(i + 1) % 3]);
+ }
+
+ P2tRTriangle *tri = p2tr_triangle_new (edges[0], edges[1], edges[2], NULL);
+
+ for (i = 0; i < 3; i++)
+ {
+ p2tr_plot_svg_plot_edge (tri->edges[i]->mirror, mecolors[i], outfile);
+ }
+
+ for (i = 0; i < 3; i++)
+ {
+ p2tr_plot_svg_plot_edge (tri->edges[i], ecolors[i], outfile);
+ }
+
+ for (i = 0; i < 3; i++)
+ {
+ P2tRPoint *P = p2tr_edge_get_start (tri->edges[i]);
+ p2tr_plot_svg_fill_point (P->x, P->y, ptcolors[i], outfile);
+ }
+}
+
+void
+refineTest(FILE* outfile)
+{
+ /*
+ gdouble RAW[5][2] = {{10,10},{50,50},{55,130},{0,100},{30,50}};
+ P2tRPoint *X[5];
+ gint N = 5;
+ */
+ gdouble RAW[10][2] = {{10,10},{30,30},{50,50},{52.5,90},{55,130},{27.5,115},{0,100},{15,75},{30,50},{20,30}};
+ P2tRPoint *X[10];
+ gint N = 10;
+
+ GList *XEs = NULL;
+ int i;
+
+ for (i = 0; i < N; i++)
+ {
+ X[i] = p2tr_point_new (RAW[i][0], RAW[i][1]);
+ p2tr_plot_svg_fill_point (RAW[i][0], RAW[i][1], "blue", outfile);
+ }
+
+ fprintf (stderr, "Preparing to work on %d points\n", N);
+ for (i = 0; i < N; i++)
+ {
+ P2tREdge *E = p2tr_edge_new (X[N-i-1], X[N-1-((i+1)%N)]);
+ XEs = g_list_prepend (XEs, E);
+ p2tr_edge_set_constrained (E, TRUE);
+ }
+
+ P2tRTriangulation *T = p2tr_triangulateA (X,N);
+
+ {
+ GList *liter;
+ foreach (liter, XEs)
+ p2tr_validate_edge ((P2tREdge*)liter->data);
+ }
+
+ DelaunayTerminator (T,XEs,M_PI/6,p2tr_false_delta);
+
+ {
+ P2trHashSetIter iter;
+ P2tRTriangle *t;
+ p2tr_hash_set_iter_init (&iter, T->tris);
+ while (p2tr_hash_set_iter_next (&iter, (gpointer*)&t))
+ {
+ p2tr_assert_and_explain (t != NULL, "NULL triangle found!\n");
+ p2tr_assert_and_explain (t->edges[0] != NULL && t->edges[1] != NULL && t->edges[2] != NULL,
+ "Removed triangle found!\n");
+ p2tr_plot_svg_plot_triangle (t, "black", outfile);
+
+ p2tr_validate_edge (t->edges[0]);
+ p2tr_validate_edge (t->edges[1]);
+ p2tr_validate_edge (t->edges[2]);
+
+ }
+ }
+
+#if FALSE
+ GPtrArray* points = mvc_findEdgePoints (T);
+ //PlotPoints (points);
+
+ P2tRPoint *testX = p2tr_point_new (40, 45);
+ p2tr_plot_svg_fill_point (testX->x, testX->y, "red");
+ /* Give special care for the part after the last point - it may have less
+ * points than other parts */
+ gint div = points->len / 16;
+ P2tRHashSet *allPts = p2tr_hash_set_set_new (g_direct_hash, g_direct_equal, NULL);
+ for (i = 0; i < 16; i++)
+ {
+ gint index1 = i * div;
+ gint index2 = MIN ((i + 1) * div, points->len); /* In the last iteration, take the last */
+ mvc_makePtList (testX, points, index1, index2, allPts);
+ }
+
+ {
+ gint count = 0;
+ P2trHashSetIter iter;
+ P2tRPoint *pt;
+ p2tr_hash_set_iter_init (&iter, allPts);
+ while (p2tr_hash_set_iter_next (&iter, (gpointer*)&pt))
+ {
+ p2tr_plot_svg_fill_point (pt->x, pt->y, "orange");
+ count++;
+ }
+ fprintf (stderr, "In total, had %d sample points\n", count);
+ }
+#endif
+}
+
+
+void
+p2tr_plot_svg (P2tRTriangulation *T, FILE *outfile)
+{
+ P2trHashSetIter siter;
+ P2tRTriangle *tr;
+
+ p2tr_debug ("Starting to write SVG output\n");
+ p2tr_plot_svg_plot_init (outfile);
+
+ p2tr_hash_set_iter_init (&siter, T->tris);
+ while (p2tr_hash_set_iter_next (&siter, (gpointer*)&tr))
+ p2tr_plot_svg_plot_triangle (tr, "black", outfile);
+
+ p2tr_plot_svg_plot_end (outfile);
+ p2tr_debug ("Finished writing SVG output\n");
+}
\ No newline at end of file
diff --git a/operations/common/seamless-clone/poly2tri-c/render/svg-plot.h b/operations/common/seamless-clone/poly2tri-c/render/svg-plot.h
new file mode 100755
index 0000000..20d7050
--- /dev/null
+++ b/operations/common/seamless-clone/poly2tri-c/render/svg-plot.h
@@ -0,0 +1,98 @@
+/*
+ * This file is a part of Poly2Tri-C - The C port of the Poly2Tri library
+ * Porting to C done by (c) Barak Itkin <lightningismyname gmail com>
+ * http://code.google.com/p/poly2tri-c/
+ *
+ * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
+ * http://code.google.com/p/poly2tri/
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without modification,
+ * are permitted provided that the following conditions are met:
+ *
+ * * Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright notice,
+ * this list of conditions and the following disclaimer in the documentation
+ * and/or other materials provided with the distribution.
+ * * Neither the name of Poly2Tri nor the names of its contributors may be
+ * used to endorse or promote products derived from this software without specific
+ * prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef SVG_PLOT_H
+#define SVG_PLOT_H
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif
+
+#include "../refine/refine.h"
+
+#define PLOT_LINE_WIDTH 0.40
+#define ARROW_SIDE_ANGLE (M_PI / 180 * 30)
+#define ARROW_HEAD_SIZE 2.0
+
+#define X_SCALE 3.
+#define Y_SCALE 3.
+#define X_TRANSLATE 500.
+#define Y_TRANSLATE 500.
+
+void
+p2tr_plot_svg_plot_group_start (const gchar *Name, FILE* outfile);
+
+void
+p2tr_plot_svg_plot_group_end (FILE* outfile);
+
+void
+p2tr_plot_svg_plot_line (gdouble x1, gdouble y1, gdouble x2, gdouble y2, const gchar *color, FILE* outfile);
+
+void
+p2tr_plot_svg_plot_arrow (gdouble x1, gdouble y1, gdouble x2, gdouble y2, const gchar* color, FILE* outfile);
+
+void
+p2tr_plot_svg_fill_triangle (gdouble x1, gdouble y1, gdouble x2, gdouble y2, gdouble x3, gdouble y3, const gchar *color, FILE* outfile);
+
+void
+p2tr_plot_svg_fill_point (gdouble x1, gdouble y1, const gchar* color, FILE* outfile);
+
+void
+p2tr_plot_svg_plot_circle (gdouble xc, gdouble yc, gdouble R, const gchar* color, FILE* outfile);
+
+void
+p2tr_plot_svg_plot_end (FILE* outfile);
+
+void
+p2tr_plot_svg_plot_init (FILE* outfile);
+
+void
+p2tr_plot_svg_plot_edge (P2tREdge *self, const gchar* color, FILE* outfile);
+
+void
+p2tr_plot_svg_plot_triangle (P2tRTriangle *self, const gchar* color, FILE* outfile);
+
+#define r() (10+(rand () % 91))
+
+void
+p2tr_plot_svg (P2tRTriangulation *T, FILE* outfile);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* SVG_PLOT_H */
+
diff --git a/operations/common/seamless-clone/poly2tri-c/sweep/advancing_front.c b/operations/common/seamless-clone/poly2tri-c/sweep/advancing_front.c
new file mode 100755
index 0000000..ca3c993
--- /dev/null
+++ b/operations/common/seamless-clone/poly2tri-c/sweep/advancing_front.c
@@ -0,0 +1,224 @@
+/*
+ * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
+ * http://code.google.com/p/poly2tri/
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without modification,
+ * are permitted provided that the following conditions are met:
+ *
+ * * Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright notice,
+ * this list of conditions and the following disclaimer in the documentation
+ * and/or other materials provided with the distribution.
+ * * Neither the name of Poly2Tri nor the names of its contributors may be
+ * used to endorse or promote products derived from this software without specific
+ * prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+#include "advancing_front.h"
+
+void
+p2t_node_init_pt (P2tNode* THIS, P2tPoint* p)
+{
+ THIS->point = p;
+ THIS->triangle = NULL;
+ THIS->value = p->x;
+ THIS->next = NULL;
+ THIS->prev = NULL;
+}
+
+P2tNode*
+p2t_node_new_pt (P2tPoint* p)
+{
+ P2tNode* THIS = g_slice_new (P2tNode);
+ p2t_node_init_pt (THIS, p);
+ return THIS;
+}
+
+void
+p2t_node_init_pt_tr (P2tNode* THIS, P2tPoint* p, P2tTriangle* t)
+{
+ THIS->point = p;
+ THIS->triangle = t;
+ THIS->value = p->x;
+ THIS->next = NULL;
+ THIS->prev = NULL;
+}
+
+P2tNode*
+p2t_node_new_pt_tr (P2tPoint* p, P2tTriangle* t)
+{
+ P2tNode* THIS = g_slice_new (P2tNode);
+ p2t_node_init_pt_tr (THIS, p, t);
+ return THIS;
+}
+
+void p2t_node_destroy (P2tNode* THIS)
+{
+}
+void p2t_node_free (P2tNode* THIS)
+{
+ p2t_node_destroy (THIS);
+ g_slice_free (P2tNode, THIS);
+}
+
+void
+p2t_advancingfront_init (P2tAdvancingFront* THIS, P2tNode* head, P2tNode* tail)
+{
+ THIS->head_ = head;
+ THIS->tail_ = tail;
+ THIS->search_node_ = head;
+}
+
+P2tAdvancingFront*
+p2t_advancingfront_new (P2tNode* head, P2tNode* tail)
+{
+ P2tAdvancingFront* THIS = g_slice_new (P2tAdvancingFront);
+ p2t_advancingfront_init (THIS, head, tail);
+ return THIS;
+}
+
+void
+p2t_advancingfront_destroy (P2tAdvancingFront* THIS) { }
+
+void
+p2t_advancingfront_free (P2tAdvancingFront* THIS)
+{
+ p2t_advancingfront_destroy (THIS);
+ g_slice_free (P2tAdvancingFront, THIS);
+}
+
+P2tNode*
+p2t_advancingfront_locate_node (P2tAdvancingFront *THIS, const double x)
+{
+ P2tNode* node = THIS->search_node_;
+
+ if (x < node->value)
+ {
+ while ((node = node->prev) != NULL)
+ {
+ if (x >= node->value)
+ {
+ THIS->search_node_ = node;
+ return node;
+ }
+ }
+ }
+ else
+ {
+ while ((node = node->next) != NULL)
+ {
+ if (x < node->value)
+ {
+ THIS->search_node_ = node->prev;
+ return node->prev;
+ }
+ }
+ }
+ return NULL;
+}
+
+P2tNode*
+p2t_advancingfront_find_search_node (P2tAdvancingFront *THIS, const double x)
+{
+ // TODO: implement BST index
+ return THIS->search_node_;
+}
+
+P2tNode*
+p2t_advancingfront_locate_point (P2tAdvancingFront *THIS, const P2tPoint* point)
+{
+ const double px = point->x;
+ P2tNode* node = p2t_advancingfront_find_search_node (THIS, px);
+ const double nx = node->point->x;
+
+ if (px == nx)
+ {
+ if (point != node->point)
+ {
+ // We might have two nodes with same x value for a short time
+ if (point == node->prev->point)
+ {
+ node = node->prev;
+ }
+ else if (point == node->next->point)
+ {
+ node = node->next;
+ }
+ else
+ {
+ assert (0);
+ }
+ }
+ }
+ else if (px < nx)
+ {
+ while ((node = node->prev) != NULL)
+ {
+ if (point == node->point)
+ {
+ break;
+ }
+ }
+ }
+ else
+ {
+ while ((node = node->next) != NULL)
+ {
+ if (point == node->point)
+ break;
+ }
+ }
+ if (node) THIS->search_node_ = node;
+ return node;
+}
+
+P2tNode*
+p2t_advancingfront_head (P2tAdvancingFront *THIS)
+{
+ return THIS->head_;
+}
+
+void
+AdvancingFront_set_head (P2tAdvancingFront *THIS, P2tNode* node)
+{
+ THIS->head_ = node;
+}
+
+P2tNode*
+p2t_advancingfront_tail (P2tAdvancingFront *THIS)
+{
+ return THIS->tail_;
+}
+
+void
+p2t_advancingfront_set_tail (P2tAdvancingFront *THIS, P2tNode* node)
+{
+ THIS->tail_ = node;
+}
+
+P2tNode*
+p2t_advancingfront_search (P2tAdvancingFront *THIS)
+{
+ return THIS->search_node_;
+}
+
+void
+p2t_advancingfront_set_search (P2tAdvancingFront *THIS, P2tNode* node)
+{
+ THIS->search_node_ = node;
+}
+
diff --git a/operations/common/seamless-clone/poly2tri-c/sweep/advancing_front.h b/operations/common/seamless-clone/poly2tri-c/sweep/advancing_front.h
new file mode 100755
index 0000000..44ef55e
--- /dev/null
+++ b/operations/common/seamless-clone/poly2tri-c/sweep/advancing_front.h
@@ -0,0 +1,88 @@
+/*
+ * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
+ * http://code.google.com/p/poly2tri/
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without modification,
+ * are permitted provided that the following conditions are met:
+ *
+ * * Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright notice,
+ * this list of conditions and the following disclaimer in the documentation
+ * and/or other materials provided with the distribution.
+ * * Neither the name of Poly2Tri nor the names of its contributors may be
+ * used to endorse or promote products derived from this software without specific
+ * prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef ADVANCED_FRONT_H
+#define ADVANCED_FRONT_H
+
+#include "../common/poly2tri-private.h"
+#include "../common/shapes.h"
+
+// Advancing front node
+
+struct _P2tNode
+{
+ P2tPoint* point;
+ P2tTriangle* triangle;
+
+ struct _P2tNode* next;
+ struct _P2tNode* prev;
+
+ double value;
+};
+
+void p2t_node_init_pt (P2tNode* THIS, P2tPoint* p);
+P2tNode* p2t_node_new_pt (P2tPoint* p);
+void p2t_node_init_pt_tr (P2tNode* THIS, P2tPoint* p, P2tTriangle* t);
+P2tNode* p2t_node_new_pt_tr (P2tPoint* p, P2tTriangle* t);
+void p2t_node_destroy (P2tNode* THIS);
+void p2t_node_free (P2tNode* THIS);
+
+// Advancing front
+
+struct AdvancingFront_
+{
+ //private:
+
+ P2tNode* head_, *tail_, *search_node_;
+
+};
+
+void p2t_advancingfront_init (P2tAdvancingFront* THIS, P2tNode* head, P2tNode* tail);
+P2tAdvancingFront* p2t_advancingfront_new (P2tNode* head, P2tNode* tail);
+
+void p2t_advancingfront_destroy (P2tAdvancingFront* THIS);
+void p2t_advancingfront_free (P2tAdvancingFront* THIS);
+
+P2tNode* p2t_advancingfront_head (P2tAdvancingFront *THIS);
+void AdvancingFront_set_head (P2tAdvancingFront *THIS, P2tNode* node);
+P2tNode* p2t_advancingfront_tail (P2tAdvancingFront *THIS);
+void p2t_advancingfront_set_tail (P2tAdvancingFront *THIS, P2tNode* node);
+P2tNode* p2t_advancingfront_search (P2tAdvancingFront *THIS);
+void p2t_advancingfront_set_search (P2tAdvancingFront *THIS, P2tNode* node);
+
+/// Locate insertion point along advancing front
+P2tNode* p2t_advancingfront_locate_node (P2tAdvancingFront *THIS, const double x);
+
+P2tNode* p2t_advancingfront_locate_point (P2tAdvancingFront *THIS, const P2tPoint* point);
+
+P2tNode* p2t_advancingfront_find_search_node (P2tAdvancingFront *THIS, const double x);
+
+#endif
diff --git a/operations/common/seamless-clone/poly2tri-c/sweep/cdt.c b/operations/common/seamless-clone/poly2tri-c/sweep/cdt.c
new file mode 100755
index 0000000..49785e6
--- /dev/null
+++ b/operations/common/seamless-clone/poly2tri-c/sweep/cdt.c
@@ -0,0 +1,90 @@
+/*
+ * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
+ * http://code.google.com/p/poly2tri/
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without modification,
+ * are permitted provided that the following conditions are met:
+ *
+ * * Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright notice,
+ * this list of conditions and the following disclaimer in the documentation
+ * and/or other materials provided with the distribution.
+ * * Neither the name of Poly2Tri nor the names of its contributors may be
+ * used to endorse or promote products derived from this software without specific
+ * prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+#include "cdt.h"
+
+void
+p2t_cdt_init (P2tCDT* THIS, P2tPointPtrArray polyline)
+{
+ THIS->sweep_context_ = p2t_sweepcontext_new (polyline);
+ THIS->sweep_ = p2t_sweep_new ();
+}
+
+P2tCDT*
+p2t_cdt_new (P2tPointPtrArray polyline)
+{
+ P2tCDT* THIS = g_slice_new (P2tCDT);
+ p2t_cdt_init (THIS, polyline);
+ return THIS;
+}
+
+void
+p2t_cdt_destroy (P2tCDT* THIS)
+{
+ p2t_sweepcontext_delete (THIS->sweep_context_);
+ p2t_sweep_free (THIS->sweep_);
+}
+
+void
+p2t_cdt_free (P2tCDT* THIS)
+{
+ p2t_cdt_destroy (THIS);
+ g_slice_free (P2tCDT, THIS);
+}
+
+void
+p2t_cdt_add_hole (P2tCDT *THIS, P2tPointPtrArray polyline)
+{
+ p2t_sweepcontext_add_hole (THIS->sweep_context_, polyline);
+}
+
+void
+p2t_cdt_add_point (P2tCDT *THIS, P2tPoint* point)
+{
+ p2t_sweepcontext_add_point (THIS->sweep_context_, point);
+}
+
+void
+p2t_cdt_triangulate (P2tCDT *THIS)
+{
+ p2t_sweep_triangulate (THIS->sweep_, THIS->sweep_context_);
+}
+
+P2tTrianglePtrArray
+p2t_cdt_get_triangles (P2tCDT *THIS)
+{
+ return p2t_sweepcontext_get_triangles (THIS->sweep_context_);
+}
+
+P2tTrianglePtrList
+p2t_cdt_get_map (P2tCDT *THIS)
+{
+ return p2t_sweepcontext_get_map (THIS->sweep_context_);
+}
diff --git a/operations/common/seamless-clone/poly2tri-c/sweep/cdt.h b/operations/common/seamless-clone/poly2tri-c/sweep/cdt.h
new file mode 100755
index 0000000..bd40198
--- /dev/null
+++ b/operations/common/seamless-clone/poly2tri-c/sweep/cdt.h
@@ -0,0 +1,101 @@
+/*
+ * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
+ * http://code.google.com/p/poly2tri/
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without modification,
+ * are permitted provided that the following conditions are met:
+ *
+ * * Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright notice,
+ * this list of conditions and the following disclaimer in the documentation
+ * and/or other materials provided with the distribution.
+ * * Neither the name of Poly2Tri nor the names of its contributors may be
+ * used to endorse or promote products derived from this software without specific
+ * prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef CDT_H
+#define CDT_H
+
+#include "../common/poly2tri-private.h"
+#include "advancing_front.h"
+#include "sweep_context.h"
+#include "sweep.h"
+
+/**
+ *
+ * @author Mason Green <mason green gmail com>
+ *
+ */
+
+struct CDT_
+{
+ //private:
+
+ /**
+ * Internals
+ */
+
+ P2tSweepContext* sweep_context_;
+ P2tSweep* sweep_;
+
+};
+/**
+ * Constructor - add polyline with non repeating points
+ *
+ * @param polyline
+ */
+void p2t_cdt_init (P2tCDT* THIS, P2tPointPtrArray polyline);
+P2tCDT* p2t_cdt_new (P2tPointPtrArray polyline);
+
+/**
+ * Destructor - clean up memory
+ */
+void p2t_cdt_destroy (P2tCDT* THIS);
+void p2t_cdt_free (P2tCDT* THIS);
+
+/**
+ * Add a hole
+ *
+ * @param polyline
+ */
+void p2t_cdt_add_hole (P2tCDT *THIS, P2tPointPtrArray polyline);
+
+/**
+ * Add a steiner point
+ *
+ * @param point
+ */
+void p2t_cdt_add_point (P2tCDT *THIS, P2tPoint* point);
+
+/**
+ * Triangulate - do this AFTER you've added the polyline, holes, and Steiner points
+ */
+void p2t_cdt_triangulate (P2tCDT *THIS);
+
+/**
+ * Get CDT triangles
+ */
+P2tTrianglePtrArray p2t_cdt_get_triangles (P2tCDT *THIS);
+
+/**
+ * Get triangle map
+ */
+P2tTrianglePtrList p2t_cdt_get_map (P2tCDT *THIS);
+
+#endif
diff --git a/operations/common/seamless-clone/poly2tri-c/sweep/sweep.c b/operations/common/seamless-clone/poly2tri-c/sweep/sweep.c
new file mode 100755
index 0000000..147191c
--- /dev/null
+++ b/operations/common/seamless-clone/poly2tri-c/sweep/sweep.c
@@ -0,0 +1,932 @@
+/*
+ * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
+ * http://code.google.com/p/poly2tri/
+ *
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without modification,
+ * are permitted provided that the following conditions are met:
+ *
+ * * Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright notice,
+ * this list of conditions and the following disclaimer in the documentation
+ * and/or other materials provided with the distribution.
+ * * Neither the name of Poly2Tri nor the names of its contributors may be
+ * used to endorse or promote products derived from this software without specific
+ * prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+#include "sweep.h"
+#include "sweep_context.h"
+#include "advancing_front.h"
+#include "../common/utils.h"
+#include "../common/shapes.h"
+
+void
+p2t_sweep_init (P2tSweep* THIS)
+{
+ THIS->nodes_ = g_ptr_array_new ();
+}
+
+P2tSweep*
+p2t_sweep_new ()
+{
+ P2tSweep* THIS = g_new (P2tSweep, 1);
+ p2t_sweep_init (THIS);
+ return THIS;
+}
+
+/**
+ * Destructor - clean up memory
+ */
+void
+p2t_sweep_destroy (P2tSweep* THIS)
+{
+ int i;
+ // Clean up memory
+ for (i = 0; i < THIS->nodes_->len; i++)
+ {
+ p2t_node_free (node_index (THIS->nodes_, i));
+ }
+
+ g_ptr_array_free (THIS->nodes_, TRUE);
+}
+
+void
+p2t_sweep_free (P2tSweep* THIS)
+{
+ p2t_sweep_destroy (THIS);
+ g_free (THIS);
+}
+
+// Triangulate simple polygon with holes
+
+void
+p2t_sweep_triangulate (P2tSweep *THIS, P2tSweepContext *tcx)
+{
+ p2t_sweepcontext_init_triangulation (tcx);
+ p2t_sweepcontext_create_advancingfront (tcx, THIS->nodes_);
+ // Sweep points; build mesh
+ p2t_sweep_sweep_points (THIS, tcx);
+ // Clean up
+ p2t_sweep_finalization_polygon (THIS, tcx);
+}
+
+void
+p2t_sweep_sweep_points (P2tSweep *THIS, P2tSweepContext *tcx)
+{
+ int i, j;
+ for (i = 1; i < p2t_sweepcontext_point_count (tcx); i++)
+ {
+ P2tPoint* point = p2t_sweepcontext_get_point (tcx, i);
+ P2tNode* node = p2t_sweep_point_event (THIS, tcx, point);
+ for (j = 0; j < point->edge_list->len; j++)
+ {
+ p2t_sweep_edge_event_ed_n (THIS, tcx, edge_index (point->edge_list, j), node);
+ }
+ }
+}
+
+void
+p2t_sweep_finalization_polygon (P2tSweep *THIS, P2tSweepContext *tcx)
+{
+ // Get an Internal triangle to start with
+ P2tTriangle* t = p2t_advancingfront_head (p2t_sweepcontext_front (tcx))->next->triangle;
+ P2tPoint* p = p2t_advancingfront_head (p2t_sweepcontext_front (tcx))->next->point;
+ while (!p2t_triangle_get_constrained_edge_cw (t, p))
+ {
+ t = p2t_triangle_neighbor_ccw (t, p);
+ }
+
+ // Collect interior triangles constrained by edges
+ p2t_sweepcontext_mesh_clean (tcx, t);
+}
+
+P2tNode*
+p2t_sweep_point_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tPoint* point)
+{
+ P2tNode* node = p2t_sweepcontext_locate_node (tcx, point);
+ P2tNode* new_node = p2t_sweep_new_front_triangle (THIS, tcx, point, node);
+
+ // Only need to check +epsilon since point never have smaller
+ // x value than node due to how we fetch nodes from the front
+ if (point->x <= node->point->x + EPSILON)
+ {
+ p2t_sweep_fill (THIS, tcx, node);
+ }
+
+ //tcx.AddNode(new_node);
+
+ p2t_sweep_fill_advancingfront (THIS, tcx, new_node);
+ return new_node;
+}
+
+void
+p2t_sweep_edge_event_ed_n (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node)
+{
+ tcx->edge_event.constrained_edge = edge;
+ tcx->edge_event.right = (edge->p->x > edge->q->x);
+
+ if (p2t_sweep_is_edge_side_of_triangle (THIS, node->triangle, edge->p, edge->q))
+ {
+ return;
+ }
+
+ // For now we will do all needed filling
+ // TODO: integrate with flip process might give some better performance
+ // but for now this avoid the issue with cases that needs both flips and fills
+ p2t_sweep_fill_edge_event (THIS, tcx, edge, node);
+ p2t_sweep_edge_event_pt_pt_tr_pt (THIS, tcx, edge->p, edge->q, node->triangle, edge->q);
+}
+
+void
+p2t_sweep_edge_event_pt_pt_tr_pt (P2tSweep *THIS, P2tSweepContext *tcx, P2tPoint* ep, P2tPoint* eq, P2tTriangle* triangle, P2tPoint* point)
+{
+ if (p2t_sweep_is_edge_side_of_triangle (THIS, triangle, ep, eq))
+ {
+ return;
+ }
+
+ P2tPoint* p1 = p2t_triangle_point_ccw (triangle, point);
+ P2tOrientation o1 = p2t_orient2d (eq, p1, ep);
+ if (o1 == COLLINEAR)
+ {
+ if (p2t_triangle_contains_pt_pt (triangle, eq, p1))
+ {
+ p2t_triangle_mark_constrained_edge_pt_pt (triangle, eq, p1);
+ // We are modifying the constraint maybe it would be better to
+ // not change the given constraint and just keep a variable for the new constraint
+ tcx->edge_event.constrained_edge->q = p1;
+ triangle = p2t_triangle_neighbor_across (triangle, point);
+ p2t_sweep_edge_event_pt_pt_tr_pt (THIS, tcx, ep, p1, triangle, p1);
+ }
+ else
+ {
+ g_error ("EdgeEvent - collinear points not supported");
+ }
+ return;
+ }
+
+ P2tPoint* p2 = p2t_triangle_point_cw (triangle, point);
+ P2tOrientation o2 = p2t_orient2d (eq, p2, ep);
+ if (o2 == COLLINEAR)
+ {
+ if (p2t_triangle_contains_pt_pt (triangle, eq, p2))
+ {
+ p2t_triangle_mark_constrained_edge_pt_pt (triangle, eq, p2);
+ // We are modifying the constraint maybe it would be better to
+ // not change the given constraint and just keep a variable for the new constraint
+ tcx->edge_event.constrained_edge->q = p2;
+ triangle = p2t_triangle_neighbor_across (triangle, point);
+ p2t_sweep_edge_event_pt_pt_tr_pt (THIS, tcx, ep, p2, triangle, p2);
+ }
+ else
+ {
+ g_error ("EdgeEvent - collinear points not supported");
+ }
+ return;
+ }
+
+ if (o1 == o2)
+ {
+ // Need to decide if we are rotating CW or CCW to get to a triangle
+ // that will cross edge
+ if (o1 == CW)
+ {
+ triangle = p2t_triangle_neighbor_ccw (triangle, point);
+ }
+ else
+ {
+ triangle = p2t_triangle_neighbor_cw (triangle, point);
+ }
+ p2t_sweep_edge_event_pt_pt_tr_pt (THIS, tcx, ep, eq, triangle, point);
+ }
+ else
+ {
+ // This triangle crosses constraint so lets flippin start!
+ p2t_sweep_flip_edge_event (THIS, tcx, ep, eq, triangle, point);
+ }
+}
+
+gboolean
+p2t_sweep_is_edge_side_of_triangle (P2tSweep *THIS, P2tTriangle *triangle, P2tPoint* ep, P2tPoint* eq)
+{
+ int index = p2t_triangle_edge_index (triangle, ep, eq);
+
+ if (index != -1)
+ {
+ p2t_triangle_mark_constrained_edge_i (triangle, index);
+ P2tTriangle* t = p2t_triangle_get_neighbor (triangle, index);
+ if (t)
+ {
+ p2t_triangle_mark_constrained_edge_pt_pt (t, ep, eq);
+ }
+ return TRUE;
+ }
+ return FALSE;
+}
+
+P2tNode*
+p2t_sweep_new_front_triangle (P2tSweep *THIS, P2tSweepContext *tcx, P2tPoint* point, P2tNode *node)
+{
+ P2tTriangle* triangle = p2t_triangle_new (point, node->point, node->next->point);
+
+ p2t_triangle_mark_neighbor_tr (triangle, node->triangle);
+ p2t_sweepcontext_add_to_map (tcx, triangle);
+
+ P2tNode* new_node = p2t_node_new_pt (point);
+ g_ptr_array_add (THIS->nodes_, new_node);
+
+ new_node->next = node->next;
+ new_node->prev = node;
+ node->next->prev = new_node;
+ node->next = new_node;
+
+ if (!p2t_sweep_legalize (THIS, tcx, triangle))
+ {
+ p2t_sweepcontext_map_triangle_to_nodes (tcx, triangle);
+ }
+
+ return new_node;
+}
+
+void
+p2t_sweep_fill (P2tSweep *THIS, P2tSweepContext *tcx, P2tNode* node)
+{
+ P2tTriangle* triangle = p2t_triangle_new (node->prev->point, node->point, node->next->point);
+
+ // TODO: should copy the constrained_edge value from neighbor triangles
+ // for now constrained_edge values are copied during the legalize
+ p2t_triangle_mark_neighbor_tr (triangle, node->prev->triangle);
+ p2t_triangle_mark_neighbor_tr (triangle, node->triangle);
+
+ p2t_sweepcontext_add_to_map (tcx, triangle);
+
+ // Update the advancing front
+ node->prev->next = node->next;
+ node->next->prev = node->prev;
+
+ // If it was legalized the triangle has already been mapped
+ if (!p2t_sweep_legalize (THIS, tcx, triangle))
+ {
+ p2t_sweepcontext_map_triangle_to_nodes (tcx, triangle);
+ }
+
+}
+
+void
+p2t_sweep_fill_advancingfront (P2tSweep *THIS, P2tSweepContext *tcx, P2tNode* n)
+{
+
+ // Fill right holes
+ P2tNode* node = n->next;
+
+ while (node->next)
+ {
+ double angle = p2t_sweep_hole_angle (THIS, node);
+ if (angle > M_PI_2 || angle < -M_PI_2) break;
+ p2t_sweep_fill (THIS, tcx, node);
+ node = node->next;
+ }
+
+ // Fill left holes
+ node = n->prev;
+
+ while (node->prev)
+ {
+ double angle = p2t_sweep_hole_angle (THIS, node);
+ if (angle > M_PI_2 || angle < -M_PI_2) break;
+ p2t_sweep_fill (THIS, tcx, node);
+ node = node->prev;
+ }
+
+ // Fill right basins
+ if (n->next && n->next->next)
+ {
+ double angle = p2t_sweep_basin_angle (THIS, n);
+ if (angle < PI_3div4)
+ {
+ p2t_sweep_fill_basin (THIS, tcx, n);
+ }
+ }
+}
+
+double
+p2t_sweep_basin_angle (P2tSweep *THIS, P2tNode* node)
+{
+ double ax = node->point->x - node->next->next->point->x;
+ double ay = node->point->y - node->next->next->point->y;
+ return atan2 (ay, ax);
+}
+
+double
+p2t_sweep_hole_angle (P2tSweep *THIS, P2tNode* node)
+{
+ /* Complex plane
+ * ab = cosA +i*sinA
+ * ab = (ax + ay*i)(bx + by*i) = (ax*bx + ay*by) + i(ax*by-ay*bx)
+ * atan2(y,x) computes the principal value of the argument function
+ * applied to the complex number x+iy
+ * Where x = ax*bx + ay*by
+ * y = ax*by - ay*bx
+ */
+ double ax = node->next->point->x - node->point->x;
+ double ay = node->next->point->y - node->point->y;
+ double bx = node->prev->point->x - node->point->x;
+ double by = node->prev->point->y - node->point->y;
+ return atan2 (ax * by - ay * bx, ax * bx + ay * by);
+}
+
+gboolean
+p2t_sweep_legalize (P2tSweep *THIS, P2tSweepContext *tcx, P2tTriangle *t)
+{
+ int i;
+ // To legalize a triangle we start by finding if any of the three edges
+ // violate the Delaunay condition
+ for (i = 0; i < 3; i++)
+ {
+ if (t->delaunay_edge[i])
+ continue;
+
+ P2tTriangle* ot = p2t_triangle_get_neighbor (t, i);
+
+ if (ot)
+ {
+ P2tPoint* p = p2t_triangle_get_point (t, i);
+ P2tPoint* op = p2t_triangle_opposite_point (ot, t, p);
+ int oi = p2t_triangle_index (ot, op);
+
+ // If this is a Constrained Edge or a Delaunay Edge(only during recursive legalization)
+ // then we should not try to legalize
+ if (ot->constrained_edge[oi] || ot->delaunay_edge[oi])
+ {
+ t->constrained_edge[i] = ot->constrained_edge[oi];
+ continue;
+ }
+
+ gboolean inside = p2t_sweep_incircle (THIS, p, p2t_triangle_point_ccw (t, p), p2t_triangle_point_cw (t, p), op);
+
+ if (inside)
+ {
+ // Lets mark this shared edge as Delaunay
+ t->delaunay_edge[i] = TRUE;
+ ot->delaunay_edge[oi] = TRUE;
+
+ // Lets rotate shared edge one vertex CW to legalize it
+ p2t_sweep_rotate_triangle_pair (THIS, t, p, ot, op);
+
+ // We now got one valid Delaunay Edge shared by two triangles
+ // This gives us 4 new edges to check for Delaunay
+
+ // Make sure that triangle to node mapping is done only one time for a specific triangle
+ gboolean not_legalized = !p2t_sweep_legalize (THIS, tcx, t);
+ if (not_legalized)
+ {
+ p2t_sweepcontext_map_triangle_to_nodes (tcx, t);
+ }
+
+ not_legalized = !p2t_sweep_legalize (THIS, tcx, ot);
+ if (not_legalized)
+ p2t_sweepcontext_map_triangle_to_nodes (tcx, ot);
+
+ // Reset the Delaunay edges, since they only are valid Delaunay edges
+ // until we add a new triangle or point.
+ // XXX: need to think about this. Can these edges be tried after we
+ // return to previous recursive level?
+ t->delaunay_edge[i] = FALSE;
+ ot->delaunay_edge[oi] = FALSE;
+
+ // If triangle have been legalized no need to check the other edges since
+ // the recursive legalization will handles those so we can end here.
+ return TRUE;
+ }
+ }
+ }
+ return FALSE;
+}
+
+gboolean
+p2t_sweep_incircle (P2tSweep *THIS, P2tPoint* pa, P2tPoint* pb, P2tPoint* pc, P2tPoint* pd)
+{
+ double adx = pa->x - pd->x;
+ double ady = pa->y - pd->y;
+ double bdx = pb->x - pd->x;
+ double bdy = pb->y - pd->y;
+
+ double adxbdy = adx * bdy;
+ double bdxady = bdx * ady;
+ double oabd = adxbdy - bdxady;
+
+ if (oabd <= 0)
+ return FALSE;
+
+ double cdx = pc->x - pd->x;
+ double cdy = pc->y - pd->y;
+
+ double cdxady = cdx * ady;
+ double adxcdy = adx * cdy;
+ double ocad = cdxady - adxcdy;
+
+ if (ocad <= 0)
+ return FALSE;
+
+ double bdxcdy = bdx * cdy;
+ double cdxbdy = cdx * bdy;
+
+ double alift = adx * adx + ady * ady;
+ double blift = bdx * bdx + bdy * bdy;
+ double clift = cdx * cdx + cdy * cdy;
+
+ double det = alift * (bdxcdy - cdxbdy) + blift * ocad + clift * oabd;
+
+ return det > 0;
+}
+
+void
+p2t_sweep_rotate_triangle_pair (P2tSweep *THIS, P2tTriangle *t, P2tPoint* p, P2tTriangle *ot, P2tPoint* op)
+{
+ P2tTriangle* n1, *n2, *n3, *n4;
+ n1 = p2t_triangle_neighbor_ccw (t, p);
+ n2 = p2t_triangle_neighbor_cw (t, p);
+ n3 = p2t_triangle_neighbor_ccw (ot, op);
+ n4 = p2t_triangle_neighbor_cw (ot, op);
+
+ gboolean ce1, ce2, ce3, ce4;
+ ce1 = p2t_triangle_get_constrained_edge_ccw (t, p);
+ ce2 = p2t_triangle_get_constrained_edge_cw (t, p);
+ ce3 = p2t_triangle_get_constrained_edge_ccw (ot, op);
+ ce4 = p2t_triangle_get_constrained_edge_cw (ot, op);
+
+ gboolean de1, de2, de3, de4;
+ de1 = p2t_triangle_get_delunay_edge_ccw (t, p);
+ de2 = p2t_triangle_get_delunay_edge_cw (t, p);
+ de3 = p2t_triangle_get_delunay_edge_ccw (ot, op);
+ de4 = p2t_triangle_get_delunay_edge_cw (ot, op);
+
+ p2t_triangle_legalize_pt_pt (t, p, op);
+ p2t_triangle_legalize_pt_pt (ot, op, p);
+
+ // Remap delaunay_edge
+ p2t_triangle_set_delunay_edge_ccw (ot, p, de1);
+ p2t_triangle_set_delunay_edge_cw (t, p, de2);
+ p2t_triangle_set_delunay_edge_ccw (t, op, de3);
+ p2t_triangle_set_delunay_edge_cw (ot, op, de4);
+
+ // Remap constrained_edge
+ p2t_triangle_set_constrained_edge_ccw (ot, p, ce1);
+ p2t_triangle_set_constrained_edge_cw (t, p, ce2);
+ p2t_triangle_set_constrained_edge_ccw (t, op, ce3);
+ p2t_triangle_set_constrained_edge_cw (ot, op, ce4);
+
+ // Remap neighbors
+ // XXX: might optimize the markNeighbor by keeping track of
+ // what side should be assigned to what neighbor after the
+ // rotation. Now mark neighbor does lots of testing to find
+ // the right side.
+ p2t_triangle_clear_neighbors (t);
+ p2t_triangle_clear_neighbors (ot);
+ if (n1) p2t_triangle_mark_neighbor_tr (ot, n1);
+ if (n2) p2t_triangle_mark_neighbor_tr (t, n2);
+ if (n3) p2t_triangle_mark_neighbor_tr (t, n3);
+ if (n4) p2t_triangle_mark_neighbor_tr (ot, n4);
+ p2t_triangle_mark_neighbor_tr (t, ot);
+}
+
+void
+p2t_sweep_fill_basin (P2tSweep *THIS, P2tSweepContext *tcx, P2tNode* node)
+{
+ if (p2t_orient2d (node->point, node->next->point, node->next->next->point) == CCW)
+ {
+ tcx->basin.left_node = node->next->next;
+ }
+ else
+ {
+ tcx->basin.left_node = node->next;
+ }
+
+ // Find the bottom and right node
+ tcx->basin.bottom_node = tcx->basin.left_node;
+ while (tcx->basin.bottom_node->next
+ && tcx->basin.bottom_node->point->y >= tcx->basin.bottom_node->next->point->y)
+ {
+ tcx->basin.bottom_node = tcx->basin.bottom_node->next;
+ }
+ if (tcx->basin.bottom_node == tcx->basin.left_node)
+ {
+ // No valid basin
+ return;
+ }
+
+ tcx->basin.right_node = tcx->basin.bottom_node;
+ while (tcx->basin.right_node->next
+ && tcx->basin.right_node->point->y < tcx->basin.right_node->next->point->y)
+ {
+ tcx->basin.right_node = tcx->basin.right_node->next;
+ }
+ if (tcx->basin.right_node == tcx->basin.bottom_node)
+ {
+ // No valid basins
+ return;
+ }
+
+ tcx->basin.width = tcx->basin.right_node->point->x - tcx->basin.left_node->point->x;
+ tcx->basin.left_highest = tcx->basin.left_node->point->y > tcx->basin.right_node->point->y;
+
+ p2t_sweep_fill_basin_req (THIS, tcx, tcx->basin.bottom_node);
+}
+
+void
+p2t_sweep_fill_basin_req (P2tSweep *THIS, P2tSweepContext *tcx, P2tNode* node)
+{
+ // if shallow stop filling
+ if (p2t_sweep_is_shallow (THIS, tcx, node))
+ {
+ return;
+ }
+
+ p2t_sweep_fill (THIS, tcx, node);
+
+ if (node->prev == tcx->basin.left_node && node->next == tcx->basin.right_node)
+ {
+ return;
+ }
+ else if (node->prev == tcx->basin.left_node)
+ {
+ P2tOrientation o = p2t_orient2d (node->point, node->next->point, node->next->next->point);
+ if (o == CW)
+ {
+ return;
+ }
+ node = node->next;
+ }
+ else if (node->next == tcx->basin.right_node)
+ {
+ P2tOrientation o = p2t_orient2d (node->point, node->prev->point, node->prev->prev->point);
+ if (o == CCW)
+ {
+ return;
+ }
+ node = node->prev;
+ }
+ else
+ {
+ // Continue with the neighbor node with lowest Y value
+ if (node->prev->point->y < node->next->point->y)
+ {
+ node = node->prev;
+ }
+ else
+ {
+ node = node->next;
+ }
+ }
+
+ p2t_sweep_fill_basin_req (THIS, tcx, node);
+}
+
+gboolean
+p2t_sweep_is_shallow (P2tSweep *THIS, P2tSweepContext *tcx, P2tNode* node)
+{
+ double height;
+
+ if (tcx->basin.left_highest)
+ {
+ height = tcx->basin.left_node->point->y - node->point->y;
+ }
+ else
+ {
+ height = tcx->basin.right_node->point->y - node->point->y;
+ }
+
+ // if shallow stop filling
+ if (tcx->basin.width > height)
+ {
+ return TRUE;
+ }
+ return FALSE;
+}
+
+void
+p2t_sweep_fill_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node)
+{
+ if (tcx->edge_event.right)
+ {
+ p2t_sweep_fill_right_above_edge_event (THIS, tcx, edge, node);
+ }
+ else
+ {
+ p2t_sweep_fill_left_above_edge_event (THIS, tcx, edge, node);
+ }
+}
+
+void
+p2t_sweep_fill_right_above_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node)
+{
+ while (node->next->point->x < edge->p->x)
+ {
+ // Check if next node is below the edge
+ if (p2t_orient2d (edge->q, node->next->point, edge->p) == CCW)
+ {
+ p2t_sweep_fill_right_below_edge_event (THIS, tcx, edge, node);
+ }
+ else
+ {
+ node = node->next;
+ }
+ }
+}
+
+void
+p2t_sweep_fill_right_below_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node)
+{
+ if (node->point->x < edge->p->x)
+ {
+ if (p2t_orient2d (node->point, node->next->point, node->next->next->point) == CCW)
+ {
+ // Concave
+ p2t_sweep_fill_right_concave_edge_event (THIS, tcx, edge, node);
+ }
+ else
+ {
+ // Convex
+ p2t_sweep_fill_right_convex_edge_event (THIS, tcx, edge, node);
+ // Retry this one
+ p2t_sweep_fill_right_below_edge_event (THIS, tcx, edge, node);
+ }
+ }
+}
+
+void
+p2t_sweep_fill_right_concave_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node)
+{
+ p2t_sweep_fill (THIS, tcx, node->next);
+ if (node->next->point != edge->p)
+ {
+ // Next above or below edge?
+ if (p2t_orient2d (edge->q, node->next->point, edge->p) == CCW)
+ {
+ // Below
+ if (p2t_orient2d (node->point, node->next->point, node->next->next->point) == CCW)
+ {
+ // Next is concave
+ p2t_sweep_fill_right_concave_edge_event (THIS, tcx, edge, node);
+ }
+ else
+ {
+ // Next is convex
+ }
+ }
+ }
+
+}
+
+void
+p2t_sweep_fill_right_convex_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node)
+{
+ // Next concave or convex?
+ if (p2t_orient2d (node->next->point, node->next->next->point, node->next->next->next->point) == CCW)
+ {
+ // Concave
+ p2t_sweep_fill_right_concave_edge_event (THIS, tcx, edge, node->next);
+ }
+ else
+ {
+ // Convex
+ // Next above or below edge?
+ if (p2t_orient2d (edge->q, node->next->next->point, edge->p) == CCW)
+ {
+ // Below
+ p2t_sweep_fill_right_convex_edge_event (THIS, tcx, edge, node->next);
+ }
+ else
+ {
+ // Above
+ }
+ }
+}
+
+void
+p2t_sweep_fill_left_above_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node)
+{
+ while (node->prev->point->x > edge->p->x)
+ {
+ // Check if next node is below the edge
+ if (p2t_orient2d (edge->q, node->prev->point, edge->p) == CW)
+ {
+ p2t_sweep_fill_left_below_edge_event (THIS, tcx, edge, node);
+ }
+ else
+ {
+ node = node->prev;
+ }
+ }
+}
+
+void
+p2t_sweep_fill_left_below_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node)
+{
+ if (node->point->x > edge->p->x)
+ {
+ if (p2t_orient2d (node->point, node->prev->point, node->prev->prev->point) == CW)
+ {
+ // Concave
+ p2t_sweep_fill_left_concave_edge_event (THIS, tcx, edge, node);
+ }
+ else
+ {
+ // Convex
+ p2t_sweep_fill_left_convex_edge_event (THIS, tcx, edge, node);
+ // Retry this one
+ p2t_sweep_fill_left_below_edge_event (THIS, tcx, edge, node);
+ }
+ }
+}
+
+void
+p2t_sweep_fill_left_convex_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node)
+{
+ // Next concave or convex?
+ if (p2t_orient2d (node->prev->point, node->prev->prev->point, node->prev->prev->prev->point) == CW)
+ {
+ // Concave
+ p2t_sweep_fill_left_concave_edge_event (THIS, tcx, edge, node->prev);
+ }
+ else
+ {
+ // Convex
+ // Next above or below edge?
+ if (p2t_orient2d (edge->q, node->prev->prev->point, edge->p) == CW)
+ {
+ // Below
+ p2t_sweep_fill_left_convex_edge_event (THIS, tcx, edge, node->prev);
+ }
+ else
+ {
+ // Above
+ }
+ }
+}
+
+void
+p2t_sweep_fill_left_concave_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node)
+{
+ p2t_sweep_fill (THIS, tcx, node->prev);
+ if (node->prev->point != edge->p)
+ {
+ // Next above or below edge?
+ if (p2t_orient2d (edge->q, node->prev->point, edge->p) == CW)
+ {
+ // Below
+ if (p2t_orient2d (node->point, node->prev->point, node->prev->prev->point) == CW)
+ {
+ // Next is concave
+ p2t_sweep_fill_left_concave_edge_event (THIS, tcx, edge, node);
+ }
+ else
+ {
+ // Next is convex
+ }
+ }
+ }
+
+}
+
+void
+p2t_sweep_flip_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tPoint* ep, P2tPoint* eq, P2tTriangle* t, P2tPoint* p)
+{
+ P2tTriangle* ot = p2t_triangle_neighbor_across (t, p);
+ P2tPoint* op = p2t_triangle_opposite_point (ot, t, p);
+
+ if (ot == NULL)
+ {
+ // If we want to integrate the fillEdgeEvent do it here
+ // With current implementation we should never get here
+ //throw new RuntimeException( "[BUG:FIXME] FLIP failed due to missing triangle");
+ assert (0);
+ }
+
+ if (p2t_utils_in_scan_area (p, p2t_triangle_point_ccw (t, p), p2t_triangle_point_cw (t, p), op))
+ {
+ // Lets rotate shared edge one vertex CW
+ p2t_sweep_rotate_triangle_pair (THIS, t, p, ot, op);
+ p2t_sweepcontext_map_triangle_to_nodes (tcx, t);
+ p2t_sweepcontext_map_triangle_to_nodes (tcx, ot);
+
+ if (p == eq && op == ep)
+ {
+ if (p2t_point_equals (eq, tcx->edge_event.constrained_edge->q) && p2t_point_equals (ep, tcx->edge_event.constrained_edge->p))
+ {
+ p2t_triangle_mark_constrained_edge_pt_pt (t, ep, eq);
+ p2t_triangle_mark_constrained_edge_pt_pt (ot, ep, eq);
+ p2t_sweep_legalize (THIS, tcx, t);
+ p2t_sweep_legalize (THIS, tcx, ot);
+ }
+ else
+ {
+ // XXX: I think one of the triangles should be legalized here?
+ }
+ }
+ else
+ {
+ P2tOrientation o = p2t_orient2d (eq, op, ep);
+ t = p2t_sweep_next_flip_triangle (THIS, tcx, (int) o, t, ot, p, op);
+ p2t_sweep_flip_edge_event (THIS, tcx, ep, eq, t, p);
+ }
+ }
+ else
+ {
+ P2tPoint* newP = p2t_sweep_next_flip_point (THIS, ep, eq, ot, op);
+ p2t_sweep_flip_scan_edge_event (THIS, tcx, ep, eq, t, ot, newP);
+ p2t_sweep_edge_event_pt_pt_tr_pt (THIS, tcx, ep, eq, t, p);
+ }
+}
+
+P2tTriangle*
+p2t_sweep_next_flip_triangle (P2tSweep *THIS, P2tSweepContext *tcx, int o, P2tTriangle *t, P2tTriangle *ot, P2tPoint* p, P2tPoint* op)
+{
+ if (o == CCW)
+ {
+ // ot is not crossing edge after flip
+ int edge_index = p2t_triangle_edge_index (ot, p, op);
+ ot->delaunay_edge[edge_index] = TRUE;
+ p2t_sweep_legalize (THIS, tcx, ot);
+ p2t_triangle_clear_delunay_edges (ot);
+ return t;
+ }
+
+ // t is not crossing edge after flip
+ int edge_index = p2t_triangle_edge_index (t, p, op);
+
+ t->delaunay_edge[edge_index] = TRUE;
+ p2t_sweep_legalize (THIS, tcx, t);
+ p2t_triangle_clear_delunay_edges (t);
+ return ot;
+}
+
+P2tPoint*
+p2t_sweep_next_flip_point (P2tSweep *THIS, P2tPoint* ep, P2tPoint* eq, P2tTriangle *ot, P2tPoint* op)
+{
+ P2tOrientation o2d = p2t_orient2d (eq, op, ep);
+ if (o2d == CW)
+ {
+ // Right
+ return p2t_triangle_point_ccw (ot, op);
+ }
+ else if (o2d == CCW)
+ {
+ // Left
+ return p2t_triangle_point_cw (ot, op);
+ }
+ else
+ {
+ //throw new RuntimeException("[Unsupported] Opposing point on constrained edge");
+ assert (0);
+ }
+}
+
+void
+p2t_sweep_flip_scan_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tPoint* ep, P2tPoint* eq, P2tTriangle *flip_triangle,
+ P2tTriangle *t, P2tPoint* p)
+{
+ P2tTriangle* ot = p2t_triangle_neighbor_across (t, p);
+ P2tPoint* op = p2t_triangle_opposite_point (ot, t, p);
+
+ if (p2t_triangle_neighbor_across (t, p) == NULL)
+ {
+ // If we want to integrate the fillEdgeEvent do it here
+ // With current implementation we should never get here
+ //throw new RuntimeException( "[BUG:FIXME] FLIP failed due to missing triangle");
+ assert (0);
+ }
+
+ if (p2t_utils_in_scan_area (eq, p2t_triangle_point_ccw (flip_triangle, eq), p2t_triangle_point_cw (flip_triangle, eq), op))
+ {
+ // flip with new edge op->eq
+ p2t_sweep_flip_edge_event (THIS, tcx, eq, op, ot, op);
+ // TODO: Actually I just figured out that it should be possible to
+ // improve this by getting the next ot and op before the the above
+ // flip and continue the flipScanEdgeEvent here
+ // set new ot and op here and loop back to inScanArea test
+ // also need to set a new flip_triangle first
+ // Turns out at first glance that this is somewhat complicated
+ // so it will have to wait.
+ }
+ else
+ {
+ P2tPoint* newP = p2t_sweep_next_flip_point (THIS, ep, eq, ot, op);
+ p2t_sweep_flip_scan_edge_event (THIS, tcx, ep, eq, flip_triangle, ot, newP);
+ }
+}
diff --git a/operations/common/seamless-clone/poly2tri-c/sweep/sweep.h b/operations/common/seamless-clone/poly2tri-c/sweep/sweep.h
new file mode 100755
index 0000000..cf33169
--- /dev/null
+++ b/operations/common/seamless-clone/poly2tri-c/sweep/sweep.h
@@ -0,0 +1,270 @@
+/*
+ * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
+ * http://code.google.com/p/poly2tri/
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without modification,
+ * are permitted provided that the following conditions are met:
+ *
+ * * Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright notice,
+ * this list of conditions and the following disclaimer in the documentation
+ * and/or other materials provided with the distribution.
+ * * Neither the name of Poly2Tri nor the names of its contributors may be
+ * used to endorse or promote products derived from this software without specific
+ * prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+/**
+ * Sweep-line, Constrained Delauney Triangulation (CDT) See: Domiter, V. and
+ * Zalik, B.(2008)'Sweep-line algorithm for constrained Delaunay triangulation',
+ * International Journal of Geographical Information Science
+ *
+ * "FlipScan" Constrained Edge Algorithm invented by Thomas ïhlïn, thahlen gmail com
+ */
+
+#ifndef SWEEP_H
+#define SWEEP_H
+
+#include "../common/poly2tri-private.h"
+#include "../common/shapes.h"
+
+struct Sweep_
+{
+//private:
+P2tNodePtrArray nodes_;
+
+};
+
+void p2t_sweep_init (P2tSweep* THIS);
+P2tSweep* p2t_sweep_new ();
+
+/**
+ * Destructor - clean up memory
+ */
+void p2t_sweep_destroy (P2tSweep* THIS);
+void p2t_sweep_free (P2tSweep* THIS);
+
+/**
+ * Triangulate
+ *
+ * @param tcx
+ */
+void p2t_sweep_triangulate (P2tSweep *THIS, P2tSweepContext *tcx);
+
+/**
+ * Start sweeping the Y-sorted point set from bottom to top
+ *
+ * @param tcx
+ */
+void p2t_sweep_sweep_points (P2tSweep *THIS, P2tSweepContext *tcx);
+
+/**
+ * Find closes node to the left of the new point and
+ * create a new triangle. If needed new holes and basins
+ * will be filled to.
+ *
+ * @param tcx
+ * @param point
+ * @return
+ */
+P2tNode* p2t_sweep_point_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tPoint* point);
+
+/**
+ *
+ *
+ * @param tcx
+ * @param edge
+ * @param node
+ */
+void p2t_sweep_edge_event_ed_n (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node);
+
+void p2t_sweep_edge_event_pt_pt_tr_pt (P2tSweep *THIS, P2tSweepContext *tcx, P2tPoint* ep, P2tPoint* eq, P2tTriangle* triangle, P2tPoint* point);
+
+/**
+ * Creates a new front triangle and legalize it
+ *
+ * @param tcx
+ * @param point
+ * @param node
+ * @return
+ */
+P2tNode* p2t_sweep_new_front_triangle (P2tSweep *THIS, P2tSweepContext *tcx, P2tPoint* point, P2tNode* node);
+
+/**
+ * Adds a triangle to the advancing front to fill a hole.
+ * @param tcx
+ * @param node - middle node, that is the bottom of the hole
+ */
+void p2t_sweep_fill (P2tSweep *THIS, P2tSweepContext *tcx, P2tNode* node);
+
+/**
+ * Returns true if triangle was legalized
+ */
+gboolean p2t_sweep_legalize (P2tSweep *THIS, P2tSweepContext *tcx, P2tTriangle *t);
+
+/**
+ * <b>Requirement</b>:<br>
+ * 1. a,b and c form a triangle.<br>
+ * 2. a and d is know to be on opposite side of bc<br>
+ * <pre>
+ * a
+ * +
+ * / \
+ * / \
+ * b/ \c
+ * +-------+
+ * / d \
+ * / \
+ * </pre>
+ * <b>Fact</b>: d has to be in area B to have a chance to be inside the circle formed by
+ * a,b and c<br>
+ * d is outside B if orient2d(a,b,d) or orient2d(c,a,d) is CW<br>
+ * This preknowledge gives us a way to optimize the incircle test
+ * @param a - triangle point, opposite d
+ * @param b - triangle point
+ * @param c - triangle point
+ * @param d - point opposite a
+ * @return true if d is inside circle, false if on circle edge
+ */
+gboolean p2t_sweep_incircle (P2tSweep *THIS, P2tPoint* pa, P2tPoint* pb, P2tPoint* pc, P2tPoint* pd);
+
+/**
+ * Rotates a triangle pair one vertex CW
+ *<pre>
+ * n2 n2
+ * P +-----+ P +-----+
+ * | t /| |\ t |
+ * | / | | \ |
+ * n1| / |n3 n1| \ |n3
+ * | / | after CW | \ |
+ * |/ oT | | oT \|
+ * +-----+ oP +-----+
+ * n4 n4
+ * </pre>
+ */
+void p2t_sweep_rotate_triangle_pair (P2tSweep *THIS, P2tTriangle *t, P2tPoint* p, P2tTriangle *ot, P2tPoint* op);
+
+/**
+ * Fills holes in the Advancing Front
+ *
+ *
+ * @param tcx
+ * @param n
+ */
+void p2t_sweep_fill_advancingfront (P2tSweep *THIS, P2tSweepContext *tcx, P2tNode* n);
+
+/**
+ *
+ * @param node - middle node
+ * @return the angle between 3 front nodes
+ */
+double p2t_sweep_hole_angle (P2tSweep *THIS, P2tNode* node);
+
+/**
+ * The basin angle is decided against the horizontal line [1,0]
+ */
+double p2t_sweep_basin_angle (P2tSweep *THIS, P2tNode* node);
+
+/**
+ * Fills a basin that has formed on the Advancing Front to the right
+ * of given node.<br>
+ * First we decide a left,bottom and right node that forms the
+ * boundaries of the basin. Then we do a reqursive fill.
+ *
+ * @param tcx
+ * @param node - starting node, this or next node will be left node
+ */
+void p2t_sweep_fill_basin (P2tSweep *THIS, P2tSweepContext *tcx, P2tNode* node);
+
+/**
+ * Recursive algorithm to fill a Basin with triangles
+ *
+ * @param tcx
+ * @param node - bottom_node
+ * @param cnt - counter used to alternate on even and odd numbers
+ */
+void p2t_sweep_fill_basin_req (P2tSweep *THIS, P2tSweepContext *tcx, P2tNode* node);
+
+gboolean p2t_sweep_is_shallow (P2tSweep *THIS, P2tSweepContext *tcx, P2tNode* node);
+
+gboolean p2t_sweep_is_edge_side_of_triangle (P2tSweep *THIS, P2tTriangle *triangle, P2tPoint* ep, P2tPoint* eq);
+
+void p2t_sweep_fill_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node);
+
+void p2t_sweep_fill_right_above_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node);
+
+void p2t_sweep_fill_right_below_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node);
+
+void p2t_sweep_fill_right_concave_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node);
+
+void p2t_sweep_fill_right_convex_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node);
+
+void p2t_sweep_fill_left_above_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node);
+
+void p2t_sweep_fill_left_below_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node);
+
+void p2t_sweep_fill_left_concave_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node);
+
+void p2t_sweep_fill_left_convex_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tEdge* edge, P2tNode* node);
+
+void p2t_sweep_flip_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tPoint* ep, P2tPoint* eq, P2tTriangle* t, P2tPoint* p);
+
+/**
+ * After a flip we have two triangles and know that only one will still be
+ * intersecting the edge. So decide which to contiune with and legalize the other
+ *
+ * @param tcx
+ * @param o - should be the result of an orient2d( eq, op, ep )
+ * @param t - triangle 1
+ * @param ot - triangle 2
+ * @param p - a point shared by both triangles
+ * @param op - another point shared by both triangles
+ * @return returns the triangle still intersecting the edge
+ */
+P2tTriangle* p2t_sweep_next_flip_triangle (P2tSweep *THIS, P2tSweepContext *tcx, int o, P2tTriangle *t, P2tTriangle *ot, P2tPoint* p, P2tPoint* op);
+
+/**
+ * When we need to traverse from one triangle to the next we need
+ * the point in current triangle that is the opposite point to the next
+ * triangle.
+ *
+ * @param ep
+ * @param eq
+ * @param ot
+ * @param op
+ * @return
+ */
+P2tPoint* p2t_sweep_next_flip_point (P2tSweep *THIS, P2tPoint* ep, P2tPoint* eq, P2tTriangle *ot, P2tPoint* op);
+
+/**
+ * Scan part of the FlipScan algorithm<br>
+ * When a triangle pair isn't flippable we will scan for the next
+ * point that is inside the flip triangle scan area. When found
+ * we generate a new flipEdgeEvent
+ *
+ * @param tcx
+ * @param ep - last point on the edge we are traversing
+ * @param eq - first point on the edge we are traversing
+ * @param flipTriangle - the current triangle sharing the point eq with edge
+ * @param t
+ * @param p
+ */
+void p2t_sweep_flip_scan_edge_event (P2tSweep *THIS, P2tSweepContext *tcx, P2tPoint* ep, P2tPoint* eq, P2tTriangle *flip_triangle, P2tTriangle *t, P2tPoint* p);
+
+void p2t_sweep_finalization_polygon (P2tSweep *THIS, P2tSweepContext *tcx);
+
+#endif
diff --git a/operations/common/seamless-clone/poly2tri-c/sweep/sweep_context.c b/operations/common/seamless-clone/poly2tri-c/sweep/sweep_context.c
new file mode 100755
index 0000000..0c827c0
--- /dev/null
+++ b/operations/common/seamless-clone/poly2tri-c/sweep/sweep_context.c
@@ -0,0 +1,313 @@
+/*
+ * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
+ * http://code.google.com/p/poly2tri/
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without modification,
+ * are permitted provided that the following conditions are met:
+ *
+ * * Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright notice,
+ * this list of conditions and the following disclaimer in the documentation
+ * and/or other materials provided with the distribution.
+ * * Neither the name of Poly2Tri nor the names of its contributors may be
+ * used to endorse or promote products derived from this software without specific
+ * prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+#include "sweep_context.h"
+#include "advancing_front.h"
+
+void
+p2t_sweepcontext_basin_init (P2tSweepContextBasin* THIS)
+{
+ p2t_sweepcontext_basin_clear (THIS);
+}
+
+void
+p2t_sweepcontext_basin_clear (P2tSweepContextBasin* THIS)
+{
+ THIS->left_node = NULL;
+ THIS->bottom_node = NULL;
+ THIS->right_node = NULL;
+ THIS->width = 0.0;
+ THIS->left_highest = FALSE;
+}
+
+void
+p2t_sweepcontext_edgeevent_init (P2tSweepContextEdgeEvent* THIS)
+{
+ THIS->constrained_edge = NULL;
+ THIS->right = FALSE;
+}
+
+void
+p2t_sweepcontext_init (P2tSweepContext* THIS, P2tPointPtrArray polyline)
+{
+ int i;
+ THIS->edge_list = g_ptr_array_new ();
+ THIS->triangles_ = g_ptr_array_new ();
+ THIS->map_ = NULL;
+
+ p2t_sweepcontext_basin_init (&THIS->basin);
+ p2t_sweepcontext_edgeevent_init (&THIS->edge_event);
+
+ THIS->points_ = g_ptr_array_sized_new (polyline->len);
+ for (i = 0; i < polyline->len; i++)
+ g_ptr_array_add (THIS->points_, point_index (polyline, i));
+
+ p2t_sweepcontext_init_edges (THIS, THIS->points_);
+}
+
+P2tSweepContext*
+p2t_sweepcontext_new (P2tPointPtrArray polyline)
+{
+ P2tSweepContext* THIS = g_new (P2tSweepContext, 1);
+ p2t_sweepcontext_init (THIS, polyline);
+ return THIS;
+}
+
+void
+p2t_sweepcontext_destroy (P2tSweepContext* THIS)
+{
+ GList* iter;
+ int i;
+ // Clean up memory
+
+ p2t_point_free (THIS->head_);
+ p2t_point_free (THIS->tail_);
+ p2t_advancingfront_free (THIS->front_);
+ p2t_node_free (THIS->af_head_);
+ p2t_node_free (THIS->af_middle_);
+ p2t_node_free (THIS->af_tail_);
+
+ g_ptr_array_free (THIS->triangles_, TRUE);
+
+ for (iter = g_list_first (THIS->map_); iter != NULL; iter = g_list_next (iter))
+ {
+ P2tTriangle* ptr = triangle_val (iter);
+ g_free (ptr);
+ }
+
+ g_list_free (THIS->map_);
+
+ for (i = 0; i < THIS->edge_list->len; i++)
+ {
+ p2t_edge_free (edge_index (THIS->edge_list, i));
+ }
+
+ g_ptr_array_free (THIS->edge_list, TRUE);
+
+}
+
+void
+p2t_sweepcontext_delete (P2tSweepContext* THIS)
+{
+ p2t_sweepcontext_destroy (THIS);
+ g_free(THIS);
+}
+
+void
+p2t_sweepcontext_add_hole (P2tSweepContext *THIS, P2tPointPtrArray polyline)
+{
+ int i;
+ p2t_sweepcontext_init_edges (THIS, polyline);
+ for (i = 0; i < polyline->len; i++)
+ {
+ g_ptr_array_add (THIS->points_, point_index (polyline, i));
+ }
+}
+
+void
+p2t_sweepcontext_add_point (P2tSweepContext *THIS, P2tPoint* point)
+{
+ g_ptr_array_add (THIS->points_, point);
+}
+
+P2tTrianglePtrArray
+p2t_sweepcontext_get_triangles (P2tSweepContext *THIS)
+{
+ return THIS->triangles_;
+}
+
+P2tTrianglePtrList
+p2t_sweepcontext_get_map (P2tSweepContext *THIS)
+{
+ return THIS->map_;
+}
+
+void
+p2t_sweepcontext_init_triangulation (P2tSweepContext *THIS)
+{
+ int i;
+ double xmax = point_index (THIS->points_, 0)->x, xmin = point_index (THIS->points_, 0)->x;
+ double ymax = point_index (THIS->points_, 0)->y, ymin = point_index (THIS->points_, 0)->y;
+
+ // Calculate bounds.
+ for (i = 0; i < THIS->points_->len; i++)
+ {
+ P2tPoint* p = point_index (THIS->points_, i);
+ if (p->x > xmax)
+ xmax = p->x;
+ if (p->x < xmin)
+ xmin = p->x;
+ if (p->y > ymax)
+ ymax = p->y;
+ if (p->y < ymin)
+ ymin = p->y;
+ }
+
+ double dx = kAlpha * (xmax - xmin);
+ double dy = kAlpha * (ymax - ymin);
+ THIS->head_ = p2t_point_new_dd (xmax + dx, ymin - dy);
+ THIS->tail_ = p2t_point_new_dd (xmin - dx, ymin - dy);
+
+ // Sort points along y-axis
+ g_ptr_array_sort (THIS->points_, p2t_point_cmp);
+}
+
+void
+p2t_sweepcontext_init_edges (P2tSweepContext *THIS, P2tPointPtrArray polyline)
+{
+ int i;
+ int num_points = polyline->len;
+ g_ptr_array_set_size (THIS->edge_list, THIS->edge_list->len + num_points); // C-OPTIMIZATION
+ for (i = 0; i < num_points; i++)
+ {
+ int j = i < num_points - 1 ? i + 1 : 0;
+ g_ptr_array_add (THIS->edge_list, p2t_edge_new (point_index (polyline, i), point_index (polyline, j)));
+ }
+}
+
+P2tPoint*
+p2t_sweepcontext_get_point (P2tSweepContext *THIS, const int index)
+{
+ return point_index (THIS->points_, index);
+}
+
+void
+p2t_sweepcontext_add_to_map (P2tSweepContext *THIS, P2tTriangle* triangle)
+{
+ THIS->map_ = g_list_append (THIS->map_, triangle);
+}
+
+P2tNode*
+p2t_sweepcontext_locate_node (P2tSweepContext *THIS, P2tPoint* point)
+{
+ // TODO implement search tree
+ return p2t_advancingfront_locate_node (THIS->front_, point->x);
+}
+
+void
+p2t_sweepcontext_create_advancingfront (P2tSweepContext *THIS, P2tNodePtrArray nodes)
+{
+
+ // Initial triangle
+ P2tTriangle* triangle = p2t_triangle_new (point_index (THIS->points_, 0), THIS->tail_, THIS->head_);
+
+ THIS->map_ = g_list_append (THIS->map_, triangle);
+
+ THIS->af_head_ = p2t_node_new_pt_tr (p2t_triangle_get_point (triangle, 1), triangle);
+ THIS->af_middle_ = p2t_node_new_pt_tr (p2t_triangle_get_point (triangle, 0), triangle);
+ THIS->af_tail_ = p2t_node_new_pt (p2t_triangle_get_point (triangle, 2));
+ THIS->front_ = p2t_advancingfront_new (THIS->af_head_, THIS->af_tail_);
+
+ // TODO: More intuitive if head is middles next and not previous?
+ // so swap head and tail
+ THIS->af_head_->next = THIS->af_middle_;
+ THIS->af_middle_->next = THIS->af_tail_;
+ THIS->af_middle_->prev = THIS->af_head_;
+ THIS->af_tail_->prev = THIS->af_middle_;
+}
+
+void
+p2t_sweepcontext_remove_node (P2tSweepContext *THIS, P2tNode* node)
+{
+ g_free (node);
+}
+
+void
+p2t_sweepcontext_map_triangle_to_nodes (P2tSweepContext *THIS, P2tTriangle* t)
+{
+ int i;
+ for (i = 0; i < 3; i++)
+ {
+ if (!p2t_triangle_get_neighbor (t, i))
+ {
+ P2tNode* n = p2t_advancingfront_locate_point (THIS->front_, p2t_triangle_point_cw (t, p2t_triangle_get_point (t, i)));
+ if (n)
+ n->triangle = t;
+ }
+ }
+}
+
+void
+p2t_sweepcontext_remove_from_map (P2tSweepContext *THIS, P2tTriangle* triangle)
+{
+ THIS->map_ = g_list_remove (THIS->map_, triangle);
+}
+
+void
+p2t_sweepcontext_mesh_clean (P2tSweepContext *THIS, P2tTriangle* triangle)
+{
+ int i;
+ if (triangle != NULL && !p2t_triangle_is_interior (triangle))
+ {
+ p2t_triangle_is_interior_b (triangle, TRUE);
+ g_ptr_array_add (THIS->triangles_, triangle);
+ for (i = 0; i < 3; i++)
+ {
+ if (!triangle->constrained_edge[i])
+ p2t_sweepcontext_mesh_clean (THIS, p2t_triangle_get_neighbor (triangle, i));
+ }
+ }
+}
+
+P2tAdvancingFront*
+p2t_sweepcontext_front (P2tSweepContext *THIS)
+{
+ return THIS->front_;
+}
+
+int
+p2t_sweepcontext_point_count (P2tSweepContext *THIS)
+{
+ return THIS->points_->len;
+}
+
+void
+p2t_sweepcontext_set_head (P2tSweepContext *THIS, P2tPoint* p1)
+{
+ THIS->head_ = p1;
+}
+
+P2tPoint*
+p2t_sweepcontext_head (P2tSweepContext *THIS)
+{
+ return THIS->head_;
+}
+
+void
+p2t_sweepcontext_set_tail (P2tSweepContext *THIS, P2tPoint* p1)
+{
+ THIS->tail_ = p1;
+}
+
+P2tPoint*
+p2t_sweepcontext_tail (P2tSweepContext *THIS)
+{
+ return THIS->tail_;
+}
diff --git a/operations/common/seamless-clone/poly2tri-c/sweep/sweep_context.h b/operations/common/seamless-clone/poly2tri-c/sweep/sweep_context.h
new file mode 100755
index 0000000..0e9a033
--- /dev/null
+++ b/operations/common/seamless-clone/poly2tri-c/sweep/sweep_context.h
@@ -0,0 +1,133 @@
+/*
+ * Poly2Tri Copyright (c) 2009-2010, Poly2Tri Contributors
+ * http://code.google.com/p/poly2tri/
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without modification,
+ * are permitted provided that the following conditions are met:
+ *
+ * * Redistributions of source code must retain the above copyright notice,
+ * this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright notice,
+ * this list of conditions and the following disclaimer in the documentation
+ * and/or other materials provided with the distribution.
+ * * Neither the name of Poly2Tri nor the names of its contributors may be
+ * used to endorse or promote products derived from this software without specific
+ * prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef SWEEP_CONTEXT_H
+#define SWEEP_CONTEXT_H
+
+#include "../common/poly2tri-private.h"
+#include "../common/shapes.h"
+#include "advancing_front.h"
+
+// Inital triangle factor, seed triangle will extend 30% of
+// PointSet width to both left and right.
+#define kAlpha 0.3
+
+struct P2tSweepContextBasin_
+{
+ P2tNode* left_node;
+ P2tNode* bottom_node;
+ P2tNode* right_node;
+ double width;
+ gboolean left_highest;
+};
+
+void p2t_sweepcontext_basin_init (P2tSweepContextBasin* THIS);
+void p2t_sweepcontext_basin_clear (P2tSweepContextBasin* THIS);
+
+struct P2tSweepContextEdgeEvent_
+{
+ P2tEdge* constrained_edge;
+ gboolean right;
+};
+
+void p2t_sweepcontext_edgeevent_init (P2tSweepContextEdgeEvent* THIS);
+
+struct SweepContext_
+{
+ P2tEdgePtrArray edge_list;
+
+ P2tSweepContextBasin basin;
+ P2tSweepContextEdgeEvent edge_event;
+
+ P2tTrianglePtrArray triangles_;
+ P2tTrianglePtrList map_;
+ P2tPointPtrArray points_;
+
+ // Advancing front
+ P2tAdvancingFront* front_;
+ // head point used with advancing front
+ P2tPoint* head_;
+ // tail point used with advancing front
+ P2tPoint* tail_;
+
+ P2tNode *af_head_, *af_middle_, *af_tail_;
+};
+
+/// Constructor
+void p2t_sweepcontext_init (P2tSweepContext* THIS, P2tPointPtrArray polyline);
+P2tSweepContext* p2t_sweepcontext_new (P2tPointPtrArray polyline);
+
+/// Destructor
+void p2t_sweepcontext_destroy (P2tSweepContext* THIS);
+void p2t_sweepcontext_delete (P2tSweepContext* THIS);
+
+void p2t_sweepcontext_set_head (P2tSweepContext *THIS, P2tPoint* p1);
+
+P2tPoint* p2t_sweepcontext_head (P2tSweepContext *THIS);
+
+void p2t_sweepcontext_set_tail (P2tSweepContext *THIS, P2tPoint* p1);
+
+P2tPoint* p2t_sweepcontext_tail (P2tSweepContext *THIS);
+
+int p2t_sweepcontext_point_count (P2tSweepContext *THIS);
+
+P2tNode* p2t_sweepcontext_locate_node (P2tSweepContext *THIS, P2tPoint* point);
+
+void p2t_sweepcontext_remove_node (P2tSweepContext *THIS, P2tNode* node);
+
+void p2t_sweepcontext_create_advancingfront (P2tSweepContext *THIS, P2tNodePtrArray nodes);
+
+/// Try to map a node to all sides of this triangle that don't have a neighbor
+void p2t_sweepcontext_map_triangle_to_nodes (P2tSweepContext *THIS, P2tTriangle* t);
+
+void p2t_sweepcontext_add_to_map (P2tSweepContext *THIS, P2tTriangle* triangle);
+
+P2tPoint* p2t_sweepcontext_get_point (P2tSweepContext *THIS, const int index);
+
+P2tPoint* SweepContext_GetPoints (P2tSweepContext *THIS);
+
+void p2t_sweepcontext_remove_from_map (P2tSweepContext *THIS, P2tTriangle* triangle);
+
+void p2t_sweepcontext_add_hole (P2tSweepContext *THIS, P2tPointPtrArray polyline);
+
+void p2t_sweepcontext_add_point (P2tSweepContext *THIS, P2tPoint* point);
+
+P2tAdvancingFront* p2t_sweepcontext_front (P2tSweepContext *THIS);
+
+void p2t_sweepcontext_mesh_clean (P2tSweepContext *THIS, P2tTriangle* triangle);
+
+P2tTrianglePtrArray p2t_sweepcontext_get_triangles (P2tSweepContext *THIS);
+P2tTrianglePtrList p2t_sweepcontext_get_map (P2tSweepContext *THIS);
+
+void p2t_sweepcontext_init_triangulation (P2tSweepContext *THIS);
+void p2t_sweepcontext_init_edges (P2tSweepContext *THIS, P2tPointPtrArray polyline);
+
+#endif
diff --git a/operations/common/seamless-clone/seamless-clone.c b/operations/common/seamless-clone/seamless-clone.c
new file mode 100644
index 0000000..d5b5e2a
--- /dev/null
+++ b/operations/common/seamless-clone/seamless-clone.c
@@ -0,0 +1,330 @@
+/* This file is an image processing operation for GEGL
+ *
+ * seamless-clone.c
+ * Copyright (C) 2011 Barak Itkin <lightningismyname gmail com>
+ *
+ * This program 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 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program 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 this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifdef GEGL_CHANT_PROPERTIES
+#else
+
+#define GEGL_CHANT_TYPE_COMPOSER
+#define GEGL_CHANT_C_FILE "seamless-clone.c"
+
+#include "config.h"
+#include <glib/gi18n-lib.h>
+#include "gegl-chant.h"
+
+#include <cairo.h>
+
+#include <stdio.h> /* TODO: get rid of this debugging way! */
+
+#include "poly2tri-c/poly2tri.h"
+#include "poly2tri-c/refine/triangulation.h"
+#include "seamless-clone.h"
+
+static GeglRectangle
+get_required_for_output (GeglOperation *operation,
+ const gchar *input_pad,
+ const GeglRectangle *region)
+{
+ GeglRectangle result;
+
+ if (g_strcmp0 (input_pad, "input"))
+ result = *gegl_operation_source_get_bounding_box (operation, "input");
+ else if (g_strcmp0 (input_pad, "aux"))
+ result = *gegl_operation_source_get_bounding_box (operation, "aux");
+ else
+ g_assert_not_reached ();
+
+ printf ("Input \"%s\" size is:\n", input_pad);
+ gegl_rectangle_dump (&result);
+
+ return result;
+}
+
+static void
+prepare (GeglOperation *operation)
+{
+ Babl *format = babl_format ("RGBA float");
+
+ gegl_operation_set_format (operation, "input", format);
+ gegl_operation_set_format (operation, "aux", format);
+ gegl_operation_set_format (operation, "output", format);
+}
+
+/*******************************************************************/
+/******************** Part 2 - Mesh rendering **********************/
+/*******************************************************************/
+
+/*
+ * Store the bounds of the mesh inside mesh_bounds
+ */
+static cairo_pattern_t*
+gimp_operation_seamless_clone_make_fine_mesh (GPtrArray *ptList,
+ GeglBuffer *aux,
+ GeglBuffer *input,
+ GeglRectangle *mesh_bounds)
+{
+ Babl *format = babl_format("RGB float");
+ gfloat dest[3], aux_c[3], input_c[3];
+ GList *X = NULL; /* List of P2tRPoint */
+ GList *XEs = NULL; /* List of P2tREdge */
+ gint i, N = ptList->len;
+
+ gint min_x = G_MAXINT, max_x = -G_MAXINT, min_y = G_MAXINT, max_y = -G_MAXINT;
+
+ GList *tmpPts = NULL, *tris = NULL;
+
+ printf ("Making mesh from %d points!\n", ptList->len);
+
+ for (i = 0; i < N; i++)
+ {
+ SPoint *pt = (SPoint*) g_ptr_array_index (ptList, i);
+ min_x = MIN (pt->x, min_x);
+ min_y = MIN (pt->y, min_y);
+ max_x = MAX (pt->x, max_x);
+ max_y = MAX (pt->y, max_y);
+ /* No one should care if the points are given in reverse order */
+ X = g_list_prepend (X, p2tr_point_new (pt->x, pt->y));
+ }
+
+ mesh_bounds->x = min_x;
+ mesh_bounds->y = min_y;
+ mesh_bounds->width = max_x - min_x;
+ mesh_bounds->height = max_y - min_y;
+
+ GList *liter = X;
+ while (liter != NULL)
+ {
+ P2tREdge *E = p2tr_edge_new ((P2tRPoint*)(liter->data), (P2tRPoint*)(g_list_cyclic_next(X,liter)->data));
+ XEs = g_list_prepend (XEs, E);
+ p2tr_edge_set_constrained (E, TRUE);
+ liter = liter->next;
+ }
+
+ printf ("Edges %p made, now just triangulate!\n", XEs);
+ P2tRTriangulation *T = p2tr_triangulate (X);
+ printf ("Triangulation %p made! %d triangles, %d(/2) edges, %d points\n", T, g_hash_table_size (T->tris),g_hash_table_size (T->edges),g_hash_table_size (T->pts));
+
+ DelaunayTerminator (T,XEs,M_PI/7,p2tr_false_delta);
+ printf ("Terminated!\n");
+
+ P2trHashSetIter iter;
+ P2tRTriangle *t;
+ p2tr_hash_set_iter_init (&iter, T->tris);
+ cairo_pattern_t *mesh = cairo_pattern_create_mesh ();
+
+ P2tRHashSet *edgePts;
+ GHashTable *sampling;
+
+ ComputeSampling (T, &edgePts, &sampling);
+
+
+#define GetPtColor(pt,dest) \
+do { \
+ if (p2tr_hash_set_contains (edgePts, (pt))) \
+ { \
+ gegl_buffer_sample (aux, (pt)->x, (pt)->y, NULL, aux_c, format, GEGL_INTERPOLATION_NEAREST); \
+ gegl_buffer_sample (input, (pt)->x, (pt)->y, NULL, input_c, format, GEGL_INTERPOLATION_NEAREST); \
+ (dest)[0] = TO_CAIRO(input_c[0] - aux_c[0]); \
+ (dest)[1] = TO_CAIRO(input_c[1] - aux_c[1]); \
+ (dest)[2] = TO_CAIRO(input_c[2] - aux_c[2]); \
+ } \
+ else \
+ ComputeInnerSample ((pt), g_hash_table_lookup (sampling, (pt)), input, aux, (dest)); \
+} while (FALSE)
+
+ while (p2tr_hash_set_iter_next (&iter, (gpointer*)&t))
+ {
+ p2tr_assert_and_explain (t != NULL, "NULL triangle found!\n");
+ p2tr_assert_and_explain (t->edges[0] != NULL && t->edges[1] != NULL && t->edges[2] != NULL,
+ "Removed triangle found!\n");
+
+
+ P2tRPoint* tpt;
+ cairo_mesh_pattern_begin_patch (mesh);
+
+ tpt = p2tr_edge_get_start (t->edges[0]);
+ cairo_mesh_pattern_move_to (mesh, tpt->x, tpt->y);
+
+ tpt = p2tr_edge_get_start (t->edges[1]);
+ cairo_mesh_pattern_line_to (mesh, tpt->x, tpt->y);
+
+ tpt = p2tr_edge_get_start (t->edges[2]);
+ cairo_mesh_pattern_line_to (mesh, tpt->x, tpt->y);
+
+// tpt = p2t_triangle_get_point (triangle_index(tris,i), 0);
+// cairo_mesh_pattern_line_to (mesh, tpt->x, tpt->y);
+
+ tpt = p2tr_edge_get_start (t->edges[0]);
+ GetPtColor (tpt,dest);
+ cairo_mesh_pattern_set_corner_color_rgb (mesh, 0, dest[2], dest[1], dest[0]);
+
+ tpt = p2tr_edge_get_start (t->edges[1]);
+ GetPtColor (tpt,dest);
+ cairo_mesh_pattern_set_corner_color_rgb (mesh, 1, dest[2], dest[1], dest[0]);
+
+ tpt = p2tr_edge_get_start (t->edges[2]);
+ GetPtColor (tpt,dest);
+ cairo_mesh_pattern_set_corner_color_rgb (mesh, 2, dest[2], dest[1], dest[0]);
+
+ cairo_mesh_pattern_end_patch (mesh);
+ }
+ return mesh;
+}
+
+static void
+render_outline (GPtrArray *pts,
+ cairo_t *cr)
+{
+ SPoint *pt;
+ gint i;
+
+ if (pts->len <= 0)
+ return;
+
+ pt = (SPoint*) g_ptr_array_index (pts, 0);
+
+ cairo_move_to (cr, pt->x, pt->y);
+
+ for (i = 1; i < pts->len; i++)
+ {
+ pt = (SPoint*) g_ptr_array_index (pts, i);
+ cairo_line_to (cr, pt->x, pt->y);
+ }
+
+ cairo_close_path (cr);
+}
+
+/*******************************************************************/
+/********************** Part 3 - Cairo Utils ***********************/
+/*******************************************************************/
+static cairo_surface_t *
+surface_for_rect (const GeglRectangle *roi)
+{
+ guchar *data;
+
+ data = g_new0 (guchar, roi->width * roi->height * 4);
+
+ return cairo_image_surface_create_for_data (data,
+ CAIRO_FORMAT_ARGB32,
+ roi->width,
+ roi->height,
+ roi->width * 4);
+}
+
+static void
+commit_and_free_surface (GeglBuffer *output,
+ GeglBuffer *aux,
+ const GeglRectangle *roi,
+ cairo_surface_t *surface)
+{
+ gint i, j;
+ Babl *format = babl_format ("RGBA u8");
+ guchar *data = cairo_image_surface_get_data (surface);
+ guchar bg[3];
+
+ g_assert (cairo_image_surface_get_width (surface) == roi->width);
+ g_assert (cairo_image_surface_get_height (surface) == roi->height);
+ g_assert (cairo_image_surface_get_stride (surface) == roi->width * 4);
+
+ for (i = 0; i < roi->height; i++)
+ for (j = 0; j < roi->width; j++)
+ {
+ gint off = (i * roi->width + j) * 4;
+ gegl_buffer_sample (aux, roi->x + j, roi->y + i, NULL, bg, format, GEGL_INTERPOLATION_NEAREST);
+
+ data[off++] = (gint)CLAMP(bg[0] + FROM_CAIRO(data[off]), 0, 255);
+ data[off++] = (gint)CLAMP(bg[1] + FROM_CAIRO(data[off]), 0, 255);
+ data[off++] = (gint)CLAMP(bg[2] + FROM_CAIRO(data[off]), 0, 255);
+ data[off] = (data[off] >= 255) ? 255 : 0;
+ }
+
+
+ gegl_buffer_set (output, roi, format, data,
+ GEGL_AUTO_ROWSTRIDE);
+
+ cairo_surface_destroy (surface);
+// g_free (data);
+}
+
+static gboolean
+process (GeglOperation *operation,
+ GeglBuffer *input,
+ GeglBuffer *aux,
+ GeglBuffer *output,
+ const GeglRectangle *result)
+{
+ GPtrArray *ptList;
+ gfloat *aux_raw;
+
+ // GeglRectangle input_rect = *gegl_buffer_get_extent (input);
+ GeglRectangle aux_rect = *gegl_operation_source_get_bounding_box (operation, "aux");
+
+ cairo_surface_t *out_surf;
+ cairo_t *cr;
+
+ printf ("The aux_rect is:\n");
+ gegl_rectangle_dump (&aux_rect);
+
+ aux_raw = g_new (gfloat, 4 * aux_rect.width * aux_rect.height);
+
+ gegl_buffer_get (aux, 1.0, &aux_rect, babl_format("RGBA float"), aux_raw, GEGL_AUTO_ROWSTRIDE);
+
+ ptList = outline_find_ccw (&aux_rect, aux_raw);
+
+ g_free (aux_raw);
+ aux_raw = NULL;
+
+ printf ("The result is:\n");
+ gegl_rectangle_dump (result);
+
+ out_surf = surface_for_rect (result);
+ cr = cairo_create (out_surf);
+
+ GeglRectangle mesh_bounds;
+ cairo_pattern_t *mesh = gimp_operation_seamless_clone_make_fine_mesh (ptList, aux, input, &mesh_bounds);
+ cairo_set_source (cr, mesh);
+ render_outline (ptList, cr);
+ cairo_fill_preserve (cr);
+
+ cairo_pattern_destroy (mesh);
+ cairo_destroy (cr);
+ commit_and_free_surface (output, aux, result, out_surf);
+
+ g_free (aux_raw);
+ g_ptr_array_free (ptList, TRUE);
+
+ return TRUE;
+}
+
+static void
+gegl_chant_class_init (GeglChantClass *klass)
+{
+ GeglOperationClass *operation_class = GEGL_OPERATION_CLASS (klass);
+ GeglOperationComposerClass *composer_class = GEGL_OPERATION_COMPOSER_CLASS (klass);
+
+ operation_class->prepare = prepare;
+ operation_class->name = "gegl:seamless-clone";
+ operation_class->categories = "blend";
+ operation_class->description = "Seamless cloning operation";
+ operation_class->get_required_for_output = get_required_for_output;
+
+ composer_class->process = process;
+}
+
+
+#endif
diff --git a/operations/common/seamless-clone/seamless-clone.h b/operations/common/seamless-clone/seamless-clone.h
new file mode 100644
index 0000000..88d41f0
--- /dev/null
+++ b/operations/common/seamless-clone/seamless-clone.h
@@ -0,0 +1,34 @@
+/* This file is an image processing operation for GEGL
+ *
+ * seamless-clone.h
+ * Copyright (C) 2011 Barak Itkin <lightningismyname gmail com>
+ *
+ * This program 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 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program 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 this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef __SEAMLESS_CLONE_H__
+#define __SEAMLESS_CLONE_H__
+
+#define TO_CAIRO(col) ((col)/2+0.5)
+//#define FROM_CAIRO(col) (((col)-0.5)*2)
+//#define TO_CAIRO(col) (col)
+#define FROM_CAIRO(col) ((col - 128)*2)
+
+#include "poly2tri-c/poly2tri.h"
+#include "poly2tri-c/refine/triangulation.h"
+
+#include "find-outline.h"
+#include "make-mesh.h"
+
+#endif
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
