#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include "tools/debug_alloc.h"
#include "R-tree.h"
//
// Useful defines
//
#ifndef MAX
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#endif
#ifndef MIN
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#endif
typedef double REALTYPE;
#define REALTYPE_MAX +1E+37
#define REALTYPE_MIN -1E+37
typedef long COORTYPE;
#define COORTYPE_MAX +2147483647L
#define COORTYPE_MIN -2147483648L
//
// RT_Rect definition
//
typedef struct RT_Rect
{
COORTYPE x1, y1;
COORTYPE x2, y2;
} RT_Rect;
RT_Rect rect_unite(RT_Rect *r1, RT_Rect *r2)
{
RT_Rect ret;
ret.x1 = MIN(r1->x1, r2->x1);
ret.x2 = MAX(r1->x2, r2->x2);
ret.y1 = MIN(r1->y1, r2->y1);
ret.y2 = MAX(r1->y2, r2->y2);
return ret;
}
#define rect_intersects(r1, r2) \
((MAX((r1)->x1, (r2)->x1) <= MIN((r1)->x2, (r2)->x2)) \
&& (MAX((r1)->y1, (r2)->y1) <= MIN((r1)->y2, (r2)->y2)))
#define rect_contains(r1, r2) \
((r1)->x1 <= (r2)->x1 && (r1)->x2 >= (r2)->x2 \
&& (r1)->y1 <= (r2)->y1 && (r1)->y2 >= (r2)->y2)
#define rect_area(r) \
((REALTYPE)((r)->x2 - (r)->x1 + 1) * (REALTYPE)((r)->y2 - (r)->y1 + 1))
#define rect_valid(r) \
((r)->x1 <= (r)->x2 && (r)->y1 <= (r)->y2)
//
// R-tree implementation
//
#define RT_MAXNODES 25
#define RT_MINNODES 13
typedef struct RT_Branch
{
RT_Rect mbr;
struct RT_Node *child;
} RT_Branch;
typedef struct RT_Node
{
int count;
int level;
RT_Branch branches[RT_MAXNODES];
} RT_Node;
typedef struct RT_Partition
{
int which_group[RT_MAXNODES + 1];
BOOL item_taken[RT_MAXNODES + 1];
int item_count;
int item_min;
RT_Rect grp_mbr[2];
REALTYPE grp_area[2];
int grp_items[2];
} RT_Partition;
typedef struct RT_Split
{
RT_Branch branch_buf[RT_MAXNODES + 1];
int branch_count; // always be RT_MAXNODES+1
RT_Rect tmp_mbr;
REALTYPE tmp_area;
RT_Partition partition;
} RT_Split;
// ~
static void __init_node(RT_Node *n)
{
n->count = 0;
n->level = -1;
memset(n->branches, 0, sizeof(n->branches));
}
static RT_Node *__new_node()
{
RT_Node *n = (RT_Node *)MALLOC(sizeof(RT_Node));
if (n == NULL) {
fprintf(stderr, "***[RTree] Lack of memory.\n");
exit(1);
}
__init_node(n);
return n;
}
static void __free_node(RT_Node *n)
{
int i;
if (n->level > 0) {
for (i = 0; i < RT_MAXNODES; ++i)
if (n->branches[i].child != NULL)
__free_node(n->branches[i].child);
}
FREE(n);
}
static RT_Rect __node_mbr(RT_Node *n)
{
assert(n->count > 0);
RT_Rect ret = n->branches[0].mbr;
int i = 1;
while (i < n->count) {
assert(n->branches[i].child != NULL);
ret = rect_unite(&ret, &n->branches[i].mbr);
++i;
}
#ifndef NDEBUG
for (; i < RT_MAXNODES; ++i)
assert(n->branches[i].child == NULL);
#endif
return ret;
}
static void __split_node(RTree *, RT_Node *, RT_Branch *, RT_Node **);
/**
* Add a branch to a node. Split the node if necessary.
* Returns FALSE if node not split. Old node updated.
* Returns TRUE if node split, sets *new_node to address of new node.
* Old node updated, becomes one of two.
*/
static BOOL __add_branch(RTree *tree, RT_Branch *b, RT_Node *n, RT_Node **new_node)
{
if (n->count < RT_MAXNODES) {
assert(n->branches[n->count].child == NULL);
n->branches[n->count++] = *b;
return FALSE;
}
else {
__split_node(tree, n, b, new_node);
return TRUE;
}
}
static void __save_branches(RTree *tree, RT_Node *n, RT_Branch *b)
{
int i;
#ifndef NDEBUG
for (i = 0; i < RT_MAXNODES; ++i)
assert(n->branches[i].child != NULL); /* node should have every entry full */
#endif
memcpy(tree->split->branch_buf, n->branches, sizeof(n->branches));
tree->split->branch_buf[RT_MAXNODES] = *b;
tree->split->branch_count = RT_MAXNODES + 1;
RT_Rect tmpr = tree->split->branch_buf[0].mbr;
for (i = 1; i < RT_MAXNODES + 1; ++i)
tmpr = rect_unite(&tmpr, &(tree->split->branch_buf[i].mbr));
tree->split->tmp_mbr = tmpr;
tree->split->tmp_area = rect_area(&tmpr);
}
static void __load_branches(RTree *tree, RT_Node *n0, RT_Node *n1, RT_Partition *p)
{
int i;
for (i = 0; i < p->item_count; ++i) {
assert(p->which_group[i] == 0 || p->which_group[i] == 1);
if (p->which_group[i] == 0)
__add_branch(tree, &(tree->split->branch_buf[i]), n0, NULL);
else
__add_branch(tree, &(tree->split->branch_buf[i]), n1, NULL);
}
}
static void __group_node(RTree *tree, int i, int grp, RT_Partition *p)
{
assert(!p->item_taken[i]);
p->which_group[i] = grp;
p->item_taken[i] = TRUE;
if (p->grp_items[grp] == 0)
p->grp_mbr[grp] = tree->split->branch_buf[i].mbr;
else
p->grp_mbr[grp] = rect_unite(p->grp_mbr + grp, &(tree->split->branch_buf[i].mbr));
p->grp_area[grp] = rect_area(p->grp_mbr + grp);
++p->grp_items[grp];
}
static void __select_seeds(RTree *tree, RT_Partition *p)
{
int i, j;
int seed0 = 0, seed1 = 0;
REALTYPE worst, waste, area[RT_MAXNODES + 1];
for (i = 0; i < p->item_count; ++i)
area[i] = rect_area(&(tree->split->branch_buf[i].mbr));
worst = -tree->split->tmp_area - 1;
for (i = 0; i < p->item_count - 1; ++i)
for (j = i + 1; j < p->item_count; ++j) {
RT_Rect r = rect_unite(&(tree->split->branch_buf[i].mbr), &(tree->split->branch_buf[j].mbr));
waste = rect_area(&r) - area[i] - area[j];
if (waste > worst) {
worst = waste;
seed0 = i;
seed1 = j;
}
}
__group_node(tree, seed0, 0, p);
__group_node(tree, seed1, 1, p);
}
static void __grouping_method0(RTree *tree, RT_Partition *p, int minitems)
{
int i;
int group;
/* initialize partition */
memset(p, 0, sizeof(RT_Partition));
p->item_count = tree->split->branch_count;
p->item_min = minitems;
for (i = 0; i < RT_MAXNODES + 1; ++i) {
p->which_group[i] = -1;
p->item_taken[i] = FALSE;
}
__select_seeds(tree, p);
while (p->grp_items[0] + p->grp_items[1] < p->item_count
&& p->grp_items[0] < p->item_count - p->item_min
&& p->grp_items[1] < p->item_count - p->item_min) {
int chosen = 0;
int better_grp = 0;
REALTYPE biggest_diff = (REALTYPE)-1;
for (i = 0; i < p->item_count; ++i) {
if (p->item_taken[i])
continue;
RT_Rect *pr, rect0, rect1;
REALTYPE diff;
pr = &(tree->split->branch_buf[i].mbr);
rect0 = rect_unite(pr, &(p->grp_mbr[0]));
rect1 = rect_unite(pr, &(p->grp_mbr[1]));
diff = (rect_area(&rect0) - p->grp_area[0])
- (rect_area(&rect1) - p->grp_area[1]);
if (diff < 0) {
group = 0;
diff = -diff;
}
else
group = 1;
if (diff > biggest_diff) {
biggest_diff = diff;
chosen = i;
better_grp = group;
}
else if (diff == biggest_diff
&& p->grp_items[group] < p->grp_items[better_grp]) {
chosen = i;
better_grp = group;
}
}
__group_node(tree, chosen, better_grp, p);
}
/* if one group too full, put remaining rects in the other */
if (p->grp_items[0] + p->grp_items[1] < p->item_count) {
group = p->grp_items[0] >= p->item_count - p->item_min ? 1 : 0;
for (i = 0; i < p->item_count; ++i)
if (!p->item_taken[i])
__group_node(tree, i, group, p);
}
assert(p->grp_items[0] + p->grp_items[1] == p->item_count);
assert(p->grp_items[0] >= p->item_min && p->grp_items[1] >= p->item_min);
}
static void __split_node(RTree *tree, RT_Node *n, RT_Branch *b, RT_Node **new_node)
{
RT_Partition *p;
int level_save;
assert(new_node != NULL);
if (tree->split == NULL) {
tree->split = (RT_Split *)MALLOC(sizeof(RT_Split));
if (tree->split == NULL) {
fprintf(stderr, "***[RTree] Lack of memory\n");
exit(1);
}
memset(tree->split, 0, sizeof(RT_Split));
}
/* save all branches into a buffer, initialize old node */
level_save = n->level;
__save_branches(tree, n, b);
__init_node(n);
p = &(tree->split->partition);
__grouping_method0(tree, p, RT_MINNODES);
/* load branches from buffer into 2 nodes according to chosen partition */
*new_node = __new_node();
(*new_node)->level = n->level = level_save;
__load_branches(tree, n, *new_node, p);
assert(n->count + (*new_node)->count == p->item_count);
}
static int __pick_branch(RT_Rect *mbr, RT_Node *n)
{
RT_Rect *r, t
电子海图引擎源码
5星 · 超过95%的资源 需积分: 49 162 浏览量
2017-11-13
22:22:43
上传
评论 26
收藏 27.22MB RAR 举报 
电子海图引擎源码 （476个子文件） 
freetype-2.4.10.tar.bz2 1.44MB R-tree.c 14KB assure_fio.c 1KB 0_500501.cds 81KB 0_500502.cds 76KB 0_500603.cds 60KB 0_500601.cds 58KB 0_500604.cds 56KB 0_500602.cds 51KB 7Csahara.cds 19KB E1302001.cds 0B cellpolicy.conf 210B encview.conf 151B configure 990B chartcanvas.cpp 147KB fpainter.cpp 71KB S52defs.cpp 48KB enc_chart.cpp 41KB fcolor_p.cpp 30KB ir_datasets.cpp 27KB s57castscanner.cpp 27KB s57_record.cpp 25KB String.cpp 25KB s57reid.cpp 21KB s57_field_codec.cpp 20KB fpolygon.cpp 16KB MainWindow.cpp 16KB h_chartedobject.cpp 15KB enc_vessel.cpp 14KB EncViewWidget.cpp 14KB enc_layer.cpp 13KB s57parsescanner.cpp 13KB Config.cpp 10KB s57extract.cpp 10KB ffontmanager.cpp 9KB enc_utmgrid.cpp 8KB enc_fishingzone.cpp 8KB MakeTilesThread.cpp 7KB logcat.cpp 7KB fcolor.cpp 7KB enc_warning.cpp 7KB fpixmap_xpm.cpp 7KB ir_modulelib.cpp 6KB debug_alloc.cpp 6KB moc_MainWindow.cpp 6KB trigonf.cpp 6KB fclipper.cpp 6KB s57_utils.cpp 6KB gcoord.cpp 5KB harbourlist.cpp 5KB moc_EncViewWidget.cpp 4KB test_string.cpp 4KB ModuleListDialog.cpp 4KB CellPolicyListDialog.cpp 4KB moc_InquiryDialog.cpp 4KB i18n.cpp 4KB s57cast.cpp 3KB moc_ModuleListDialog.cpp 3KB moc_CellPolicyListDialog.cpp 3KB fpixmap_png.cpp 3KB moc_MakeTilesDialog.cpp 3KB s57_module.cpp 3KB moc_CellPolicyCreateDialog.cpp 3KB moc_MyCastScanner.cpp 3KB moc_ScaleDialog.cpp 3KB ObjectDetailDialog.cpp 3KB moc_CenterRotationDialog.cpp 3KB utmproject.cpp 3KB InquiryDialog.cpp 2KB fpixmap.cpp 2KB s57look.cpp 2KB frect.cpp 2KB fbitmap.cpp 2KB h_object.cpp 2KB CellPolicyEditDialog.cpp 2KB enc_highlight.cpp 2KB flinemetrics.cpp 2KB ffontmetrics.cpp 2KB rcsrotation.cpp 2KB ffont.cpp 2KB MakeTilesDialog.cpp 2KB ScaleDialog.cpp 1KB grect.cpp 1KB CellPolicyCreateDialog.cpp 1KB enc_mark.cpp 1KB CenterRotationDialog.cpp 1KB Log.cpp 1KB frotation.cpp 809B env.cpp 675B MyProgressBar.cpp 438B main.cpp 336B EncPaintDeviceQt.cpp 314B test_logcat.cpp 293B MyCastScanner.cpp 240B fpoint.cpp 39B FishingZone.dat 24KB Makefile.ft 660B ui_MainWindow.h 14KB fpainter.h 12KB fpainter.h 12KB共 476 条
- 1
- 2
- 3
- 4
- 5
- 1
- 2
前往页