Adding upstream version 2.10.34.upstream/2.10.34upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 841 insertions, 0 deletions

diff --git a/app/core/gimp-transform-resize.c b/app/core/gimp-transform-resize.c
new file mode 100644
index 0000000..7aabd67
--- /dev/null
+++ b/app/core/gimp-transform-resize.c
@@ -0,0 +1,841 @@
+/* GIMP - The GNU Image Manipulation Program
+ * Copyright (C) 1995-2001 Spencer Kimball, Peter Mattis, and others
+ *
+ * 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 <https://www.gnu.org/licenses/>.
+ */
+
+#include "config.h"
+
+#include <string.h>
+
+#include <gio/gio.h>
+#include <gegl.h>
+
+#include "libgimpmath/gimpmath.h"
+
+#include "core-types.h"
+
+#include "gimp-transform-resize.h"
+#include "gimp-transform-utils.h"
+#include "gimp-utils.h"
+
+
+#if defined (HAVE_ISFINITE)
+#define FINITE(x) isfinite(x)
+#elif defined (HAVE_FINITE)
+#define FINITE(x) finite(x)
+#elif defined (G_OS_WIN32)
+#define FINITE(x) _finite(x)
+#else
+#error "no FINITE() implementation available?!"
+#endif
+
+#define EPSILON 0.00000001
+
+
+typedef struct
+{
+  GimpVector2 a, b, c, d;
+  gdouble     area;
+  gdouble     aspect;
+} Rectangle;
+
+
+static void      gimp_transform_resize_adjust        (const GimpVector2 *points,
+                                                      gint               n_points,
+                                                      gint              *x1,
+                                                      gint              *y1,
+                                                      gint              *x2,
+                                                      gint              *y2);
+static void      gimp_transform_resize_crop          (const GimpVector2 *points,
+                                                      gint               n_points,
+                                                      gdouble            aspect,
+                                                      gint              *x1,
+                                                      gint              *y1,
+                                                      gint              *x2,
+                                                      gint              *y2);
+
+static void      add_rectangle                       (const GimpVector2 *points,
+                                                      gint               n_points,
+                                                      Rectangle         *r,
+                                                      GimpVector2        a,
+                                                      GimpVector2        b,
+                                                      GimpVector2        c,
+                                                      GimpVector2        d);
+static gboolean  intersect                           (GimpVector2        a,
+                                                      GimpVector2        b,
+                                                      GimpVector2        c,
+                                                      GimpVector2        d,
+                                                      GimpVector2       *i);
+static gboolean  intersect_x                         (GimpVector2        a,
+                                                      GimpVector2        b,
+                                                      GimpVector2        c,
+                                                      GimpVector2       *i);
+static gboolean  intersect_y                         (GimpVector2        a,
+                                                      GimpVector2        b,
+                                                      GimpVector2        c,
+                                                      GimpVector2       *i);
+static gboolean  in_poly                             (const GimpVector2 *points,
+                                                      gint               n_points,
+                                                      GimpVector2        p);
+static gboolean  point_on_border                     (const GimpVector2 *points,
+                                                      gint               n_points,
+                                                      GimpVector2        p);
+
+static void      find_two_point_rectangle            (Rectangle         *r,
+                                                      const GimpVector2 *points,
+                                                      gint               n_points,
+                                                      gint               p);
+static void      find_three_point_rectangle_corner   (Rectangle         *r,
+                                                      const GimpVector2 *points,
+                                                      gint               n_points,
+                                                      gint               p);
+static void      find_three_point_rectangle          (Rectangle          *r,
+                                                      const GimpVector2 *points,
+                                                      gint               n_points,
+                                                      gint               p);
+static void      find_three_point_rectangle_triangle (Rectangle         *r,
+                                                      const GimpVector2 *points,
+                                                      gint               n_points,
+                                                      gint               p);
+static void      find_maximum_aspect_rectangle       (Rectangle          *r,
+                                                      const GimpVector2 *points,
+                                                      gint               n_points,
+                                                      gint               p);
+
+
+/*
+ * This function wants to be passed the inverse transformation matrix!!
+ */
+gboolean
+gimp_transform_resize_boundary (const GimpMatrix3   *inv,
+                                GimpTransformResize  resize,
+                                gdouble              u1,
+                                gdouble              v1,
+                                gdouble              u2,
+                                gdouble              v2,
+                                gint                *x1,
+                                gint                *y1,
+                                gint                *x2,
+                                gint                *y2)
+{
+  GimpVector2 bounds[4];
+  GimpVector2 points[5];
+  gint        n_points;
+  gboolean    valid;
+  gint        i;
+
+  g_return_val_if_fail (inv != NULL, FALSE);
+
+  /*  initialize with the original boundary  */
+  *x1 = floor (u1);
+  *y1 = floor (v1);
+  *x2 = ceil  (u2);
+  *y2 = ceil  (v2);
+
+  /* if clipping then just return the original rectangle */
+  if (resize == GIMP_TRANSFORM_RESIZE_CLIP)
+    return TRUE;
+
+  bounds[0] = (GimpVector2) { u1, v1 };
+  bounds[1] = (GimpVector2) { u2, v1 };
+  bounds[2] = (GimpVector2) { u2, v2 };
+  bounds[3] = (GimpVector2) { u1, v2 };
+
+  gimp_transform_polygon (inv, bounds, 4, TRUE,
+                          points, &n_points);
+
+  valid = (n_points >= 2);
+
+  /*  check if the transformation matrix is valid at all  */
+  for (i = 0; i < n_points && valid; i++)
+    valid = (FINITE (points[i].x) && FINITE (points[i].y));
+
+  if (! valid)
+    {
+      /* since there is no sensible way to deal with this, just do the same as
+       * with GIMP_TRANSFORM_RESIZE_CLIP: return
+       */
+      return FALSE;
+    }
+
+  switch (resize)
+    {
+    case GIMP_TRANSFORM_RESIZE_ADJUST:
+      /* return smallest rectangle (with sides parallel to x- and y-axis)
+       * that surrounds the new points */
+      gimp_transform_resize_adjust (points, n_points,
+                                    x1, y1, x2, y2);
+      break;
+
+    case GIMP_TRANSFORM_RESIZE_CROP:
+      gimp_transform_resize_crop (points, n_points,
+                                  0.0,
+                                  x1, y1, x2, y2);
+      break;
+
+    case GIMP_TRANSFORM_RESIZE_CROP_WITH_ASPECT:
+      gimp_transform_resize_crop (points, n_points,
+                                  (u2 - u1) / (v2 - v1),
+                                  x1, y1, x2, y2);
+      break;
+
+    case GIMP_TRANSFORM_RESIZE_CLIP:
+      /* Remove warning about not handling all enum values. We handle
+       * this case in the beginning of the function
+       */
+      break;
+    }
+
+  /* ensure that resulting rectangle has at least area 1 */
+  if (*x1 == *x2)
+    (*x2)++;
+
+  if (*y1 == *y2)
+    (*y2)++;
+
+  return TRUE;
+}
+
+/* this calculates the smallest rectangle (with sides parallel to x- and
+ * y-axis) that contains the points d1 to d4
+ */
+static void
+gimp_transform_resize_adjust (const GimpVector2 *points,
+                              gint               n_points,
+                              gint              *x1,
+                              gint              *y1,
+                              gint              *x2,
+                              gint              *y2)
+{
+  GimpVector2 top_left;
+  GimpVector2 bottom_right;
+  gint        i;
+
+  top_left = bottom_right = points[0];
+
+  for (i = 1; i < n_points; i++)
+    {
+      top_left.x     = MIN (top_left.x,     points[i].x);
+      top_left.y     = MIN (top_left.y,     points[i].y);
+
+      bottom_right.x = MAX (bottom_right.x, points[i].x);
+      bottom_right.y = MAX (bottom_right.y, points[i].y);
+    }
+
+  *x1 = (gint) floor (top_left.x + EPSILON);
+  *y1 = (gint) floor (top_left.y + EPSILON);
+
+  *x2 = (gint) ceil (bottom_right.x - EPSILON);
+  *y2 = (gint) ceil (bottom_right.y - EPSILON);
+}
+
+static void
+gimp_transform_resize_crop (const GimpVector2 *orig_points,
+                            gint               n_points,
+                            gdouble            aspect,
+                            gint              *x1,
+                            gint              *y1,
+                            gint              *x2,
+                            gint              *y2)
+{
+  GimpVector2 points[5];
+  Rectangle   r;
+  GimpVector2 t,a;
+  gint        i, j;
+  gint        min;
+
+  memcpy (points, orig_points, sizeof (GimpVector2) * n_points);
+
+  /* find lowest, rightmost corner of surrounding rectangle */
+  a.x = 0;
+  a.y = 0;
+  for (i = 0; i < 4; i++)
+    {
+      if (points[i].x < a.x)
+        a.x = points[i].x;
+
+      if (points[i].y < a.y)
+        a.y = points[i].y;
+    }
+
+  /* and translate all the points to the first quadrant */
+  for (i = 0; i < n_points; i++)
+    {
+      points[i].x += (-a.x) * 2;
+      points[i].y += (-a.y) * 2;
+    }
+
+  /* find the convex hull using Jarvis's March as the points are passed
+   * in different orders due to gimp_matrix3_transform_point()
+   */
+  min = 0;
+  for (i = 0; i < n_points; i++)
+    {
+      if (points[i].y < points[min].y)
+        min = i;
+    }
+
+  t = points[0];
+  points[0] = points[min];
+  points[min] = t;
+
+  for (i = 1; i < n_points - 1; i++)
+    {
+      gdouble min_theta;
+      gdouble min_mag;
+      int next;
+
+      next = n_points - 1;
+      min_theta = 2.0 * G_PI;
+      min_mag = DBL_MAX;
+
+      for (j = i; j < n_points; j++)
+        {
+          gdouble theta;
+          gdouble sy;
+          gdouble sx;
+          gdouble mag;
+
+          sy = points[j].y - points[i - 1].y;
+          sx = points[j].x - points[i - 1].x;
+
+          if ((sx == 0.0) && (sy == 0.0))
+            {
+              next = j;
+              break;
+            }
+
+          theta = atan2 (-sy, -sx);
+          mag = (sx * sx) + (sy * sy);
+
+          if ((theta < min_theta) ||
+              ((theta == min_theta) && (mag < min_mag)))
+            {
+              min_theta = theta;
+              min_mag = mag;
+              next = j;
+            }
+        }
+
+      t = points[i];
+      points[i] = points[next];
+      points[next] = t;
+    }
+
+  /* reverse the order of points */
+  for (i = 0; i < n_points / 2; i++)
+    {
+      t                        = points[i];
+      points[i]                = points[n_points - i - 1];
+      points[n_points - i - 1] = t;
+    }
+
+  r.a.x = r.a.y = r.b.x = r.b.y = r.c.x = r.c.y = r.d.x = r.d.y = r.area = 0;
+  r.aspect = aspect;
+
+  if (aspect != 0)
+    {
+      for (i = 0; i < n_points; i++)
+        find_maximum_aspect_rectangle (&r, points, n_points, i);
+    }
+  else
+    {
+      for (i = 0; i < n_points; i++)
+        {
+          find_three_point_rectangle          (&r, points, n_points, i);
+          find_three_point_rectangle_corner   (&r, points, n_points, i);
+          find_two_point_rectangle            (&r, points, n_points, i);
+          find_three_point_rectangle_triangle (&r, points, n_points, i);
+        }
+    }
+
+  if (r.area == 0)
+    {
+      /* saveguard if something went wrong, adjust and give warning */
+      gimp_transform_resize_adjust (orig_points, n_points,
+                                    x1, y1, x2, y2);
+      g_printerr ("no rectangle found by algorithm, no cropping done\n");
+      return;
+    }
+  else
+    {
+      /* round and translate the calculated points back */
+      *x1 = floor (r.a.x + 0.5);
+      *y1 = floor (r.a.y + 0.5);
+      *x2 = ceil  (r.c.x - 0.5);
+      *y2 = ceil  (r.c.y - 0.5);
+
+      *x1 = *x1 - ((-a.x) * 2);
+      *y1 = *y1 - ((-a.y) * 2);
+      *x2 = *x2 - ((-a.x) * 2);
+      *y2 = *y2 - ((-a.y) * 2);
+      return;
+    }
+}
+
+static void
+find_three_point_rectangle (Rectangle         *r,
+                            const GimpVector2 *points,
+                            gint               n_points,
+                            gint               p)
+{
+  GimpVector2 a = points[p       % n_points];  /* 0 1 2 3 */
+  GimpVector2 b = points[(p + 1) % n_points];  /* 1 2 3 0 */
+  GimpVector2 c = points[(p + 2) % n_points];  /* 2 3 0 1 */
+  GimpVector2 d = points[(p + 3) % n_points];  /* 3 0 1 2 */
+  GimpVector2 i1;                              /* intersection point */
+  GimpVector2 i2;                              /* intersection point */
+  GimpVector2 i3;                              /* intersection point */
+
+  if (intersect_x (b, c, a,  &i1) &&
+      intersect_y (c, d, i1, &i2) &&
+      intersect_x (d, a, i2, &i3))
+    add_rectangle (points, n_points, r, i3, i3, i1, i1);
+
+  if (intersect_y (b, c, a,  &i1) &&
+      intersect_x (c, d, i1, &i2) &&
+      intersect_y (d, a, i2, &i3))
+    add_rectangle (points, n_points, r, i3, i3, i1, i1);
+
+  if (intersect_x (d, c, a,  &i1) &&
+      intersect_y (c, b, i1, &i2) &&
+      intersect_x (b, a, i2, &i3))
+    add_rectangle (points, n_points, r, i3, i3, i1, i1);
+
+  if (intersect_y (d, c, a,  &i1) &&
+      intersect_x (c, b, i1, &i2) &&
+      intersect_y (b, a, i2, &i3))
+    add_rectangle (points, n_points, r, i3, i3, i1, i1);
+}
+
+static void
+find_three_point_rectangle_corner (Rectangle         *r,
+                                   const GimpVector2 *points,
+                                   gint               n_points,
+                                   gint               p)
+{
+  GimpVector2 a = points[p       % n_points];  /* 0 1 2 3 */
+  GimpVector2 b = points[(p + 1) % n_points];  /* 1 2 3 0 */
+  GimpVector2 c = points[(p + 2) % n_points];  /* 2 3 0 2 */
+  GimpVector2 d = points[(p + 3) % n_points];  /* 3 0 2 1 */
+  GimpVector2 i1;                              /* intersection point */
+  GimpVector2 i2;                              /* intersection point */
+
+  if (intersect_x (b, c, a , &i1) &&
+      intersect_y (c, d, i1, &i2))
+    add_rectangle (points, n_points, r, a, a, i1, i2);
+
+  if (intersect_y (b, c, a , &i1) &&
+      intersect_x (c, d, i1, &i2))
+    add_rectangle (points, n_points, r, a, a, i1, i2);
+
+  if (intersect_x (c, d, a , &i1) &&
+      intersect_y (b, c, i1, &i2))
+    add_rectangle (points, n_points, r, a, a, i1, i2);
+
+  if (intersect_y (c, d, a , &i1) &&
+      intersect_x (b, c, i1, &i2))
+    add_rectangle (points, n_points, r, a, a, i1, i2);
+}
+
+static void
+find_two_point_rectangle (Rectangle         *r,
+                          const GimpVector2 *points,
+                          gint               n_points,
+                          gint               p)
+{
+  GimpVector2 a = points[ p      % n_points];  /* 0 1 2 3 */
+  GimpVector2 b = points[(p + 1) % n_points];  /* 1 2 3 0 */
+  GimpVector2 c = points[(p + 2) % n_points];  /* 2 3 0 1 */
+  GimpVector2 d = points[(p + 3) % n_points];  /* 3 0 1 2 */
+  GimpVector2 i1;                              /* intersection point */
+  GimpVector2 i2;                              /* intersection point */
+  GimpVector2 mid;                             /* Mid point */
+
+  add_rectangle (points, n_points, r, a, a, c, c);
+  add_rectangle (points, n_points, r, b, b, d, d);
+
+  if (intersect_x (c, b, a, &i1) &&
+      intersect_y (c, b, a, &i2))
+    {
+      mid.x = ( i1.x + i2.x ) / 2.0;
+      mid.y = ( i1.y + i2.y ) / 2.0;
+
+      add_rectangle (points, n_points, r, a, a, mid, mid);
+    }
+}
+
+static void
+find_three_point_rectangle_triangle (Rectangle         *r,
+                                     const GimpVector2 *points,
+                                     gint               n_points,
+                                     gint               p)
+{
+  GimpVector2 a = points[p       % n_points];  /* 0 1 2 3 */
+  GimpVector2 b = points[(p + 1) % n_points];  /* 1 2 3 0 */
+  GimpVector2 c = points[(p + 2) % n_points];  /* 2 3 0 1 */
+  GimpVector2 d = points[(p + 3) % n_points];  /* 3 0 1 2 */
+  GimpVector2 i1;                              /* intersection point */
+  GimpVector2 i2;                              /* intersection point */
+  GimpVector2 mid;
+
+  mid.x = (a.x + b.x) / 2.0;
+  mid.y = (a.y + b.y) / 2.0;
+
+  if (intersect_x (b, c, mid, &i1) &&
+      intersect_y (a, d, mid, &i2))
+    add_rectangle (points, n_points, r, mid, mid, i1, i2);
+
+  if (intersect_y (b, c, mid, &i1) &&
+      intersect_x (a, d, mid, &i2))
+    add_rectangle (points, n_points, r, mid, mid, i1, i2);
+
+  if (intersect_x (a, d, mid, &i1) &&
+      intersect_y (b, c, mid, &i2))
+    add_rectangle (points, n_points, r, mid, mid, i1, i2);
+
+  if (intersect_y (a, d, mid, &i1) &&
+      intersect_x (b, c, mid, &i2))
+    add_rectangle (points, n_points, r, mid, mid, i1, i2);
+}
+
+static void
+find_maximum_aspect_rectangle (Rectangle         *r,
+                               const GimpVector2 *points,
+                               gint               n_points,
+                               gint               p)
+{
+  GimpVector2 a = points[ p      % n_points];  /* 0 1 2 3 */
+  GimpVector2 b = points[(p + 1) % n_points];  /* 1 2 3 0 */
+  GimpVector2 c = points[(p + 2) % n_points];  /* 2 3 0 1 */
+  GimpVector2 d = points[(p + 3) % n_points];  /* 3 0 1 2 */
+  GimpVector2 i1;                              /* intersection point */
+  GimpVector2 i2;                              /* intersection point */
+  GimpVector2 i3;                              /* intersection point */
+
+  if (intersect_x (b, c, a, &i1))
+    {
+      i2.x = i1.x + 1.0 * r->aspect;
+      i2.y = i1.y + 1.0;
+
+      if (intersect (d, a, i1, i2, &i3))
+        add_rectangle (points, n_points, r, i1, i3, i1, i3);
+
+      if (intersect (a, b, i1, i2, &i3))
+        add_rectangle (points, n_points, r, i1, i3, i1, i3);
+
+      if (intersect (c, d, i1, i2, &i3))
+        add_rectangle (points, n_points, r, i1, i3, i1, i3);
+
+      i2.x = i1.x - 1.0 * r->aspect;
+      i2.y = i1.y + 1.0;
+
+      if (intersect (d, a, i1, i2, &i3))
+        add_rectangle (points, n_points, r, i1, i3, i1, i3);
+
+      if (intersect (a, b, i1, i2, &i3))
+        add_rectangle (points, n_points, r, i1, i3, i1, i3);
+
+      if (intersect (c, d, i1, i2, &i3))
+        add_rectangle (points, n_points, r, i1, i3, i1, i3);
+    }
+
+  if (intersect_y (b, c, a, &i1))
+    {
+      i2.x = i1.x + 1.0 * r->aspect;
+      i2.y = i1.y + 1.0;
+
+      if (intersect (d, a, i1, i2, &i3))
+        add_rectangle (points, n_points, r, i1, i3, i1, i3);
+
+      if (intersect (a, b, i1, i2, &i3))
+        add_rectangle (points, n_points, r, i1, i3, i1, i3);
+
+      if (intersect (c, d, i1, i2, &i3))
+        add_rectangle (points, n_points, r, i1, i3, i1, i3);
+
+      i2.x = i1.x - 1.0 * r->aspect;
+      i2.y = i1.y + 1.0;
+
+      if (intersect (d, a, i1, i2, &i3))
+        add_rectangle (points, n_points, r, i1, i3, i1, i3);
+
+      if (intersect (a, b, i1, i2, &i3))
+        add_rectangle (points, n_points, r, i1, i3, i1, i3);
+
+      if (intersect (c, d, i1, i2, &i3))
+        add_rectangle (points, n_points, r, i1, i3, i1, i3);
+    }
+
+  if (intersect_x (c, d, a,  &i1))
+    {
+      i2.x = i1.x + 1.0 * r->aspect;
+      i2.y = i1.y + 1.0;
+
+      if (intersect (d, a, i1, i2, &i3))
+        add_rectangle (points, n_points, r, i1, i3, i1, i3);
+
+      if (intersect (a, b, i1, i2, &i3))
+        add_rectangle (points, n_points, r, i1, i3, i1, i3);
+
+      if (intersect (b, c, i1, i2, &i3))
+        add_rectangle (points, n_points, r, i1, i3, i1, i3);
+
+      i2.x = i1.x - 1.0 * r->aspect;
+      i2.y = i1.y + 1.0;
+
+      if (intersect (d, a, i1, i2, &i3))
+        add_rectangle (points, n_points, r, i1, i3, i1, i3);
+
+      if (intersect (a, b, i1, i2, &i3))
+        add_rectangle (points, n_points, r, i1, i3, i1, i3);
+
+      if (intersect (b, c, i1, i2, &i3))
+        add_rectangle (points, n_points, r, i1, i3, i1, i3);
+    }
+
+  if (intersect_y (c, d, a,  &i1))
+    {
+      i2.x = i1.x + 1.0 * r->aspect;
+      i2.y = i1.y + 1.0;
+
+      if (intersect (d, a, i1, i2, &i3))
+        add_rectangle (points, n_points, r, i1, i3, i1, i3);
+
+      if (intersect (a, b, i1, i2, &i3))
+        add_rectangle (points, n_points, r, i1, i3, i1, i3);
+
+      if (intersect (b, c, i1, i2, &i3))
+        add_rectangle (points, n_points, r, i1, i3, i1, i3);
+
+      i2.x = i1.x - 1.0 * r->aspect;
+      i2.y = i1.y + 1.0;
+
+      if (intersect (d, a, i1, i2, &i3))
+        add_rectangle (points, n_points, r, i1, i3, i1, i3);
+
+      if (intersect (a, b, i1, i2, &i3))
+        add_rectangle (points, n_points, r, i1, i3, i1, i3);
+
+      if (intersect (b, c, i1, i2, &i3))
+        add_rectangle (points, n_points, r, i1, i3, i1, i3);
+    }
+}
+
+/* check if point is inside the polygon "points", if point is on border
+ * its still inside.
+ */
+static gboolean
+in_poly (const GimpVector2 *points,
+         gint               n_points,
+         GimpVector2        p)
+{
+  GimpVector2 p1, p2;
+  gint  counter = 0;
+  gint  i;
+
+  p1 = points[0];
+
+  for (i = 1; i <= n_points; i++)
+    {
+      p2 = points[i % n_points];
+
+      if (p.y > MIN (p1.y, p2.y))
+        {
+          if (p.y <= MAX (p1.y, p2.y))
+            {
+              if (p.x <= MAX (p1.x, p2.x))
+                {
+                  if (p1.y != p2.y)
+                    {
+                      gdouble xinters = ((p.y - p1.y) * (p2.x - p1.x) /
+                                         (p2.y - p1.y) + p1.x);
+
+                      if (p1.x == p2.x || p.x <= xinters)
+                        counter++;
+                    }
+                }
+            }
+        }
+
+      p1 = p2;
+    }
+
+  /* border check */
+  if (point_on_border (points, n_points, p))
+    return TRUE;
+
+  return (counter % 2 != 0);
+}
+
+/* check if the point p lies on the polygon "points"
+ */
+static gboolean
+point_on_border (const GimpVector2 *points,
+                 gint               n_points,
+                 GimpVector2        p)
+{
+  gint i;
+
+  for (i = 0; i <= n_points; i++)
+    {
+      GimpVector2   a  = points[i       % n_points];
+      GimpVector2   b  = points[(i + 1) % n_points];
+      gdouble a1 = (b.y - a.y);
+      gdouble b1 = (a.x - b.x);
+      gdouble c1 = a1 * a.x + b1 * a.y;
+      gdouble c2 = a1 * p.x + b1 * p.y;
+
+      if (ABS (c1 - c2) < EPSILON &&
+          MIN (a.x, b.x) <= p.x   &&
+          MAX (a.x, b.x) >= p.x   &&
+          MIN (a.y, b.y) <= p.y   &&
+          MAX (a.y, b.y) >= p.y)
+        return TRUE;
+    }
+
+  return FALSE;
+}
+
+/* calculate the intersection point of the line a-b with the line c-d
+ * and write it to i, if existing.
+ */
+static gboolean
+intersect (GimpVector2  a,
+           GimpVector2  b,
+           GimpVector2  c,
+           GimpVector2  d,
+           GimpVector2 *i)
+{
+  gdouble a1  = (b.y - a.y);
+  gdouble b1  = (a.x - b.x);
+  gdouble c1  = a1 * a.x + b1 * a.y;
+
+  gdouble a2  = (d.y - c.y);
+  gdouble b2  = (c.x - d.x);
+  gdouble c2  = a2 * c.x + b2 * c.y;
+  gdouble det = a1 * b2 - a2 * b1;
+
+  if (det == 0)
+    return FALSE;
+
+  i->x = (b2 * c1 - b1 * c2) / det;
+  i->y = (a1 * c2 - a2 * c1) / det;
+
+  return TRUE;
+}
+
+/* calculate the intersection point of the line a-b with the vertical line
+ * through c and write it to i, if existing.
+ */
+static gboolean
+intersect_x (GimpVector2  a,
+             GimpVector2  b,
+             GimpVector2  c,
+             GimpVector2 *i)
+{
+  GimpVector2   d = c;
+  d.y += 1;
+
+  return intersect(a,b,c,d,i);
+}
+
+/* calculate the intersection point of the line a-b with the horizontal line
+ * through c and write it to i, if existing.
+ */
+static gboolean
+intersect_y (GimpVector2  a,
+             GimpVector2  b,
+             GimpVector2  c,
+             GimpVector2 *i)
+{
+  GimpVector2   d = c;
+  d.x += 1;
+
+  return intersect(a,b,c,d,i);
+}
+
+/* this takes the smallest ortho-aligned (the sides of the rectangle are
+ * parallel to the x- and y-axis) rectangle fitting around the points a to d,
+ * checks if the whole rectangle is inside the polygon described by points and
+ * writes it to r if the area is bigger than the rectangle already stored in r.
+ */
+static void
+add_rectangle (const GimpVector2 *points,
+               gint               n_points,
+               Rectangle         *r,
+               GimpVector2        a,
+               GimpVector2        b,
+               GimpVector2        c,
+               GimpVector2        d)
+{
+  gdouble width;
+  gdouble height;
+  gdouble minx, maxx;
+  gdouble miny, maxy;
+
+  /* get the orthoaligned (the sides of the rectangle are parallel to the x-
+   * and y-axis) rectangle surrounding the points a to d.
+   */
+  minx = MIN4 (a.x, b.x, c.x, d.x);
+  maxx = MAX4 (a.x, b.x, c.x, d.x);
+  miny = MIN4 (a.y, b.y, c.y, d.y);
+  maxy = MAX4 (a.y, b.y, c.y, d.y);
+
+  a.x = minx;
+  a.y = miny;
+
+  b.x = maxx;
+  b.y = miny;
+
+  c.x = maxx;
+  c.y = maxy;
+
+  d.x = minx;
+  d.y = maxy;
+
+  width  =  maxx - minx;
+  height =  maxy - miny;
+
+  /* check if this rectangle is inside the polygon "points" */
+  if (in_poly (points, n_points, a) &&
+      in_poly (points, n_points, b) &&
+      in_poly (points, n_points, c) &&
+      in_poly (points, n_points, d))
+    {
+      gdouble area = width * height;
+
+      /* check if the new rectangle is larger (in terms of area)
+       * than the currently stored rectangle in r, if yes store
+       * new rectangle to r
+       */
+      if (r->area <= area)
+        {
+          r->a.x = a.x;
+          r->a.y = a.y;
+
+          r->b.x = b.x;
+          r->b.y = b.y;
+
+          r->c.x = c.x;
+          r->c.y = c.y;
+
+          r->d.x = d.x;
+          r->d.y = d.y;
+
+          r->area = area;
+        }
+    }
+}