4 * Copyright (c) 2010-2013 Samsung Electronics Co., Ltd. All rights reserved.
6 * Licensed under the Apache License, Version 2.0 (the "License");
7 * you may not use this file except in compliance with the License.
8 * You may obtain a copy of the License at
10 * http://www.apache.org/licenses/LICENSE-2.0
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
20 * location_boundary_if_inside(LocationBoundary* boundary,
21 * LocationPosition* position)
24 * Copyright (c) 1970-2003, Wm. Randolph Franklin
26 * Permission is hereby granted, free of charge, to any person obtaining a copy
27 * of this software and associated documentation files (the "Software"),
28 * to deal in the Software without restriction, including without limitation
29 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
30 * and/or sell copies of the Software, and to permit persons to whom
31 * the Software is furnished to do so, subject to the following conditions:
33 * 1.Redistributions of source code must retain the above copyright notice,
34 * this list of conditions and the following disclaimers.
35 * 2.Redistributions in binary form must reproduce the above copyright notice
36 * in the documentation and/or other materials provided with the distribution.
37 * 3.The name of W. Randolph Franklin may not be used to endorse or promote
38 * products derived from this Software without specific prior written permission.
41 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
42 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
43 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
44 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
45 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
46 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
51 * location_boundary_get_center_position (LocationBoundary *boundary)
52 * algorithm from http://en.wikipedia.org/wiki/Centroid
62 #include "location-boundary.h"
63 #include "location-common-util.h"
64 #include "location-log.h"
65 #include "location-position.h"
66 #define DEG2RAD(x) ((x) * M_PI / 180)
67 #define RAD2DEG(x) ((x) * 180 / M_PI)
68 #define EARTH_RADIUS 6371009
70 static double mercator(double latitude)
72 return log(tan(latitude * 0.5 + M_PI / 4));
75 static double inverseMercator(double x)
77 return 2 * atan(exp(x)) - M_PI / 2;
80 static double wrap(double n, double min, double max)
82 return (n >= min && n < max) ? n : (fmod(n - min, max - min) + min);
86 location_boundary_get_type(void)
88 static volatile gsize type_volatile = 0;
89 if (g_once_init_enter(&type_volatile)) {
90 GType type = g_boxed_type_register_static(
91 g_intern_static_string("LocationBoundary"),
92 (GBoxedCopyFunc) location_boundary_copy,
93 (GBoxedFreeFunc) location_boundary_free);
94 g_once_init_leave(&type_volatile, type);
99 static void _append_polygon_position(gpointer data, gpointer user_data)
101 g_return_if_fail(data);
102 g_return_if_fail(user_data);
104 LocationBoundary *boundary = (LocationBoundary *)user_data;
105 LocationPosition *position = (LocationPosition *)data;
106 LocationPosition *new_position = location_position_copy(position);
108 boundary->polygon.position_list = g_list_append(boundary->polygon.position_list, new_position);
111 static void _free_polygon_position(gpointer data)
113 g_return_if_fail(data);
115 LocationPosition *position = (LocationPosition *)data;
116 location_position_free(position);
119 EXPORT_API LocationBoundary *
120 location_boundary_new_for_rect(LocationPosition *left_top, LocationPosition *right_bottom)
122 g_return_val_if_fail(left_top, NULL);
123 g_return_val_if_fail(right_bottom, NULL);
125 gdouble lon_interval = right_bottom->longitude - left_top->longitude;
127 if (lon_interval < 180 && lon_interval > -180) {
128 if (right_bottom->longitude <= left_top->longitude || right_bottom->latitude >= left_top->latitude)
131 if (right_bottom->latitude >= left_top->latitude)
135 LocationBoundary *boundary = g_slice_new0(LocationBoundary);
136 g_return_val_if_fail(boundary, NULL);
138 boundary->type = LOCATION_BOUNDARY_RECT;
139 boundary->rect.left_top = location_position_copy(left_top);
140 boundary->rect.right_bottom = location_position_copy(right_bottom);
144 EXPORT_API LocationBoundary *
145 location_boundary_new_for_circle(LocationPosition *center, gdouble radius)
147 g_return_val_if_fail(center, NULL);
148 g_return_val_if_fail(radius > 0, NULL);
149 LocationBoundary *boundary = g_slice_new0(LocationBoundary);
150 g_return_val_if_fail(boundary, NULL);
152 boundary->type = LOCATION_BOUNDARY_CIRCLE;
153 boundary->circle.center = location_position_copy(center);
154 boundary->circle.radius = radius;
158 EXPORT_API LocationBoundary *
159 location_boundary_new_for_polygon(GList *position_list)
161 g_return_val_if_fail(position_list, NULL);
162 g_return_val_if_fail(g_list_length(position_list) > 2, NULL);
164 LocationBoundary *boundary = g_slice_new0(LocationBoundary);
165 g_return_val_if_fail(boundary, NULL);
167 g_list_foreach(position_list, (GFunc)_append_polygon_position, boundary);
168 boundary->type = LOCATION_BOUNDARY_POLYGON;
169 boundary->polygon.position_list = g_list_first(boundary->polygon.position_list);
175 location_boundary_free(LocationBoundary *boundary)
177 g_return_if_fail(boundary);
179 if (boundary->type == LOCATION_BOUNDARY_RECT) {
180 location_position_free(boundary->rect.left_top);
181 location_position_free(boundary->rect.right_bottom);
182 } else if (boundary->type == LOCATION_BOUNDARY_CIRCLE) {
183 location_position_free(boundary->circle.center);
184 } else if (boundary->type == LOCATION_BOUNDARY_POLYGON) {
185 g_list_free_full(boundary->polygon.position_list, (GDestroyNotify)_free_polygon_position);
187 g_slice_free(LocationBoundary, boundary);
190 EXPORT_API LocationBoundary *
191 location_boundary_copy(const LocationBoundary *boundary)
193 g_return_val_if_fail(boundary, NULL);
194 if (boundary->type == LOCATION_BOUNDARY_RECT)
195 return location_boundary_new_for_rect(boundary->rect.left_top, boundary->rect.right_bottom);
196 else if (boundary->type == LOCATION_BOUNDARY_CIRCLE)
197 return location_boundary_new_for_circle(boundary->circle.center, boundary->circle.radius);
198 else if (boundary->type == LOCATION_BOUNDARY_POLYGON)
199 return location_boundary_new_for_polygon(boundary->polygon.position_list);
205 location_boundary_if_inside(LocationBoundary *boundary, LocationPosition *position)
207 g_return_val_if_fail(boundary, FALSE);
208 g_return_val_if_fail(position, FALSE);
210 gboolean is_inside = FALSE;
212 switch (boundary->type) {
213 case LOCATION_BOUNDARY_RECT: {
214 gdouble y = position->latitude;
215 gdouble x = position->longitude;
217 gdouble lt_y = boundary->rect.left_top->latitude;
218 gdouble lt_x = boundary->rect.left_top->longitude;
219 gdouble rb_y = boundary->rect.right_bottom->latitude;
220 gdouble rb_x = boundary->rect.right_bottom->longitude;
222 if (lt_x - rb_x < 180 && lt_x - rb_x > -180) {
223 if ((rb_y < y && y < lt_y) && (lt_x < x && x < rb_x)) {
224 LOCATION_LOGD("\tInside of Rectangular boundary");
228 if ((rb_y < y && y < lt_y) && (lt_x < x || x < rb_x)) {
229 LOCATION_LOGD("\tInside of Rectangular boundary near 180th meridian");
235 case LOCATION_BOUNDARY_CIRCLE: {
237 LocationPosition center;
240 center.latitude = boundary->circle.center->latitude;
241 center.longitude = boundary->circle.center->longitude;
243 location_get_distance(¢er, position, &distance);
244 if (distance < boundary->circle.radius) {
245 LOCATION_LOGD("\tInside Circle boundary");
250 case LOCATION_BOUNDARY_POLYGON: {
252 double interval_x = 0.0, interval_y = 0.0;
253 double x0 = 0.0, y0 = 0.0;
255 int crossing_num = 0;
256 GList *position_list = boundary->polygon.position_list;
257 GList *pos1_list = NULL;
258 GList *pos2_list = NULL;
259 LocationPosition *pos1 = NULL;
260 LocationPosition *pos2 = NULL;
262 pos1_list = g_list_first(position_list);
263 pos2_list = g_list_last(position_list);
266 pos1 = pos1_list->data;
267 pos2 = pos2_list->data;
268 interval_y = pos1->longitude - pos2->longitude;
269 interval_x = pos1->latitude - pos2->latitude;
271 * Case 1. -180 < longitude2 - longitude1 < 180 : normal case
272 * Case 2. longitude2 - longitude1 < -180 : interval_y = longitude2 - longitude1 + 360
273 * Case 3. longitude2 - longitude1 > 180 : intreval_y = longitude2 - longitude1 - 360
275 if (interval_y > 180) {
276 interval_y = interval_y - 360;
278 } else if (interval_y < -180) {
279 interval_y = interval_y + 360;
283 if (edge_area && (pos1->longitude > position->longitude) == (pos2->longitude > position->longitude)) {
284 if (pos2->longitude * position->longitude > 0) {
286 y0 = pos2->longitude;
289 y0 = pos1->longitude;
292 if (position->latitude < ((interval_x / interval_y) * (position->longitude - y0) + x0)) {
294 LOCATION_LOGD("Reverse");
297 } else if (!edge_area && (pos1->longitude > position->longitude) != (pos2->longitude > position->longitude)) {
299 y0 = pos2->longitude;
300 if (position->latitude < ((interval_x / interval_y) * (position->longitude - y0) + x0)) {
301 LOCATION_LOGD("Common");
304 } else LOCATION_LOGD("It is not crossed.");
306 pos2_list = pos1_list;
307 pos1_list = g_list_next(pos1_list);
309 LOCATION_LOGW("num[%d]", crossing_num);
310 is_inside = crossing_num & 1; /* Odd : inside, Even : outside */
315 LOCATION_LOGW("\tboundary type is undefined.[%d]", boundary->type);
324 location_boundary_on_path(LocationBoundary *boundary, LocationPosition *position, double tolerance)
326 g_return_val_if_fail(boundary, FALSE);
327 g_return_val_if_fail(position, FALSE);
328 g_return_val_if_fail(tolerance, FALSE);
330 switch (boundary->type) {
331 case LOCATION_BOUNDARY_RECT: {
332 double lt_x = boundary->rect.left_top->latitude;
333 double lt_y = boundary->rect.left_top->longitude;
334 double rb_x = boundary->rect.right_bottom->latitude;
335 double rb_y = boundary->rect.right_bottom->longitude;
336 GList *pos1_list = NULL;
337 GList *pos2_list = NULL;
338 LocationPosition *_position = location_position_new(0, lt_x, lt_y, 0.0, LOCATION_STATUS_2D_FIX);
339 pos1_list = g_list_append(pos1_list, _position);
340 _position = location_position_new(0, rb_x, lt_y, 0.0, LOCATION_STATUS_2D_FIX);
341 pos1_list = g_list_append(pos1_list, _position);
342 _position = location_position_new(0, rb_x, rb_y, 0.0, LOCATION_STATUS_2D_FIX);
343 pos1_list = g_list_append(pos1_list, _position);
344 _position = location_position_new(0, lt_x, rb_y, 0.0, LOCATION_STATUS_2D_FIX);
345 pos1_list = g_list_append(pos1_list, _position);
347 LocationPosition *pos1 = NULL;
348 LocationPosition *pos2 = NULL;
349 LocationPosition *pos = position;
350 LocationPosition *posClose = NULL;
351 double lat3 = DEG2RAD(pos->latitude);
352 double lon3 = DEG2RAD(pos->longitude);
353 double lat1 = 0.0, lon1 = 0.0, lat2 = 0.0, lon2 = 0.0;
354 double x1 = 0.0, y1 = 0.0, x2 = 0.0, x3 = 0.0, y3 = 0.0, xClose = 0.0, yClose = 0.0, latClose = 0.0, px = 0.0, norm = 0.0, u = 0.0, distance = 0.0;
355 double minBound = lat3 - tolerance/EARTH_RADIUS;
356 double maxBound = lat3 + tolerance/EARTH_RADIUS;
358 pos1_list = g_list_first(pos1_list);
359 pos2_list = g_list_last(pos1_list);
362 pos1 = pos1_list->data;
363 pos2 = pos2_list->data;
365 lat1 = DEG2RAD(pos1->latitude);
366 lon1 = DEG2RAD(pos1->longitude);
368 lat2 = DEG2RAD(pos2->latitude);
369 lon2 = DEG2RAD(pos2->longitude);
374 if(fmax(lat1, lat2) >= minBound && fmin(lat1, lat2) <= maxBound)
378 // longitudes values are offset by -lon2; the implicit y2 is 0.
379 y1 = wrap(lon1-lon2, - M_PI, M_PI);
380 y3 = wrap(lon3-lon2, - M_PI, M_PI);
383 norm = y1 * y1 + px * px;
387 u = ( y3 * y1 + ( x3 - x2 ) * px ) / norm;
394 xClose = x2 + u * px;
396 latClose = inverseMercator(xClose);
397 posClose = location_position_new(0, RAD2DEG(latClose), RAD2DEG(yClose + lon2), 0.0, LOCATION_STATUS_2D_FIX);
398 location_get_distance(pos, posClose, &distance);
399 if (posClose) location_position_free(posClose);
400 if(distance < tolerance)
405 pos2_list = pos1_list;
406 pos1_list = g_list_next(pos1_list);
411 if(_position) location_position_free(_position);
415 case LOCATION_BOUNDARY_CIRCLE: {
416 LocationPosition center;
419 center.latitude = boundary->circle.center->latitude;
420 center.longitude = boundary->circle.center->longitude;
422 location_get_distance(¢er, position, &distance);
423 if (distance < boundary->circle.radius + tolerance && distance > boundary->circle.radius - tolerance) {
429 case LOCATION_BOUNDARY_POLYGON: {
430 GList *position_list = boundary->polygon.position_list;
431 GList *pos1_list = NULL;
432 GList *pos2_list = NULL;
433 LocationPosition *pos1 = NULL;
434 LocationPosition *pos2 = NULL;
435 LocationPosition *pos = position;
436 LocationPosition *posClose = NULL;
437 double lat3 = DEG2RAD(pos->latitude);
438 double lon3 = DEG2RAD(pos->longitude);
439 double lat1 = 0.0, lon1 = 0.0, lat2 = 0.0, lon2 = 0.0;
440 double x1 = 0.0, y1 = 0.0, x2 = 0.0, x3 = 0.0, y3 = 0.0, xClose = 0.0, yClose = 0.0, latClose = 0.0, px = 0.0, norm = 0.0, u = 0.0, distance = 0.0;
441 double minBound = lat3 - tolerance/EARTH_RADIUS;
442 double maxBound = lat3 + tolerance/EARTH_RADIUS;
444 pos1_list = g_list_first(position_list);
445 pos2_list = g_list_last(position_list);
448 pos1 = pos1_list->data;
449 pos2 = pos2_list->data;
451 lat1 = DEG2RAD(pos1->latitude);
452 lon1 = DEG2RAD(pos1->longitude);
454 lat2 = DEG2RAD(pos2->latitude);
455 lon2 = DEG2RAD(pos2->longitude);
460 if(fmax(lat1, lat2) >= minBound && fmin(lat1, lat2) <= maxBound)
464 // longitudes values are offset by -lon2; the implicit y2 is 0.
465 y1 = wrap(lon1-lon2, - M_PI, M_PI);
466 y3 = wrap(lon3-lon2, - M_PI, M_PI);
469 norm = y1 * y1 + px * px;
473 u = ( y3 * y1 + ( x3 - x2 ) * px ) / norm;
480 xClose = x2 + u * px;
482 latClose = inverseMercator(xClose);
483 posClose = location_position_new(0, RAD2DEG(latClose), RAD2DEG(yClose + lon2), 0.0, LOCATION_STATUS_2D_FIX);
484 location_get_distance(pos, posClose, &distance);
485 if (posClose) location_position_free(posClose);
486 if(distance < tolerance)
491 pos2_list = pos1_list;
492 pos1_list = g_list_next(pos1_list);
500 LOCATION_LOGW("\tboundary type is undefined.[%d]", boundary->type);
508 location_boundary_add(const LocationObject *obj, const LocationBoundary *boundary)
510 g_return_val_if_fail(obj, LOCATION_ERROR_PARAMETER);
511 g_return_val_if_fail(boundary, LOCATION_ERROR_PARAMETER);
513 GList *boundary_priv_list = NULL;
515 LocationBoundaryPrivate *priv = g_slice_new0(LocationBoundaryPrivate);
516 g_return_val_if_fail(priv, LOCATION_ERROR_PARAMETER);
518 priv->boundary = location_boundary_copy(boundary);
519 priv->zone_status = ZONE_STATUS_NONE;
521 boundary_priv_list = g_list_append(boundary_priv_list, (gpointer) priv);
523 g_object_set(G_OBJECT(obj), "boundary", boundary_priv_list, NULL);
525 g_list_free(boundary_priv_list);
527 return LOCATION_ERROR_NONE;
531 location_boundary_remove(const LocationObject *obj, const LocationBoundary *boundary)
533 g_return_val_if_fail(obj, LOCATION_ERROR_PARAMETER);
534 g_return_val_if_fail(boundary, LOCATION_ERROR_PARAMETER);
536 g_object_set(G_OBJECT(obj), "removal-boundary", boundary, NULL);
538 return LOCATION_ERROR_NONE;
542 location_boundary_foreach(const LocationObject *obj, LocationBoundaryFunc func, gpointer user_data)
544 g_return_val_if_fail(obj, LOCATION_ERROR_PARAMETER);
545 g_return_val_if_fail(func, LOCATION_ERROR_PARAMETER);
548 GList *boundary_priv_list = NULL;
549 GList *boundary_list = NULL;
550 LocationBoundaryPrivate *priv;
552 g_object_get(G_OBJECT(obj), "boundary", &boundary_priv_list, NULL);
554 if (boundary_priv_list == NULL) {
555 LOCATION_LOGD("There is no boundary.");
556 return LOCATION_ERROR_UNKNOWN;
559 while ((priv = (LocationBoundaryPrivate *)g_list_nth_data(boundary_priv_list, index)) != NULL) {
560 boundary_list = g_list_append(boundary_list, (gpointer) priv->boundary);
564 g_list_foreach(boundary_list, (GFunc)func, user_data);
565 g_list_free(boundary_list);
567 return LOCATION_ERROR_NONE;
570 EXPORT_API LocationBoundary *
571 location_boundary_get_bounding_box(LocationBoundary *boundary)
573 g_return_val_if_fail(boundary, NULL);
574 LocationBoundary *bbox = NULL;
579 EXPORT_API LocationPosition *
580 location_boundary_get_center_position(LocationBoundary *boundary)
582 g_return_val_if_fail(boundary, NULL);
584 LocationPosition *center = NULL;
586 switch (boundary->type) {
587 case LOCATION_BOUNDARY_RECT: {
588 gdouble latitude, longitude, altitude;
589 latitude = (boundary->rect.left_top->latitude + boundary->rect.right_bottom->latitude) / 2.0;
590 longitude = (boundary->rect.left_top->longitude + boundary->rect.right_bottom->longitude) / 2.0;
591 altitude = (boundary->rect.left_top->altitude + boundary->rect.right_bottom->altitude) / 2.0;
593 center = location_position_new(boundary->rect.left_top->timestamp, latitude, longitude, altitude, boundary->rect.left_top->status);
596 case LOCATION_BOUNDARY_CIRCLE: {
597 center = location_position_copy(boundary->circle.center);
600 case LOCATION_BOUNDARY_POLYGON: {
601 gdouble center_latitude = 0.0;
602 gdouble center_longitude = 0.0;
607 GList *position_list = boundary->polygon.position_list;
608 GList *pos1_list = g_list_first(position_list);
609 GList *pos2_list = g_list_next(pos1_list);
610 LocationPosition *pos1 = NULL;
611 LocationPosition *pos2 = NULL;
614 pos1 = pos1_list->data;
615 pos2 = pos2_list->data;
617 x1 = pos1->latitude + 90.0;
618 y1 = pos1->longitude + 180.0;
619 x2 = pos2->latitude + 90.0;
620 y2 = pos2->longitude + 180.0;
622 center_latitude += (x1 + x2) * (x1 * y2 - x2 * y1);
623 center_longitude += (y1 + y2) * (x1 * y2 - x2 * y1);
624 area += x1 * y2 - x2 * y1;
626 pos1_list = pos2_list;
627 pos2_list = g_list_next(pos2_list);
630 pos2_list = g_list_first(position_list);
631 pos1 = pos1_list->data;
632 pos2 = pos2_list->data;
634 x1 = pos1->latitude + 90.0;
635 y1 = pos1->longitude + 180.0;
636 x2 = pos2->latitude + 90.0;
637 y2 = pos2->longitude + 180.0;
639 center_latitude += (x1 + x2) * (x1 * y2 - x2 * y1);
640 center_longitude += (y1 + y2) * (x1 * y2 - x2 * y1);
641 area += x1 * y2 - x2 * y1;
643 area = fabs(area / 2.0);
645 center_latitude = (center_latitude - 90.0) / (6.0 * area);
646 center_longitude = (center_longitude - 180.0) / (6.0 * area);
647 center = location_position_new(0, center_latitude, center_longitude, 0, LOCATION_STATUS_2D_FIX);