Root/
| 1 | /* |
| 2 | * p2d_hsort.c - Hierarchical polygon sort |
| 3 | * |
| 4 | * Written 2012 by Werner Almesberger |
| 5 | * Copyright 2012 Werner Almesberger |
| 6 | * |
| 7 | * This library is free software; you can redistribute it and/or |
| 8 | * modify it under the terms of the GNU Lesser General Public |
| 9 | * License as published by the Free Software Foundation; either |
| 10 | * version 2.1 of the License, or (at your option) any later version. |
| 11 | */ |
| 12 | |
| 13 | |
| 14 | #include "util.h" |
| 15 | #include "poly2d.h" |
| 16 | #include "p2d_hsort.h" |
| 17 | |
| 18 | |
| 19 | static struct p2d_hier *recurse_hsort(struct p2d *p) |
| 20 | { |
| 21 | struct p2d *sub = NULL, *sub2 = NULL, **last = ⊂ |
| 22 | struct p2d **a, *b, **next; |
| 23 | struct p2d_hier *res = NULL, *t; |
| 24 | struct p2d **res_last = (struct p2d **) &res; |
| 25 | |
| 26 | /* |
| 27 | * Move all polygons that are inside some other polygon to "sub". |
| 28 | */ |
| 29 | for (a = &p; *a; a = next) { |
| 30 | next = &(*a)->next; |
| 31 | for (b = p; b; b = b->next) |
| 32 | if (*a != b && p2d_contains_poly(b, *a)) { |
| 33 | *last = *a; |
| 34 | last = &(*last)->next; |
| 35 | *a = *next; |
| 36 | next = a; |
| 37 | *last = NULL; |
| 38 | break; |
| 39 | } |
| 40 | } |
| 41 | |
| 42 | while (p) { |
| 43 | /* |
| 44 | * Begin transplanting "p" into t->p. |
| 45 | */ |
| 46 | t = alloc_type(struct p2d_hier); |
| 47 | t->p = *p; |
| 48 | |
| 49 | /* |
| 50 | * Move all polygons inside the current one from "sub" to |
| 51 | * "sub2". (Direct and indirect subordinates.) |
| 52 | */ |
| 53 | sub2 = NULL; |
| 54 | last = &sub2; |
| 55 | for (a = ⊂ *a; a = next) { |
| 56 | next = &(*a)->next; |
| 57 | if (p2d_contains_poly(p, *a)) { |
| 58 | *last = *a; |
| 59 | last = &(*last)->next; |
| 60 | *a = *next; |
| 61 | next = a; |
| 62 | *last = NULL; |
| 63 | } |
| 64 | } |
| 65 | |
| 66 | /* |
| 67 | * Sort the subordinates. |
| 68 | */ |
| 69 | t->holes = recurse_hsort(sub2); |
| 70 | |
| 71 | /* |
| 72 | * End transplanting "p" into t->p. |
| 73 | */ |
| 74 | free(p); |
| 75 | p = t->p.next; |
| 76 | |
| 77 | /* |
| 78 | * Append "t" to "res". |
| 79 | */ |
| 80 | *res_last = &t->p; |
| 81 | res_last = &t->p.next; |
| 82 | t->p.next = NULL; |
| 83 | |
| 84 | } |
| 85 | return res; |
| 86 | } |
| 87 | |
| 88 | |
| 89 | struct p2d_hier *p2d_hsort(const struct p2d *p) |
| 90 | { |
| 91 | return recurse_hsort(p2d_copy_all(p)); |
| 92 | } |
| 93 | |
| 94 | |
| 95 | void p2d_hier_free(struct p2d_hier *t) |
| 96 | { |
| 97 | struct p2d_hier *next; |
| 98 | struct p2d *p; |
| 99 | |
| 100 | while (t) { |
| 101 | p2d_hier_free(t->holes); |
| 102 | p = &t->p; |
| 103 | next = p2d_to_hier(p->next); |
| 104 | p2d_free(p); |
| 105 | t = next; |
| 106 | } |
| 107 | } |
| 108 |
Branches:
master
