Graphviz 13.1.3~dev.20250813.2319
Loading...
Searching...
No Matches
furtherest_point.c
Go to the documentation of this file.
1/*************************************************************************
2 * Copyright (c) 2011 AT&T Intellectual Property
3 * All rights reserved. This program and the accompanying materials
4 * are made available under the terms of the Eclipse Public License v1.0
5 * which accompanies this distribution, and is available at
6 * https://www.eclipse.org/legal/epl-v10.html
7 *
8 * Contributors: Details at https://graphviz.org
9 *************************************************************************/
10
11#include <sparse/general.h>
12#include <sparse/QuadTree.h>
14#include <stdbool.h>
15#include <stddef.h>
16#include <string.h>
17#include <util/alloc.h>
18#include <util/gv_math.h>
19#include <util/list.h>
20#include <util/prisize_t.h>
21
22static double dist(int dim, double *x, double *y){
23 int k;
24 double d = 0;
25 for (k = 0; k < dim; k++) d += (x[k] - y[k])*(x[k]-y[k]);
26 return sqrt(d);
27}
28
29
30static double distance_to_group(int k, int dim, double *wgt, double *pts, double *center){
31 int i;
32 double distance = -1, dist_min = 0;
33 if (!wgt){
34 for (i = 0; i < k; i++){
35 distance = dist(dim, &(pts[i*dim]), center);
36 if (i == 0){
37 dist_min = distance;
38 } else {
39 dist_min = MIN(dist_min, distance);
40 }
41 }
42 } else {
43 for (i = 0; i < k; i++){
44 distance = dist(dim, &(pts[i*dim]), center);
45 if (i == 0){
46 dist_min = wgt[i]*distance;
47 } else {
48 dist_min = MIN(dist_min, wgt[i]*distance);
49 }
50 }
51 }
52 return dist_min;
53}
54
55DEFINE_LIST(qt_list, QuadTree)
56
57void furtherest_point(int k, int dim, double *wgt, double *pts, double *center, double width, int max_level, double *dist_max, double **argmax){
58 /* Assume that in the box defined by {center, width} are feasible;
59 find, in the, a point "furtherest_point" that is furtherest away from a group of k-points pts, using quadtree,
60 with up to max_level. Here the distance of a point to a group of point is defined as the minimum
61 of the distance of that point to all the points in the group,
62 and each distance is defined by the function dist.
63
64 Input:
65
66 k: number of points in the group
67 dim: dimension
68 wgt: if not null, the weighting factor for the i-th point is wgt[i]. The color distance
69 . of a point p to a group of points pts is min_i(wgt[i]*dist(p, pts[i])), instead of min_i(dist(p, pts[i]))
70 pts: the i-th point is [i*k, (i+1)*k)
71 center: the center of the root of quadtree
72 width: the width of the root
73 max_level: max level to go down
74 argmax: on entry, if NULL, will be allocated, iotherwise must be an array of size >= dim which will hold the furtherest point.
75
76 Return: the point (argmax) furtherest away from the group, and the distance dist_max.
77 */
78 QuadTree qt, qt0;
79 double distance;
80 int level = 0;
81 int ii, j;
82 double wmax = 0;
83
84 if (wgt){
85 for (int i = 0; i < k; i++) wmax = MAX(wgt[i], wmax);
86 } else {
87 wmax = 1.;
88 }
89
90 qt0 = qt = QuadTree_new(dim, center, width, max_level);
91
92 qt->total_weight = *dist_max = distance_to_group(k, dim, wgt, pts, center);/* store distance in total_weight */
93 if (!(*argmax)) *argmax = gv_calloc(dim, sizeof(double));
94 memcpy(*argmax, center, sizeof(double)*dim);
95
96 qt_list_t candidates = {0};
97 qt_list_t candidates2 = {0};
98 qt_list_append(&candidates, qt);
99
100 /* idea: maintain the current best point and best (largest) distance. check the list of candidate. Subdivide each into quadrants, if any quadrant gives better distance, update, and put on the candidate
101 list. If we can not prune a quadrant (a quadrant can be pruned if the distance of its center to the group of points pts, plus that from the center to the corner of the quadrant, is smaller than the best), we
102 also put it down on the candidate list. We then recurse on the candidate list, unless the max level is reached. */
103 while (level++ < max_level){
104 if (Verbose > 10) {
105 fprintf(stderr,"level=%d=================\n", level);
106 }
107 qt_list_clear(&candidates2);
108 for (size_t i = 0; i < qt_list_size(&candidates); i++){
109
110
111 qt = qt_list_get(&candidates, i);
112 assert(!(qt->qts));
113
114 if (Verbose > 10) {
115 fprintf(stderr, "candidate %" PRISIZE_T " at {", i);
116 for (j = 0; j < dim; j++) fprintf(stderr,"%f, ", qt->center[j]);
117 fprintf(stderr,"}, width = %f, dist = %f\n", qt->width, qt->total_weight);
118 }
119
120 distance = qt->total_weight;/* total_weight is used to store the distance from the center to the group */
121 if (distance + wmax*sqrt(((double) dim))*qt->width < *dist_max) continue;/* this could happen if this candidate was entered into the list earlier than a better one later in the list */
122 qt->qts = gv_calloc((size_t)1 << dim, sizeof(QuadTree));
123 for (ii = 0; ii < 1<<dim; ii++) {
124 qt->qts[ii] = QuadTree_new_in_quadrant(qt->dim, qt->center, (qt->width)/2, max_level, ii);
125 qt->qts[ii]->total_weight = distance = distance_to_group(k, dim, wgt, pts, qt->qts[ii]->center);/* store distance in total_weight */
126 bool pruned = false;
127 if (distance > *dist_max){
128 *dist_max = distance;
129 if (Verbose > 10) {
130 fprintf(stderr,"new distmax=%f, pt={", *dist_max);
131 for (j = 0; j < dim; j++) fprintf(stderr,"%f, ", qt->qts[ii]->center[j]);
132 fprintf(stderr,"}\n");
133 }
134 memcpy(*argmax, qt->qts[ii]->center, sizeof(double)*dim);
135 } else if (distance + wmax*sqrt(((double) dim))*(qt->width)/2 < *dist_max){
136 pruned = true;
137 }
138 if (!pruned){
139 qt_list_append(&candidates2, qt->qts[ii]);
140 }
141 }/* finish checking every of the 2^dim siblings */
142 }/* finish checking all the candidates */
143
144 SWAP(&candidates, &candidates2);
145
146 }/* continue down the quadtree */
147
148 QuadTree_delete(qt0);
149
150 qt_list_free(&candidates);
151 qt_list_free(&candidates2);
152}
153
154void furtherest_point_in_list(int k, int dim, double *wgt, double *pts, QuadTree qt, int max_level,
155 double *dist_max, double **argmax){
156 /* Given a list of points in the Euclidean space contained in the quadtree qt (called the feasible points), find among them one that
157 is closest to another list of point {dim, k, pts}.
158
159
160 find, in the, a point "furtherest_point" that is furtherest away from a group of k-points pts, using quadtree,
161 with up to max_level. Here the distance of a point to a group of point is defined as the minimum
162 of the distance of that point to all the points in the group,
163 and each distance is defined by the function dist.
164
165 Input:
166
167 k: number of points in the group
168 dim: dimension
169 wgt: if not null, the weighting factor for the i-th point is wgt[i]. The color distance
170 . of a point p to a group of points pts is min_i(wgt[i]*dist(p, pts[i])), instead of min_i(dist(p, pts[i]))
171 pts: the i-th point is [i*k, (i+1)*k)
172 center: the center of the root of quadtree
173 width: the width of the root
174 max_level: max level to go down
175 argmax: on entry, if NULL, will be allocated, otherwise must be an array of size >= dim which will hold the furtherest point.
176
177 Return: the point (argmax) furtherest away from the group, and the distance dist_max.
178 */
179
180 double distance;
181 int level = 0;
182 int ii, j;
183 double *average;
184 double wmax = 0.;
185
186 if (wgt){
187 for (int i = 0; i < k; i++) wmax = MAX(wgt[i], wmax);
188 } else {
189 wmax = 1.;
190 }
191
192 average = qt->average;
193 qt->total_weight = *dist_max = distance_to_group(k, dim, wgt, pts, average);/* store distance in total_weight */
194 if (!(*argmax)) *argmax = gv_calloc(dim, sizeof(double));
195 memcpy(*argmax, average, sizeof(double)*dim);
196
197 qt_list_t candidates = {0};
198 qt_list_t candidates2 = {0};
199 qt_list_append(&candidates, qt);
200
201 /* idea: maintain the current best point and best (largest) distance. check the list of candidate. Subdivide each into quadrants, if any quadrant gives better distance, update, and put on the candidate
202 list. If we can not prune a quadrant (a quadrant can be pruned if the distance of its center to the group of points pts, plus that from the center to the corner of the quadrant, is smaller than the best), we
203 also put it down on the candidate list. We then recurse on the candidate list, unless the max level is reached. */
204 while (level++ < max_level){
205 if (Verbose > 10) {
206 fprintf(stderr,"level=%d=================\n", level);
207 }
208 qt_list_clear(&candidates2);
209 for (size_t i = 0; i < qt_list_size(&candidates); i++){
210 qt = qt_list_get(&candidates, i);
211
212 if (Verbose > 10) {
213 fprintf(stderr,"candidate %" PRISIZE_T " at {", i);
214 for (j = 0; j < dim; j++) fprintf(stderr,"%f, ", qt->center[j]);
215 fprintf(stderr,"}, width = %f, dist = %f\n", qt->width, qt->total_weight);
216 }
217
218 distance = qt->total_weight;/* total_weight is used to store the distance from average feasible points to the group */
219 if (qt->n == 1 || distance + wmax*2*sqrt(((double) dim))*qt->width < *dist_max) continue;/* this could happen if this candidate was entered into the list earlier than a better one later in the list. Since the distance
220 is from the average of the feasible points in the square which may not be at the center */
221
222 if (!(qt->qts)) continue;
223
224 for (ii = 0; ii < 1<<dim; ii++) {
225 if (!(qt->qts[ii])) continue;
226 qt->qts[ii]->total_weight = distance = distance_to_group(k, dim, wgt, pts, qt->qts[ii]->average);/* store distance in total_weight */
227 bool pruned = false;
228 if (distance > *dist_max){
229 *dist_max = distance;
230 if (Verbose > 10) {
231 fprintf(stderr,"new distmax=%f, pt={", *dist_max);
232 for (j = 0; j < dim; j++) fprintf(stderr,"%f, ", qt->qts[ii]->average[j]);
233 fprintf(stderr,"}\n");
234 }
235 memcpy(*argmax, qt->qts[ii]->average, sizeof(double)*dim);
236 } else if (distance + wmax*sqrt(((double) dim))*(qt->width) < *dist_max){/* average feasible point in this square is too close to the point set */
237 pruned = true;
238 }
239 if (!pruned){
240 qt_list_append(&candidates2, qt->qts[ii]);
241 }
242 }/* finish checking every of the 2^dim siblings */
243 }/* finish checking all the candidates */
244
245 SWAP(&candidates, &candidates2);
246
247 }/* continue down the quadtree */
248
249 qt_list_free(&candidates);
250 qt_list_free(&candidates2);
251}
QuadTree QuadTree_new_in_quadrant(int dim, double *center, double width, int max_level, int i)
Definition QuadTree.c:413
QuadTree QuadTree_new(int dim, double *center, double width, int max_level)
Definition QuadTree.c:357
void QuadTree_delete(QuadTree q)
Definition QuadTree.c:375
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
#define MIN(a, b)
Definition arith.h:28
void furtherest_point_in_list(int k, int dim, double *wgt, double *pts, QuadTree qt, int max_level, double *dist_max, double **argmax)
static double dist(int dim, double *x, double *y)
static double distance_to_group(int k, int dim, double *wgt, double *pts, double *center)
void furtherest_point(int k, int dim, double *wgt, double *pts, double *center, double width, int max_level, double *dist_max, double **argmax)
double distance(double *x, int dim, int i, int j)
Definition general.c:121
static bool Verbose
Definition gml2gv.c:24
Arithmetic helper functions.
#define SWAP(a, b)
Definition gv_math.h:131
#define DEFINE_LIST(name, type)
Definition list.h:22
static const int dim
#define PRISIZE_T
Definition prisize_t.h:25
double total_weight
Definition QuadTree.h:37
double * average
Definition QuadTree.h:42
QuadTree * qts
Definition QuadTree.h:43
double * center
Definition QuadTree.h:39
static point center(point vertex[], size_t n)
#define MAX(a, b)
Definition write.c:32