1 /* SCCS Id: @(#)gr_rect.c 3.4 2001/12/10 */
2 /* Copyright (c) Christian Bressler, 2001 */
3 /* NetHack may be freely redistributed. See license for details. */
4 /* This is an almost exact copy of qt_clust.cpp */
5 /* gr_rect.c */
6 #include <stdlib.h>
7 #include <stdio.h>
8 #include <limits.h>
9 #include "gr_rect.h"
new_dirty_rect(int size)10 dirty_rect *new_dirty_rect(int size){
11 dirty_rect *new=NULL;
12 if(size>0){
13 new=(dirty_rect *)calloc(1L,sizeof(dirty_rect));
14 if(new){
15 new->rects=(GRECT *)calloc((long)size,sizeof(GRECT));
16 if(new->rects==NULL){
17 free(new);
18 return(NULL);
19 }
20 new->max=size;
21 }
22 }
23 return(new);
24 }
delete_dirty_rect(dirty_rect * this)25 void delete_dirty_rect(dirty_rect *this){
26 if(this==NULL)
27 return;
28 if(this->rects)
29 free(this->rects);
30 /* In case the Pointer is reused wrongly */
31 this->rects=NULL;
32 this->max=0;
33 this->used=0;
34 free(this);
35 }
36 static int gc_inside(GRECT *frame,GRECT *test);
37 static int gc_touch(GRECT *frame,GRECT *test);
38 static void gc_combine(GRECT *frame,GRECT *test);
39 static long gc_area(GRECT *area);
add_dirty_rect(dirty_rect * dr,GRECT * area)40 int add_dirty_rect(dirty_rect *dr,GRECT *area){
41 int cursor;
42 long lowestcost=9999999L;
43 int cheapest=-1;
44 int cheapestmerge1=-1;
45 int cheapestmerge2=-1;
46 int merge1;
47 int merge2;
48 for (cursor=0; cursor<dr->used; cursor++) {
49 if (gc_inside(&dr->rects[cursor],area)) {
50 /* Wholly contained already. */
51 return(TRUE);
52 }
53 }
54 for (cursor=0; cursor<dr->used; cursor++) {
55 if (gc_touch(&dr->rects[cursor],area)) {
56 GRECT larger=dr->rects[cursor];
57 long cost;
58 gc_combine(&larger,area);
59 cost=gc_area(&larger)-gc_area(&dr->rects[cursor]);
60 if (cost < lowestcost) {
61 int bad=FALSE,c;
62 for (c=0; c<dr->used && !bad; c++) {
63 bad=gc_touch(&dr->rects[c],&larger) && c!=cursor;
64 }
65 if (!bad) {
66 cheapest=cursor;
67 lowestcost=cost;
68 }
69 }
70 }
71 }
72 if (cheapest>=0) {
73 gc_combine(&dr->rects[cheapest],area);
74 return(TRUE);
75 }
76 if (dr->used < dr->max) {
77 dr->rects[dr->used++]=*area;
78 return(TRUE);
79 }
80 // Do cheapest of:
81 // add to closest cluster
82 // do cheapest cluster merge, add to new cluster
83 lowestcost=9999999L;
84 cheapest=-1;
85 for (cursor=0; cursor<dr->used; cursor++) {
86 GRECT larger=dr->rects[cursor];
87 long cost;
88 gc_combine(&larger,area);
89 cost=gc_area(&larger)-gc_area(&dr->rects[cursor]);
90 if (cost < lowestcost) {
91 int bad=FALSE, c;
92 for (c=0; c<dr->used && !bad; c++) {
93 bad=gc_touch(&dr->rects[c],&larger) && c!=cursor;
94 }
95 if (!bad) {
96 cheapest=cursor;
97 lowestcost=cost;
98 }
99 }
100 }
101 // XXX could make an heuristic guess as to whether we
102 // XXX need to bother looking for a cheap merge.
103 for (merge1=0; merge1<dr->used; merge1++) {
104 for (merge2=0; merge2<dr->used; merge2++) {
105 if (merge1!=merge2) {
106 GRECT larger=dr->rects[merge1];
107 long cost;
108 gc_combine(&larger,&dr->rects[merge2]);
109 cost=gc_area(&larger)-gc_area(&dr->rects[merge1])-gc_area(&dr->rects[merge2]);
110 if (cost < lowestcost) {
111 int bad=FALSE, c;
112 for (c=0; c<dr->used && !bad; c++) {
113 bad=gc_touch(&dr->rects[c],&larger) && c!=cursor;
114 }
115 if (!bad) {
116 cheapestmerge1=merge1;
117 cheapestmerge2=merge2;
118 lowestcost=cost;
119 }
120 }
121 }
122 }
123 }
124 if (cheapestmerge1>=0) {
125 gc_combine(&dr->rects[cheapestmerge1],&dr->rects[cheapestmerge2]);
126 dr->rects[cheapestmerge2]=dr->rects[dr->used-1];
127 dr->rects[dr->used-1]=*area;
128 } else {
129 gc_combine(&dr->rects[cheapest],area);
130 }
131 // NB: clusters do not intersect (or intersection will
132 // overwrite). This is a result of the above algorithm,
133 // given the assumption that (x,y) are ordered topleft
134 // to bottomright.
135 return(TRUE);
136 }
get_dirty_rect(dirty_rect * dr,GRECT * area)137 int get_dirty_rect(dirty_rect* dr,GRECT *area){
138 if(dr==NULL || area==NULL || dr->rects==NULL || dr->used<=0 || dr->max<=0)
139 return(FALSE);
140 *area=dr->rects[--dr->used];
141 return(TRUE);
142 }
clear_dirty_rect(dirty_rect * dr)143 int clear_dirty_rect(dirty_rect *dr){
144 if(dr)
145 dr->used=0;
146 return(TRUE);
147 }
resize_dirty_rect(dirty_rect * dr,int new_size)148 int resize_dirty_rect(dirty_rect *dr,int new_size){
149 return(FALSE);
150 }
gc_inside(GRECT * frame,GRECT * test)151 static int gc_inside(GRECT *frame,GRECT *test){
152 if(frame && test && frame->g_x<=test->g_x && frame->g_y<=test->g_y &&
153 frame->g_x+frame->g_w>=test->g_x+test->g_w &&
154 frame->g_y+frame->g_h>=test->g_y+test->g_h
155 )
156 return(TRUE);
157 return(FALSE);
158 }
gc_touch(GRECT * frame,GRECT * test)159 static int gc_touch(GRECT *frame,GRECT *test){
160 GRECT tmp={test->g_x-1,test->g_y-1,test->g_w+2,test->g_h+2};
161 return(rc_intersect(frame,&tmp));
162 }
gc_combine(GRECT * frame,GRECT * test)163 static void gc_combine(GRECT *frame,GRECT *test){
164 if(!frame || !test)
165 return;
166 if(frame->g_x>test->g_x){
167 frame->g_w+=frame->g_x-test->g_x;
168 frame->g_x=test->g_x;
169 }
170 if(frame->g_y>test->g_y){
171 frame->g_h+=frame->g_y-test->g_y;
172 frame->g_y=test->g_y;
173 }
174 if(frame->g_x+frame->g_w<test->g_x+test->g_w)
175 frame->g_w=test->g_x+test->g_w-frame->g_x;
176 if(frame->g_y+frame->g_h<test->g_y+test->g_h)
177 frame->g_h=test->g_y+test->g_h-frame->g_y;
178 }
gc_area(GRECT * area)179 static long gc_area(GRECT *area){
180 return((long)area->g_h*(long)area->g_w);
181 }
182