1 /*****************************************************************************
2 Copyright (c) 2014, 2021, Oracle and/or its affiliates.
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License, version 2.0,
6 as published by the Free Software Foundation.
7
8 This program is also distributed with certain software (including
9 but not limited to OpenSSL) that is licensed under separate terms,
10 as designated in a particular file or component or in included license
11 documentation. The authors of MySQL hereby grant you an additional
12 permission to link the program and your derivative works with the
13 separately licensed software that they have included with MySQL.
14
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License, version 2.0, for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software Foundation,
22 51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
23 *****************************************************************************/
24
25 /**************************************************//**
26 @file gis0geo.h
27 The r-tree define from MyISAM
28 *******************************************************/
29
30 #ifndef _gis0geo_h
31 #define _gis0geo_h
32
33 #include "my_global.h"
34 #include "string.h"
35
36 #define SPTYPE HA_KEYTYPE_DOUBLE
37 #define SPLEN 8
38
39 /* Since the mbr could be a point or a linestring, in this case, area of
40 mbr is 0. So, we define this macro for calculating the area increasing
41 when we need to enlarge the mbr. */
42 #define LINE_MBR_WEIGHTS 0.001
43
44 /* Types of "well-known binary representation" (wkb) format. */
45 enum wkbType
46 {
47 wkbPoint = 1,
48 wkbLineString = 2,
49 wkbPolygon = 3,
50 wkbMultiPoint = 4,
51 wkbMultiLineString = 5,
52 wkbMultiPolygon = 6,
53 wkbGeometryCollection = 7
54 };
55
56 /* Byte order of "well-known binary representation" (wkb) format. */
57 enum wkbByteOrder
58 {
59 wkbXDR = 0, /* Big Endian */
60 wkbNDR = 1 /* Little Endian */
61 };
62
63 /** Get the wkb of default POINT value, which represents POINT(0 0)
64 if it's of dimension 2, etc.
65 @param[in] n_dims dimensions
66 @param[out] wkb wkb buffer for default POINT
67 @param[in] len length of wkb buffer
68 @return non-0 indicate the length of wkb of the default POINT,
69 0 if the buffer is too small */
70 uint
71 get_wkb_of_default_point(
72 uint n_dims,
73 uchar* wkb,
74 uint len);
75
76 /*************************************************************//**
77 Calculate minimal bounding rectangle (mbr) of the spatial object
78 stored in "well-known binary representation" (wkb) format.
79 @return 0 if ok */
80 int
81 rtree_mbr_from_wkb(
82 /*===============*/
83 uchar* wkb, /*!< in: pointer to wkb. */
84 uint size, /*!< in: size of wkb. */
85 uint n_dims, /*!< in: dimensions. */
86 double* mbr); /*!< in/out: mbr. */
87
88 /* Rtree split node structure. */
89 struct rtr_split_node_t
90 {
91 double square; /* square of the mbr.*/
92 int n_node; /* which group in.*/
93 uchar* key; /* key. */
94 double* coords; /* mbr. */
95 };
96
97 /*************************************************************//**
98 Inline function for reserving coords */
99 inline
100 static
101 double*
reserve_coords(double ** d_buffer,int n_dim)102 reserve_coords(double **d_buffer, /*!< in/out: buffer. */
103 int n_dim) /*!< in: dimensions. */
104 /*===========*/
105 {
106 double *coords = *d_buffer;
107 (*d_buffer) += n_dim * 2;
108 return coords;
109 }
110
111 /*************************************************************//**
112 Split rtree nodes.
113 Return which group the first rec is in. */
114 int
115 split_rtree_node(
116 /*=============*/
117 rtr_split_node_t* node, /*!< in: split nodes.*/
118 int n_entries, /*!< in: entries number.*/
119 int all_size, /*!< in: total key's size.*/
120 int key_size, /*!< in: key's size.*/
121 int min_size, /*!< in: minimal group size.*/
122 int size1, /*!< in: size of group.*/
123 int size2, /*!< in: initial group sizes */
124 double** d_buffer, /*!< in/out: buffer.*/
125 int n_dim, /*!< in: dimensions. */
126 uchar* first_rec); /*!< in: the first rec. */
127
128 /*************************************************************//**
129 Compares two keys a and b depending on nextflag
130 nextflag can contain these flags:
131 MBR_INTERSECT(a,b) a overlaps b
132 MBR_CONTAIN(a,b) a contains b
133 MBR_DISJOINT(a,b) a disjoint b
134 MBR_WITHIN(a,b) a within b
135 MBR_EQUAL(a,b) All coordinates of MBRs are equal
136 MBR_DATA(a,b) Data reference is the same
137 Returns 0 on success. */
138 int
139 rtree_key_cmp(
140 /*==========*/
141 page_cur_mode_t mode, /*!< in: compare method. */
142 const uchar* b, /*!< in: first key. */
143 int b_len, /*!< in: first key len. */
144 const uchar* a, /*!< in: second key. */
145 int a_len); /*!< in: second key len. */
146
147 /*************************************************************//**
148 Calculates MBR_AREA(a+b) - MBR_AREA(a)
149 Note: when 'a' and 'b' objects are far from each other,
150 the area increase can be really big, so this function
151 can return 'inf' as a result. */
152 double
153 rtree_area_increase(
154 const uchar* a, /*!< in: first mbr. */
155 const uchar* b, /*!< in: second mbr. */
156 int a_len, /*!< in: mbr length. */
157 double* ab_area); /*!< out: increased area. */
158
159 /** Calculates overlapping area
160 @param[in] a mbr a
161 @param[in] b mbr b
162 @param[in] mbr_len mbr length
163 @return overlapping area */
164 double
165 rtree_area_overlapping(
166 const uchar* a,
167 const uchar* b,
168 int mbr_len);
169 #endif
170