1 /* aNetHack 0.0.1 gr_rect.c $ANH-Date: 1432512810 2015/05/25 00:13:30 $ $ANH-Branch: master $:$ANH-Revision: 1.7 $ */
3 /* Copyright (c) Christian Bressler, 2001 */
4 /* aNetHack may be freely redistributed. See license for details. */
5 /* This is an almost exact copy of qt_clust.cpp */
12 new_dirty_rect(int size
)
14 dirty_rect
*new = NULL
;
16 new = (dirty_rect
*) calloc(1L, sizeof(dirty_rect
));
18 new->rects
= (GRECT
*) calloc((long) size
, sizeof(GRECT
));
19 if (new->rects
== NULL
) {
29 delete_dirty_rect(dirty_rect
*this)
35 /* In case the Pointer is reused wrongly */
41 static int gc_inside(GRECT
*frame
, GRECT
*test
);
42 static int gc_touch(GRECT
*frame
, GRECT
*test
);
43 static void gc_combine(GRECT
*frame
, GRECT
*test
);
44 static long gc_area(GRECT
*area
);
46 add_dirty_rect(dirty_rect
*dr
, GRECT
*area
)
49 long lowestcost
= 9999999L;
51 int cheapestmerge1
= -1;
52 int cheapestmerge2
= -1;
55 for (cursor
= 0; cursor
< dr
->used
; cursor
++) {
56 if (gc_inside(&dr
->rects
[cursor
], area
)) {
57 /* Wholly contained already. */
61 for (cursor
= 0; cursor
< dr
->used
; cursor
++) {
62 if (gc_touch(&dr
->rects
[cursor
], area
)) {
63 GRECT larger
= dr
->rects
[cursor
];
65 gc_combine(&larger
, area
);
66 cost
= gc_area(&larger
) - gc_area(&dr
->rects
[cursor
]);
67 if (cost
< lowestcost
) {
69 for (c
= 0; c
< dr
->used
&& !bad
; c
++) {
70 bad
= gc_touch(&dr
->rects
[c
], &larger
) && c
!= cursor
;
80 gc_combine(&dr
->rects
[cheapest
], area
);
83 if (dr
->used
< dr
->max
) {
84 dr
->rects
[dr
->used
++] = *area
;
88 // add to closest cluster
89 // do cheapest cluster merge, add to new cluster
90 lowestcost
= 9999999L;
92 for (cursor
= 0; cursor
< dr
->used
; cursor
++) {
93 GRECT larger
= dr
->rects
[cursor
];
95 gc_combine(&larger
, area
);
96 cost
= gc_area(&larger
) - gc_area(&dr
->rects
[cursor
]);
97 if (cost
< lowestcost
) {
99 for (c
= 0; c
< dr
->used
&& !bad
; c
++) {
100 bad
= gc_touch(&dr
->rects
[c
], &larger
) && c
!= cursor
;
108 // XXX could make an heuristic guess as to whether we
109 // XXX need to bother looking for a cheap merge.
110 for (merge1
= 0; merge1
< dr
->used
; merge1
++) {
111 for (merge2
= 0; merge2
< dr
->used
; merge2
++) {
112 if (merge1
!= merge2
) {
113 GRECT larger
= dr
->rects
[merge1
];
115 gc_combine(&larger
, &dr
->rects
[merge2
]);
116 cost
= gc_area(&larger
) - gc_area(&dr
->rects
[merge1
])
117 - gc_area(&dr
->rects
[merge2
]);
118 if (cost
< lowestcost
) {
120 for (c
= 0; c
< dr
->used
&& !bad
; c
++) {
121 bad
= gc_touch(&dr
->rects
[c
], &larger
) && c
!= cursor
;
124 cheapestmerge1
= merge1
;
125 cheapestmerge2
= merge2
;
132 if (cheapestmerge1
>= 0) {
133 gc_combine(&dr
->rects
[cheapestmerge1
], &dr
->rects
[cheapestmerge2
]);
134 dr
->rects
[cheapestmerge2
] = dr
->rects
[dr
->used
- 1];
135 dr
->rects
[dr
->used
- 1] = *area
;
137 gc_combine(&dr
->rects
[cheapest
], area
);
139 // NB: clusters do not intersect (or intersection will
140 // overwrite). This is a result of the above algorithm,
141 // given the assumption that (x,y) are ordered topleft
146 get_dirty_rect(dirty_rect
*dr
, GRECT
*area
)
148 if (dr
== NULL
|| area
== NULL
|| dr
->rects
== NULL
|| dr
->used
<= 0
151 *area
= dr
->rects
[--dr
->used
];
155 clear_dirty_rect(dirty_rect
*dr
)
162 resize_dirty_rect(dirty_rect
*dr
, int new_size
)
167 gc_inside(GRECT
*frame
, GRECT
*test
)
169 if (frame
&& test
&& frame
->g_x
<= test
->g_x
&& frame
->g_y
<= test
->g_y
170 && frame
->g_x
+ frame
->g_w
>= test
->g_x
+ test
->g_w
171 && frame
->g_y
+ frame
->g_h
>= test
->g_y
+ test
->g_h
)
176 gc_touch(GRECT
*frame
, GRECT
*test
)
178 GRECT tmp
= { test
->g_x
- 1, test
->g_y
- 1, test
->g_w
+ 2,
180 return (rc_intersect(frame
, &tmp
));
183 gc_combine(GRECT
*frame
, GRECT
*test
)
187 if (frame
->g_x
> test
->g_x
) {
188 frame
->g_w
+= frame
->g_x
- test
->g_x
;
189 frame
->g_x
= test
->g_x
;
191 if (frame
->g_y
> test
->g_y
) {
192 frame
->g_h
+= frame
->g_y
- test
->g_y
;
193 frame
->g_y
= test
->g_y
;
195 if (frame
->g_x
+ frame
->g_w
< test
->g_x
+ test
->g_w
)
196 frame
->g_w
= test
->g_x
+ test
->g_w
- frame
->g_x
;
197 if (frame
->g_y
+ frame
->g_h
< test
->g_y
+ test
->g_h
)
198 frame
->g_h
= test
->g_y
+ test
->g_h
- frame
->g_y
;
203 return ((long) area
->g_h
* (long) area
->g_w
);