108 lines
2.0 KiB
C
108 lines
2.0 KiB
C
/*
|
|
* p2d_hsort.c - Hierarchical polygon sort
|
|
*
|
|
* Written 2012 by Werner Almesberger
|
|
* Copyright 2012 Werner Almesberger
|
|
*
|
|
* This library is free software; you can redistribute it and/or
|
|
* modify it under the terms of the GNU Lesser General Public
|
|
* License as published by the Free Software Foundation; either
|
|
* version 2.1 of the License, or (at your option) any later version.
|
|
*/
|
|
|
|
|
|
#include "util.h"
|
|
#include "poly2d.h"
|
|
#include "p2d_hsort.h"
|
|
|
|
|
|
static struct p2d_hier *recurse_hsort(struct p2d *p)
|
|
{
|
|
struct p2d *sub = NULL, *sub2 = NULL, **last = ⊂
|
|
struct p2d **a, *b, **next;
|
|
struct p2d_hier *res = NULL, *t;
|
|
struct p2d **res_last = (struct p2d **) &res;
|
|
|
|
/*
|
|
* Move all polygons that are inside some other polygon to "sub".
|
|
*/
|
|
for (a = &p; *a; a = next) {
|
|
next = &(*a)->next;
|
|
for (b = p; b; b = b->next)
|
|
if (*a != b && p2d_contains_poly(b, *a)) {
|
|
*last = *a;
|
|
last = &(*last)->next;
|
|
*a = *next;
|
|
next = a;
|
|
*last = NULL;
|
|
break;
|
|
}
|
|
}
|
|
|
|
while (p) {
|
|
/*
|
|
* Begin transplanting "p" into t->p.
|
|
*/
|
|
t = alloc_type(struct p2d_hier);
|
|
t->p = *p;
|
|
|
|
/*
|
|
* Move all polygons inside the current one from "sub" to
|
|
* "sub2". (Direct and indirect subordinates.)
|
|
*/
|
|
sub2 = NULL;
|
|
last = &sub2;
|
|
for (a = ⊂ *a; a = next) {
|
|
next = &(*a)->next;
|
|
if (p2d_contains_poly(p, *a)) {
|
|
*last = *a;
|
|
last = &(*last)->next;
|
|
*a = *next;
|
|
next = a;
|
|
*last = NULL;
|
|
}
|
|
}
|
|
|
|
/*
|
|
* Sort the subordinates.
|
|
*/
|
|
t->holes = recurse_hsort(sub2);
|
|
|
|
/*
|
|
* End transplanting "p" into t->p.
|
|
*/
|
|
free(p);
|
|
p = t->p.next;
|
|
|
|
/*
|
|
* Append "t" to "res".
|
|
*/
|
|
*res_last = &t->p;
|
|
res_last = &t->p.next;
|
|
t->p.next = NULL;
|
|
|
|
}
|
|
return res;
|
|
}
|
|
|
|
|
|
struct p2d_hier *p2d_hsort(const struct p2d *p)
|
|
{
|
|
return recurse_hsort(p2d_copy_all(p));
|
|
}
|
|
|
|
|
|
void p2d_hier_free(struct p2d_hier *t)
|
|
{
|
|
struct p2d_hier *next;
|
|
struct p2d *p;
|
|
|
|
while (t) {
|
|
p2d_hier_free(t->holes);
|
|
p = &t->p;
|
|
next = p2d_to_hier(p->next);
|
|
p2d_free(p);
|
|
t = next;
|
|
}
|
|
}
|