[gimp/soc-2011-seamless-clone] Work in progress, add triangular mesh rendering support. Depends on poly2tri-c
- From: Barak Itkin <barakitkin src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gimp/soc-2011-seamless-clone] Work in progress, add triangular mesh rendering support. Depends on poly2tri-c
- Date: Thu, 21 Jul 2011 20:48:28 +0000 (UTC)
commit 0ef19875d6be003571c12ce8f25a84d8f99e4e95
Author: Barak Itkin <lightningismyname gmail com>
Date: Thu Jul 21 23:47:00 2011 +0300
Work in progress, add triangular mesh rendering support. Depends on poly2tri-c
app/gegl/Makefile.am | 18 +
app/gegl/gimp-gegl-types.h | 1 +
app/gegl/gimp-gegl.c | 2 +
app/gegl/gimpoperationfindoutline.c | 31 +-
app/gegl/gimpoperationfindoutline.h | 6 +-
app/gegl/gimpoperationseamlessclone.c | 291 ++++++++
app/gegl/gimpoperationseamlessclone.h | 58 ++
app/gegl/poly2tri-c/common/cutils.h | 37 +
app/gegl/poly2tri-c/common/poly2tri-private.h | 34 +
app/gegl/poly2tri-c/common/shapes.c | 732 +++++++++++++++++++
app/gegl/poly2tri-c/common/shapes.h | 150 ++++
app/gegl/poly2tri-c/common/utils.c | 95 +++
app/gegl/poly2tri-c/common/utils.h | 63 ++
app/gegl/poly2tri-c/poly2tri.h | 39 +
app/gegl/poly2tri-c/sweep/advancing_front.c | 215 ++++++
app/gegl/poly2tri-c/sweep/advancing_front.h | 87 +++
app/gegl/poly2tri-c/sweep/cdt.c | 90 +++
app/gegl/poly2tri-c/sweep/cdt.h | 101 +++
app/gegl/poly2tri-c/sweep/sweep.c | 932 +++++++++++++++++++++++++
app/gegl/poly2tri-c/sweep/sweep.h | 270 +++++++
app/gegl/poly2tri-c/sweep/sweep_context.c | 313 +++++++++
app/gegl/poly2tri-c/sweep/sweep_context.h | 133 ++++
app/tools/gimpseamlessclonetool.c | 39 +-
23 files changed, 3702 insertions(+), 35 deletions(-)
---
diff --git a/app/gegl/Makefile.am b/app/gegl/Makefile.am
index bcd5143..c62a4a1 100644
--- a/app/gegl/Makefile.am
+++ b/app/gegl/Makefile.am
@@ -73,9 +73,27 @@ libappgegl_a_sources = \
gimpoperationlevels.h \
gimpoperationposterize.c \
gimpoperationposterize.h \
+ gimpoperationseamlessclone.c \
+ gimpoperationseamlessclone.h \
gimpoperationthreshold.c \
gimpoperationthreshold.h \
\
+ poly2tri-c/poly2tri.h \
+ poly2tri-c/common/cutils.h \
+ poly2tri-c/common/poly2tri-private.h \
+ poly2tri-c/common/shapes.c \
+ poly2tri-c/common/shapes.h \
+ poly2tri-c/common/utils.c \
+ poly2tri-c/common/utils.h \
+ poly2tri-c/sweep/advancing_front.c \
+ poly2tri-c/sweep/advancing_front.h \
+ poly2tri-c/sweep/cdt.c \
+ poly2tri-c/sweep/cdt.h \
+ poly2tri-c/sweep/sweep.c \
+ poly2tri-c/sweep/sweep.h \
+ poly2tri-c/sweep/sweep_context.c \
+ poly2tri-c/sweep/sweep_context.h \
+ \
gimpoperationpointlayermode.c \
gimpoperationpointlayermode.h \
gimpoperationdissolvemode.c \
diff --git a/app/gegl/gimp-gegl-types.h b/app/gegl/gimp-gegl-types.h
index 413d341..612f369 100644
--- a/app/gegl/gimp-gegl-types.h
+++ b/app/gegl/gimp-gegl-types.h
@@ -41,6 +41,7 @@ typedef struct _GimpOperationFindOutline GimpOperationFindOutline;
typedef struct _GimpOperationHueSaturation GimpOperationHueSaturation;
typedef struct _GimpOperationLevels GimpOperationLevels;
typedef struct _GimpOperationPosterize GimpOperationPosterize;
+typedef struct _GimpOperationSeamlessClone GimpOperationSeamlessClone;
typedef struct _GimpOperationThreshold GimpOperationThreshold;
typedef struct _GimpOperationPointLayerMode GimpOperationPointLayerMode;
diff --git a/app/gegl/gimp-gegl.c b/app/gegl/gimp-gegl.c
index c07f380..3707a48 100644
--- a/app/gegl/gimp-gegl.c
+++ b/app/gegl/gimp-gegl.c
@@ -41,6 +41,7 @@
#include "gimpoperationhuesaturation.h"
#include "gimpoperationlevels.h"
#include "gimpoperationposterize.h"
+#include "gimpoperationseamlessclone.h"
#include "gimpoperationthreshold.h"
#include "gimpoperationtilesink.h"
#include "gimpoperationtilesource.h"
@@ -108,6 +109,7 @@ gimp_gegl_init (Gimp *gimp)
g_type_class_ref (GIMP_TYPE_OPERATION_HUE_SATURATION);
g_type_class_ref (GIMP_TYPE_OPERATION_LEVELS);
g_type_class_ref (GIMP_TYPE_OPERATION_POSTERIZE);
+ g_type_class_ref (GIMP_TYPE_OPERATION_SEAMLESS_CLONE);
g_type_class_ref (GIMP_TYPE_OPERATION_THRESHOLD);
g_type_class_ref (GIMP_TYPE_OPERATION_POINT_LAYER_MODE);
diff --git a/app/gegl/gimpoperationfindoutline.c b/app/gegl/gimpoperationfindoutline.c
index b54bc72..b3e21a4 100644
--- a/app/gegl/gimpoperationfindoutline.c
+++ b/app/gegl/gimpoperationfindoutline.c
@@ -90,10 +90,10 @@ gimp_operation_find_outline_class_init (GimpOperationFindOutlineClass *klass)
G_PARAM_READWRITE));
g_object_class_install_property (object_class, PROP_THRESHOLD,
- g_param_spec_double ("threshold",
+ g_param_spec_float ("threshold",
"Threshold",
"The threshold for determining the difference between black and white (white >= thres)",
- -G_MAXDOUBLE, G_MAXDOUBLE, 0.5,
+ -G_MAXFLOAT, G_MAXFLOAT, 0.5f,
G_PARAM_READWRITE));
/* Workaround around wrong ROI calculation in GEGL for Sink ops when needs_full is set */
@@ -145,7 +145,7 @@ gimp_operation_find_outline_get_property (GObject *object,
g_value_set_pointer (value, self->ptList);
break;
case PROP_THRESHOLD:
- g_value_set_double (value, self->threshold);
+ g_value_set_float (value, self->threshold);
break;
case PROP_X:
g_value_set_int (value, self->x);
@@ -180,7 +180,7 @@ gimp_operation_find_outline_set_property (GObject *object,
self->ptList = g_value_get_pointer (value);
break;
case PROP_THRESHOLD:
- self->threshold = g_value_get_double (value);
+ self->threshold = g_value_get_float (value);
break;
case PROP_X:
self->x = g_value_get_int (value);
@@ -241,6 +241,7 @@ typedef enum {
#define isEast(s) (((s) == D_NE) || ((s) == D_E) || ((s) == D_SE))
#define isWest(s) (((s) == D_NW) || ((s) == D_W) || ((s) == D_SW))
+#define BABL_FORMAT
typedef struct {
gint x, y;
} SPoint;
@@ -278,7 +279,7 @@ gimp_operation_find_outline_is_inside (OutlineProcPrivate *OPP, SPoint *pt)
&& in_range (pt->y, OPP->ymin, OPP->ymax);
}
-#define get_value(OPP,x,y) (((OPP)->im)[((y)-(OPP)->ymin)*(OPP)->rowstride+(x)-(OPP)->xmin])
+#define get_value(OPP,x,y) (((OPP)->im)[(((y)-(OPP)->ymin)*(OPP)->rowstride+(x)-(OPP)->xmin)*4+3])
#define get_valuePT(OPP,pt) get_value(OPP,(pt)->x,(pt)->y)
static inline gboolean
@@ -394,27 +395,13 @@ gimp_operation_find_outline_process (GeglOperation *operation,
OPP->ymax = self->y + self->height - 1;
OPP->threshold = self->threshold;
- OPP->im = g_new (gdouble,(rect.width) * rect.height);
+ OPP->im = g_new (gfloat,4 * (rect.width) * rect.height);
OPP->rowstride = rect.width;
- gegl_buffer_get (input, 1.0, &rect, babl_format("Y double"), OPP->im, GEGL_AUTO_ROWSTRIDE);
+ gegl_buffer_get (input, 1.0, &rect, babl_format("RGBA float"), OPP->im, GEGL_AUTO_ROWSTRIDE);
gimp_operation_find_outline_find_outline_ccw (OPP, self->ptList);
-// gint x, y;
-// /* First of all try to find a white pixel */
-// for (y = OPP->ymin; y < OPP->ymax; y++)
-// {
-// for (x = OPP->xmin; x < OPP->xmax; x++)
-// {
-// if (get_value (OPP, x, y) >= OPP->threshold)
-// printf ("1");
-// else
-// printf ("0");
-// }
-// printf("\n");
-// }
-
g_free (OPP->im);
OPP->im = NULL;
@@ -426,5 +413,5 @@ gimp_operation_find_outline_prepare (GeglOperation *operation)
{
printf ("Preparing!\n");
- gegl_operation_set_format (operation, "input", babl_format("Y double"));
+ gegl_operation_set_format (operation, "input", babl_format("RGBA float"));
}
diff --git a/app/gegl/gimpoperationfindoutline.h b/app/gegl/gimpoperationfindoutline.h
index ba80bc9..5685410 100644
--- a/app/gegl/gimpoperationfindoutline.h
+++ b/app/gegl/gimpoperationfindoutline.h
@@ -40,8 +40,8 @@ typedef struct
gint xmin, xmax;
gint ymin, ymax;
gint rowstride;
- gdouble threshold;
- gdouble *im;
+ float threshold;
+ float *im;
} OutlineProcPrivate;
struct _GimpOperationFindOutline
@@ -50,7 +50,7 @@ struct _GimpOperationFindOutline
GPtrArray *ptList;
gint x, y, width, height;
- gdouble threshold;
+ float threshold;
/* Remains from old versions. Merge with properties above one day */
OutlineProcPrivate *opp;
diff --git a/app/gegl/gimpoperationseamlessclone.c b/app/gegl/gimpoperationseamlessclone.c
new file mode 100644
index 0000000..f3e20ed
--- /dev/null
+++ b/app/gegl/gimpoperationseamlessclone.c
@@ -0,0 +1,291 @@
+/* GIMP - The GNU Image Manipulation Program
+ *
+ * gimpoperationseamlessclone.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/>.
+ */
+
+/* TODO: release resources, mainly the mesh pattern and points */
+
+#include "config.h"
+#include <gegl.h>
+#include <cairo.h>
+
+#include "gimp-gegl-types.h"
+
+#include "gimpoperationseamlessclone.h"
+#include "poly2tri-c/poly2tri.h"
+
+#include <stdio.h> /* TODO: get rid of this debugging way! */
+
+enum
+{
+ PROP0,
+ PROP_POINTS,
+ PROP_X,
+ PROP_Y
+};
+
+static void
+gimp_operation_seamless_clone_init (GimpOperationSeamlessClone *self);
+
+static void
+gimp_operation_seamless_clone_get_property (GObject *object,
+ guint property_id,
+ GValue *value,
+ GParamSpec *pspec);
+
+static void
+gimp_operation_seamless_clone_set_property (GObject *object,
+ guint property_id,
+ const GValue *value,
+ GParamSpec *pspec);
+
+static gboolean
+gimp_operation_seamless_clone_process (GeglOperation *operation,
+ GeglBuffer *output,
+ const GeglRectangle *roi);
+
+static GeglRectangle
+gimp_operation_seamless_clone_get_bounding_box (GeglOperation *operation);
+
+static void
+gimp_operation_seamless_clone_prepare (GeglOperation *operation);
+
+G_DEFINE_TYPE (GimpOperationSeamlessClone, gimp_operation_seamless_clone,
+ GEGL_TYPE_OPERATION_SOURCE)
+
+#define parent_class gimp_operation_seamless_clone_parent_class
+
+static void
+gimp_operation_seamless_clone_class_init (GimpOperationSeamlessCloneClass *klass)
+{
+ GObjectClass *object_class = G_OBJECT_CLASS (klass);
+ GeglOperationClass *operation_class = GEGL_OPERATION_CLASS (klass);
+ GeglOperationSourceClass *source_class = GEGL_OPERATION_SOURCE_CLASS (klass);
+
+ object_class->set_property = gimp_operation_seamless_clone_set_property;
+ object_class->get_property = gimp_operation_seamless_clone_get_property;
+
+ operation_class->prepare = gimp_operation_seamless_clone_prepare;
+ operation_class->get_bounding_box = gimp_operation_seamless_clone_get_bounding_box;
+ operation_class->name = "gimp:seamless-clone";
+ operation_class->categories = "programming";
+ operation_class->description = "GIMP seamless clone operation";
+
+ source_class->process = gimp_operation_seamless_clone_process;
+
+ g_object_class_install_property (object_class, PROP_POINTS,
+ g_param_spec_pointer ("points",
+ "Points",
+ "A GPtrArray* of struct {gint x, y;} containing the points",
+ G_PARAM_READWRITE));
+
+ /* Workaround around wrong ROI calculation in GEGL for Sink ops when needs_full is set */
+ g_object_class_install_property (object_class, PROP_X,
+ g_param_spec_int ("x",
+ "X",
+ "The minimal x of the scaning rect",
+ -G_MAXINT, G_MAXINT, 0,
+ G_PARAM_READWRITE));
+
+ g_object_class_install_property (object_class, PROP_Y,
+ g_param_spec_int ("y",
+ "Y",
+ "The minimal Y of the scaning rect",
+ -G_MAXINT, G_MAXINT, 0,
+ G_PARAM_READWRITE));
+
+}
+
+static void
+gimp_operation_seamless_clone_init (GimpOperationSeamlessClone *self)
+{
+ self->mesh = NULL;
+}
+
+static void
+gimp_operation_seamless_clone_get_property (GObject *object,
+ guint property_id,
+ GValue *value,
+ GParamSpec *pspec)
+{
+ GimpOperationSeamlessClone *self = GIMP_OPERATION_SEAMLESS_CLONE (object);
+
+ switch (property_id)
+ {
+ case PROP_POINTS:
+ g_value_set_pointer (value, self->ptList);
+ break;
+ case PROP_X:
+ g_value_set_int (value, self->x);
+ break;
+ case PROP_Y:
+ g_value_set_int (value, self->y);
+ break;
+
+ default:
+ G_OBJECT_WARN_INVALID_PROPERTY_ID (object, property_id, pspec);
+ break;
+ }
+}
+
+static void
+gimp_operation_seamless_clone_set_property (GObject *object,
+ guint property_id,
+ const GValue *value,
+ GParamSpec *pspec)
+{
+ GimpOperationSeamlessClone *self = GIMP_OPERATION_SEAMLESS_CLONE (object);
+
+ switch (property_id)
+ {
+ case PROP_POINTS:
+ self->ptList = g_value_get_pointer (value);
+ break;
+ case PROP_X:
+ self->x = g_value_get_int (value);
+ break;
+ case PROP_Y:
+ self->y = g_value_get_int (value);
+ break;
+
+ default:
+ G_OBJECT_WARN_INVALID_PROPERTY_ID (object, property_id, pspec);
+ break;
+ }
+}
+
+typedef struct {
+ gint x, y;
+} SPoint;
+
+static void
+gimp_operation_seamless_clone_make_mesh (GimpOperationSeamlessClone *self)
+{
+ P2tCDT *CDT;
+ SPoint *pt;
+ gint i;
+
+ gint min_x = G_MAXINT, max_x = -G_MAXINT, min_y = G_MAXINT, max_y = -G_MAXINT;
+
+ GPtrArray *tmpPts, *tris;
+
+ if (self->mesh != NULL)
+ return;
+
+ tmpPts = g_ptr_array_new ();
+
+ printf ("Making mesh from %d points!\n", self->ptList->len);
+
+ for (i = 0; i < self->ptList->len; i++)
+ {
+ pt = (SPoint*) g_ptr_array_index (self->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);
+ g_ptr_array_add (tmpPts, p2t_point_new_dd (pt->x, pt->y));
+ }
+
+ self->mesh_bounds.x = min_x;
+ self->mesh_bounds.y = min_y;
+ self->mesh_bounds.width = max_x - min_x;
+ self->mesh_bounds.height = max_y - min_y;
+
+ CDT = p2t_cdt_new (tmpPts);
+ p2t_cdt_triangulate (CDT);
+
+ tris = p2t_cdt_get_triangles (CDT);
+ printf ("The mesh has %d triangles!\n", tris->len);
+
+ self->mesh = cairo_pattern_create_mesh ();
+
+ for (i = 0; i < tris->len; i++)
+ {
+ P2tPoint* tpt;
+ cairo_mesh_pattern_begin_patch (self->mesh);
+
+ tpt = p2t_triangle_get_point (triangle_index(tris,i), 0);
+ cairo_mesh_pattern_move_to (self->mesh, tpt->x, tpt->y);
+
+ tpt = p2t_triangle_get_point (triangle_index(tris,i), 1);
+ cairo_mesh_pattern_line_to (self->mesh, tpt->x, tpt->y);
+
+ tpt = p2t_triangle_get_point (triangle_index(tris,i), 2);
+ cairo_mesh_pattern_line_to (self->mesh, tpt->x, tpt->y);
+
+ tpt = p2t_triangle_get_point (triangle_index(tris,i), 0);
+ cairo_mesh_pattern_line_to (self->mesh, tpt->x, tpt->y);
+
+ cairo_mesh_pattern_set_corner_color_rgb (self->mesh, 0, 1, 0, 0);
+ cairo_mesh_pattern_set_corner_color_rgb (self->mesh, 1, 0, 1, 0);
+ cairo_mesh_pattern_set_corner_color_rgb (self->mesh, 2, 0, 0, 1);
+
+ cairo_mesh_pattern_end_patch (self->mesh);
+ }
+
+ p2t_cdt_free (CDT);
+}
+
+static GeglRectangle
+gimp_operation_seamless_clone_get_bounding_box (GeglOperation *operation)
+{
+ return GIMP_OPERATION_SEAMLESS_CLONE (operation)->mesh_bounds;
+}
+
+static gboolean
+gimp_operation_seamless_clone_process (GeglOperation *operation,
+ GeglBuffer *output,
+ const GeglRectangle *roi)
+{
+ GimpOperationSeamlessClone *self = GIMP_OPERATION_SEAMLESS_CLONE (operation);
+
+ guchar *data = g_new0 (guchar, roi->width * roi->height * 4);
+ cairo_t *cr;
+ cairo_surface_t *surface;
+
+ surface = cairo_image_surface_create_for_data (data,
+ CAIRO_FORMAT_ARGB32,
+ roi->width,
+ roi->height,
+ roi->width * 4);
+
+ cr = cairo_create (surface);
+ // cairo_translate (cr, -roi->x, -roi->y);
+ cairo_set_source (cr, self->mesh);
+ cairo_paint (cr);
+
+ gegl_buffer_set (output, roi, babl_format ("B'aG'aR'aA u8"), data,
+ GEGL_AUTO_ROWSTRIDE);
+
+ cairo_destroy (cr);
+ cairo_surface_destroy (surface);
+ g_free (data);
+
+ return TRUE;
+}
+
+static void
+gimp_operation_seamless_clone_prepare (GeglOperation *operation)
+{
+ GimpOperationSeamlessClone *self = GIMP_OPERATION_SEAMLESS_CLONE (operation);
+
+ printf ("Preparing!\n");
+
+ gegl_operation_set_format (operation, "output", babl_format ("RaGaBaA float"));
+
+ gimp_operation_seamless_clone_make_mesh (self);
+}
diff --git a/app/gegl/gimpoperationseamlessclone.h b/app/gegl/gimpoperationseamlessclone.h
new file mode 100644
index 0000000..477cd52
--- /dev/null
+++ b/app/gegl/gimpoperationseamlessclone.h
@@ -0,0 +1,58 @@
+/* GIMP - The GNU Image Manipulation Program
+ *
+ * gimpoperationseamlessclone.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 __GIMP_OPERATION_SEAMLESS_CLONE_H__
+#define __GIMP_OPERATION_SEAMLESS_CLONE_H__
+
+
+#include <gegl-plugin.h>
+#include <operation/gegl-operation-source.h>
+#include <cairo.h>
+
+#define GIMP_TYPE_OPERATION_SEAMLESS_CLONE (gimp_operation_seamless_clone_get_type ())
+#define GIMP_OPERATION_SEAMLESS_CLONE(obj) (G_TYPE_CHECK_INSTANCE_CAST ((obj), GIMP_TYPE_OPERATION_SEAMLESS_CLONE, GimpOperationSeamlessClone))
+#define GIMP_OPERATION_SEAMLESS_CLONE_CLASS(klass) (G_TYPE_CHECK_CLASS_CAST ((klass), GIMP_TYPE_OPERATION_SEAMLESS_CLONE, GimpOperationSeamlessCloneClass))
+#define GIMP_IS_OPERATION_SEAMLESS_CLONE(obj) (G_TYPE_CHECK_INSTANCE_TYPE ((obj), GIMP_TYPE_OPERATION_SEAMLESS_CLONE))
+#define GIMP_IS_OPERATION_SEAMLESS_CLONE_CLASS(klass) (G_TYPE_CHECK_CLASS_TYPE ((klass), GIMP_TYPE_OPERATION_SEAMLESS_CLONE))
+#define GIMP_OPERATION_SEAMLESS_CLONE_GET_CLASS(obj) (G_TYPE_INSTANCE_GET_CLASS ((obj), GIMP_TYPE_OPERATION_SEAMLESS_CLONE, GimpOperationSeamlessCloneClass))
+
+
+typedef struct _GimpOperationSeamlessCloneClass GimpOperationSeamlessCloneClass;
+
+struct _GimpOperationSeamlessClone
+{
+ GeglOperationSource parent_instance;
+
+ GPtrArray *ptList;
+ gint x, y;
+
+ cairo_pattern_t *mesh;
+ GeglRectangle mesh_bounds;
+};
+
+struct _GimpOperationSeamlessCloneClass
+{
+ GeglOperationSourceClass parent_class;
+};
+
+
+GType gimp_operation_seamless_clone_get_type (void) G_GNUC_CONST;
+
+
+#endif /* __GIMP_OPERATION_SEAMLESS_CLONE_H__ */
diff --git a/app/gegl/poly2tri-c/common/cutils.h b/app/gegl/poly2tri-c/common/cutils.h
new file mode 100644
index 0000000..45bfe9d
--- /dev/null
+++ b/app/gegl/poly2tri-c/common/cutils.h
@@ -0,0 +1,37 @@
+/*
+ * 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))
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* CUTILS_H */
+
diff --git a/app/gegl/poly2tri-c/common/poly2tri-private.h b/app/gegl/poly2tri-c/common/poly2tri-private.h
new file mode 100644
index 0000000..4fe6da7
--- /dev/null
+++ b/app/gegl/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 Node_ P2tNode;
+typedef struct AdvancingFront_ P2tAdvancingFront;
+typedef struct CDT_ P2tCDT;
+typedef struct Edge_ P2tEdge;
+typedef struct Point_ P2tPoint;
+typedef struct Triangle_ 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/app/gegl/poly2tri-c/common/shapes.c b/app/gegl/poly2tri-c/common/shapes.c
new file mode 100644
index 0000000..4bd4160
--- /dev/null
+++ b/app/gegl/poly2tri-c/common/shapes.c
@@ -0,0 +1,732 @@
+/*
+ * 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_new (P2tPoint, 1);
+ 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_new (P2tPoint, 1);
+ 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_free (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_new (P2tEdge, 1);
+ 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_free (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/app/gegl/poly2tri-c/common/shapes.h b/app/gegl/poly2tri-c/common/shapes.h
new file mode 100644
index 0000000..03686dc
--- /dev/null
+++ b/app/gegl/poly2tri-c/common/shapes.h
@@ -0,0 +1,150 @@
+/*
+ * 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 guard
+#ifndef SHAPES_H
+#define SHAPES_H
+
+#include <stddef.h>
+#include <assert.h>
+#include <math.h>
+#include "poly2tri-private.h"
+#include "cutils.h"
+
+struct Point_
+{
+ double x, y;
+ /// The edges this point constitutes an upper ending point
+ P2tEdgePtrArray edge_list;
+};
+
+void p2t_point_init_dd (P2tPoint* THIS, double x, double y);
+P2tPoint* p2t_point_new_dd (double x, double y);
+void p2t_point_init (P2tPoint* THIS);
+P2tPoint* p2t_point_new ();
+
+void p2t_point_destroy (P2tPoint* THIS);
+void
+p2t_point_free (P2tPoint* THIS);
+
+// Represents a simple polygon's edge
+
+struct Edge_
+{
+ P2tPoint* p, *q;
+};
+
+void p2t_edge_init (P2tEdge* THIS, P2tPoint* p1, P2tPoint* p2);
+P2tEdge* p2t_edge_new (P2tPoint* p1, P2tPoint* p2);
+
+void p2t_edge_destroy (P2tEdge* 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"
+
+struct Triangle_
+{
+ /// Flags to determine if an edge is a Constrained edge
+ gboolean constrained_edge[3];
+ /// Flags to determine if an edge is a Delauney edge
+ gboolean delaunay_edge[3];
+
+ //private:
+
+ /// Triangle points
+ P2tPoint * points_[3];
+ /// Neighbor list
+ struct Triangle_ * neighbors_[3];
+
+ /// Has this triangle been marked as an interior triangle?
+ 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/app/gegl/poly2tri-c/common/utils.c b/app/gegl/poly2tri-c/common/utils.c
new file mode 100644
index 0000000..24ce71b
--- /dev/null
+++ b/app/gegl/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/app/gegl/poly2tri-c/common/utils.h b/app/gegl/poly2tri-c/common/utils.h
new file mode 100644
index 0000000..83188c8
--- /dev/null
+++ b/app/gegl/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-12)
+
+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/app/gegl/poly2tri-c/poly2tri.h b/app/gegl/poly2tri-c/poly2tri.h
new file mode 100644
index 0000000..487755e
--- /dev/null
+++ b/app/gegl/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/app/gegl/poly2tri-c/sweep/advancing_front.c b/app/gegl/poly2tri-c/sweep/advancing_front.c
new file mode 100644
index 0000000..2b387f9
--- /dev/null
+++ b/app/gegl/poly2tri-c/sweep/advancing_front.c
@@ -0,0 +1,215 @@
+/*
+ * 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_new (P2tNode, 1);
+ 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_new (P2tNode, 1);
+ p2t_node_init_pt_tr (THIS, p, t);
+ return 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_new (P2tAdvancingFront, 1);
+ 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_free (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/app/gegl/poly2tri-c/sweep/advancing_front.h b/app/gegl/poly2tri-c/sweep/advancing_front.h
new file mode 100644
index 0000000..c232fae
--- /dev/null
+++ b/app/gegl/poly2tri-c/sweep/advancing_front.h
@@ -0,0 +1,87 @@
+/*
+ * 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 Node_
+{
+ P2tPoint* point;
+ P2tTriangle* triangle;
+
+ struct Node_* next;
+ struct Node_* 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);
+
+// 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/app/gegl/poly2tri-c/sweep/cdt.c b/app/gegl/poly2tri-c/sweep/cdt.c
new file mode 100644
index 0000000..9a0b679
--- /dev/null
+++ b/app/gegl/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_new (P2tCDT, 1);
+ 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_free (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/app/gegl/poly2tri-c/sweep/cdt.h b/app/gegl/poly2tri-c/sweep/cdt.h
new file mode 100644
index 0000000..bd40198
--- /dev/null
+++ b/app/gegl/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/app/gegl/poly2tri-c/sweep/sweep.c b/app/gegl/poly2tri-c/sweep/sweep.c
new file mode 100644
index 0000000..2718bb3
--- /dev/null
+++ b/app/gegl/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++)
+ {
+ g_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/app/gegl/poly2tri-c/sweep/sweep.h b/app/gegl/poly2tri-c/sweep/sweep.h
new file mode 100644
index 0000000..d1d2da3
--- /dev/null
+++ b/app/gegl/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/app/gegl/poly2tri-c/sweep/sweep_context.c b/app/gegl/poly2tri-c/sweep/sweep_context.c
new file mode 100644
index 0000000..2e41e5e
--- /dev/null
+++ b/app/gegl/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_);
+ g_free (THIS->af_head_);
+ g_free (THIS->af_middle_);
+ g_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/app/gegl/poly2tri-c/sweep/sweep_context.h b/app/gegl/poly2tri-c/sweep/sweep_context.h
new file mode 100644
index 0000000..0e9a033
--- /dev/null
+++ b/app/gegl/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/app/tools/gimpseamlessclonetool.c b/app/tools/gimpseamlessclonetool.c
index 0354d42..a023517 100644
--- a/app/tools/gimpseamlessclonetool.c
+++ b/app/tools/gimpseamlessclonetool.c
@@ -61,7 +61,8 @@
#include "gimp-intl.h"
-#define DBG_CALL_NAME() g_print ("@@@ %s @@@\n", __func__)
+#define DBG_CALL_NAME() g_print ("@@@ start %s @@@\n", __func__)
+#define DBG_CALL_NAME_E() g_print ("@@@ finish %s @@@\n", __func__)
#define SEAMLESS_CLONE_LIVE_PREVIEW TRUE
enum
@@ -210,10 +211,12 @@ gimp_seamless_clone_tool_init (GimpSeamlessCloneTool *self)
self->state = SEAMLESS_CLONE_STATE_NOTHING;
self->paste_buf = NULL;
+ self->paste_node = NULL;
self->render_node = NULL;
self->image_map = NULL;
self->translate_op = NULL;
self->outline = NULL;
+ DBG_CALL_NAME_E();
}
static void
@@ -271,6 +274,7 @@ gimp_seamless_clone_tool_control (GimpTool *tool,
}
GIMP_TOOL_CLASS (parent_class)->control (tool, action, display);
+ DBG_CALL_NAME_E();
}
/**
@@ -299,6 +303,7 @@ gimp_seamless_clone_tool_update_image_map_easy (GimpSeamlessCloneTool *sct)
}
gimp_seamless_clone_tool_image_map_update (sct);
+ DBG_CALL_NAME_E();
}
/* When one of the tool options was modified, we wish to take the following
@@ -333,6 +338,8 @@ gimp_seamless_clone_tool_options_notify (GimpTool *tool,
/* Allow drawing to continue */
gimp_draw_tool_resume (GIMP_DRAW_TOOL (tool));
+
+ DBG_CALL_NAME_E();
}
static void
@@ -344,7 +351,7 @@ gimp_seamless_clone_tool_start (GimpSeamlessCloneTool *sct,
gimp_draw_tool_start (GIMP_DRAW_TOOL (sct), display);
// TODO free and update stuff
-
+ DBG_CALL_NAME_E();
}
static void
gimp_seamless_clone_tool_button_press (GimpTool *tool,
@@ -441,6 +448,7 @@ gimp_seamless_clone_tool_motion (GimpTool *tool,
#endif
gimp_draw_tool_resume (GIMP_DRAW_TOOL (tool));
+ DBG_CALL_NAME_E();
}
void
@@ -480,6 +488,7 @@ gimp_seamless_clone_tool_button_release (GimpTool *tool,
}
gimp_draw_tool_resume (GIMP_DRAW_TOOL (tool));
+ DBG_CALL_NAME_E();
}
static void
@@ -499,6 +508,7 @@ gimp_seamless_clone_tool_cursor_update (GimpTool *tool,
gimp_tool_control_set_cursor_modifier (tool->control, GIMP_CURSOR_MODIFIER_NONE);
GIMP_TOOL_CLASS (parent_class)->cursor_update (tool, coords, state, display);
+ DBG_CALL_NAME_E();
}
typedef struct {
@@ -537,6 +547,7 @@ gimp_seamless_clone_tool_draw (GimpDrawTool *draw_tool)
(gdouble)(sct->paste_y + (gint)(sct->cursor_y - sct->movement_start_y + sct->paste_h / 2)));
gimp_draw_tool_pop_group (draw_tool);
+ DBG_CALL_NAME_E();
}
/* TODO - extract this logic for general gimp->gegl buffer conversion.
@@ -585,6 +596,7 @@ gimp_buffer_to_gegl_buffer_with_progress (GimpSeamlessCloneTool *sct)
"points", sct->outline,
"width", gimp_buffer_get_width (gimpbuf),
"height", gimp_buffer_get_height (gimpbuf),
+ "threshold", 0.5f,
NULL);
gegl_node_connect_to (input, "output",
@@ -627,6 +639,7 @@ gimp_buffer_to_gegl_buffer_with_progress (GimpSeamlessCloneTool *sct)
sct->paste_h = tempR.height;
tile_manager_unref (tiles);
+ DBG_CALL_NAME_E();
}
/* The final graph would be
@@ -674,7 +687,8 @@ gimp_seamless_clone_tool_create_render_node (GimpSeamlessCloneTool *sct)
NULL);
interpolate = gegl_node_new_child (node,
- "operation", "gegl:nop",
+ "operation", "gimp:seamless-clone",
+ "points", sct->outline,
NULL);
sct->translate_op = gegl_node_new_child (node,
@@ -683,13 +697,13 @@ gimp_seamless_clone_tool_create_render_node (GimpSeamlessCloneTool *sct)
"filter", "nearest", NULL);
add = gegl_node_new_child (node,
- "operation", "gegl:add",
- NULL);
+ "operation", "gegl:add",
+ NULL);
paste = gegl_node_new_child (node,
- "operation", "gegl:buffer-source",
- "buffer", sct->paste_buf,
- NULL);
+ "operation", "gegl:buffer-source",
+ "buffer", sct->paste_buf,
+ NULL);
sct->paste_node = paste;
@@ -705,8 +719,8 @@ gimp_seamless_clone_tool_create_render_node (GimpSeamlessCloneTool *sct)
gegl_node_connect_to (input, "output",
diff, "aux");
- gegl_node_connect_to (diff, "output",
- interpolate, "input");
+// gegl_node_connect_to (diff, "output",
+// interpolate, "input");
gegl_node_connect_to (interpolate, "output",
add, "aux");
@@ -715,6 +729,7 @@ gimp_seamless_clone_tool_create_render_node (GimpSeamlessCloneTool *sct)
output, "input");
sct->render_node = node;
+ DBG_CALL_NAME_E();
}
static void
@@ -722,6 +737,7 @@ gimp_seamless_clone_tool_render_node_update (GimpSeamlessCloneTool *sct)
{
DBG_CALL_NAME();
/* For now, do nothing */
+ DBG_CALL_NAME_E();
}
static void
@@ -741,6 +757,7 @@ gimp_seamless_clone_tool_create_image_map (GimpSeamlessCloneTool *sct,
g_signal_connect (sct->image_map, "flush",
G_CALLBACK (gimp_seamless_clone_tool_image_map_flush),
sct);
+ DBG_CALL_NAME_E();
}
static void
@@ -752,6 +769,7 @@ gimp_seamless_clone_tool_image_map_flush (GimpImageMap *image_map,
DBG_CALL_NAME();
gimp_projection_flush_now (gimp_image_get_projection (image));
gimp_display_flush_now (tool->display);
+ DBG_CALL_NAME();
}
static void
@@ -792,4 +810,5 @@ gimp_seamless_clone_tool_image_map_update (GimpSeamlessCloneTool *ct)
visible.y -= off_y;
gimp_image_map_apply (ct->image_map, &visible);
+ DBG_CALL_NAME_E();
}
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
