/* gdkDPSgeomentry.c -- geometry calculation codes that comes from gyve * Copyright (C) 1999 GYVE Development Team * * Author: Masatake YAMATO * Time-stamp: <00/04/03 05:09:53 masata-y> * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Library General Public * License as published by the Free Software Foundation; either * version 2 of the License, or (at your option) any later version. * * This library 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 * Library General Public License for more details. * * You should have received a copy of the GNU Library General Public * License along with this library; if not, write to the Free * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */ #include "gdkDPS.h" #include "gdkDPSgeometry.h" #include "config.h" #include #include #include /* * Coordtr */ void gdk_dps_coordtr_init(GdkDPSCoordtr* coordtr) { g_return_if_fail(coordtr); gdk_dps_matrix_init(coordtr->ctm); gdk_dps_matrix_init(coordtr->invctm); coordtr->x_offset = 0.0; coordtr->y_offset = 0.0; coordtr->data_dirty = TRUE; } void gdk_dps_coordtr_copy(GdkDPSCoordtr* from, GdkDPSCoordtr * to) { g_return_if_fail (from); g_return_if_fail ( to); g_return_if_fail ( from->ctm); g_return_if_fail ( from->invctm); g_return_if_fail ( to->ctm); g_return_if_fail ( to->invctm); gdk_dps_matrix_copy(from->ctm, to->ctm); gdk_dps_matrix_copy(from->invctm, to->invctm); to->x_offset = from->x_offset; to->y_offset = from->y_offset; to->data_dirty = from->data_dirty; } gboolean gdk_dps_coordtr_equal(GdkDPSCoordtr* a, GdkDPSCoordtr * b) { if (FALSE == gdk_dps_matrix_equal(a->ctm, b->ctm)) return FALSE; if (FALSE == gdk_dps_matrix_equal(a->invctm, b->invctm)) return FALSE; if (a->x_offset != b->x_offset) return FALSE; if (a->y_offset != b->y_offset) return FALSE; if (a->data_dirty != b->data_dirty) return FALSE; return TRUE; } void gdk_dps_coordtr_make_dirty(GdkDPSCoordtr* coordtr) { g_return_if_fail(coordtr); coordtr->data_dirty = TRUE; } void gdk_dps_coordtr_make_clean(GdkDPSCoordtr* coordtr) { g_assert(coordtr); coordtr->data_dirty = FALSE; } gboolean gdk_dps_coordtr_is_dirty(GdkDPSCoordtr* coordtr) { g_return_val_if_fail(coordtr, FALSE); return coordtr->data_dirty; } void gdk_dps_coordtr_point(GdkDPSCoordtr* coordtr, GdkDPSTrDirection trdir, gpointer src, gpointer dist) { if (trdir == GDK_DPS_TRDIR_DPS2X) gdk_dps_coordtr_point_dps2x(coordtr, src, dist); else if (trdir == GDK_DPS_TRDIR_X2DPS) gdk_dps_coordtr_point_x2dps(coordtr, src, dist); else g_assert_not_reached(); } void gdk_dps_coordtr_point_x2dps( GdkDPSCoordtr* coordtr, GdkPoint * x_src, GdkDPSPoint* dps_dist) { GdkDPSPoint tmp; g_return_if_fail(coordtr); g_return_if_fail(dps_dist); g_return_if_fail(x_src); g_return_if_fail(!(coordtr->data_dirty)); tmp.x = (float)(x_src->x - coordtr->x_offset); tmp.y = (float)(x_src->y - coordtr->y_offset); gdk_dps_matrix_apply(coordtr->invctm, &tmp); *dps_dist = tmp; } void gdk_dps_coordtr_point_dps2x( GdkDPSCoordtr* coordtr, GdkDPSPoint * dps_src, GdkPoint* x_dist) { GdkDPSPoint tmp = *dps_src; gdk_dps_matrix_apply(coordtr->ctm, &tmp); x_dist->x = (int)(tmp.x + coordtr->x_offset); x_dist->y = (int)(tmp.y + coordtr->y_offset); } void gdk_dps_coordtr_rectangle(GdkDPSCoordtr* coordtr, GdkDPSTrDirection trdir, gpointer src, gpointer dist) { g_return_if_fail(trdir == GDK_DPS_TRDIR_DPS2X || trdir == GDK_DPS_TRDIR_X2DPS); if (trdir == GDK_DPS_TRDIR_DPS2X) gdk_dps_coordtr_rectangle_dps2x(coordtr, src, dist); else if (trdir == GDK_DPS_TRDIR_X2DPS) gdk_dps_coordtr_rectangle_x2dps(coordtr, src, dist); } void gdk_dps_coordtr_rectangle_x2dps(GdkDPSCoordtr* coordtr, GdkRectangle * x_src, GdkDPSRectangle* dps_dist) { GdkPoint a_x, b_x; GdkDPSPoint a_dps, b_dps; g_return_if_fail(coordtr); g_return_if_fail(x_src); g_return_if_fail(dps_dist); g_return_if_fail(!(coordtr->data_dirty)); a_x.x = x_src->x; a_x.y = x_src->y; b_x.x = x_src->x + x_src->width; b_x.y = x_src->y + x_src->height; gdk_dps_coordtr_point_x2dps(coordtr, &a_x, &a_dps); gdk_dps_coordtr_point_x2dps(coordtr, &b_x, &b_dps); if (a_dps.x < b_dps.x) { dps_dist->x = a_dps.x; dps_dist->width = b_dps.x - a_dps.x; } else { dps_dist->x = b_dps.x; dps_dist->width = a_dps.x - b_dps.x; } if (a_dps.y < b_dps.y) { dps_dist->y = a_dps.y; dps_dist->height = b_dps.y - a_dps.y; } else { dps_dist->y = b_dps.y; dps_dist->height = a_dps.y - b_dps.y; } } void gdk_dps_coordtr_rectangle_dps2x(GdkDPSCoordtr* coordtr, GdkDPSRectangle * dps_src, GdkRectangle * x_dist) { /* a_dps a_x *---+ *---+ |DPS| => | X | +---* +---* b_dps b_x */ GdkDPSPoint a_dps, b_dps; GdkPoint a_x, b_x; g_return_if_fail(coordtr); g_return_if_fail(dps_src); g_return_if_fail(x_dist); g_return_if_fail(!(coordtr->data_dirty)); a_dps.x = dps_src->x; a_dps.y = dps_src->y + dps_src->height; gdk_dps_coordtr_point_dps2x(coordtr, &a_dps, &a_x); b_dps.x = dps_src->x + dps_src->width; b_dps.y = dps_src->y; gdk_dps_coordtr_point_dps2x(coordtr, &b_dps, &b_x); if (a_x.x < b_x.x) { x_dist->x = a_x.x; x_dist->width = b_x.x - a_x.x; } else { x_dist->x = b_x.x; x_dist->width = a_x.x - b_x.x; } if (a_x.y < b_x.y) { x_dist->y = a_x.y; x_dist->height = b_x.y - a_x.y; } else { x_dist->y = b_x.y; x_dist->height = a_x.y - b_x.y; } } void gdk_dps_coordtr_size (GdkDPSCoordtr * coordtr, GdkDPSTrDirection trdir, gpointer src, gpointer dist) { g_return_if_fail(coordtr); g_return_if_fail(!(coordtr->data_dirty)); g_return_if_fail(trdir == GDK_DPS_TRDIR_DPS2X || trdir == GDK_DPS_TRDIR_X2DPS); g_return_if_fail(src); g_return_if_fail(dist); if (trdir == GDK_DPS_TRDIR_DPS2X) { ((GdkSize *)dist)->width = (guint)gdk_dps_coordtr_width (coordtr, trdir, ((GdkDPSSize*)src)->width); ((GdkSize *)dist)->height = (guint)gdk_dps_coordtr_height (coordtr, trdir, ((GdkDPSSize*)src)->height); } else { ((GdkDPSSize *)dist)->width = gdk_dps_coordtr_width (coordtr, trdir, (gfloat)(((GdkSize*)src)->width)); ((GdkDPSSize *)dist)->height = gdk_dps_coordtr_height (coordtr, trdir, (gfloat)(((GdkSize*)src)->height)); } } void gdk_dps_coordtr_size_x2dps(GdkDPSCoordtr* coordtr, GdkSize * x_src, GdkDPSSize * dps_dist) { gdk_dps_coordtr_size (coordtr, GDK_DPS_TRDIR_DPS2X, x_src, dps_dist); } void gdk_dps_coordtr_size_dps2x(GdkDPSCoordtr* coordtr, GdkDPSSize * dps_src, GdkSize * x_dist) { gdk_dps_coordtr_size (coordtr, GDK_DPS_TRDIR_X2DPS, dps_src, x_dist); } gfloat gdk_dps_coordtr_width(GdkDPSCoordtr* coordtr, GdkDPSTrDirection trdir, gfloat width) { GdkDPSPoint dps_a, dps_b; GdkPoint x_a, x_b; g_return_val_if_fail(coordtr, 0.0); g_return_val_if_fail(!(coordtr->data_dirty), 0.0); g_return_val_if_fail(trdir == GDK_DPS_TRDIR_DPS2X || trdir == GDK_DPS_TRDIR_X2DPS, 0.0); g_return_val_if_fail(width >= 0.0, 0.0); if (width == 0.0) return 0.0; if (trdir == GDK_DPS_TRDIR_DPS2X) { dps_a.x = width; dps_a.y = 0.0; gdk_dps_coordtr_point_dps2x(coordtr, &dps_a, &x_a); dps_b.x = 0.0; dps_b.y = 0.0; gdk_dps_coordtr_point_dps2x(coordtr, &dps_b, &x_b); if (x_b.y == x_a.y) return (gfloat)abs(x_b.x - x_a.x); else return sqrt((x_b.x - x_a.x)*(x_b.x - x_a.x) + (x_b.y - x_a.y)*(x_b.y - x_a.y)); } else /* GDK_DPS_TRDIR_X2DPS */ { x_a.x = (int)width; x_a.y = 0; gdk_dps_coordtr_point_x2dps(coordtr, &x_a, &dps_a); x_b.x = 0; x_b.y = 0; gdk_dps_coordtr_point_x2dps(coordtr, &x_b, &dps_b); return gdk_dps_point_distance(&dps_a, &dps_b); } } gfloat gdk_dps_coordtr_height(GdkDPSCoordtr* coordtr, GdkDPSTrDirection trdir, gfloat height) { GdkDPSPoint dps_a, dps_b; GdkPoint x_a, x_b; g_return_val_if_fail(coordtr, 0.0); g_return_val_if_fail(!(coordtr->data_dirty), 0.0); g_return_val_if_fail(trdir == GDK_DPS_TRDIR_DPS2X || trdir == GDK_DPS_TRDIR_X2DPS, 0.0); g_return_val_if_fail(height >= 0.0, 0.0); if (height == 0.0) return 0.0; if (trdir == GDK_DPS_TRDIR_DPS2X) { dps_a.x = 0.0; dps_a.y = height; gdk_dps_coordtr_point_dps2x(coordtr, &dps_a, &x_a); dps_b.x = 0.0; dps_b.y = 0.0; gdk_dps_coordtr_point_dps2x(coordtr, &dps_b, &x_b); if (x_b.x == x_a.x) return (gfloat)abs(x_b.y - x_a.y); else return sqrt((x_b.x - x_a.x)*(x_b.x - x_a.x) + (x_b.y - x_a.y)*(x_b.y - x_a.y)); } else /* X->DPS */ { x_a.x = 0; x_a.y = (int)height; gdk_dps_coordtr_point_x2dps(coordtr, &x_a, &dps_a); x_b.x = 0; x_b.y = 0; gdk_dps_coordtr_point_x2dps(coordtr, &x_b, &dps_b); return gdk_dps_point_distance(&dps_a, &dps_b); } } /* * Point */ GdkDPSPoint * gdk_dps_point_new(gfloat x, gfloat y) { GdkDPSPoint * point = g_new(GdkDPSPoint, 1); gdk_dps_point_set(point, x, y); return point; } void gdk_dps_point_init(GdkDPSPoint * point) { g_return_if_fail(point); point->x = 0.0; point->y = 0.0; } void gdk_dps_point_free(GdkDPSPoint * point) { g_return_if_fail(point); g_free(point); } void gdk_dps_point_set(GdkDPSPoint * point, gfloat x, gfloat y) { g_return_if_fail(point); point->x = x; point->y = y; } GdkDPSPoint gdk_dps_point_edge(GdkDPSPoint * a, GdkDPSPoint * b, GdkDPSEdge x_edge, GdkDPSEdge y_edge) { GdkDPSPoint result = {0.0, 0.0}; g_return_val_if_fail(a, result); g_return_val_if_fail(b, result); switch (x_edge) { case GDK_DPS_EDGE_MIN: result.x = (a->x > b->x)?b->x:a->x; break; case GDK_DPS_EDGE_MID: result.x = (a->x + b->x)/2.0; break; case GDK_DPS_EDGE_MAX: result.x = (a->x < b->x)?b->x:a->x; break; default: g_return_val_if_fail ((x_edge != GDK_DPS_EDGE_MIN) && (x_edge != GDK_DPS_EDGE_MID) && (x_edge != GDK_DPS_EDGE_MAX), result); } switch (y_edge) { case GDK_DPS_EDGE_MIN: result.y = (a->y > b->y)?b->y:a->y; break; case GDK_DPS_EDGE_MID: result.y = (a->y + b->y)/2.0; break; case GDK_DPS_EDGE_MAX: result.y = (a->y < b->y)?b->y:a->y; break; default: g_return_val_if_fail ((y_edge != GDK_DPS_EDGE_MIN) && (y_edge != GDK_DPS_EDGE_MID) && (y_edge != GDK_DPS_EDGE_MAX), result); } return result; } gboolean gdk_dps_point_equal(GdkDPSPoint * a, GdkDPSPoint * b) { g_return_val_if_fail(a, FALSE); g_return_val_if_fail(b, FALSE); if ((a->x == b->x) && (a->y == b->y)) return TRUE; else return FALSE; } gboolean gdk_dps_point_is_origin(GdkDPSPoint * point) { g_return_val_if_fail(point, FALSE); if ((point->x == 0.0) && (point->y == 0.0)) return TRUE ; else return FALSE; } gfloat gdk_dps_point_distance(GdkDPSPoint * a, GdkDPSPoint * b) { g_return_val_if_fail(a, 0.0); g_return_val_if_fail(b, 0.0); if (a->x == b->x) return fabs(a->y - b->y); else if (a->y == b->y) return fabs(a->x - b->x); return sqrt((a->x - b->x)*(a->x - b->x) + (a->y - b->y)*(a->y - b->y)); } void gdk_dps_point_message(GdkDPSPoint * point, gchar * message) { g_return_if_fail(point); if (message) g_message("%s: (x, y) = (%f, %f)", message, point->x, point->y); else g_message("(x, y) = (%f, %f)", point->x, point->y); } /* * Rectangle */ /* Constructor and Destructor */ GdkDPSRectangle * gdk_dps_rectangle_new(gfloat x, gfloat y, gfloat width, gfloat height) { GdkDPSRectangle * result; g_return_val_if_fail(width >= 0.0, NULL); g_return_val_if_fail(height >= 0.0, NULL); result = g_new(GdkDPSRectangle, 1); gdk_dps_rectangle_set(result, x, y, width, height); return result; } void gdk_dps_rectangle_free(GdkDPSRectangle * rect) { g_return_if_fail(rect); g_free(rect); } /* Accessors */ void gdk_dps_rectangle_set(GdkDPSRectangle * rect, gfloat x, gfloat y, gfloat width, gfloat height) { g_return_if_fail(rect); g_return_if_fail(width >= 0.0); g_return_if_fail(height >= 0.0); rect->x = x; rect->y = y; rect->width = width; rect->height = height; } void gdk_dps_rectangle_set_from_points(GdkDPSRectangle * rect, GdkDPSPoint * a, GdkDPSPoint * b) { GdkDPSPoint p, q; g_return_if_fail(rect); g_return_if_fail(a); g_return_if_fail(b); p = gdk_dps_point_edge(a, b, GDK_DPS_EDGE_MIN, GDK_DPS_EDGE_MIN); q = gdk_dps_point_edge(a, b, GDK_DPS_EDGE_MAX, GDK_DPS_EDGE_MAX); rect->x = p.x; rect->y = p.y; rect->width = q.x - p.x; rect->height = q.y - p.y; } void gdk_dps_rectangle_set_from_segment (GdkDPSRectangle * rect, GdkDPSSegment * segment) { g_return_if_fail (rect); g_return_if_fail (segment); *rect = gdk_dps_segment_get_rectangle (segment); } void gdk_dps_rectangle_set_from_center(GdkDPSRectangle * rect, GdkDPSPoint * center, gfloat width, gfloat height) { g_return_if_fail(rect); g_return_if_fail(center); g_return_if_fail(width >= 0.0); g_return_if_fail(height >= 0.0); rect->x = center->x - width/2.0; rect->y = center->y - height/2.0; rect->width = width; rect->height = height; } GdkDPSPoint gdk_dps_rectangle_get_point(GdkDPSRectangle * rect, GdkDPSEdge x_edge, GdkDPSEdge y_edge) { GdkDPSPoint p = {0.0, 0.0}; g_return_val_if_fail(rect, p); switch (x_edge) { case GDK_DPS_EDGE_MIN: p.x = rect->x; break; case GDK_DPS_EDGE_MID: p.x = rect->x + rect->width/2.0; break; case GDK_DPS_EDGE_MAX: p.x = rect->x + rect->width; break; default: g_return_val_if_fail ((x_edge != GDK_DPS_EDGE_MIN) && (x_edge != GDK_DPS_EDGE_MID) && (x_edge != GDK_DPS_EDGE_MAX), p); } switch (y_edge) { case GDK_DPS_EDGE_MIN: p.y = rect->y; break; case GDK_DPS_EDGE_MID: p.y = rect->y + rect->height/2.0; break; case GDK_DPS_EDGE_MAX: p.y = rect->y + rect->height; break; default: g_return_val_if_fail ((y_edge != GDK_DPS_EDGE_MIN) && (y_edge != GDK_DPS_EDGE_MID) && (y_edge != GDK_DPS_EDGE_MAX), p); } return p; } /* Predicators */ gboolean gdk_dps_rectangle_equal(GdkDPSRectangle * a, GdkDPSRectangle * b) { g_return_val_if_fail(a, FALSE); g_return_val_if_fail(b, FALSE); if ((a->x == b->x) && (a->y == b->y) && (a->width == b->width) && (a->height == b->height)) return TRUE ; else return FALSE; } gboolean gdk_dps_rectangle_is_empty(GdkDPSRectangle * rect) { g_return_val_if_fail(rect, FALSE); if ((rect->width == 0.0) && (rect->height == 0.0)) return TRUE ; else return FALSE; } gboolean gdk_dps_rectangle_is_normalized(GdkDPSRectangle * rect) { g_return_val_if_fail(rect, FALSE); if ((rect->x == 0.0) && (rect->y == 0.0)) return TRUE ; else return FALSE; } /* Hit detect */ gboolean gdk_dps_rectangle_contains_point(GdkDPSRectangle * rect, GdkDPSPoint * point, gboolean accept_on_line) { g_return_val_if_fail(rect, FALSE); g_return_val_if_fail(point, FALSE); if (TRUE == accept_on_line) { if ((point->x >= rect->x) && (point->y >= rect->y) && (point->x <= rect->x + rect->width) && (point->y <= rect->y + rect->height)) return TRUE; else return FALSE; } else { if ((point->x > rect->x) && (point->y > rect->y) && (point->x < rect->x + rect->width) && (point->y < rect->y + rect->height)) return TRUE; else return FALSE; } } gboolean gdk_dps_rectangle_contains_rectangle(GdkDPSRectangle * super_rect, GdkDPSRectangle * sub_rect, gboolean accept_on_line) { g_return_val_if_fail(super_rect, FALSE); g_return_val_if_fail(sub_rect, FALSE); if (accept_on_line) { if ((super_rect->x <= sub_rect->x) && (super_rect->y <= sub_rect->y) && (super_rect->width + super_rect->x >= sub_rect->width + sub_rect->x) && (super_rect->height + super_rect->y >= sub_rect->height + sub_rect->y)) return TRUE; else return FALSE; } else { if ((super_rect->x < sub_rect->x) && (super_rect->y < sub_rect->y) && (super_rect->width + super_rect->x > sub_rect->width + sub_rect->x) && (super_rect->height + super_rect->y > sub_rect->height + sub_rect->y)) return TRUE; else return FALSE; } } /* Operators from gdkrectangle.c */ void gdk_dps_rectangle_union(GdkDPSRectangle * src1, GdkDPSRectangle * src2, GdkDPSRectangle * dest) { g_return_if_fail (src1 != NULL); g_return_if_fail (src2 != NULL); g_return_if_fail (dest != NULL); dest->x = MIN (src1->x, src2->x); dest->y = MIN (src1->y, src2->y); dest->width = MAX (src1->x + src1->width, src2->x + src2->width) - dest->x; dest->height = MAX (src1->y + src1->height, src2->y + src2->height) - dest->y; } gboolean gdk_dps_rectangle_intersect(GdkDPSRectangle * src1, GdkDPSRectangle * src2, GdkDPSRectangle * dest) { GdkDPSRectangle v_dest; GdkDPSRectangle *temp; gfloat src1_x2, src1_y2; gfloat src2_x2, src2_y2; gboolean return_val; g_return_val_if_fail (src1 != NULL, FALSE); g_return_val_if_fail (src2 != NULL, FALSE); if (dest == NULL) dest = &v_dest; return_val = FALSE; if (src2->x < src1->x) { temp = src1; src1 = src2; src2 = temp; } dest->x = src2->x; src1_x2 = src1->x + src1->width; src2_x2 = src2->x + src2->width; if (src2->x < src1_x2) { if (src1_x2 < src2_x2) dest->width = src1_x2 - dest->x; else dest->width = src2_x2 - dest->x; if (src2->y < src1->y) { temp = src1; src1 = src2; src2 = temp; } dest->y = src2->y; src1_y2 = src1->y + src1->height; src2_y2 = src2->y + src2->height; if (src2->y < src1_y2) { return_val = TRUE; if (src1_y2 < src2_y2) dest->height = src1_y2 - dest->y; else dest->height = src2_y2 - dest->y; if (dest->height == 0.0) return_val = FALSE; if (dest->width == 0.0) return_val = FALSE; } } return return_val; } gboolean gdk_dps_rectangle_border (GdkDPSRectangle * src1, GdkDPSRectangle * src2, GdkDPSRectangle * dest) { GdkDPSRectangle v_dest; GdkDPSRectangle *temp; gfloat src1_x2, src1_y2; gfloat src2_x2, src2_y2; gboolean return_val; g_return_val_if_fail (src1 != NULL, FALSE); g_return_val_if_fail (src2 != NULL, FALSE); if (dest == NULL) dest = &v_dest; return_val = FALSE; if (src2->x < src1->x) { temp = src1; src1 = src2; src2 = temp; } dest->x = src2->x; src1_x2 = src1->x + src1->width; src2_x2 = src2->x + src2->width; if (src2->x <= src1_x2) { if (src1_x2 < src2_x2) dest->width = src1_x2 - dest->x; else dest->width = src2_x2 - dest->x; if (src2->y < src1->y) { temp = src1; src1 = src2; src2 = temp; } dest->y = src2->y; src1_y2 = src1->y + src1->height; src2_y2 = src2->y + src2->height; if (src2->y <= src1_y2) { return_val = TRUE; if (src1_y2 < src2_y2) dest->height = src1_y2 - dest->y; else dest->height = src2_y2 - dest->y; } } return return_val; } void gdk_dps_rectangle_enlarge_by_delta(GdkDPSRectangle * rect, gfloat dx, gfloat dy) { g_return_if_fail(rect); rect->x -= dx; rect->y -= dy; rect->width += (2 * dx); rect->height += (2 * dy); } void gdk_dps_rectangle_enlarge_by_point(GdkDPSRectangle * rect, GdkDPSPoint * point) { gfloat tmp; g_return_if_fail(rect); g_return_if_fail(point); if (gdk_dps_rectangle_contains_point(rect, point, TRUE)) return; if (rect->x > point->x) { tmp = rect->x - point->x; rect->x = point->x; rect->width += tmp; } else if (rect->x + rect->width < point->x) rect->width = point->x - rect->x; if (rect->y > point->y) { tmp = rect->y - point->y; rect->y = point->y; rect->height += tmp; } else if (rect->y + rect->height < point->y) { rect->height = point->y - rect->y; } } void gdk_dps_rectangle_enlarge_size(GdkDPSRectangle * rect, gfloat dx, gfloat dy) { g_return_if_fail(rect); rect->width += dx; rect->height += dy; } void gdk_dps_rectangle_shrink(GdkDPSRectangle * rect, gfloat dx, gfloat dy) { gdk_dps_rectangle_enlarge_by_delta(rect, -dx, -dy); } void gdk_dps_rectangle_shrink_size(GdkDPSRectangle * rect, gfloat dx, gfloat dy) { gdk_dps_rectangle_enlarge_size(rect, -dx, -dy); } /* -- implementation comes from GNUStep/base/NSGeometry.h */ void gdk_dps_rectangle_integral(GdkDPSRectangle * rect) { float tmp_x, tmp_y; #ifdef HAVE_FLOORF tmp_x = floorf(rect->x); tmp_y = floorf(rect->y); #else tmp_x = (float)floor(rect->x); tmp_y = (float)floor(rect->y); #endif /* HAVE_FLOORF */ #ifdef HAVE_CEILF rect->width = ceilf(rect->x + rect->width) - tmp_x; rect->height = ceilf(rect->y + rect->height) - tmp_y; #else rect->width = (float)ceil(rect->x + rect->width) - tmp_x; rect->height = (float)ceil(rect->y + rect->height) - tmp_y; #endif /* HAVE_CEILF */ rect->x = tmp_x; rect->y = tmp_y; } void gdk_dps_rectangle_move(GdkDPSRectangle * rect, gfloat dx, gfloat dy) { g_return_if_fail(rect); rect->x += dx; rect->y += dy; } /* Utilities */ void gdk_dps_rectangle_to_bbox(GdkDPSRectangle * rect, GdkDPSBBox * bbox) { g_return_if_fail(rect); g_return_if_fail(bbox); bbox->llx = rect->x; bbox->lly = rect->y; bbox->urx = rect->x + rect->width; bbox->ury = rect->y + rect->height; } void gdk_dps_rectangle_to_size (GdkDPSRectangle * rect, GdkDPSSize * size) { g_return_if_fail(size); g_return_if_fail(rect); size->width = rect->width; size->height = rect->height; } void gdk_dps_rectangle_message(GdkDPSRectangle * rect, gchar * message) { g_return_if_fail(rect); if (message) g_message("%s: (x, y, w, h) = (%f, %f, %f, %f)", message, rect->x, rect->y, rect->width, rect->height); else g_message("(x, y, w, h) = (%f, %f, %f, %f)", rect->x, rect->y, rect->width, rect->height); } /* * BBox */ GdkDPSBBox * gdk_dps_bbox_new(gfloat llx, gfloat lly, gfloat urx, gfloat ury) { GdkDPSBBox * bbox = g_new(GdkDPSBBox, 1); gdk_dps_bbox_set(bbox, llx, lly, urx, ury); return bbox; } void gdk_dps_bbox_init(GdkDPSBBox * bbox) { gdk_dps_bbox_set (bbox, 0.0, 0.0, 0.0, 0.0); } gboolean gdk_dps_bbox_is_empty(GdkDPSBBox * bbox) { gfloat s = ((bbox->urx - bbox->llx) * (bbox->ury - bbox->lly)); return (s == 0.0)? TRUE: FALSE; } void gdk_dps_bbox_free(GdkDPSBBox * bbox) { g_return_if_fail(bbox); g_free(bbox); } void gdk_dps_bbox_to_rectangle(GdkDPSBBox * bbox, GdkDPSRectangle * rect) { g_return_if_fail(bbox); g_return_if_fail(rect); gdk_dps_rectangle_set(rect, bbox->llx, bbox->lly, bbox->urx - bbox->llx, bbox->ury - bbox->lly); } void gdk_dps_bbox_set(GdkDPSBBox * bbox, gfloat llx, gfloat lly, gfloat urx, gfloat ury) { g_return_if_fail(bbox); bbox->llx = llx; bbox->lly = lly; bbox->urx = urx; bbox->ury = ury; } void gdk_dps_bbox_set_from_points(GdkDPSBBox * bbox, GdkDPSPoint * a, GdkDPSPoint * b) { g_return_if_fail(bbox); g_return_if_fail(a); g_return_if_fail(b); if (a->x > b->x) { bbox->llx = b->x; bbox->urx = a->x; } else { bbox->llx = a->x; bbox->urx = b->x; } if (a->y > b->y) { bbox->lly = b->y; bbox->ury = a->y; } else { bbox->lly = a->y; bbox->ury = b->y; } } void gdk_dps_bbox_set_from_rectangle(GdkDPSBBox * bbox, GdkDPSRectangle * rect) { gdk_dps_bbox_set(bbox, rect->x, rect->y, rect->x + rect->width, rect->y + rect->height); } void gdk_dps_bbox_message(GdkDPSBBox * bbox, gchar * message) { g_return_if_fail(bbox); if (message) g_message("%s: (llx, lly, urx, ury) = (%f, %f, %f, %f)", message, bbox->llx, bbox->lly, bbox->urx, bbox->ury); else g_message("(llx, lly, urx, ury) = (%f, %f, %f, %f)", bbox->llx, bbox->lly, bbox->urx, bbox->ury); } /* * Matrix */ gboolean gdk_dps_melt_in_range(int index) { if (GDK_DPS_MELT_MIN <= index && index <= GDK_DPS_MELT_MAX) return TRUE; else return FALSE; } void gdk_dps_matrix_init(GdkDPSMatrix matrix) { g_return_if_fail(matrix); matrix[GDK_DPS_MELT_A] = 1.0; matrix[GDK_DPS_MELT_B] = 0.0; matrix[GDK_DPS_MELT_C] = 0.0; matrix[GDK_DPS_MELT_D] = 1.0; matrix[GDK_DPS_MELT_TX] = 0.0; matrix[GDK_DPS_MELT_TY] = 0.0; } void gdk_dps_matrix_copy(GdkDPSMatrix src, GdkDPSMatrix dist) { gint i; g_return_if_fail(src); g_return_if_fail(dist); for (i = GDK_DPS_MELT_MIN; i <= GDK_DPS_MELT_MAX; i++) dist[i] = src[i]; } gboolean gdk_dps_matrix_equal(GdkDPSMatrix a, GdkDPSMatrix b) { g_return_val_if_fail(a, FALSE); g_return_val_if_fail(b, FALSE); if ((a[GDK_DPS_MELT_A] == b[GDK_DPS_MELT_A]) && (a[GDK_DPS_MELT_B] == b[GDK_DPS_MELT_B]) && (a[GDK_DPS_MELT_C] == b[GDK_DPS_MELT_C]) && (a[GDK_DPS_MELT_D] == b[GDK_DPS_MELT_D]) && (a[GDK_DPS_MELT_TX] == b[GDK_DPS_MELT_TX]) && (a[GDK_DPS_MELT_TY] == b[GDK_DPS_MELT_TY])) return TRUE; else return FALSE; } void gdk_dps_matrix_apply(GdkDPSMatrix matrix, GdkDPSPoint * point) { GdkDPSPoint tmp; g_return_if_fail(matrix); g_return_if_fail(point); tmp.x = matrix[GDK_DPS_MELT_A] * point->x + matrix[GDK_DPS_MELT_C] * point->y + matrix[GDK_DPS_MELT_TX]; tmp.y = matrix[GDK_DPS_MELT_B] * point->x + matrix[GDK_DPS_MELT_D] * point->y + matrix[GDK_DPS_MELT_TY]; *point = tmp; } void gdk_dps_matrix_message(GdkDPSMatrix matrix, gchar * message) { g_return_if_fail(matrix); if (message) g_message("%s: (a, b, c, d, tx, ty) = (%f, %f, %f, %f, %f, %f)", message, matrix[GDK_DPS_MELT_A], matrix[GDK_DPS_MELT_B], matrix[GDK_DPS_MELT_C], matrix[GDK_DPS_MELT_D], matrix[GDK_DPS_MELT_TX], matrix[GDK_DPS_MELT_TY]); else g_message("(a, b, c, d, tx, ty) = (%f, %f, %f, %f, %f, %f)", matrix[GDK_DPS_MELT_A], matrix[GDK_DPS_MELT_B], matrix[GDK_DPS_MELT_C], matrix[GDK_DPS_MELT_D], matrix[GDK_DPS_MELT_TX], matrix[GDK_DPS_MELT_TY]); } /* * */ /**** * Size */ GdkDPSSize * gdk_dps_size_new (gfloat width, gfloat height) { GdkDPSSize * size; g_return_val_if_fail (width >= 0.0, NULL); g_return_val_if_fail (height >= 0.0, NULL); size = g_new(GdkDPSSize, 1); gdk_dps_size_set(size, width, height); return size; } void gdk_dps_size_free (GdkDPSSize * size) { g_return_if_fail(size); g_free(size); } void gdk_dps_size_init (GdkDPSSize * size) { g_return_if_fail(size); gdk_dps_size_set(size, 0.0, 0.0); } void gdk_dps_size_set (GdkDPSSize * size, gfloat width, gfloat height) { g_return_if_fail(size); g_return_if_fail (width >= 0.0); g_return_if_fail (height >= 0.0); size->width = width; size->height = height; } gboolean gdk_dps_size_is_empty (GdkDPSSize * size) { g_return_val_if_fail(size, FALSE); return ((size->width * size->height) == 0.0)? TRUE: FALSE; } gboolean gdk_dps_size_equal (GdkDPSSize * a, GdkDPSSize * b) { g_return_val_if_fail(a, FALSE); g_return_val_if_fail(b, FALSE); if ((a->width == b->width) && (a->height == b->height)) return TRUE; else return FALSE; } void gdk_dps_size_to_rectangle (GdkDPSSize * size, GdkDPSRectangle * rect) { g_return_if_fail(size); g_return_if_fail(rect); rect->x = rect->y = 0.0; rect->width = (gfloat)size->width; rect->height = (gfloat)size->height; } void gdk_dps_size_message(GdkDPSSize * size, gchar * message) { g_return_if_fail(size); if (message) g_message("%s: (width, height) = (%f, %f)", message, size->width, size->height); else g_message("(width, height) = (%f, %f)", size->width, size->height); } /* * Segment */ #define EXPAND4_ADDRESS(p) &(p[0]), &(p[1]), &(p[2]), &(p[3]) #define EXPAND4_VALUE(p) (p[0]), (p[1]), (p[2]), (p[3]) #define FLOAT_IS_ZERO(D) ((D) == 0.0 \ || ((- 10.0 * FLT_EPSILON <= (D)) \ && ((D) <= 10.0 * FLT_EPSILON))) #define T_RANGE_CHECK(t) ((0.0 <= (t)) && ((t) <= 1.0)) static int float_compar (const void * a, const void * b); GdkDPSSegment gdk_dps_segment_by_points (GdkDPSPoint * p0, GdkDPSPoint * p1, GdkDPSPoint * p2, GdkDPSPoint * p3) { GdkDPSSegment segment = {{0.0, 0.0, 0.0, 0.0}, {0.0, 0.0, 0.0, 0.0}}; g_return_val_if_fail (p0, segment); g_return_val_if_fail (p1, segment); g_return_val_if_fail (p2, segment); g_return_val_if_fail (p3, segment); segment.a[3] = p3->x - 3 * p2->x + 3 * p1->x- p0->x; segment.a[2] = 3 * (p2->x - 2 * p1->x + p0->x); segment.a[1] = 3 * (p1->x - p0->x); segment.a[0] = p0->x; segment.b[3] = p3->y - (3 * p2->y) + (3 * p1->y) - p0->y; segment.b[2] = 3 * (p2->y - 2 * p1->y + p0->y); segment.b[1] = 3 * (p1->y - p0->y); segment.b[0] = p0->y; return segment; } GdkDPSPoint gdk_dps_segment_get_point (GdkDPSSegment * segment, float t) { GdkDPSPoint p = {0.0, 0.0}; float ttt; float tt; g_return_val_if_fail (segment, p); g_return_val_if_fail (T_RANGE_CHECK(t), p); ttt = t * t * t; tt = t * t; p.x = segment->a[3] * ttt + segment->a[2] * tt + segment->a[1] * t + segment->a[0]; p.y = segment->b[3] * ttt + segment->b[2] * tt + segment->b[1] * t + segment->b[0]; return p; } void gdk_dps_segment_get_control_points (GdkDPSSegment * segment, GdkDPSPoint * p0, GdkDPSPoint * p1, GdkDPSPoint * p2, GdkDPSPoint * p3) { g_return_if_fail(segment); g_return_if_fail(p0); g_return_if_fail(p1); g_return_if_fail(p2); g_return_if_fail(p3); p0->x = segment->a[0]; p0->y = segment->b[0]; p1->x = p0->x + segment->a[1]/3.0; p1->y = p0->y + segment->b[1]/3.0; p2->x = p1->x + (segment->a[2] + segment->a[1])/3.0; p2->y = p1->y + (segment->b[2] + segment->b[1])/3.0; p3->x = segment->a[3] + segment->a[2] + segment->a[1] + p0->x; p3->y = segment->b[3] + segment->b[2] + segment->b[1] + p0->y; } void gdk_dps_segment_message(GdkDPSSegment * segment, gchar * message) { g_return_if_fail (segment); if (message) g_message("%s: a(3:%f 2:%f 1:%f 0:%f), b(3:%f 2:%f 1:%f 0:%f)", message, segment->a[3], segment->a[2], segment->a[1], segment->a[0], segment->b[3], segment->b[2], segment->b[1], segment->b[0]); else g_message("a(3:%f 2:%f 1:%f 0:%f), b(3:%f 2:%f 1:%f 0:%f)", segment->a[3], segment->a[2], segment->a[1], segment->a[0], segment->b[3], segment->b[2], segment->b[1], segment->b[0]); } void gdk_dps_segment_split (GdkDPSSegment * base_segment, gfloat t, GdkDPSSegment * sub_segment0, GdkDPSSegment * sub_segment1) { g_return_if_fail (base_segment); g_return_if_fail (T_RANGE_CHECK(t)); g_return_if_fail (sub_segment0); g_return_if_fail (sub_segment1); /* This implementation is inefficient. 1. Calculate control points for SEGMENT from SEGMENT 2. Calculate control points for SUB_SEGMENT0 and SUB_SEGMENT1 3. Calculate SUB_SEGMENT0 and SUB_SEGMENT1 from the control points calculated at step 2. TODO: We should calculate SUB_SEGMENT0 and SUB_SEGMENT1 directly from SEGMENT. */ { float t0 = 1.0 - t; float t1 = t; GdkDPSPoint base_points[4]; GdkDPSPoint sub_points0[4]; GdkDPSPoint sub_points1[4]; GdkDPSPoint tmp_p11; /* STEP1 */ gdk_dps_segment_get_control_points (base_segment, EXPAND4_ADDRESS(base_points)); /* STEP2 */ sub_points0[0] = base_points[0]; sub_points0[1].x = t0 * base_points[0].x + t1 * base_points[1].x; sub_points0[1].y = t0 * base_points[0].y + t1 * base_points[1].y; tmp_p11.x = t0 * base_points[1].x + t1 * base_points[2].x; tmp_p11.y = t0 * base_points[1].y + t1 * base_points[2].y; sub_points0[2].x = t0 * sub_points0[0].x + t1 * tmp_p11.x; sub_points0[2].y = t0 * sub_points0[0].y + t1 * tmp_p11.y; sub_points0[3] = gdk_dps_segment_get_point (base_segment, t); sub_points1[3] = base_points[3]; sub_points1[2].x = t0 * base_points[2].x + t1 * base_points[3].x; sub_points1[2].y = t0 * base_points[2].y + t1 * base_points[3].y; sub_points1[1].x = t0 * tmp_p11.x * t1 * sub_points1[2].x; sub_points1[1].y = t0 * tmp_p11.y * t1 * sub_points1[2].y; sub_points1[0] = sub_points0[3]; /* STEP3 */ *sub_segment0 = gdk_dps_segment_by_points (EXPAND4_ADDRESS(sub_points0)); *sub_segment1 = gdk_dps_segment_by_points (EXPAND4_ADDRESS(sub_points1)); } } void gdk_dps_segment_reverse (GdkDPSSegment * segment) { g_return_if_fail (segment); #define SWAP(A, B) { \ float tmp = A; \ A = B; \ B = tmp; \ } SWAP(segment->a[0], segment->a[3]); SWAP(segment->a[1], segment->a[2]); SWAP(segment->b[0], segment->b[3]); SWAP(segment->b[1], segment->b[2]); #undef SWAP } /* MMT */ static int gdk_dps_segment_get_mmt_x (GdkDPSSegment * segment, float * t0, float * t1); static int gdk_dps_segment_get_mmt_y (GdkDPSSegment * segment, float * t0, float * t1); static int gdk_dps_segment_get_mmt_raw (float a0, float a1, float a2, float a3, float * t0, float * t1); int gdk_dps_segment_get_mmt (GdkDPSSegment * segment, float * t0, float * t1, float * t2, float * t3) { float t[4]; int n, nx, ny; int i; g_return_val_if_fail (segment, 0); g_return_val_if_fail (t0, 0); g_return_val_if_fail (t1, 0); g_return_val_if_fail (t2, 0); g_return_val_if_fail (t3, 0); nx = gdk_dps_segment_get_mmt_x (segment, &t[0], &t[1]); g_return_val_if_fail (nx != -1, 0); ny = gdk_dps_segment_get_mmt_y (segment, &t[nx], &t[nx+1]); g_return_val_if_fail (ny != -1, 0); n = nx + ny; qsort (t, n, sizeof (float), float_compar); for (i = 0; i < (n - 1); i++) { if (t[i] == t[i+1]) { g_memmove (&(t[i+1]), &(t[i+2]), sizeof(float)* (n - (i+2))); n--; } } switch (n) { case 4: *t3 = t[3]; case 3: *t2 = t[2]; case 2: *t1 = t[1]; case 1: *t0 = t[0]; case 0: break; default: g_assert_not_reached(); } return n; } static int gdk_dps_segment_get_mmt_x (GdkDPSSegment * segment, float * t0, float * t1) { return gdk_dps_segment_get_mmt_raw (EXPAND4_VALUE(segment->a), t0, t1); } static int gdk_dps_segment_get_mmt_y (GdkDPSSegment * segment, float * t0, float * t1) { return gdk_dps_segment_get_mmt_raw (EXPAND4_VALUE(segment->b), t0, t1); } static int gdk_dps_segment_get_mmt_raw (float a0, float a1, float a2, float a3, float * t0, float * t1) { float D; int result; g_return_val_if_fail (t0, 0); g_return_val_if_fail (t1, 0); /* x(t) = a3*t^3 + a2*t^2 + a1*t + a0 x'(t) = 3*a3*t^2 + 2*a2*t + a1 */ if (FLOAT_IS_ZERO(a3)) { if (FLOAT_IS_ZERO(a2)) { /* x(t) = a1 * t + a0 x'(t) = a1 */ if (FLOAT_IS_ZERO(a1)) return -1; else return 0; } else { *t0 = *t1 = -a1 / (2.0 * a2); return 1; } } /* Here after a3 != 0 */ D = (a2)*(a2) - 3 * (a1) * (a3); if (FLOAT_IS_ZERO(D)) { *t0 = *t1 = - a2 / (3 * a3); if (T_RANGE_CHECK(*t0)) result = 1; else result = 0; } else if (D < 0.0) result = 0; else /* D > 0.0 */ { float d = sqrtf (D); result = 0; *t0 = (- a2 - d)/ (3 * a3); *t1 = (- a2 + d)/ (3 * a3); if (T_RANGE_CHECK(*t0)) result++; else *t0 = * t1; if (T_RANGE_CHECK(*t1)) result++; } return result; } /* gdk_dps_segment_intersect --- find cross point */ typedef struct { float t[2]; /* Range */ GdkDPSRectangle rect; GdkDPSSegment * root_segment; } sub_segment_t; typedef struct { float t; float s; } segment_intersection_t; static void sub_segment_init (sub_segment_t * sub_segment, float t0, float t1, GdkDPSSegment * root_segment); static GList * sub_segment_intersect (sub_segment_t * sub_segment0, sub_segment_t * sub_segment1); static GList * sub_segment_intersect_sub (sub_segment_t * s0, sub_segment_t * s1); static sub_segment_t sub_segment_derive (sub_segment_t * parent ,float t0, float t1); static gboolean sub_segment_split (sub_segment_t * parent, sub_segment_t * s0, sub_segment_t * s1); static segment_intersection_t * sub_segment_intersect_approximate (sub_segment_t * s0, sub_segment_t * s1); GdkDPSRectangle gdk_dps_segment_get_rectangle (GdkDPSSegment * segment) { GdkDPSPoint control_points[4]; GdkDPSRectangle rect = {0.0, 0.0, 0.0, 0.0}; g_return_val_if_fail (segment, rect); gdk_dps_segment_get_control_points(segment, EXPAND4_ADDRESS(control_points)); gdk_dps_rectangle_set_from_points (&rect, &control_points[0], &control_points[1]); gdk_dps_rectangle_enlarge_by_point (&rect, &control_points[2]); gdk_dps_rectangle_enlarge_by_point (&rect, &control_points[3]); return rect; } GList * gdk_dps_segment_intersect (GdkDPSSegment * segment0, GdkDPSSegment * segment1) { GList * tmp; sub_segment_t sub_segment0, sub_segment1; float t0, t1, s0, s1, t, s; GList * remove; GList * head; g_return_val_if_fail (segment0, NULL); g_return_val_if_fail (segment1, NULL); sub_segment_init(&sub_segment0, 0.0, 1.0, segment0); sub_segment_init(&sub_segment1, 0.0, 1.0, segment1); tmp = sub_segment_intersect (&sub_segment0, &sub_segment1); /* Remove same parameters in the list */ head = tmp; while (tmp && tmp->next) { t0 = (((float *)tmp->data)[0]); t1 = (((float *)tmp->next->data)[0]); s0 = (((float *)tmp->data)[1]); s1 = (((float *)tmp->next->data)[1]); t = (t1-t0); s = (s1-s0); if (FLOAT_IS_ZERO(t) || FLOAT_IS_ZERO(s)) { remove = tmp->next; tmp = g_list_remove_link (tmp, remove); g_free(remove->data); g_list_free (remove); remove = NULL; } else { tmp = tmp->next; if (!tmp) break; } } tmp = head; return tmp; } static void sub_segment_init (sub_segment_t * sub_segment, float t0, float t1, GdkDPSSegment * root_segment) { g_return_if_fail (sub_segment); g_return_if_fail (root_segment); g_return_if_fail (T_RANGE_CHECK(t0)); g_return_if_fail (T_RANGE_CHECK(t1)); g_return_if_fail (t0 <= t1); sub_segment->t[0] = t0; sub_segment->t[1] = t1; sub_segment->root_segment = root_segment; if (t0 == 0.0 && t1 == 1.0) gdk_dps_rectangle_set_from_segment (&sub_segment->rect, root_segment); else { GdkDPSPoint p0 = gdk_dps_segment_get_point (root_segment, t0); GdkDPSPoint p1 = gdk_dps_segment_get_point (root_segment, t1); gdk_dps_rectangle_set_from_points (&sub_segment->rect, &p0, &p1); } } static GList * sub_segment_intersect (sub_segment_t * sub_segment0, sub_segment_t * sub_segment1) { GList * result = NULL; GList * tmp; GdkDPSRectangle rect_dumy; int i, j; float t0, t1; sub_segment_t * sub_segment[2]; float t[2][4]; int n[2]; sub_segment_t s[2][5]; if (FALSE == gdk_dps_rectangle_border (&(sub_segment0->rect), &(sub_segment1->rect), &rect_dumy)) { if (gdk_dps_debug_flags & GDK_DPS_DEBUG_INTERSECT) { g_message ("Fail in root segemnt rect\n"); gdk_dps_rectangle_message (&(sub_segment0->rect), NULL); gdk_dps_rectangle_message (&(sub_segment1->rect), NULL); } return NULL; } sub_segment[0] = sub_segment0; sub_segment[1] = sub_segment1; for (i = 0; i < 2; i++) { n[i] = gdk_dps_segment_get_mmt (sub_segment[i]->root_segment, EXPAND4_ADDRESS(t[i])); if (n[i] == 0) { n[i] = 1; t[i][0] = 0.5; } } for (i = 0; i < 2; i++) { for (j = 0; j <= n[i]; j++) { if (j == 0) t0 = 0.0, t1 = t[i][j]; else if (j == n[i]) t0 = t[i][j-1], t1 = 1.0; else t0 = t[i][j-1], t1 = t[i][j]; s[i][j] = sub_segment_derive (sub_segment[i], t0, t1); } } for (i = 0; i <= n[0]; i++) for (j = 0; j <= n[1]; j++) { if (gdk_dps_debug_flags & GDK_DPS_DEBUG_INTERSECT) g_message ("Root split begin %d:%d", i, j); tmp = sub_segment_intersect_sub (&s[0][i], &s[1][j]); if (tmp) result = g_list_concat (result, tmp); if (gdk_dps_debug_flags & GDK_DPS_DEBUG_INTERSECT) g_message ("Root split end %d:%d", i, j); } return result; } static GList * sub_segment_intersect_sub (sub_segment_t * s0, sub_segment_t * s1) { GList * result = NULL; GList * tmp = NULL; gboolean borderp, intersectp; sub_segment_t s[2][2]; int i, j; borderp = gdk_dps_rectangle_border (&(s0->rect), &(s1->rect), NULL); intersectp = gdk_dps_rectangle_intersect (&(s0->rect), &(s1->rect), NULL); if (FALSE == borderp) return NULL; if (TRUE == borderp && FALSE == intersectp) if (gdk_dps_debug_flags & GDK_DPS_DEBUG_INTERSECT) g_message ("Border: %d Intersct: %d", borderp, intersectp); if (gdk_dps_debug_flags & GDK_DPS_DEBUG_INTERSECT) g_message ("Sub split begin"); if (FALSE == sub_segment_split (s0, &s[0][0], &s[0][1])) { if (FALSE == sub_segment_split (s1, &s[1][0], &s[1][1])) { segment_intersection_t * intersection; intersection = sub_segment_intersect_approximate (s0, s1); if (intersection) { result = g_list_append (result, (gpointer)intersection); if (gdk_dps_debug_flags & GDK_DPS_DEBUG_INTERSECT) { g_message ("Border: %d Intersct: %d", borderp, intersectp); g_message ("Found t->%f, s->%f", intersection->t, intersection->s); } } } else { for (i = 0; i < 2; i++) { tmp = sub_segment_intersect_sub (s0, &s[1][i]); if (tmp) result = g_list_concat (result, tmp); } } } else if (FALSE == sub_segment_split (s1, &s[1][0], &s[1][1])) { for (i = 0; i < 2; i++) { tmp = sub_segment_intersect_sub (&s[0][i], s1); if (tmp) result = g_list_concat (result, tmp); } } else { for (i = 0; i < 2; i++) for (j = 0; j < 2; j++) { tmp = sub_segment_intersect_sub (&s[0][i], &s[1][j]); if (tmp) result = g_list_concat (result, tmp); } } if (gdk_dps_debug_flags & GDK_DPS_DEBUG_INTERSECT) g_message ("Sub split end"); return result; } static segment_intersection_t * sub_segment_intersect_approximate (sub_segment_t * s0, sub_segment_t * s1) { segment_intersection_t * intersection = NULL; GdkDPSPoint p[2][2]; float intersection_y, intersection_x; float d0y, d1y; float d0x, d1x; float a0, b0; float a1, b1; int i, j; sub_segment_t * s[2]; g_return_val_if_fail (s0, NULL); g_return_val_if_fail (s1, NULL); s[0] = s0; s[1] = s1; for (i = 0; i < 2; i++) for (j = 0; j < 2; j++) p[i][j] = gdk_dps_segment_get_point (s[i]->root_segment, s[i]->t[j]); d0y = (p[0][0].y - p[0][1].y); d1y = (p[1][0].y - p[1][1].y); d0x = (p[0][0].x - p[0][1].x); d1x = (p[1][0].x - p[1][1].x); if ((!FLOAT_IS_ZERO(d0y)) && (!FLOAT_IS_ZERO(d1y))) { a0 = d0x/d0y; b0 = p[0][1].y - (a0 * p[0][1].x); a1 = d1x/d1y; b1 = p[1][1].y - (a1 * p[1][1].x); if (FLOAT_IS_ZERO(a1 - a0)) { if (gdk_dps_debug_flags & GDK_DPS_DEBUG_INTERSECT) g_message ("Zero: a1 - a0"); return NULL; } intersection_y = (b0 * a1- b1 * a0)/(a1 - a0); intersection = g_new (segment_intersection_t, 1); intersection->t = ((s[0]->t[1] - s[0]->t[0]) * (intersection_y - p[0][0].y)) / (-d0y) + s[0]->t[0]; intersection->s = ((s[1]->t[1] - s[1]->t[0]) * (intersection_y - p[1][0].y)) / (-d1y) + s[1]->t[0]; g_return_val_if_fail (T_RANGE_CHECK(intersection->s), NULL); g_return_val_if_fail (T_RANGE_CHECK(intersection->t), NULL); } else if ((!FLOAT_IS_ZERO(d0x)) && (!FLOAT_IS_ZERO(d1x))) { a0 = d0y/d0x; b0 = p[0][1].x - (a0 * p[0][1].y); a1 = d1y/d1x; b1 = p[1][1].x - (a1 * p[1][1].y); intersection_x = (b0 * a1- b1 * a0)/(a1 - a0); if (FLOAT_IS_ZERO(a1 - a0)) { if (gdk_dps_debug_flags & GDK_DPS_DEBUG_INTERSECT) g_message ("Zero: a1 - a0"); return NULL; } intersection = g_new (segment_intersection_t, 1); intersection->t = ((s[0]->t[1] - s[0]->t[0]) * (intersection_x - p[0][0].x)) / (-d0x) + s[0]->t[0]; intersection->s = ((s[1]->t[1] - s[1]->t[0]) * (intersection_x - p[1][0].x)) / (-d1x) + s[1]->t[0]; g_return_val_if_fail (T_RANGE_CHECK(intersection->s), NULL); g_return_val_if_fail (T_RANGE_CHECK(intersection->t), NULL); } else if (!FLOAT_IS_ZERO(d0y)) { /* d1y == 0.0 */ intersection_y = p[1][0].y; intersection = g_new (segment_intersection_t, 1); intersection->t = ((s[0]->t[1] - s[0]->t[0]) * (intersection_y - p[0][0].y)) / (-d0y) + s[0]->t[0]; if (!FLOAT_IS_ZERO(d0x)) { /* d1x == 0.0 */ intersection_x = p[1][1].x; intersection->s = s[1]->t[0] + ((s[1]->t[1] - s[1]->t[0])/2.0); } else if (!FLOAT_IS_ZERO(d1x)) { /* d0x == 0.0 */ intersection_x = p[0][0].x; intersection->s = ((s[1]->t[1] - s[1]->t[0]) * (intersection_x - p[1][0].x)) / (-d1x) + s[1]->t[0]; } else { /* d1x == d0x == 0.0 */ intersection->s = s[1]->t[0] + ((s[1]->t[1] - s[1]->t[0])/2.0); } } else if (!FLOAT_IS_ZERO(d1y)) { /* d0y == 0.0 */ intersection_y = p[0][0].y; intersection = g_new (segment_intersection_t, 1); intersection->s = ((s[1]->t[1] - s[1]->t[0]) * (intersection_y - p[1][0].y)) / (-d1y) + s[1]->t[0]; if (!FLOAT_IS_ZERO(d0x)) { /* d1x == 0 */ intersection_x = p[1][1].x; intersection->t = ((s[0]->t[1] - s[0]->t[0]) * (intersection_x - p[0][0].x)) / (-d0x) + s[0]->t[0]; } else if (!FLOAT_IS_ZERO(d1x)) { /* d0x == 0 */ intersection_x = p[0][0].x; intersection->t = s[0]->t[0] + (s[0]->t[1] - s[0]->t[0])/2.0; } else { /* d0x == d1x == 0 */ intersection->s = s[1]->t[0] + ((s[1]->t[1] - s[1]->t[0])/2.0); } } else if (!FLOAT_IS_ZERO(d0x)) { /* d1x == 0.0 */ intersection_x = p[1][0].x; intersection = g_new (segment_intersection_t, 1); intersection->t = ((s[0]->t[1] - s[0]->t[0]) * (intersection_x - p[0][0].x)) / (-d0x) + s[0]->t[0]; if (!FLOAT_IS_ZERO(d0y)) { /* d1y == 0 */ intersection_y = p[1][0].y; intersection->s = s[1]->t[0] + ((s[1]->t[1] - s[1]->t[0])/2.0); } else if (!FLOAT_IS_ZERO(d1y)) { /* d0y == 0 */ intersection_y = p[0][0].y; intersection->s = ((s[1]->t[1] - s[1]->t[0]) * (intersection_y - p[1][0].y)) / (-d1y) + s[1]->t[0]; } else { /* d0x == d1x == 0 */ intersection->s = s[1]->t[0] + ((s[1]->t[1] - s[1]->t[0])/2.0); } } else if (!FLOAT_IS_ZERO(d1x)) { /* d0x == 0.0 */ intersection_x = p[0][0].x; intersection = g_new (segment_intersection_t, 1); intersection->s = ((s[1]->t[1] - s[1]->t[0]) * (intersection_x - p[1][0].x)) / (-d1x) + s[1]->t[0]; if (!FLOAT_IS_ZERO(d0y)) { /* d1y == 0 */ intersection_y = p[1][0].y; intersection->t = ((s[0]->t[1] - s[0]->t[0]) * (intersection_y - p[0][0].y)) / (-d0y) + s[0]->t[0]; } else if (!FLOAT_IS_ZERO(d1y)) { /* d0y == 0 */ intersection_y = p[0][0].y; intersection->t = s[0]->t[0] + (s[0]->t[1] - s[0]->t[0])/2.0; } else { /* d0y == 0 && d1y == 0 */ intersection->t = s[0]->t[0] + (s[0]->t[1] - s[0]->t[0])/2.0; } } else { intersection = g_new (segment_intersection_t, 1); intersection->s = s[1]->t[0] + ((s[1]->t[1] - s[1]->t[0])/2.0); intersection->t = s[0]->t[0] + (s[0]->t[1] - s[0]->t[0])/2.0; } return intersection; } static sub_segment_t sub_segment_derive (sub_segment_t * parent, float t0, float t1) { sub_segment_t child; g_return_val_if_fail (T_RANGE_CHECK(t0), child); g_return_val_if_fail (T_RANGE_CHECK(t1), child); g_return_val_if_fail (t0 <= t1, child); g_return_val_if_fail (parent, child); sub_segment_init (&child, t0, t1, parent->root_segment); return child; } /* sub_segment_split --- Split PARENT into S0 and S1. Return TRUE if it is successful to split PARENT. Return FALSE it the PARENT is too small to split. */ static gboolean sub_segment_split (sub_segment_t * parent, sub_segment_t * s0, sub_segment_t * s1) { float t0, t1, t2, t1_0, t1_1; g_return_val_if_fail (parent, FALSE); g_return_val_if_fail (s0, FALSE); g_return_val_if_fail (s1, FALSE); t0 = parent->t[0]; t2 = parent->t[1]; t1 = (t2 - t0); if (t1 <= FLT_EPSILON) return FALSE; /* Cannot split anymore */ else { t1 /= 2.0; if (t1 < FLT_EPSILON) return FALSE; /* Cannot split anymore */ } t1 += t0; t1_0 = t1; t1_1 = t1; *s0 = sub_segment_derive(parent, t0, t1_0); *s1 = sub_segment_derive(parent, t1_1, t2); return TRUE; } static int float_compar (const void * a, const void * b) { float A, B; A = *(float *)a; B = *(float *)b; if (A < B) return -1; else if (A == B) return 0; else return 1; }