/* Simple box operations */ /* * Copyright (C) 2005 Elijah Newren * [According to the ChangeLog, Anders, Havoc, and Rob were responsible * for the meta_rectangle_intersect() and meta_rectangle_equal() * functions that I copied from display.c] * Copyright (C) 2002 Anders Carlsson * Copyright (C) 2002 Red Hat, Inc. * Copyright (C) 2003 Rob Adams * * 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 2 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, write to the Free Software * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA * 02111-1307, USA. */ #include "boxes.h" #include "util.h" #include // Just for the definition of the various gravities #include // For snprintf /* PRINT_DEBUG may be useful to define when compiling the testboxes program if * any issues crop up. */ /* #define PRINT_DEBUG */ char* meta_rectangle_to_string (const MetaRectangle *rect, char *output) { /* 25 = 2 commas, space, plus, trailing \0 + 5 for each digit. * Should be more than enough space. Note that of this space, the * trailing \0 will be overwritten for all but the last rectangle. */ snprintf (output, 25, "%d,%d +%d,%d", rect->x, rect->y, rect->width, rect->height); return output; } char* meta_rectangle_region_to_string (GList *region, const char *separator_string, char *output) { /* 27 = 2 commas, 2 square brackets, space, plus, trailing \0 + 5 for * each digit. Should be more than enough space. Note that of this * space, the trailing \0 will be overwritten for all but the last * rectangle. */ char rect_string[27]; char *cur = output; GList *tmp = region; while (tmp) { MetaRectangle *rect = tmp->data; snprintf (rect_string, 27, "[%d,%d +%d,%d]", rect->x, rect->y, rect->width, rect->height); cur = g_stpcpy (cur, rect_string); tmp = tmp->next; if (tmp) cur = g_stpcpy (cur, separator_string); } return output; } int meta_rectangle_area (const MetaRectangle *rect) { g_return_val_if_fail (rect != NULL, 0); return rect->width * rect->height; } gboolean meta_rectangle_intersect (const MetaRectangle *src1, const MetaRectangle *src2, MetaRectangle *dest) { int dest_x, dest_y; int dest_w, dest_h; int return_val; g_return_val_if_fail (src1 != NULL, FALSE); g_return_val_if_fail (src2 != NULL, FALSE); g_return_val_if_fail (dest != NULL, FALSE); return_val = FALSE; dest_x = MAX (src1->x, src2->x); dest_y = MAX (src1->y, src2->y); dest_w = MIN (src1->x + src1->width, src2->x + src2->width) - dest_x; dest_h = MIN (src1->y + src1->height, src2->y + src2->height) - dest_y; if (dest_w > 0 && dest_h > 0) { dest->x = dest_x; dest->y = dest_y; dest->width = dest_w; dest->height = dest_h; return_val = TRUE; } else { dest->width = 0; dest->height = 0; } return return_val; } gboolean meta_rectangle_equal (const MetaRectangle *src1, const MetaRectangle *src2) { return ((src1->x == src2->x) && (src1->y == src2->y) && (src1->width == src2->width) && (src1->height == src2->height)); } gboolean meta_rectangle_overlap (const MetaRectangle *rect1, const MetaRectangle *rect2) { g_return_val_if_fail (rect1 != NULL, FALSE); g_return_val_if_fail (rect2 != NULL, FALSE); return !((rect1->x + rect1->width <= rect2->x) || (rect2->x + rect2->width <= rect1->x) || (rect1->y + rect1->height <= rect2->y) || (rect2->y + rect2->height <= rect1->y)); } gboolean meta_rectangle_vert_overlap (const MetaRectangle *rect1, const MetaRectangle *rect2) { return (rect1->y < rect2->y + rect2->height && rect2->y < rect1->y + rect1->height); } gboolean meta_rectangle_horiz_overlap (const MetaRectangle *rect1, const MetaRectangle *rect2) { return (rect1->x < rect2->x + rect2->width && rect2->x < rect1->x + rect1->width); } gboolean meta_rectangle_could_fit_rect (const MetaRectangle *outer_rect, const MetaRectangle *inner_rect) { return (outer_rect->width >= inner_rect->width && outer_rect->height >= inner_rect->height); } gboolean meta_rectangle_contains_rect (const MetaRectangle *outer_rect, const MetaRectangle *inner_rect) { return inner_rect->x >= outer_rect->x && inner_rect->y >= outer_rect->y && inner_rect->x + inner_rect->width <= outer_rect->x + outer_rect->width && inner_rect->y + inner_rect->height <= outer_rect->y + outer_rect->height; } void meta_rectangle_resize_with_gravity (const MetaRectangle *old_rect, MetaRectangle *rect, int gravity, int new_width, int new_height) { /* FIXME: I'm too deep into this to know whether the below comment is * still clear or not now that I've moved it out of constraints.c. * boxes.h has a good comment, but I'm not sure if the below info is also * helpful on top of that (or whether it has superfluous info). */ /* These formulas may look overly simplistic at first but you can work * everything out with a left_frame_with, right_frame_width, * border_width, and old and new client area widths (instead of old total * width and new total width) and you come up with the same formulas. * * Also, note that the reason we can treat NorthWestGravity and * StaticGravity the same is because we're not given a location at * which to place the window--the window was already placed * appropriately before. So, NorthWestGravity for this function * means to just leave the upper left corner of the outer window * where it already is, and StaticGravity for this function means to * just leave the upper left corner of the inner window where it * already is. But leaving either of those two corners where they * already are will ensure that the other corner is fixed as well * (since frame size doesn't change)--thus making the two * equivalent. */ /* First, the x direction */ int adjust = 0; switch (gravity) { case NorthWestGravity: case WestGravity: case SouthWestGravity: /* No need to modify rect->x */ break; case NorthGravity: case CenterGravity: case SouthGravity: /* FIXME: Needing to adjust new_width kind of sucks, but not doing so * would cause drift. */ new_width -= (old_rect->width - new_width) % 2; rect->x = old_rect->x + (old_rect->width - new_width)/2; break; case NorthEastGravity: case EastGravity: case SouthEastGravity: rect->x = old_rect->x + (old_rect->width - new_width); break; case StaticGravity: default: /* No need to modify rect->x */ break; } rect->width = new_width; /* Next, the y direction */ adjust = 0; switch (gravity) { case NorthWestGravity: case NorthGravity: case NorthEastGravity: /* No need to modify rect->y */ break; case WestGravity: case CenterGravity: case EastGravity: /* FIXME: Needing to adjust new_height kind of sucks, but not doing so * would cause drift. */ new_height -= (old_rect->height - new_height) % 2; rect->y = old_rect->y + (old_rect->height - new_height)/2; break; case SouthWestGravity: case SouthGravity: case SouthEastGravity: rect->y = old_rect->y + (old_rect->height - new_height); break; case StaticGravity: default: /* No need to modify rect->y */ break; } rect->height = new_height; } /* Not so simple helper function for get_minimal_spanning_set_for_region() */ static GList* merge_spanning_rects_in_region (GList *region) { /* NOTE FOR ANY OPTIMIZATION PEOPLE OUT THERE: Please see the * documentation of get_minimal_spanning_set_for_region() for performance * considerations that also apply to this function. */ GList* compare; #ifdef PRINT_DEBUG int num_contains, num_merged, num_part_contains, num_adjacent; num_contains = num_merged = num_part_contains = num_adjacent = 0; #endif compare = region; g_assert (region); #ifdef PRINT_DEBUG char spanning_region[1 + 28 * g_list_length (region)]; char rect1_string[25]; char rect2_string[25]; printf ("Merging stats:\n"); printf (" Length of initial list: %d\n", g_list_length (region)); printf (" Initial rectangles: %s\n", meta_rectangle_region_to_string (region, ", ", spanning_region)); #endif while (compare && compare->next) { MetaRectangle *a = compare->data; GList *other = compare->next; g_assert (a->width > 0 && a->height > 0); while (other) { MetaRectangle *b = other->data; GList *delete_me = NULL; g_assert (b->width > 0 && b->height > 0); #ifdef PRINT_DEBUG printf (" -- Comparing %s to %s --\n", meta_rectangle_to_string (a, rect1_string), meta_rectangle_to_string (b, rect2_string)); #endif /* If a contains b, just remove b */ if (meta_rectangle_contains_rect (a, b)) { delete_me = other; #ifdef PRINT_DEBUG num_contains++; num_merged++; #endif } /* If b contains a, just remove a */ else if (meta_rectangle_contains_rect (a, b)) { delete_me = compare; #ifdef PRINT_DEBUG num_contains++; num_merged++; #endif } /* If a and b might be mergeable horizontally */ else if (a->y == b->y && a->height == b->height) { /* If a and b overlap */ if (meta_rectangle_overlap (a, b)) { int new_x = MIN (a->x, b->x); a->width = MAX (a->x + a->width, b->x + b->width) - new_x; a->x = new_x; delete_me = other; #ifdef PRINT_DEBUG num_part_contains++; num_merged++; #endif } /* If a and b are adjacent */ else if (a->x + a->width == b->x || a->x == b->x + b->width) { int new_x = MIN (a->x, b->x); a->width = MAX (a->x + a->width, b->x + b->width) - new_x; a->x = new_x; delete_me = other; #ifdef PRINT_DEBUG num_adjacent++; num_merged++; #endif } } /* If a and b might be mergeable vertically */ else if (a->x == b->x && a->width == b->width) { /* If a and b overlap */ if (meta_rectangle_overlap (a, b)) { int new_y = MIN (a->y, b->y); a->height = MAX (a->y + a->height, b->y + b->height) - new_y; a->y = new_y; delete_me = other; #ifdef PRINT_DEBUG num_part_contains++; num_merged++; #endif } /* If a and b are adjacent */ else if (a->y + a->height == b->y || a->y == b->y + b->height) { int new_y = MIN (a->y, b->y); a->height = MAX (a->y + a->height, b->y + b->height) - new_y; a->y = new_y; delete_me = other; #ifdef PRINT_DEBUG num_adjacent++; num_merged++; #endif } } other = other->next; /* Delete any rectangle in the list that is no longer wanted */ if (delete_me != NULL) { #ifdef PRINT_DEBUG MetaRectangle *bla = delete_me->data; printf (" Deleting rect %s\n", meta_rectangle_to_string (bla, rect1_string)); #endif /* Deleting the rect we compare others to is a little tricker */ if (compare == delete_me) { compare = compare->next; other = compare->next; a = compare->data; } /* Okay, we can free it now */ g_free (delete_me->data); region = g_list_delete_link (region, delete_me); } #ifdef PRINT_DEBUG char new_list[1 + 28 * g_list_length (region)]; printf (" After comparison, new list is: %s\n", meta_rectangle_region_to_string (region, ", ", new_list)); #endif } compare = compare->next; } #ifdef PRINT_DEBUG /* Note that I believe it will be the case that num_part_contains and * num_adjacent will alwyas be 0 while num_contains will be equal to * num_merged. If so, this might be useful information to use to come up * with some kind of optimization for this funcation, given that there * exists someone who really wants to do that. */ char final_list[1 + 28 * g_list_length (region)]; printf (" Num rectangles contained in others : %d\n", num_contains); printf (" Num rectangles partially contained in others: %d\n", num_part_contains); printf (" Num rectangles adjacent to others : %d\n", num_adjacent); printf (" Num rectangles merged with others : %d\n", num_merged); printf (" Final rectangles: %s\n", meta_rectangle_region_to_string (region, ", ", final_list)); #endif return region; } /* Simple helper function for get_minimal_spanning_set_for_region()... */ static gint compare_rect_areas (gconstpointer a, gconstpointer b) { const MetaRectangle *a_rect = (gconstpointer) a; const MetaRectangle *b_rect = (gconstpointer) b; int a_area = meta_rectangle_area (a_rect); int b_area = meta_rectangle_area (b_rect); return b_area - a_area; /* positive ret value denotes b > a, ... */ } /* This function is trying to find a "minimal spanning set (of rectangles)" * for a given region. * * The region is given by taking basic_rect, then removing the areas * covered by all the rectangles in the all_struts list, and then expanding * the resulting region by the given number of pixels in each direction. * * A "minimal spanning set (of rectangles)" is the best name I could come * up with for the concept I had in mind. Basically, for a given region, I * want a set of rectangles with the property that a window is contained in * the region if and only if it is contained within at least one of the * rectangles. * * The GList* returned will be a list of (allocated) MetaRectangles. * The list will need to be freed by calling * meta_rectangle_free_spanning_set() on it (or by manually * implementing that function...) */ GList* meta_rectangle_get_minimal_spanning_set_for_region ( const MetaRectangle *basic_rect, const GSList *all_struts, const int left_expand, const int right_expand, const int top_expand, const int bottom_expand) { /* NOTE FOR OPTIMIZERS: This function *might* be somewhat slow, * especially due to the call to merge_spanning_rects_in_region() (which * is O(n^2) where n is the size of the list generated in this function). * This is made more onerous due to the fact that it involves a fair * number of memory allocation and deallocation calls. However, n is 1 * for default installations of Gnome (because partial struts aren't used * by default and only partial struts increase the size of the spanning * set generated). With one partial strut, n will be 2 or 3. With 2 * partial struts, n will probably be 4 or 5. So, n probably isn't large * enough to make this worth bothering. If it ever does show up on * profiles (most likely because people start using large numbers of * partial struts), possible optimizations include: * * (1) rewrite merge_spanning_rects_in_region() to be O(n) or O(nlogn). * I'm not totally sure it's possible, but with a couple copies of * the list and sorting them appropriately, I believe it might be. * (2) only call merge_spanning_rects_in_region() with a subset of the * full list of rectangles. I believe from some of my preliminary * debugging and thinking about it that it is possible to figure out * apriori groups of rectangles which are only merge candidates with * each other. (See testboxes.c:get_screen_region() when which==2 * and track the steps of this function carefully to see what gave * me the hint that this might work) * (3) figure out how to avoid merge_spanning_rects_in_region(). I think * it might be possible to modify this function to make that * possible, and I spent just a little while thinking about it, but n * wasn't large enough to convince me to care yet. * (4) just don't call this function that much. Currently, it's called * from a few places in constraints.c, and thus is called multiple * times for every meta_window_constrain() call, which itself is * called an awful lot. However, the answer we provide is always the * same unless the screen size, number of xineramas, or list of * struts has changed. I'm not aware of any case where screen size * or number of xineramas changes without logging out. struts change * very rarely. So we should be able to just save the appropriate * info in the MetaWorkspace (or maybe MetaScreen), update it when * the struts change, and then just use those precomputed values * instead of calling this function so much. * * In terms of work, 1-3 would be hard (and I'm not entirely certain that * they would work) and 4 would be relatively easy. 4 would also provide * the greatest benefit. Therefore, do 4 first. Don't even think about * 1-3 or other micro-optimizations until you've done that one. */ GList *ret; GList *tmp_list; const GSList *strut_iter; MetaRectangle *temp_rect; /* The algorithm is basically as follows: * Ignore directional expansions until the end * Initialize rectangle_set to basic_rect * Foreach strut: * Foreach rectangle in rectangle_set: * - Split the rectangle into new rectangles that don't overlap the * strut (but which are as big as possible otherwise) * Now do directional expansion of all rectangles in rectangle_set */ temp_rect = g_new (MetaRectangle, 1); *temp_rect = *basic_rect; ret = g_list_prepend (NULL, temp_rect); #ifdef PRINT_DEBUG char rect_string[25]; printf("Initialized spanning set with %s.\n", meta_rectangle_to_string (basic_rect, rect_string)); #endif strut_iter = all_struts; while (strut_iter) { GList *rect_iter; MetaRectangle *strut = (MetaRectangle*) strut_iter->data; #ifdef PRINT_DEBUG printf("Dealing with strut %s.\n", meta_rectangle_to_string (strut, rect_string)); #endif tmp_list = ret; ret = NULL; rect_iter = tmp_list; while (rect_iter) { MetaRectangle *rect = (MetaRectangle*) rect_iter->data; #ifdef PRINT_DEBUG printf(" Looking if we need to chop up %s.\n", meta_rectangle_to_string (rect, rect_string)); #endif if (!meta_rectangle_overlap (rect, strut)) { ret = g_list_prepend (ret, rect); #ifdef PRINT_DEBUG printf(" No chopping of %s.\n", meta_rectangle_to_string (rect, rect_string)); #endif } else { /* If there is area in rect left of strut */ if (rect->x < strut->x) { temp_rect = g_new (MetaRectangle, 1); *temp_rect = *rect; temp_rect->width = strut->x - rect->x; ret = g_list_prepend (ret, temp_rect); #ifdef PRINT_DEBUG printf(" Added %s.\n", meta_rectangle_to_string (temp_rect, rect_string)); #endif } /* If there is area in rect right of strut */ if (rect->x + rect->width > strut->x + strut->width) { int new_x; temp_rect = g_new (MetaRectangle, 1); *temp_rect = *rect; new_x = strut->x + strut->width; temp_rect->width = rect->x + rect->width - new_x; temp_rect->x = new_x; ret = g_list_prepend (ret, temp_rect); #ifdef PRINT_DEBUG printf(" Added %s.\n", meta_rectangle_to_string (temp_rect, rect_string)); #endif } /* If there is area in rect above strut */ if (rect->y < strut->y) { temp_rect = g_new (MetaRectangle, 1); *temp_rect = *rect; temp_rect->height = strut->y - rect->y; ret = g_list_prepend (ret, temp_rect); #ifdef PRINT_DEBUG printf(" Added %s.\n", meta_rectangle_to_string (temp_rect, rect_string)); #endif } /* If there is area in rect below strut */ if (rect->y + rect->height > strut->y + strut->height) { int new_y; temp_rect = g_new (MetaRectangle, 1); *temp_rect = *rect; new_y = strut->y + strut->height; temp_rect->height = rect->y + rect->height - new_y; temp_rect->y = new_y; ret = g_list_prepend (ret, temp_rect); #ifdef PRINT_DEBUG printf(" Added %s.\n", meta_rectangle_to_string (temp_rect, rect_string)); #endif } g_free (rect); } rect_iter = rect_iter->next; } g_list_free (tmp_list); strut_iter = strut_iter->next; } /* Now it's time to do the directional expansion */ tmp_list = ret; while (tmp_list) { MetaRectangle *rect = (MetaRectangle*) tmp_list->data; rect->x -= left_expand; rect->width += (left_expand + right_expand); rect->y -= top_expand; rect->height += (top_expand + bottom_expand); tmp_list = tmp_list->next; } /* Sort by maximal area, just because I feel like it... */ ret = g_list_sort (ret, compare_rect_areas); /* Merge rectangles if possible so that the list really is minimal */ ret = merge_spanning_rects_in_region (ret); return ret; } void meta_rectangle_free_spanning_set (GList *spanning_rects) { g_list_foreach (spanning_rects, (void (*)(gpointer,gpointer))&g_free, /* ew, for ugly */ NULL); g_list_free (spanning_rects); } gboolean meta_rectangle_could_fit_in_region (const GList *spanning_rects, const MetaRectangle *rect) { const GList *temp; gboolean could_fit; temp = spanning_rects; could_fit = FALSE; while (!could_fit && temp != NULL) { could_fit = could_fit || meta_rectangle_could_fit_rect (temp->data, rect); temp = temp->next; } return could_fit; } gboolean meta_rectangle_contained_in_region (const GList *spanning_rects, const MetaRectangle *rect) { const GList *temp; gboolean contained; temp = spanning_rects; contained = FALSE; while (!contained && temp != NULL) { contained = contained || meta_rectangle_contains_rect (temp->data, rect); temp = temp->next; } return contained; } void meta_rectangle_clamp_to_fit_into_region (const GList *spanning_rects, FixedDirections fixed_directions, MetaRectangle *rect, const MetaRectangle *min_size) { const GList *temp; const MetaRectangle *best_rect = NULL; int best_overlap = 0; /* First, find best rectangle from spanning_rects to which we can clamp * rect to fit into. */ temp = spanning_rects; while (temp) { int factor = 1; MetaRectangle *compare_rect = temp->data; int maximal_overlap_amount_for_compare; /* If x is fixed and the entire width of rect doesn't fit in compare, set * factor to 0. */ if ((fixed_directions & FIXED_DIRECTION_X) && (compare_rect->x > rect->x || compare_rect->x + compare_rect->width < rect->x + rect->width)) factor = 0; /* If y is fixed and the entire height of rect doesn't fit in compare, set * factor to 0. */ if ((fixed_directions & FIXED_DIRECTION_Y) && (compare_rect->y > rect->y || compare_rect->y + compare_rect->height < rect->y + rect->height)) factor = 0; /* If compare can't hold the min_size window, set factor to 0 */ if (compare_rect->width < min_size->width || compare_rect->height < min_size->height) factor = 0; /* Determine maximal overlap amount */ maximal_overlap_amount_for_compare = MIN (rect->width, compare_rect->width) * MIN (rect->height, compare_rect->height); maximal_overlap_amount_for_compare *= factor; /* See if this is the best rect so far */ if (maximal_overlap_amount_for_compare > best_overlap) { best_rect = compare_rect; best_overlap = maximal_overlap_amount_for_compare; } temp = temp->next; } /* Clamp rect appropriately */ if (best_rect == NULL) { meta_warning ("No rect whose size to clamp to found!\n"); /* If it doesn't fit, at least make it no bigger than it has to be */ if (!(fixed_directions & FIXED_DIRECTION_X)) rect->width = min_size->width; if (!(fixed_directions & FIXED_DIRECTION_Y)) rect->height = min_size->height; } else { rect->width = MIN (rect->width, best_rect->width); rect->height = MIN (rect->height, best_rect->height); } } void meta_rectangle_clip_to_region (const GList *spanning_rects, FixedDirections fixed_directions, MetaRectangle *rect) { const GList *temp; const MetaRectangle *best_rect = NULL; int best_overlap = 0; /* First, find best rectangle from spanning_rects to which we will clip * rect into. */ temp = spanning_rects; while (temp) { int factor = 1; MetaRectangle *compare_rect = temp->data; MetaRectangle overlap; int maximal_overlap_amount_for_compare; /* If x is fixed and the entire width of rect doesn't fit in compare, set * factor to 0. */ if ((fixed_directions & FIXED_DIRECTION_X) && (compare_rect->x > rect->x || compare_rect->x + compare_rect->width < rect->x + rect->width)) factor = 0; /* If y is fixed and the entire height of rect doesn't fit in compare, set * factor to 0. */ if ((fixed_directions & FIXED_DIRECTION_Y) && (compare_rect->y > rect->y || compare_rect->y + compare_rect->height < rect->y + rect->height)) factor = 0; /* Determine maximal overlap amount */ meta_rectangle_intersect (rect, compare_rect, &overlap); maximal_overlap_amount_for_compare = meta_rectangle_area (&overlap); maximal_overlap_amount_for_compare *= factor; /* See if this is the best rect so far */ if (maximal_overlap_amount_for_compare > best_overlap) { best_rect = compare_rect; best_overlap = maximal_overlap_amount_for_compare; } temp = temp->next; } /* Clip rect appropriately */ if (best_rect == NULL) meta_warning ("No rect to clip to found!\n"); else { /* Extra precaution with checking fixed direction shouldn't be needed * due to logic above, but it shouldn't hurt either. */ if (!(fixed_directions & FIXED_DIRECTION_X)) { /* Find the new left and right */ int new_x = MAX (rect->x, best_rect->x); rect->width = MIN ((rect->x + rect->width) - new_x, (best_rect->x + best_rect->width) - new_x); rect->x = new_x; } /* Extra precaution with checking fixed direction shouldn't be needed * due to logic above, but it shouldn't hurt either. */ if (!(fixed_directions & FIXED_DIRECTION_Y)) { /* Clip the top, if needed */ int new_y = MAX (rect->y, best_rect->y); rect->height = MIN ((rect->y + rect->height) - new_y, (best_rect->y + best_rect->height) - new_y); rect->y = new_y; } } } void meta_rectangle_shove_into_region (const GList *spanning_rects, FixedDirections fixed_directions, MetaRectangle *rect) { const GList *temp; const MetaRectangle *best_rect = NULL; int best_overlap = 0; int shortest_distance = G_MAXINT; /* First, find best rectangle from spanning_rects to which we will shove * rect into. */ temp = spanning_rects; while (temp) { int factor = 1; MetaRectangle *compare_rect = temp->data; int maximal_overlap_amount_for_compare; int dist_to_compare; /* If x is fixed and the entire width of rect doesn't fit in compare, set * factor to 0. */ if ((fixed_directions & FIXED_DIRECTION_X) && (compare_rect->x > rect->x || compare_rect->x + compare_rect->width < rect->x + rect->width)) factor = 0; /* If y is fixed and the entire height of rect doesn't fit in compare, set * factor to 0. */ if ((fixed_directions & FIXED_DIRECTION_Y) && (compare_rect->y > rect->y || compare_rect->y + compare_rect->height < rect->y + rect->height)) factor = 0; /* Determine maximal overlap amount between rect & compare_rect */ maximal_overlap_amount_for_compare = MIN (rect->width, compare_rect->width) * MIN (rect->height, compare_rect->height); /* Determine distance necessary to put rect into comapre_rect */ dist_to_compare = 0; if (compare_rect->x > rect->x) dist_to_compare += compare_rect->x - rect->x; if (compare_rect->x + compare_rect->width < rect->x + rect->width) dist_to_compare += (rect->x + rect->width) - (compare_rect->x + compare_rect->width); if (compare_rect->y > rect->y) dist_to_compare += compare_rect->y - rect->y; if (compare_rect->y + compare_rect->height < rect->y + rect->height) dist_to_compare += (rect->y + rect->height) - (compare_rect->y + compare_rect->height); /* If we'd have to move in the wrong direction, disqualify compare_rect */ if (factor == 0) { maximal_overlap_amount_for_compare = 0; dist_to_compare = G_MAXINT; } /* See if this is the best rect so far */ if ((maximal_overlap_amount_for_compare > best_overlap) || (maximal_overlap_amount_for_compare == best_overlap && dist_to_compare < shortest_distance)) { best_rect = compare_rect; best_overlap = maximal_overlap_amount_for_compare; shortest_distance = dist_to_compare; } temp = temp->next; } /* Shove rect appropriately */ if (best_rect == NULL) meta_warning ("No rect to shove into found!\n"); else { /* Extra precaution with checking fixed direction shouldn't be needed * due to logic above, but it shouldn't hurt either. */ if (!(fixed_directions & FIXED_DIRECTION_X)) { /* Shove to the right, if needed */ if (best_rect->x > rect->x) rect->x = best_rect->x; /* Shove to the left, if needed */ if (best_rect->x + best_rect->width < rect->x + rect->width) rect->x = (best_rect->x + best_rect->width) - rect->width; } /* Extra precaution with checking fixed direction shouldn't be needed * due to logic above, but it shouldn't hurt either. */ if (!(fixed_directions & FIXED_DIRECTION_Y)) { /* Shove down, if needed */ if (best_rect->y > rect->y) rect->y = best_rect->y; /* Shove up, if needed */ if (best_rect->y + best_rect->height < rect->y + rect->height) rect->y = (best_rect->y + best_rect->height) - rect->height; } } } void meta_rectangle_find_linepoint_closest_to_point (double x1, double y1, double x2, double y2, double px, double py, double *valx, double *valy) { /* I'll use the shorthand rx, ry for the return values, valx & valy. * Now, we need (rx,ry) to be on the line between (x1,y1) and (x2,y2). * For that to happen, we first need the slope of the line from (x1,y1) * to (rx,ry) must match the slope of (x1,y1) to (x2,y2), i.e.: * (ry-y1) (y2-y1) * ------- = ------- * (rx-x1) (x2-x1) * If x1==x2, though, this gives divide by zero errors, so we want to * rewrite the equation by multiplying both sides by (rx-x1)*(x2-x1): * (ry-y1)(x2-x1) = (y2-y1)(rx-x1) * This is a valid requirement even when x1==x2 (when x1==x2, this latter * equation will basically just mean that rx must also be equal to x1 and * x2) * * The other requirement that we have is that the line from (rx,ry) to * (px,py) must be perpendicular to the line from (x1,y1) to (x2,y2). So * we just need to get a vector in the direction of each line, take the * dot product of the two, and ensure that the result is 0: * (rx-px)*(x2-x1) + (ry-py)*(y2-y1) = 0. * * This gives us two equations and two unknowns: * * (ry-y1)(x2-x1) = (y2-y1)(rx-x1) * (rx-px)*(x2-x1) + (ry-py)*(y2-y1) = 0. * * This particular pair of equations is always solvable so long as * (x1,y1) and (x2,y2) are not the same point (and note that anyone who * calls this function that way is braindead because it means that they * really didn't specify a line after all). However, the caller should * be careful to avoid making (x1,y1) and (x2,y2) too close (e.g. like * 10^{-8} apart in each coordinate), otherwise roundoff error could * cause issues. Solving these equations by hand (or using Maple(TM) or * Mathematica(TM) or whatever) results in slightly messy expressions, * but that's all the below few lines do. */ double diffx, diffy, den; diffx = x2 - x1; diffy = y2 - y1; den = diffx*diffx + diffy*diffy; *valx = (py*diffx*diffy + px*diffx*diffx + y2*x1*diffy - y1*x2*diffy) / den; *valy = (px*diffx*diffy + py*diffy*diffy + x2*y1*diffx - x1*y2*diffx) / den; }