aboutsummaryrefslogtreecommitdiff
path: root/src_c/csp.c
diff options
context:
space:
mode:
Diffstat (limited to 'src_c/csp.c')
-rw-r--r--src_c/csp.c236
1 files changed, 194 insertions, 42 deletions
diff --git a/src_c/csp.c b/src_c/csp.c
index 8ff94cc..9cd25ec 100644
--- a/src_c/csp.c
+++ b/src_c/csp.c
@@ -24,10 +24,10 @@ static void sort_panels(opcut_panel_t **first, opcut_panel_t **last) {
for (opcut_panel_t *panel = (*first)->next; panel;) {
opcut_panel_t *next = panel->next;
- if (panel->area < pivot_first->area) {
+ if (panel->area > pivot_first->area) {
panel->next = left_first;
left_first = panel;
- } else if (panel->area > pivot_first->area) {
+ } else if (panel->area < pivot_first->area) {
panel->next = right_first;
right_first = panel;
} else {
@@ -123,9 +123,11 @@ static void calculate_fitness(opcut_result_t *result, fitness_t *fitness) {
max_unused_area = unused->area;
}
- fitness->fitness += (panel->area - used_areas) / result->panels_area;
- fitness->fitness -= FITNESS_K * min_used_area * max_unused_area /
- (result->panels_area * result->panels_area);
+ fitness->fitness +=
+ (panel->area - used_areas) / result->params->panels_area;
+ fitness->fitness -=
+ FITNESS_K * min_used_area * max_unused_area /
+ (result->params->panels_area * result->params->panels_area);
}
fitness->unused_initial_count = 0;
@@ -139,69 +141,219 @@ static void calculate_fitness(opcut_result_t *result, fitness_t *fitness) {
}
-static int cut_item_from_unused(opcut_item_t *item, opcut_unused_t *unused,
- bool rotate, double cut_width, bool vertical,
- opcut_used_t *new_used,
- opcut_unused_t *new_unused,
- size_t *new_unused_len) {
+static inline bool item_fits_unused(opcut_item_t *item, opcut_unused_t *unused,
+ bool rotate) {
+ if (rotate && !item->can_rotate)
+ return false;
+
+ double item_width = (rotate ? item->height : item->width);
+ double item_height = (rotate ? item->width : item->height);
+
+ return unused->height >= item_height && unused->width >= item_width;
+}
+
+
+static int cut_item_from_unused(opcut_result_t *result, opcut_item_t *item,
+ opcut_unused_t *unused, bool rotate,
+ bool vertical) {
double item_width = (rotate ? item->height : item->width);
double item_height = (rotate ? item->width : item->height);
if (unused->height < item_height || unused->width < item_width)
- return OPCUT_UNSOLVABLE;
+ return OPCUT_ERROR;
+
+ opcut_used_t *used = opcut_pool_alloc(result->used_pool);
+ if (!used)
+ return OPCUT_ERROR;
+ *used = (opcut_used_t){.panel = unused->panel,
+ .item = item,
+ .x = unused->x,
+ .y = unused->y,
+ .rotate = rotate,
+ .next = result->used};
+ result->used = used;
- new_used->panel = unused->panel;
- new_used->item = item;
- new_used->x = unused->x;
- new_used->y = unused->y;
- new_used->rotate = rotate;
double width;
double height;
- *new_unused_len = 0;
- width = unused->width - item_width - cut_width;
+ width = unused->width - item_width - result->params->cut_width;
if (width > 0) {
height = (vertical ? unused->height : item_height);
- new_unused[(*new_unused_len)++] =
- (opcut_unused_t){.panel = unused->panel,
- .width = width,
- .height = height,
- .x = unused->x + item_width + cut_width,
- .y = unused->y,
- .area = width * height,
- .initial = false};
+ opcut_unused_t *new_unused = opcut_pool_alloc(result->unused_pool);
+ if (!new_unused)
+ return OPCUT_ERROR;
+ *new_unused = (opcut_unused_t){.panel = unused->panel,
+ .width = width,
+ .height = height,
+ .x = unused->x + item_width +
+ result->params->cut_width,
+ .y = unused->y,
+ .next = result->unused,
+ .area = width * height,
+ .initial = false};
+ result->unused = new_unused;
}
- height = unused->height - item_height - cut_width;
+ height = unused->height - item_height - result->params->cut_width;
if (height > 0) {
width = (vertical ? item_width : unused->width);
- new_unused[(*new_unused_len)++] =
- (opcut_unused_t){.panel = unused->panel,
- .width = width,
- .height = height,
- .x = unused->x,
- .y = unused->y + item_height + cut_width,
- .area = width * height,
- .initial = false};
+ opcut_unused_t *new_unused = opcut_pool_alloc(result->unused_pool);
+ if (!new_unused)
+ return OPCUT_ERROR;
+ *new_unused = (opcut_unused_t){.panel = unused->panel,
+ .width = width,
+ .height = height,
+ .x = unused->x,
+ .y = unused->y + item_height +
+ result->params->cut_width,
+ .next = result->unused,
+ .area = width * height,
+ .initial = false};
+ result->unused = new_unused;
}
return OPCUT_SUCCESS;
}
-void opcut_sort_params(opcut_params_t *params) {
- sort_panels(&(params->panels), NULL);
- sort_items(&(params->items), NULL);
+static int copy_unused(opcut_result_t *result, opcut_unused_t *exclude) {
+ opcut_unused_t *unused = NULL;
+ for (opcut_unused_t *i = result->unused; i; i = i->next) {
+ if (i == exclude)
+ continue;
+
+ opcut_unused_t *temp = opcut_pool_alloc(result->unused_pool);
+ if (!temp)
+ return OPCUT_ERROR;
+
+ *temp = *i;
+ temp->next = unused;
+ unused = temp;
+ }
+
+ result->unused = NULL;
+ while (unused) {
+ opcut_unused_t *next = unused->next;
+ unused->next = result->unused;
+ result->unused = unused;
+ unused = next;
+ }
+
+ return OPCUT_SUCCESS;
}
-int opcut_calculate(opcut_method_t method, opcut_params_t *params,
- opcut_result_t *result) {
+static void free_unused(opcut_result_t *result) {
+ while (result->unused) {
+ opcut_unused_t *next = result->unused->next;
+ opcut_pool_free(result->unused_pool, result->unused);
+ result->unused = next;
+ }
+}
+
+
+static void free_last_used(opcut_result_t *result) {
+ opcut_pool_free(result->used_pool, result->used);
+}
+
+
+static int calculate_greedy(opcut_result_t *result, opcut_item_t *items) {
+ for (opcut_item_t *item = items; item; item = item->next) {
+ opcut_result_t best_result;
+ fitness_t best_fitness;
+ bool solvable = false;
+ for (opcut_unused_t *unused = result->unused; unused;
+ unused = unused->next) {
+ for (size_t rotate = 0; rotate < 2; ++rotate) {
+ if (!item_fits_unused(item, unused, rotate))
+ continue;
+
+ for (size_t vertical = 0; vertical < 2; ++vertical) {
+ opcut_result_t temp_result = *result;
+ if (copy_unused(&temp_result, unused))
+ return OPCUT_ERROR;
+
+ if (cut_item_from_unused(&temp_result, item, unused, rotate,
+ vertical))
+ return OPCUT_ERROR;
+
+ fitness_t temp_fitness;
+ calculate_fitness(&temp_result, &temp_fitness);
+
+ if (!solvable) {
+ best_result = temp_result;
+ best_fitness = temp_fitness;
+ solvable = true;
+
+ } else if (compare_fitness(&temp_fitness, &best_fitness) <
+ 0) {
+ free_last_used(&best_result);
+ free_unused(&best_result);
+ best_result = temp_result;
+ best_fitness = temp_fitness;
+
+ } else {
+ free_last_used(&temp_result);
+ free_unused(&temp_result);
+ }
+ }
+ }
+ }
+
+ if (!solvable)
+ return OPCUT_UNSOLVABLE;
+
+ free_unused(result);
+ *result = best_result;
+ }
+
+ return OPCUT_SUCCESS;
+}
+
+
+static int calculate_forward_greedy(opcut_result_t *result,
+ opcut_item_t *items) {
+ for (opcut_item_t *item = items; item; item = item->next) {
+ }
+
+ return OPCUT_SUCCESS;
+}
+
+
+int opcut_calculate(opcut_pool_t *used_pool, opcut_pool_t *unused_pool,
+ opcut_method_t method, opcut_params_t *params,
+ opcut_result_t *result) {
+ result->used_pool = used_pool;
+ result->unused_pool = unused_pool;
result->params = params;
result->used = NULL;
result->unused = NULL;
- result->panels_area = 0;
- return OPCUT_SUCCESS;
+ sort_panels(&(params->panels), NULL);
+ sort_items(&(params->items), NULL);
+
+ for (opcut_panel_t *panel = params->panels; panel; panel = panel->next) {
+ opcut_unused_t *unused = opcut_pool_alloc(unused_pool);
+ if (!unused)
+ return OPCUT_ERROR;
+
+ *unused = (opcut_unused_t){.panel = panel,
+ .width = panel->width,
+ .height = panel->height,
+ .x = 0,
+ .y = 0,
+ .next = result->unused,
+ .area = panel->area,
+ .initial = true};
+ result->unused = unused;
+ }
+
+ if (method == OPCUT_METHOD_GREEDY)
+ return calculate_greedy(result, params->items);
+
+ if (method == OPCUT_METHOD_FORWARD_GREEDY)
+ return calculate_forward_greedy(result, params->items);
+
+ return OPCUT_ERROR;
}
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2026-02-11 16:28:05 +0000