summaryrefslogtreecommitdiffstats
path: root/app/core/gimpboundary.c
diff options
context:
space:
mode:
Diffstat (limited to 'app/core/gimpboundary.c')
-rw-r--r--app/core/gimpboundary.c1016
1 files changed, 1016 insertions, 0 deletions
diff --git a/app/core/gimpboundary.c b/app/core/gimpboundary.c
new file mode 100644
index 0000000..995242c
--- /dev/null
+++ b/app/core/gimpboundary.c
@@ -0,0 +1,1016 @@
+/* GIMP - The GNU Image Manipulation Program
+ * Copyright (C) 1995 Spencer Kimball and Peter Mattis
+ *
+ * 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 <stdlib.h>
+#include <string.h>
+
+#include <gegl.h>
+
+#include "libgimpmath/gimpmath.h"
+
+#include "core-types.h"
+
+#include "gimpboundary.h"
+
+
+/* GimpBoundSeg array growth parameter */
+#define MAX_SEGS_INC 2048
+
+
+typedef struct _GimpBoundary GimpBoundary;
+
+struct _GimpBoundary
+{
+ /* The array of segments */
+ GimpBoundSeg *segs;
+ gint num_segs;
+ gint max_segs;
+
+ /* The array of vertical segments */
+ gint *vert_segs;
+
+ /* The empty segment arrays */
+ gint *empty_segs_n;
+ gint *empty_segs_c;
+ gint *empty_segs_l;
+ gint max_empty_segs;
+};
+
+
+/* local function prototypes */
+
+static GimpBoundary * gimp_boundary_new (const GeglRectangle *region);
+static GimpBoundSeg * gimp_boundary_free (GimpBoundary *boundary,
+ gboolean free_segs);
+
+static void gimp_boundary_add_seg (GimpBoundary *bounrady,
+ gint x1,
+ gint y1,
+ gint x2,
+ gint y2,
+ gboolean open);
+
+static void find_empty_segs (const GeglRectangle *region,
+ const gfloat *line_data,
+ gint scanline,
+ gint empty_segs[],
+ gint max_empty,
+ gint *num_empty,
+ GimpBoundaryType type,
+ gint x1,
+ gint y1,
+ gint x2,
+ gint y2,
+ gfloat threshold);
+static void process_horiz_seg (GimpBoundary *boundary,
+ gint x1,
+ gint y1,
+ gint x2,
+ gint y2,
+ gboolean open);
+static void make_horiz_segs (GimpBoundary *boundary,
+ gint start,
+ gint end,
+ gint scanline,
+ gint empty[],
+ gint num_empty,
+ gint top);
+static GimpBoundary * generate_boundary (GeglBuffer *buffer,
+ const GeglRectangle *region,
+ const Babl *format,
+ GimpBoundaryType type,
+ gint x1,
+ gint y1,
+ gint x2,
+ gint y2,
+ gfloat threshold);
+
+static gint cmp_segptr_xy1_addr (const GimpBoundSeg **seg_ptr_a,
+ const GimpBoundSeg **seg_ptr_b);
+static gint cmp_segptr_xy2_addr (const GimpBoundSeg **seg_ptr_a,
+ const GimpBoundSeg **seg_ptr_b);
+
+static gint cmp_segptr_xy1 (const GimpBoundSeg **seg_ptr_a,
+ const GimpBoundSeg **seg_ptr_b);
+static gint cmp_segptr_xy2 (const GimpBoundSeg **seg_ptr_a,
+ const GimpBoundSeg **seg_ptr_b);
+
+static const GimpBoundSeg * find_segment (const GimpBoundSeg **segs_by_xy1,
+ const GimpBoundSeg **segs_by_xy2,
+ gint num_segs,
+ gint x,
+ gint y);
+
+static const GimpBoundSeg * find_segment_with_func (const GimpBoundSeg **segs,
+ gint num_segs,
+ const GimpBoundSeg *search_seg,
+ GCompareFunc cmp_func);
+
+static void simplify_subdivide (const GimpBoundSeg *segs,
+ gint start_idx,
+ gint end_idx,
+ GArray **ret_points);
+
+
+/* public functions */
+
+/**
+ * gimp_boundary_find:
+ * @buffer: a #GeglBuffer
+ * @format: a #Babl float format representing the component to analyze
+ * @type: type of bounds
+ * @x1: left side of bounds
+ * @y1: top side of bounds
+ * @x2: right side of bounds
+ * @y2: bottom side of bounds
+ * @threshold: pixel value of boundary line
+ * @num_segs: number of returned #GimpBoundSeg's
+ *
+ * This function returns an array of #GimpBoundSeg's which describe all
+ * outlines along pixel value @threahold, optionally within specified
+ * bounds instead of the whole region.
+ *
+ * The @maskPR parameter can be any PixelRegion. If the region has
+ * more than 1 bytes/pixel, the last byte of each pixel is used to
+ * determine the boundary outline.
+ *
+ * Return value: the boundary array.
+ **/
+GimpBoundSeg *
+gimp_boundary_find (GeglBuffer *buffer,
+ const GeglRectangle *region,
+ const Babl *format,
+ GimpBoundaryType type,
+ int x1,
+ int y1,
+ int x2,
+ int y2,
+ gfloat threshold,
+ int *num_segs)
+{
+ GimpBoundary *boundary;
+ GeglRectangle rect = { 0, };
+
+ g_return_val_if_fail (GEGL_IS_BUFFER (buffer), NULL);
+ g_return_val_if_fail (num_segs != NULL, NULL);
+ g_return_val_if_fail (format != NULL, NULL);
+ g_return_val_if_fail (babl_format_get_bytes_per_pixel (format) ==
+ sizeof (gfloat), NULL);
+
+ if (region)
+ {
+ rect = *region;
+ }
+ else
+ {
+ rect.width = gegl_buffer_get_width (buffer);
+ rect.height = gegl_buffer_get_height (buffer);
+ }
+
+ boundary = generate_boundary (buffer, &rect, format, type,
+ x1, y1, x2, y2, threshold);
+
+ *num_segs = boundary->num_segs;
+
+ return gimp_boundary_free (boundary, FALSE);
+}
+
+/**
+ * gimp_boundary_sort:
+ * @segs: unsorted input segs.
+ * @num_segs: number of input segs
+ * @num_groups: number of groups in the sorted segs
+ *
+ * This function takes an array of #GimpBoundSeg's as returned by
+ * gimp_boundary_find() and sorts it by contiguous groups. The returned
+ * array contains markers consisting of -1 coordinates and is
+ * @num_groups elements longer than @segs.
+ *
+ * Return value: the sorted segs
+ **/
+GimpBoundSeg *
+gimp_boundary_sort (const GimpBoundSeg *segs,
+ gint num_segs,
+ gint *num_groups)
+{
+ GimpBoundary *boundary;
+ const GimpBoundSeg **segs_ptrs_by_xy1;
+ const GimpBoundSeg **segs_ptrs_by_xy2;
+ gint index;
+ gint x, y;
+ gint startx, starty;
+
+ g_return_val_if_fail ((segs == NULL && num_segs == 0) ||
+ (segs != NULL && num_segs > 0), NULL);
+ g_return_val_if_fail (num_groups != NULL, NULL);
+
+ *num_groups = 0;
+
+ if (num_segs == 0)
+ return NULL;
+
+ /* prepare arrays with GimpBoundSeg pointers sorted by xy1 and xy2
+ * accordingly
+ */
+ segs_ptrs_by_xy1 = g_new (const GimpBoundSeg *, num_segs);
+ segs_ptrs_by_xy2 = g_new (const GimpBoundSeg *, num_segs);
+
+ for (index = 0; index < num_segs; index++)
+ {
+ segs_ptrs_by_xy1[index] = segs + index;
+ segs_ptrs_by_xy2[index] = segs + index;
+ }
+
+ qsort (segs_ptrs_by_xy1, num_segs, sizeof (GimpBoundSeg *),
+ (GCompareFunc) cmp_segptr_xy1_addr);
+ qsort (segs_ptrs_by_xy2, num_segs, sizeof (GimpBoundSeg *),
+ (GCompareFunc) cmp_segptr_xy2_addr);
+
+ for (index = 0; index < num_segs; index++)
+ ((GimpBoundSeg *) segs)[index].visited = FALSE;
+
+ boundary = gimp_boundary_new (NULL);
+
+ for (index = 0; index < num_segs; index++)
+ {
+ const GimpBoundSeg *cur_seg;
+
+ if (segs[index].visited)
+ continue;
+
+ gimp_boundary_add_seg (boundary,
+ segs[index].x1, segs[index].y1,
+ segs[index].x2, segs[index].y2,
+ segs[index].open);
+
+ ((GimpBoundSeg *) segs)[index].visited = TRUE;
+
+ startx = segs[index].x1;
+ starty = segs[index].y1;
+ x = segs[index].x2;
+ y = segs[index].y2;
+
+ while ((cur_seg = find_segment (segs_ptrs_by_xy1, segs_ptrs_by_xy2,
+ num_segs, x, y)) != NULL)
+ {
+ /* make sure ordering is correct */
+ if (x == cur_seg->x1 && y == cur_seg->y1)
+ {
+ gimp_boundary_add_seg (boundary,
+ cur_seg->x1, cur_seg->y1,
+ cur_seg->x2, cur_seg->y2,
+ cur_seg->open);
+ x = cur_seg->x2;
+ y = cur_seg->y2;
+ }
+ else
+ {
+ gimp_boundary_add_seg (boundary,
+ cur_seg->x2, cur_seg->y2,
+ cur_seg->x1, cur_seg->y1,
+ cur_seg->open);
+ x = cur_seg->x1;
+ y = cur_seg->y1;
+ }
+
+ ((GimpBoundSeg *) cur_seg)->visited = TRUE;
+ }
+
+ if (G_UNLIKELY (x != startx || y != starty))
+ g_warning ("sort_boundary(): Unconnected boundary group!");
+
+ /* Mark the end of a group */
+ *num_groups = *num_groups + 1;
+ gimp_boundary_add_seg (boundary, -1, -1, -1, -1, 0);
+ }
+
+ g_free (segs_ptrs_by_xy1);
+ g_free (segs_ptrs_by_xy2);
+
+ return gimp_boundary_free (boundary, FALSE);
+}
+
+/**
+ * gimp_boundary_simplify:
+ * @sorted_segs: sorted input segs
+ * @num_groups: number of groups in the sorted segs
+ * @num_segs: number of returned segs.
+ *
+ * This function takes an array of #GimpBoundSeg's which has been sorted
+ * with gimp_boundary_sort() and reduces the number of segments while
+ * preserving the general shape as close as possible.
+ *
+ * Return value: the simplified segs.
+ **/
+GimpBoundSeg *
+gimp_boundary_simplify (GimpBoundSeg *sorted_segs,
+ gint num_groups,
+ gint *num_segs)
+{
+ GArray *new_bounds;
+ gint i, seg;
+
+ g_return_val_if_fail ((sorted_segs == NULL && num_groups == 0) ||
+ (sorted_segs != NULL && num_groups > 0), NULL);
+ g_return_val_if_fail (num_segs != NULL, NULL);
+
+ new_bounds = g_array_new (FALSE, FALSE, sizeof (GimpBoundSeg));
+
+ seg = 0;
+
+ for (i = 0; i < num_groups; i++)
+ {
+ gint start = seg;
+ gint n_points = 0;
+
+ while (sorted_segs[seg].x1 != -1 ||
+ sorted_segs[seg].x2 != -1 ||
+ sorted_segs[seg].y1 != -1 ||
+ sorted_segs[seg].y2 != -1)
+ {
+ n_points++;
+ seg++;
+ }
+
+ if (n_points > 0)
+ {
+ GArray *tmp_points;
+ GimpBoundSeg tmp_seg;
+ gint j;
+
+ tmp_points = g_array_new (FALSE, FALSE, sizeof (gint));
+
+ /* temporarily use the delimiter to close the polygon */
+ tmp_seg = sorted_segs[seg];
+ sorted_segs[seg] = sorted_segs[start];
+ simplify_subdivide (sorted_segs,
+ start, start + n_points, &tmp_points);
+ sorted_segs[seg] = tmp_seg;
+
+ for (j = 0; j < tmp_points->len; j++)
+ g_array_append_val (new_bounds,
+ sorted_segs[g_array_index (tmp_points,
+ gint, j)]);
+
+ g_array_append_val (new_bounds, sorted_segs[seg]);
+
+ g_array_free (tmp_points, TRUE);
+ }
+
+ seg++;
+ }
+
+ *num_segs = new_bounds->len;
+
+ return (GimpBoundSeg *) g_array_free (new_bounds, FALSE);
+}
+
+void
+gimp_boundary_offset (GimpBoundSeg *segs,
+ gint num_segs,
+ gint off_x,
+ gint off_y)
+{
+ gint i;
+
+ g_return_if_fail ((segs == NULL && num_segs == 0) ||
+ (segs != NULL && num_segs > 0));
+
+ for (i = 0; i < num_segs; i++)
+ {
+ /* don't offset sorting sentinels */
+ if (!(segs[i].x1 == -1 &&
+ segs[i].y1 == -1 &&
+ segs[i].x2 == -1 &&
+ segs[i].y2 == -1))
+ {
+ segs[i].x1 += off_x;
+ segs[i].y1 += off_y;
+ segs[i].x2 += off_x;
+ segs[i].y2 += off_y;
+ }
+ }
+}
+
+
+/* private functions */
+
+static GimpBoundary *
+gimp_boundary_new (const GeglRectangle *region)
+{
+ GimpBoundary *boundary = g_slice_new0 (GimpBoundary);
+
+ if (region)
+ {
+ gint i;
+
+ /* array for determining the vertical line segments
+ * which must be drawn
+ */
+ boundary->vert_segs = g_new (gint, region->width + region->x + 1);
+
+ for (i = 0; i <= (region->width + region->x); i++)
+ boundary->vert_segs[i] = -1;
+
+ /* find the maximum possible number of empty segments
+ * given the current mask
+ */
+ boundary->max_empty_segs = region->width + 3;
+
+ boundary->empty_segs_n = g_new (gint, boundary->max_empty_segs);
+ boundary->empty_segs_c = g_new (gint, boundary->max_empty_segs);
+ boundary->empty_segs_l = g_new (gint, boundary->max_empty_segs);
+ }
+
+ return boundary;
+}
+
+static GimpBoundSeg *
+gimp_boundary_free (GimpBoundary *boundary,
+ gboolean free_segs)
+{
+ GimpBoundSeg *segs = NULL;
+
+ if (free_segs)
+ g_free (boundary->segs);
+ else
+ segs = boundary->segs;
+
+ g_free (boundary->vert_segs);
+ g_free (boundary->empty_segs_n);
+ g_free (boundary->empty_segs_c);
+ g_free (boundary->empty_segs_l);
+
+ g_slice_free (GimpBoundary, boundary);
+
+ return segs;
+}
+
+static void
+gimp_boundary_add_seg (GimpBoundary *boundary,
+ gint x1,
+ gint y1,
+ gint x2,
+ gint y2,
+ gboolean open)
+{
+ if (boundary->num_segs >= boundary->max_segs)
+ {
+ boundary->max_segs += MAX_SEGS_INC;
+
+ boundary->segs = g_renew (GimpBoundSeg, boundary->segs, boundary->max_segs);
+ }
+
+ boundary->segs[boundary->num_segs].x1 = x1;
+ boundary->segs[boundary->num_segs].y1 = y1;
+ boundary->segs[boundary->num_segs].x2 = x2;
+ boundary->segs[boundary->num_segs].y2 = y2;
+ boundary->segs[boundary->num_segs].open = open;
+
+ boundary->num_segs ++;
+}
+
+static void
+find_empty_segs (const GeglRectangle *region,
+ const gfloat *line_data,
+ gint scanline,
+ gint empty_segs[],
+ gint max_empty,
+ gint *num_empty,
+ GimpBoundaryType type,
+ gint x1,
+ gint y1,
+ gint x2,
+ gint y2,
+ gfloat threshold)
+{
+ gint start = 0;
+ gint end = 0;
+ gint endx = 0;
+ gint last = -1;
+ gint l_num_empty;
+ gint x;
+
+ *num_empty = 0;
+
+ if (scanline < region->y || scanline >= (region->y + region->height))
+ {
+ empty_segs[(*num_empty)++] = 0;
+ empty_segs[(*num_empty)++] = G_MAXINT;
+ return;
+ }
+
+ if (type == GIMP_BOUNDARY_WITHIN_BOUNDS)
+ {
+ if (scanline < y1 || scanline >= y2)
+ {
+ empty_segs[(*num_empty)++] = 0;
+ empty_segs[(*num_empty)++] = G_MAXINT;
+ return;
+ }
+
+ start = x1;
+ end = x2;
+ }
+ else if (type == GIMP_BOUNDARY_IGNORE_BOUNDS)
+ {
+ start = region->x;
+ end = region->x + region->width;
+ if (scanline < y1 || scanline >= y2)
+ x2 = -1;
+ }
+
+ empty_segs[(*num_empty)++] = 0;
+
+ l_num_empty = *num_empty;
+
+ endx = end;
+
+ line_data += start;
+
+ for (x = start; x < end;)
+ {
+ if (type == GIMP_BOUNDARY_IGNORE_BOUNDS && (endx > x1 || x < x2))
+ {
+ for (; x < endx; x++)
+ {
+ gint val;
+
+ if (*line_data > threshold)
+ {
+ if (x >= x1 && x < x2)
+ val = -1;
+ else
+ val = 1;
+ }
+ else
+ {
+ val = -1;
+ }
+
+ line_data++;
+
+ if (last != val)
+ empty_segs[l_num_empty++] = x;
+
+ last = val;
+ }
+ }
+ else
+ {
+ for (; x < endx; x++)
+ {
+ gint val;
+
+ if (*line_data > threshold)
+ val = 1;
+ else
+ val = -1;
+
+ line_data++;
+
+ if (last != val)
+ empty_segs[l_num_empty++] = x;
+
+ last = val;
+ }
+ }
+ }
+
+ *num_empty = l_num_empty;
+
+ if (last > 0)
+ empty_segs[(*num_empty)++] = x;
+
+ empty_segs[(*num_empty)++] = G_MAXINT;
+}
+
+static void
+process_horiz_seg (GimpBoundary *boundary,
+ gint x1,
+ gint y1,
+ gint x2,
+ gint y2,
+ gboolean open)
+{
+ /* This procedure accounts for any vertical segments that must be
+ drawn to close in the horizontal segments. */
+
+ if (boundary->vert_segs[x1] >= 0)
+ {
+ gimp_boundary_add_seg (boundary, x1, boundary->vert_segs[x1], x1, y1, !open);
+ boundary->vert_segs[x1] = -1;
+ }
+ else
+ boundary->vert_segs[x1] = y1;
+
+ if (boundary->vert_segs[x2] >= 0)
+ {
+ gimp_boundary_add_seg (boundary, x2, boundary->vert_segs[x2], x2, y2, open);
+ boundary->vert_segs[x2] = -1;
+ }
+ else
+ boundary->vert_segs[x2] = y2;
+
+ gimp_boundary_add_seg (boundary, x1, y1, x2, y2, open);
+}
+
+static void
+make_horiz_segs (GimpBoundary *boundary,
+ gint start,
+ gint end,
+ gint scanline,
+ gint empty[],
+ gint num_empty,
+ gint top)
+{
+ gint empty_index;
+ gint e_s, e_e; /* empty segment start and end values */
+
+ for (empty_index = 0; empty_index < num_empty; empty_index += 2)
+ {
+ e_s = *empty++;
+ e_e = *empty++;
+
+ if (e_s <= start && e_e >= end)
+ {
+ process_horiz_seg (boundary,
+ start, scanline, end, scanline, top);
+ }
+ else if ((e_s > start && e_s < end) ||
+ (e_e < end && e_e > start))
+ {
+ process_horiz_seg (boundary,
+ MAX (e_s, start), scanline,
+ MIN (e_e, end), scanline, top);
+ }
+ }
+}
+
+static GimpBoundary *
+generate_boundary (GeglBuffer *buffer,
+ const GeglRectangle *region,
+ const Babl *format,
+ GimpBoundaryType type,
+ gint x1,
+ gint y1,
+ gint x2,
+ gint y2,
+ gfloat threshold)
+{
+ GimpBoundary *boundary;
+ GeglRectangle line_rect = { 0, };
+ gfloat *line_data;
+ gint scanline;
+ gint i;
+ gint start, end;
+ gint *tmp_segs;
+
+ gint num_empty_n = 0;
+ gint num_empty_c = 0;
+ gint num_empty_l = 0;
+
+ boundary = gimp_boundary_new (region);
+
+ line_rect.width = gegl_buffer_get_width (buffer);
+ line_rect.height = 1;
+
+ line_data = g_alloca (sizeof (gfloat) * line_rect.width);
+
+ start = 0;
+ end = 0;
+
+ if (type == GIMP_BOUNDARY_WITHIN_BOUNDS)
+ {
+ start = y1;
+ end = y2;
+ }
+ else if (type == GIMP_BOUNDARY_IGNORE_BOUNDS)
+ {
+ start = region->y;
+ end = region->y + region->height;
+ }
+
+ /* Find the empty segments for the previous and current scanlines */
+ find_empty_segs (region, NULL,
+ start - 1, boundary->empty_segs_l,
+ boundary->max_empty_segs, &num_empty_l,
+ type, x1, y1, x2, y2,
+ threshold);
+
+ line_rect.y = start;
+ gegl_buffer_get (buffer, &line_rect, 1.0, format,
+ line_data, GEGL_AUTO_ROWSTRIDE,
+ GEGL_ABYSS_NONE);
+
+ find_empty_segs (region, line_data,
+ start, boundary->empty_segs_c,
+ boundary->max_empty_segs, &num_empty_c,
+ type, x1, y1, x2, y2,
+ threshold);
+
+ for (scanline = start; scanline < end; scanline++)
+ {
+ /* find the empty segment list for the next scanline */
+ line_rect.y = scanline + 1;
+ if (scanline + 1 == end)
+ line_data = NULL;
+ else
+ gegl_buffer_get (buffer, &line_rect, 1.0, format,
+ line_data, GEGL_AUTO_ROWSTRIDE,
+ GEGL_ABYSS_NONE);
+
+ find_empty_segs (region, line_data,
+ scanline + 1, boundary->empty_segs_n,
+ boundary->max_empty_segs, &num_empty_n,
+ type, x1, y1, x2, y2,
+ threshold);
+
+ /* process the segments on the current scanline */
+ for (i = 1; i < num_empty_c - 1; i += 2)
+ {
+ make_horiz_segs (boundary,
+ boundary->empty_segs_c [i],
+ boundary->empty_segs_c [i+1],
+ scanline,
+ boundary->empty_segs_l, num_empty_l, 1);
+ make_horiz_segs (boundary,
+ boundary->empty_segs_c [i],
+ boundary->empty_segs_c [i+1],
+ scanline + 1,
+ boundary->empty_segs_n, num_empty_n, 0);
+ }
+
+ /* get the next scanline of empty segments, swap others */
+ tmp_segs = boundary->empty_segs_l;
+ boundary->empty_segs_l = boundary->empty_segs_c;
+ num_empty_l = num_empty_c;
+ boundary->empty_segs_c = boundary->empty_segs_n;
+ num_empty_c = num_empty_n;
+ boundary->empty_segs_n = tmp_segs;
+ }
+
+ return boundary;
+}
+
+/* sorting utility functions */
+
+static inline gint
+cmp_xy (const gint ax,
+ const gint ay,
+ const gint bx,
+ const gint by)
+{
+ if (ay < by)
+ {
+ return -1;
+ }
+ else if (ay > by)
+ {
+ return 1;
+ }
+ else if (ax < bx)
+ {
+ return -1;
+ }
+ else if (ax > bx)
+ {
+ return 1;
+ }
+ else
+ {
+ return 0;
+ }
+}
+
+
+/*
+ * Compares (x1, y1) pairs in specified segments, using their addresses if
+ * (x1, y1) pairs are equal.
+ */
+static gint
+cmp_segptr_xy1_addr (const GimpBoundSeg **seg_ptr_a,
+ const GimpBoundSeg **seg_ptr_b)
+{
+ const GimpBoundSeg *seg_a = *seg_ptr_a;
+ const GimpBoundSeg *seg_b = *seg_ptr_b;
+
+ gint result = cmp_xy (seg_a->x1, seg_a->y1, seg_b->x1, seg_b->y1);
+
+ if (result == 0)
+ {
+ if (seg_a < seg_b)
+ result = -1;
+ else if (seg_a > seg_b)
+ result = 1;
+ }
+
+ return result;
+}
+
+/*
+ * Compares (x2, y2) pairs in specified segments, using their addresses if
+ * (x2, y2) pairs are equal.
+ */
+static gint
+cmp_segptr_xy2_addr (const GimpBoundSeg **seg_ptr_a,
+ const GimpBoundSeg **seg_ptr_b)
+{
+ const GimpBoundSeg *seg_a = *seg_ptr_a;
+ const GimpBoundSeg *seg_b = *seg_ptr_b;
+
+ gint result = cmp_xy (seg_a->x2, seg_a->y2, seg_b->x2, seg_b->y2);
+
+ if (result == 0)
+ {
+ if (seg_a < seg_b)
+ result = -1;
+ else if (seg_a > seg_b)
+ result = 1;
+ }
+
+ return result;
+}
+
+
+/*
+ * Compares (x1, y1) pairs in specified segments.
+ */
+static gint
+cmp_segptr_xy1 (const GimpBoundSeg **seg_ptr_a,
+ const GimpBoundSeg **seg_ptr_b)
+{
+ const GimpBoundSeg *seg_a = *seg_ptr_a, *seg_b = *seg_ptr_b;
+
+ return cmp_xy (seg_a->x1, seg_a->y1, seg_b->x1, seg_b->y1);
+}
+
+/*
+ * Compares (x2, y2) pairs in specified segments.
+ */
+static gint
+cmp_segptr_xy2 (const GimpBoundSeg **seg_ptr_a,
+ const GimpBoundSeg **seg_ptr_b)
+{
+ const GimpBoundSeg *seg_a = *seg_ptr_a;
+ const GimpBoundSeg *seg_b = *seg_ptr_b;
+
+ return cmp_xy (seg_a->x2, seg_a->y2, seg_b->x2, seg_b->y2);
+}
+
+
+static const GimpBoundSeg *
+find_segment (const GimpBoundSeg **segs_by_xy1,
+ const GimpBoundSeg **segs_by_xy2,
+ gint num_segs,
+ gint x,
+ gint y)
+{
+ const GimpBoundSeg *segptr_xy1;
+ const GimpBoundSeg *segptr_xy2;
+ GimpBoundSeg search_seg;
+
+ search_seg.x1 = search_seg.x2 = x;
+ search_seg.y1 = search_seg.y2 = y;
+
+ segptr_xy1 = find_segment_with_func (segs_by_xy1, num_segs, &search_seg,
+ (GCompareFunc) cmp_segptr_xy1);
+ segptr_xy2 = find_segment_with_func (segs_by_xy2, num_segs, &search_seg,
+ (GCompareFunc) cmp_segptr_xy2);
+
+ /* return segment with smaller address */
+ if (segptr_xy1 != NULL && segptr_xy2 != NULL)
+ return MIN(segptr_xy1, segptr_xy2);
+ else if (segptr_xy1 != NULL)
+ return segptr_xy1;
+ else if (segptr_xy2 != NULL)
+ return segptr_xy2;
+
+ return NULL;
+}
+
+
+static const GimpBoundSeg *
+find_segment_with_func (const GimpBoundSeg **segs,
+ gint num_segs,
+ const GimpBoundSeg *search_seg,
+ GCompareFunc cmp_func)
+{
+ const GimpBoundSeg **seg;
+ const GimpBoundSeg *found_seg = NULL;
+
+ seg = bsearch (&search_seg, segs, num_segs, sizeof (GimpBoundSeg *), cmp_func);
+
+ if (seg != NULL)
+ {
+ /* find first matching segment */
+ while (seg > segs && cmp_func (seg - 1, &search_seg) == 0)
+ seg--;
+
+ /* find first non-visited segment */
+ while (seg != segs + num_segs && cmp_func (seg, &search_seg) == 0)
+ if (!(*seg)->visited)
+ {
+ found_seg = *seg;
+ break;
+ }
+ else
+ seg++;
+ }
+
+ return found_seg;
+}
+
+
+/* simplifying utility functions */
+
+static void
+simplify_subdivide (const GimpBoundSeg *segs,
+ gint start_idx,
+ gint end_idx,
+ GArray **ret_points)
+{
+ gint maxdist_idx;
+ gint maxdist;
+ gint threshold;
+ gint i, dx, dy;
+
+ if (end_idx - start_idx < 2)
+ {
+ *ret_points = g_array_append_val (*ret_points, start_idx);
+ return;
+ }
+
+ maxdist = 0;
+
+ if (segs[start_idx].x1 == segs[end_idx].x1 &&
+ segs[start_idx].y1 == segs[end_idx].y1)
+ {
+ /* start and endpoint are at the same coordinates */
+ for (i = start_idx + 1; i < end_idx; i++)
+ {
+ /* compare the sqared distances */
+ gint dist = (SQR (segs[i].x1 - segs[start_idx].x1) +
+ SQR (segs[i].y1 - segs[start_idx].y1));
+
+ if (dist > maxdist)
+ {
+ maxdist = dist;
+ }
+ }
+
+ threshold = 1;
+ }
+ else
+ {
+ dx = segs[end_idx].x1 - segs[start_idx].x1;
+ dy = segs[end_idx].y1 - segs[start_idx].y1;
+
+ for (i = start_idx + 1; i < end_idx; i++)
+ {
+ /* this is not really the euclidic distance, but is
+ * proportional for this part of the line
+ * (for the real distance we'd have to divide by
+ * (SQR(dx)+SQR(dy)))
+ */
+ gint dist = abs (dx * (segs[start_idx].y1 - segs[i].y1) -
+ dy * (segs[start_idx].x1 - segs[i].x1));
+
+ if (dist > maxdist)
+ {
+ maxdist = dist;
+ }
+ }
+
+ /* threshold is chosen to catch 45 degree stairs */
+ threshold = SQR (dx) + SQR (dy);
+ }
+
+ if (maxdist <= threshold)
+ {
+ *ret_points = g_array_append_val (*ret_points, start_idx);
+ return;
+ }
+
+ /* Simons hack */
+ maxdist_idx = (start_idx + end_idx) / 2;
+
+ simplify_subdivide (segs, start_idx, maxdist_idx, ret_points);
+ simplify_subdivide (segs, maxdist_idx, end_idx, ret_points);
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-11 17:27:28 +0000