[63a589]: src / libgeoc / ptopol.h Maximize Restore History

Download this file

ptopol.h    869 lines (864 with data), 51.6 kB

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
/* -*- coding: utf-8 -*- */
/**
\ingroup geom
@{
\file ptopol.h
\brief Declaración de funciones para la realización de chequeos de inclusión de
puntos en polígonos.
En el momento de la compilación ha de seleccionarse el tipo de dato que se
utilizará en los cálculos intermedios de las funciones
\ref PtoEnPoligonoVerticeBorde y \ref PtoEnPoligonoVerticeBordeDouble. Si los
puntos de trabajo están muy alejados de los polígonos pueden darse casos de
resultados erróneos. Sería conveniente que los cálculos internedios se hiciesen
en variables de 64 bits, pero el tipo <tt>long int</tt> suele ser de 4 bytes en
procesadores de 32 bits. Para seleccionar este tipo como <tt>long long int</tt>,
lo que en procesadores de 32 bits equivale a una variable de 64 bits, es
necesario definir la variable para el preprocesador \em PTOPOL_BORDE_LONG_64. En
procesadores de 64 bits no es necesario (aunque puede utilizarse), ya que el
tipo <tt>long int</tt> tiene una longitud de 64 bits. Si no se define la
variable, se usará un tipo <tt>long int</tt> para los cálculos intermedios. En
\p gcc, las variables para el preprocesador se pasan como \em -DXXX, donde
\em XXX es la variable a introducir. El uso del tipo <tt>long long int</tt> en
procesadores de 32 bits puede hacer que las funciones se ejecuten hasta 10 veces
más lentamente que si se utiliza el tipo <tt>long int</tt>. Con cálculos
internos de 32 bits las coordenadas de los vértices del polígono no han de estar
más lejos de las de los puntos de trabajo de unas 40000 unidades. Con cálculos
de 64 bits, los polígonos pueden estar alejados de los puntos de trabajo unas
3000000000 unidades, lo que corresponde a coordenadas Y UTM ajustadas al
centímetro. Con esto podríamos chequear un punto en un polo con respecto a un
polígono en el ecuador en coordenadas UTM expresadas en centímetros.
\author José Luis García Pallero, jgpallero@gmail.com
\note Este fichero contiene funciones paralelizadas con OpenMP.
\date 05 de abril de 2010
\section Licencia Licencia
Copyright (c) 2009-2011, José Luis García Pallero. All rights reserved.
Redistribution and use in source and binary forms, with or without modification,
are permitted provided that the following conditions are met:
- Redistributions of source code must retain the above copyright notice, this
list of conditions and the following disclaimer.
- Redistributions in binary form must reproduce the above copyright notice, this
list of conditions and the following disclaimer in the documentation and/or
other materials provided with the distribution.
- Neither the name of the copyright holders nor the names of its contributors
may be used to endorse or promote products derived from this software without
specific prior written permission.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL COPYRIGHT HOLDER BE LIABLE FOR ANY DIRECT,
INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
/******************************************************************************/
/******************************************************************************/
#ifndef _PTOPOL_H_
#define _PTOPOL_H_
/******************************************************************************/
/******************************************************************************/
#include<stdlib.h>
#include<math.h>
#include"libgeoc/errores.h"
#include"libgeoc/fgeneral.h"
/******************************************************************************/
/******************************************************************************/
#ifdef __cplusplus
extern "C" {
#endif
/******************************************************************************/
/******************************************************************************/
/**
\def GEOC_PTO_FUERA_POLIG
\brief Identificador de punto fuera de un polígono.
\date 12 de abril de 2011: Creación de la constante.
*/
#define GEOC_PTO_FUERA_POLIG 0
/******************************************************************************/
/******************************************************************************/
/**
\def GEOC_PTO_DENTRO_POLIG
\brief Identificador de punto dentro de un polígono.
\date 12 de abril de 2011: Creación de la constante.
*/
#define GEOC_PTO_DENTRO_POLIG 1
/******************************************************************************/
/******************************************************************************/
/**
\def GEOC_PTO_VERTICE_POLIG
\brief Identificador de punto que es un vértice de un polígono.
\date 12 de abril de 2011: Creación de la constante.
*/
#define GEOC_PTO_VERTICE_POLIG 2
/******************************************************************************/
/******************************************************************************/
/**
\def GEOC_PTO_BORDE_POLIG
\brief Identificador de punto que está en el borde de un polígono.
\date 12 de abril de 2011: Creación de la constante.
*/
#define GEOC_PTO_BORDE_POLIG 3
/******************************************************************************/
/******************************************************************************/
/**
\typedef ptopol_long
\brief Nombre del tipo <tt>long int</tt> o <tt>long long int</tt> para utilizar
en los cálculos intermedios de las funciones
\ref PtoEnPoligonoVerticeBorde y \ref PtoEnPoligonoVerticeBordeDouble. Si
los puntos de trabajo están muy alejados de los polígonos pueden darse
casos de resultados erróneos. Sería conveniente que los cálculos
internedios se hiciesen en variables de 64 bits, pero el tipo
<tt>long int</tt> suele ser de 4 bytes en procesadores de 32 bits.
Mediante la variable del preprocesador PTOPOL_BORDE_LONG_64 indicamos que
este tipo sea <tt>long long int</tt>, lo que en procesadores de 32 bits
equivale a una variable de 64 bits.
\note Este tipo de dato sólo es para uso interno en el fichero \ref ptopol.c. No
se recomienda su uso fuera de él, ya que habría que tener el cuenta la
variable del preprocesador cada vez que se incluyera este fichero
(\ref ptopol.h) en un programa u otro fichero.
\date 19 de abril de 2011: Creación del tipo.
*/
#if defined(PTOPOL_BORDE_LONG_64)
typedef long long int ptopol_long;
#else
typedef long int ptopol_long;
#endif
/******************************************************************************/
/******************************************************************************/
/**
\brief Indica si hay alguna función compilada en paralelo con OpenMP en el
fichero \ref ptopol.c.
\return Dos posibles valores:
- 0: No hay ninguna función compilada en paralelo con OpenMP.
- Distinto de 0: Sí hay alguna función compilada en paralelo con OpenMP.
\date 13 de abril de 2011: Creación de la función.
*/
int GeocParOmpPtopol(void);
/******************************************************************************/
/******************************************************************************/
/**
\brief Indica si se está utilizando el tipo <tt>log long int</tt> para la
realización de cálculos intermedios en las funciones de chequeo de puntos
en polígonos que son capaces de detectar si un punto está en el borde.
\return Dos posibles valores:
- 0: No se está utilizando <tt>log long int</tt>.
- Distinto de 0: Sí se está utilizando <tt>log long int</tt>.
\date 19 de abril de 2011: Creación de la función.
*/
int GeocLongLongIntPtopol(void);
/******************************************************************************/
/******************************************************************************/
/**
\brief Comprueba si un punto está contenido en un rectángulo.
\param[in] x Coordenada X del punto de trabajo.
\param[in] y Coordenada Y del punto de trabajo.
\param[in] xMin Coordenada X mínima del rectángulo.
\param[in] xMax Coordenada X máxima del rectángulo.
\param[in] yMin Coordenada Y mínima del rectángulo.
\param[in] yMax Coordenada Y máxima del rectángulo.
\return Varias posibilidades:
- #GEOC_PTO_FUERA_POLIG: El punto está fuera del rectángulo.
- #GEOC_PTO_DENTRO_POLIG: El punto está dentro del rectángulo.
- #GEOC_PTO_VERTICE_POLIG: El punto es un vértice del rectángulo.
- #GEOC_PTO_BORDE_POLIG: El punto pertenece a la frontera del
rectángulo, pero no es un vértice.
\note Esta función asume que \em xMin<xMax y \em yMin<yMax.
\date 05 de abril de 2010: Creación de la función.
\date 12 de abril de 2011: Las variables de salida son ahora constantes
simbólicas.
\todo Esta función no está probada.
*/
int PtoEnRectangulo(const double x,
const double y,
const double xMin,
const double xMax,
const double yMin,
const double yMax);
/******************************************************************************/
/******************************************************************************/
/**
\brief Comprueba si un punto está contenido en un polígono de un número
arbitrario de lados. Esta función puede no dar resultados correctos para
puntos en los bordes y/o los vértices del polígono.
\param[in] x Coordenada X del punto de trabajo.
\param[in] y Coordenada Y del punto de trabajo.
\param[in] coorX Vector que contiene las coordenadas X de los vértices del
polígono. Puede contener varios polígonos.
\param[in] coorY Vector que contiene las coordenadas Y de los vértices del
polígono. Puede contener varios polígonos.
\param[in] N Número de elementos que contienen los vectores \em coorX y
\em coorY.
\param[in] incX Posiciones de separación entre los elementos del vector
\em coorX. Este argumento siempre ha de ser un número positivo.
\param[in] incY Posiciones de separación entre los elementos del vector
\em coorY. Este argumento siempre ha de ser un número positivo.
\return Dos posibilidades:
- #GEOC_PTO_FUERA_POLIG: El punto está fuera del polígono.
- #GEOC_PTO_DENTRO_POLIG: El punto está dentro del polígono.
\note El código de esta función ha sido tomado de
http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html y
se han hecho pequeñas modificaciones para permitir el trabajo con vectores
que contengan elementos separados entre sí por varias posiciones.
\note Esta función no comprueba si el número de elementos de los vectores
\em coorX y \em coorY es congruente con los valores pasados en \em N,
\em incX e \em incY. Tampoco comprueba si \em N es un valor mayor o igual
a 3, que es el número mínimo de vértices que ha de tener un polígono.
\note Esta función no detecta el caso de que el punto de trabajo esté en el
borde o en un vértice del polígono. En este caso, el test puede dar el
punto dentro o fuera, indistintamente (el chequeo del mismo punto con el
mismo polígono siempre dará el mismo resultado).
\note La estructura de los vectores de coordenadas puede contener uno o varios
polígonos, de la siguiente manera:
-# Los vectores de vértices pasados puedes contener elementos aislados
(varios polígonos) y/o agujeros en los elementos. En los vectores de
entrada se han de separar los polígonos y los agujeros mediante un
vértice de coordenadas NaN=(#GEOC_NAN, #GEOC_NAN), de la siguiente
forma:
-# Primero, se incluye un vértice NaN.
-# A continuación, se incluyen las coordenadas de los vértices del
primer elemento, repitiendo el primer vértice después del último.
-# Se incluye otro vértice NaN.
-# Se incluye otro elemento, repitiendo el primer vértice después del
último.
-# Se repiten los dos pasos anteriores por cada elemento o agujero.
-# Se incluye un vértice NaN al final.
-# Por ejemplo, dados tres elementos aislados de vértices A1, A2, A3, B1,
B2, B3 y C1, C2, C3, y dos agujeros de vértices H1, H2, H3 e I1, I2,
I3, los vértices serán listados en los vectores de coordenadas como:
- NaN,A1,A2,A2,A1,NaN,B1,B2,B3,B1,NaN,C1,C2,C3,C1,NaN,H1,H2,H3,H1,NaN,
I1,I2,I3,I1,NaN.
-# Los vértices de cada elemento y/o agujero pueden ser listados en
sentido dextrógiro o levógiro.
-# Si el polígono es único y no tiene agujeros es opcional repetir el
primer vértice después del último e iniciar y terminar el listado de
coordenadas con el vértice NaN. Pero si se inicia y termina el listado
con vértices NaN, ha de repetirse el primer vértice del polígono.
\date 05 de abril de 2010: Creación de la función.
\date 10 de abril de 2011: Adición de los argumentos de entrada \em incX e
\em incY.
\date 12 de abril de 2011: Las variables de salida son ahora constantes
simbólicas.
\todo Esta función no está probada.
*/
int PtoEnPoligono(const double x,
const double y,
const double* coorX,
const double* coorY,
const size_t N,
const size_t incX,
const size_t incY);
/******************************************************************************/
/******************************************************************************/
/**
\brief Comprueba si un punto está contenido o es un vértice de un polígono de un
número arbitrario de lados. Esta función puede no dar resultados
correctos para puntos en los bordes del polígono.
\param[in] x Coordenada X del punto de trabajo.
\param[in] y Coordenada Y del punto de trabajo.
\param[in] coorX Vector que contiene las coordenadas X de los vértices del
polígono. Sólo puede contener un polígono.
\param[in] coorY Vector que contiene las coordenadas Y de los vértices del
polígono. Sólo puede contener un polígono.
\param[in] N Número de elementos que contienen los vectores \em coorX y
\em coorY.
\param[in] incX Posiciones de separación entre los elementos del vector
\em coorX. Este argumento siempre ha de ser un número positivo.
\param[in] incY Posiciones de separación entre los elementos del vector
\em coorY. Este argumento siempre ha de ser un número positivo.
\return Dos posibilidades:
- #GEOC_PTO_FUERA_POLIG: El punto está fuera del polígono.
- #GEOC_PTO_DENTRO_POLIG: El punto está dentro del polígono.
- #GEOC_PTO_VERTICE_POLIG: El punto es un vértice del polígono.
\note Esta función no comprueba si el número de elementos de los vectores
\em coorX y \em coorY es congruente con los valores pasados en \em N,
\em incX e \em incY. Tampoco comprueba si \em N es un valor mayor o igual
a 3, que es el número mínimo de vértices que ha de tener un polígono.
\note Esta función utiliza en uno de sus pasos la función \ref PtoEnPoligono y
se comporta igual que ella en el caso de puntos en el borde.
\note La estructura de los vectores de coordenadas es idéntica a la de la
función \ref PtoEnPoligono.
\date 09 de abril de 2010: Creación de la función.
\date 10 de abril de 2011: Adición de los argumentos de entrada \em incX e
\em incY.
\date 12 de abril de 2011: Las variables de salida son ahora constantes
simbólicas.
\todo Esta función no está probada.
*/
int PtoEnPoligonoVertice(const double x,
const double y,
const double* coorX,
const double* coorY,
const size_t N,
const size_t incX,
const size_t incY);
/******************************************************************************/
/******************************************************************************/
/**
\brief Comprueba si un punto está contenido en un polígono de un número
arbitrario de lados. Esta función trata correctamente los puntos situados
en los bordes y/o los vértices del polígono, pero sólo trabaja con datos
de tipo entero.
\param[in] x Coordenada X del punto de trabajo.
\param[in] y Coordenada Y del punto de trabajo.
\param[in] coorX Vector que contiene las coordenadas X de los vértices del
polígono. Sólo puede contener un polígono.
\param[in] coorY Vector que contiene las coordenadas Y de los vértices del
polígono. Sólo puede contener un polígono.
\param[in] N Número de elementos que contienen los vectores \em coorX y
\em coorY.
\param[in] incX Posiciones de separación entre los elementos del vector
\em coorX. Este argumento siempre ha de ser un número positivo.
\param[in] incY Posiciones de separación entre los elementos del vector
\em coorY. Este argumento siempre ha de ser un número positivo.
\return Varias posibilidades:
- #GEOC_PTO_FUERA_POLIG: El punto está fuera del polígono.
- #GEOC_PTO_DENTRO_POLIG: El punto está dentro del polígono.
- #GEOC_PTO_VERTICE_POLIG: El punto es un vértice del polígono.
- #GEOC_PTO_BORDE_POLIG: El punto pertenece a la frontera del polígono,
pero no es un vértice.
\note El código de esta función ha sido tomado del texto Joseph O'Rourke (2001),
Computational geometry in C, 2a edición, Cambridge University Press,
página 244.
\note Esta función no comprueba si el número de elementos de los vectores
\em coorX y \em coorY es congruente con los valores pasados en \em N,
\em incX e \em incY. Tampoco comprueba si \em N es un valor mayor o igual
a 3, que es el número mínimo de vértices que ha de tener un polígono.
\note El polígono ha de ser único, sin huecos. Es opcional repetir las
coordenadas del primer punto al final del listado.
\note Los vértices del polígono pueden listarse en sentido dextrógiro o
levógiro.
\note <b>Esta función puede dar resultados incorrectos para puntos muy alejados
de los polígonos de trabajo. Para intentar mitigar este efecto, puede
seleccionarse mediante una variable del preprocesador la precisión de
algunas variables intermedias. Para más información se recomienda leer el
encabezado de este fichero.</b>
\note Con cálculos internos de 32 bits las coordenadas de los vértices del
polígono no han de estar más lejos de las de los puntos de trabajo de unas
40000 unidades. Con cálculos de 64 bits, los polígonos pueden estar
alejados de los puntos de trabajo unas 3000000000 unidades, lo que
corresponde a coordenadas Y UTM ajustadas al centímetro. Con esto
podríamos chequear un punto en un polo con respecto a un polígono en el
ecuador en coordenadas UTM expresadas en centímetros.
\date 06 de abril de 2010: Creación de la función.
\date 10 de abril de 2011: Adición de los argumentos de entrada \em incX e
\em incY.
\date 12 de abril de 2011: Las variables de salida son ahora constantes
simbólicas.
\date 18 de abril de 2011: Reescritura de la función, siguiendo la página 244
del libro de O'Rourke. La versión anterior la había adaptado del código de
la web de O'Rourke, y lo había hecho mal.
\todo Esta función no está probada.
*/
int PtoEnPoligonoVerticeBorde(const long x,
const long y,
const long* coorX,
const long* coorY,
const size_t N,
const size_t incX,
const size_t incY);
/******************************************************************************/
/******************************************************************************/
/**
\brief Comprueba si un punto está contenido en un polígono de un número
arbitrario de lados. Esta función trata correctamente los puntos situados
en los bordes y/o los vértices del polígono. Trabaja con datos de tipo
real, que convierte a enteros (por redondeo o truncamiento) intermamente,
mediante la aplicación de un factor de escala.
\param[in] x Coordenada X del punto de trabajo.
\param[in] y Coordenada Y del punto de trabajo.
\param[in] coorX Vector que contiene las coordenadas X de los vértices del
polígono. Sólo puede contener un polígono.
\param[in] coorY Vector que contiene las coordenadas Y de los vértices del
polígono. Sólo puede contener un polígono.
\param[in] N Número de elementos que contienen los vectores \em coorX y
\em coorY.
\param[in] incX Posiciones de separación entre los elementos del vector
\em coorX. Este argumento siempre ha de ser un número positivo.
\param[in] incY Posiciones de separación entre los elementos del vector
\em coorY. Este argumento siempre ha de ser un número positivo.
\param[in] factor Factor de multiplicación para aplicar a las coordenadas del
punto de trabajo y de los vértices del polígono, con el fin de
aumentar su resolución antes de convertirlas en valores de tipo
entero (\p long \p int). El uso de factores muy grandes puede
provocar resultados erróneos. Ver la nota al final de la
documentación de esta función.
\param[in] redondeo Identificador de redondeo o truncamiento en la conversión
interna de variables de tipo \p double en variables de tipo
\p long \p int. Dos posibilidades:
- 0: La conversión se hace por truncamiento.
- Distinto de 0: La conversión se hace por redondeo.
\return Varias posibilidades:
- #GEOC_PTO_FUERA_POLIG: El punto está fuera del polígono.
- #GEOC_PTO_DENTRO_POLIG: El punto está dentro del polígono.
- #GEOC_PTO_VERTICE_POLIG: El punto es un vértice del polígono.
- #GEOC_PTO_BORDE_POLIG: El punto pertenece a la frontera del polígono,
pero no es un vértice.
\note Esta función no comprueba si el número de elementos de los vectores
\em coorX y \em coorY es congruente con los valores pasados en \em N,
\em incX e \em incY. Tampoco comprueba si \em N es un valor mayor o igual
a 3, que es el número mínimo de vértices que ha de tener un polígono.
\note El polígono ha de ser único, sin huecos. Es opcional repetir las
coordenadas del primer punto al final del listado.
\note Los vértices del polígono pueden listarse en sentido dextrógiro o
levógiro.
\note El código de esta función es el mismo que el de la función
\ref PtoEnPoligonoVerticeBorde, salvo que convierte internamente varias
variables intermedias de tipo \p double a tipo \p long \p int, que es el
tipo de datos necesario para detectar correctamente si un punto pertenece
al borde de un polígono.
\note Las variables se redondean internamente con la orden
<tt>(long)(round(factor*variable))</tt>, y se truncan con la orden
<tt>(long)(factor*variable)</tt>.
\note <b>Esta función puede dar resultados incorrectos para puntos muy alejados
de los polígonos de trabajo. Para intentar mitigar este efecto, puede
seleccionarse mediante una variable del preprocesador la precisión de
algunas variables intermedias. Para más información se recomienda leer el
encabezado de este fichero.</b>
\note Con cálculos internos de 32 bits las coordenadas de los vértices del
polígono no han de estar más lejos de las de los puntos de trabajo de unas
40000 unidades. Con cálculos de 64 bits, los polígonos pueden estar
alejados de los puntos de trabajo unas 3000000000 unidades, lo que
corresponde a coordenadas Y UTM ajustadas al centímetro. Con esto
podríamos chequear un punto en un polo con respecto a un polígono en el
ecuador en coordenadas UTM expresadas en centímetros. En este caso nos
referimos a las coordenadas una vez aplicado el factor de escala
\em factor.
\date 10 de abril de 2011: Creación de la función.
\date 11 de abril de 2011: Adición del argumento de entrada \em redondeo.
\date 12 de abril de 2011: Las variables de salida son ahora constantes
simbólicas.
\date 18 de abril de 2011: Reescritura de la función, siguiendo la página 244
del libro de O'Rourke. La versión anterior la había adaptado del código de
la web de O'Rourke, y lo había hecho mal.
\todo Esta función no está probada.
*/
int PtoEnPoligonoVerticeBordeDouble(const double x,
const double y,
const double* coorX,
const double* coorY,
const size_t N,
const size_t incX,
const size_t incY,
const double factor,
const int redondeo);
/******************************************************************************/
/******************************************************************************/
/**
\brief Busca valores #GEOC_NAN es uno o dos vectores de datos. Esta función
está pensada para el chequeo en paralelo de la inclusión de puntos en
polígonos.
\param[in] x Vector que contiene las coordenadas X de los vértices de una serie
de polígonos, tal y como entraría en la definición de múltiples
elementos (pero sin huecos) para la función \ref PtoEnPoligono. La
marca de separación entre polígonos ha de ser #GEOC_NAN.
\param[in] y Vector que contiene las coordenadas Y de los vértices de una serie
de polígonos, tal y como entraría en la definición de múltiples
elementos (pero sin huecos) para la función \ref PtoEnPoligono. La
marca de separación entre polígonos ha de ser #GEOC_NAN. Este
argumento puede valer NULL, en cuyo caso sólo se trabajará con el
vector \em x.
\param[in] N Número de elementos que contienen los vectores \em x e \em y.
\param[in] incX Posiciones de separación entre los elementos del vector \em x.
Este argumento siempre ha de ser un número positivo.
\param[in] incY Posiciones de separación entre los elementos del vector \em y.
Este argumento siempre ha de ser un número positivo.
\param[out] nNan Número de valores #GEOC_NAN encontrados, que es el número de
elementos del vector de salida.
\return Varias posibilidades:
- Si todo ha ido bien, vector que contiene las posiciones en el vector o
vectores originales donde se almacena el valor #GEOC_NAN. Si se
trabaja con los vectores \em x e \em y, la posición sólo se extrae si
ambos vectores contienen #GEOC_NAN para una misma posición.
- NULL: Pueden haber ocurrido dos cosas:
- Si \em nNan vale 0, en los datos de entrada no hay ningún valor
#GEOC_NAN.
- Si \em nNan es mayor que 0, ha ocurrido un error interno de
asignación de memoria.
\note Esta función no comprueba si el número de elementos de los vectores \em x
e \em y es congruente con los valores pasados en \em N, \em incX e
\em incY.
\note Las posiciones de los elementos #GEOC_NAN encontradas se refieren al
número de elementos \em N de los vectores de trabajo. Para encontrar la
posición real en memoria es necesario tener en cuenta las variables
\em incX e \em incY.
\date 13 de abril de 2011: Creación de la función.
\todo Esta función no está probada.
*/
size_t* BuscaGeocNanEnVectores(const double* x,
const double* y,
const size_t N,
const size_t incX,
const size_t incY,
size_t* nNan);
/******************************************************************************/
/******************************************************************************/
/**
\brief Extrae los parámetros de inicio y número de elementos de un polígono en
una lista de polígonos separados por un indicador. Esta función está
pensada para el chequeo en paralelo de la inclusión de puntos en
polígonos.
\param[in] posInd Vector que contiene las posiciones de los indicadores en el
vector original. Este argumento es el vector que devuelve la función
\ref BuscaGeocNanEnVectores.
\param[in] indPosInd Índice en el vector de posiciones de indicadores del
indicador que da comienzo al polígono de trabajo.
\param[in] incX Posiciones de separación entre los elementos del vector original
que almacena las coordenadas X del listado de polígonos. Este
argumento siempre ha de ser un número positivo.
\param[in] incY Posiciones de separación entre los elementos del vector original
que almacena las coordenadas Y del listado de polígonos. Este
argumento siempre ha de ser un número positivo.
\param[out] iniX Posición de inicio de la coordenada X del polígono de trabajo
en el vector original que almacena las coordenadas X del listado de
polígonos. Para encontrar la posición real en memoria es necesario
tener en cuenta la variable \em incX.
\param[out] iniY Posición de inicio de la coordenada Y del polígono de trabajo
en el vector original que almacena las coordenadas Y del listado de
polígonos. Para encontrar la posición real en memoria es necesario
tener en cuenta la variable \em incY.
\param[out] nElem Número de elementos que conforman el polígono de trabajo.
\note Esta función no comprueba si el vector \em posInd contiene datos.
\note Esta función asume que el vector \em posInd contiene un número \b *PAR* de
datos.
\note Esta función asume que el argumento \em indPosInd no es la última posición
del vector \em posInd.
\date 13 de abril de 2011: Creación de la función.
\todo Esta función no está probada.
*/
void DatosPoliIndividualEnVecInd(const size_t* posInd,
const size_t indPosInd,
const size_t incX,
const size_t incY,
size_t* iniX,
size_t* iniY,
size_t* nElem);
/******************************************************************************/
/******************************************************************************/
/**
\brief Comprueba si un punto está contenido en una serie de polígonos
individuales de un número arbitrario de lados. Esta función puede no dar
resultados correctos para puntos en los bordes y/o los vértices del
polígono.
\param[in] x Coordenada X del punto de trabajo.
\param[in] y Coordenada Y del punto de trabajo.
\param[in] coorX Vector que contiene las coordenadas X de los vértices de los
elementos. Puede contener varios polígonos, pero no huecos (si los
hay, serán tratados como otros polígonos).
\param[in] coorY Vector que contiene las coordenadas Y de los vértices de los
elementos. Puede contener varios polígonos, pero no huecos (si los
hay, serán tratados como otros polígonos).
\param[in] N Número de elementos que contienen los vectores \em coorX y
\em coorY.
\param[in] incX Posiciones de separación entre los elementos del vector
\em coorX. Este argumento siempre ha de ser un número positivo.
\param[in] incY Posiciones de separación entre los elementos del vector
\em coorY. Este argumento siempre ha de ser un número positivo.
\param[in] posNan Vector que almacena las posiciones en los vectores \em coorX y
\em coorY de los elementos #GEOC_NAN, que separan los polígonos
individuales. Este vector es la salida de la función
\ref BuscaGeocNanEnVectores.
\param[in] nNan Número de elementos del vector \em posNan.
\param[out] poli Número del polígono en que está incluido el punto de trabajo.
Si hay varios polígonos que contienen al punto de trabajo no se
puede asegurar cuál de ellos será el indicado en este argumento.
Este argumento sólo tiene sentido si el valor retornado por la
función es distinto de #GEOC_PTO_FUERA_POLIG.
\return Dos posibilidades:
- #GEOC_PTO_FUERA_POLIG: El punto está fuera de todos los polígonos
listados.
- #GEOC_PTO_DENTRO_POLIG: El punto está dentro de, al menos, un polígono
de entre los listados.
\note Esta función se puede ejecutar en paralelo con OpenMP.
\note Esta función no comprueba si el número de elementos de los vectores
\em coorX y \em coorY es congruente con los valores pasados en \em N,
\em incX e \em incY. Tampoco comprueba si \em N es un valor mayor o igual
a 3, que es el número mínimo de vértices que ha de tener un polígono.
\note Esta función no comprueba si el número de elementos del vector \em posNan
es congruente con el valor pasado en \em nNan.
\note Esta función no detecta el caso de que el punto de trabajo esté en el
borde o en un vértice del polígono. En este caso, el test puede dar el
punto dentro o fuera, indistintamente (el chequeo del mismo punto con el
mismo polígono siempre dará el mismo resultado).
\note La estructura de los vectores de coordenadas es la misma que la de la
función \ref PtoEnPoligono. Las marcas de comienzo y final de los
listados, así como las de separación entre polígonos han de ser valores
#GEOC_NAN.
\note Aunque los vectores \em coorX y \em coorY sólo contengan un polígono, los
elementos primero y último han de ser #GEOC_NAN.
\note Los huecos en los polígonos no serán tenidos en cuenta, serán tratados
como polígonos individuales.
\date 14 de abril de 2011: Creación de la función.
\todo Esta función no está probada.
*/
int PtoEnPoligonoInd(const double x,
const double y,
const double* coorX,
const double* coorY,
const size_t N,
const size_t incX,
const size_t incY,
const size_t* posNan,
const size_t nNan,
size_t* poli);
/******************************************************************************/
/******************************************************************************/
/**
\brief Comprueba si un punto está contenido en una serie de polígonos
individuales de un número arbitrario de lados. Esta función puede no dar
resultados correctos para puntos en los bordes del polígono.
\param[in] x Coordenada X del punto de trabajo.
\param[in] y Coordenada Y del punto de trabajo.
\param[in] coorX Vector que contiene las coordenadas X de los vértices de los
elementos. Puede contener varios polígonos, pero no huecos (si los
hay, serán tratados como otros polígonos).
\param[in] coorY Vector que contiene las coordenadas Y de los vértices de los
elementos. Puede contener varios polígonos, pero no huecos (si los
hay, serán tratados como otros polígonos).
\param[in] N Número de elementos que contienen los vectores \em coorX y
\em coorY.
\param[in] incX Posiciones de separación entre los elementos del vector
\em coorX. Este argumento siempre ha de ser un número positivo.
\param[in] incY Posiciones de separación entre los elementos del vector
\em coorY. Este argumento siempre ha de ser un número positivo.
\param[in] posNan Vector que almacena las posiciones en los vectores \em coorX y
\em coorY de los elementos #GEOC_NAN, que separan los polígonos
individuales. Este vector es la salida de la función
\ref BuscaGeocNanEnVectores.
\param[in] nNan Número de elementos del vector \em posNan.
\param[out] poli Número del polígono en que está incluido el punto de trabajo.
Si hay varios polígonos que contienen al punto de trabajo no se
puede asegurar cuál de ellos será el indicado en este argumento.
Este argumento sólo tiene sentido si el valor retornado por la
función es distinto de #GEOC_PTO_FUERA_POLIG.
\return Dos posibilidades:
- #GEOC_PTO_FUERA_POLIG: El punto está fuera de todos los polígonos
listados.
- #GEOC_PTO_DENTRO_POLIG: El punto está dentro de, al menos, un polígono
de entre los listados.
- #GEOC_PTO_VERTICE_POLIG: El punto es un vértice de, al menos, un
polígono de entre los listados.
\note Esta función se puede ejecutar en paralelo con OpenMP.
\note Esta función no comprueba si el número de elementos de los vectores
\em coorX y \em coorY es congruente con los valores pasados en \em N,
\em incX e \em incY. Tampoco comprueba si \em N es un valor mayor o igual
a 3, que es el número mínimo de vértices que ha de tener un polígono.
\note Esta función no comprueba si el número de elementos del vector \em posNan
es congruente con el valor pasado en \em nNan.
\note Esta función no detecta el caso de que el punto de trabajo esté en el
borde del polígono. En este caso, el test puede dar el punto dentro o
fuera, indistintamente (el chequeo del mismo punto con el mismo polígono
siempre dará el mismo resultado).
\note La estructura de los vectores de coordenadas es la misma que la de la
función \ref PtoEnPoligono. Las marcas de comienzo y final de los
listados, así como las de separación entre polígonos han de ser valores
#GEOC_NAN.
\note Aunque los vectores \em coorX y \em coorY sólo contengan un polígono, los
elementos primero y último han de ser #GEOC_NAN.
\note Los huecos en los polígonos no serán tenidos en cuenta, serán tratados
como polígonos individuales.
\date 14 de abril de 2011: Creación de la función.
\todo Esta función no está probada.
*/
int PtoEnPoligonoVerticeInd(const double x,
const double y,
const double* coorX,
const double* coorY,
const size_t N,
const size_t incX,
const size_t incY,
const size_t* posNan,
const size_t nNan,
size_t* poli);
/******************************************************************************/
/******************************************************************************/
/**
\brief Comprueba si un punto está contenido en una serie de polígonos
individuales de un número arbitrario de lados. Esta función trata
correctamente los puntos situados en los bordes y/o los vértices del
polígono, pero sólo trabaja con datos de tipo entero.
\param[in] x Coordenada X del punto de trabajo.
\param[in] y Coordenada Y del punto de trabajo.
\param[in] coorX Vector que contiene las coordenadas X de los vértices de los
elementos. Puede contener varios polígonos, pero no huecos (si los
hay, serán tratados como otros polígonos).
\param[in] coorY Vector que contiene las coordenadas Y de los vértices de los
elementos. Puede contener varios polígonos, pero no huecos (si los
hay, serán tratados como otros polígonos).
\param[in] N Número de elementos que contienen los vectores \em coorX y
\em coorY.
\param[in] incX Posiciones de separación entre los elementos del vector
\em coorX. Este argumento siempre ha de ser un número positivo.
\param[in] incY Posiciones de separación entre los elementos del vector
\em coorY. Este argumento siempre ha de ser un número positivo.
\param[in] posNan Vector que almacena las posiciones en los vectores \em coorX y
\em coorY de los elementos #GEOC_NAN, que separan los polígonos
individuales. Este vector es la salida de la función
\ref BuscaGeocNanEnVectores.
\param[in] nNan Número de elementos del vector \em posNan.
\param[out] poli Número del polígono en que está incluido el punto de trabajo.
Si hay varios polígonos que contienen al punto de trabajo no se
puede asegurar cuál de ellos será el indicado en este argumento.
Este argumento sólo tiene sentido si el valor retornado por la
función es distinto de #GEOC_PTO_FUERA_POLIG.
\return Dos posibilidades:
- #GEOC_PTO_FUERA_POLIG: El punto está fuera de todos los polígonos
listados.
- #GEOC_PTO_DENTRO_POLIG: El punto está dentro de, al menos, un polígono
de entre los listados.
- #GEOC_PTO_VERTICE_POLIG: El punto es un vértice de, al menos, un
polígono de entre los listados.
- #GEOC_PTO_BORDE_POLIG: El punto pertenece a la frontera de, al menos,
un polígono de entre los listados, pero no es un vértice.
\note Esta función se puede ejecutar en paralelo con OpenMP.
\note Esta función no comprueba si el número de elementos de los vectores
\em coorX y \em coorY es congruente con los valores pasados en \em N,
\em incX e \em incY. Tampoco comprueba si \em N es un valor mayor o igual
a 3, que es el número mínimo de vértices que ha de tener un polígono.
\note Esta función no comprueba si el número de elementos del vector \em posNan
es congruente con el valor pasado en \em nNan.
\note La estructura de los vectores de coordenadas es la misma que la de la
función \ref PtoEnPoligono. Las marcas de comienzo y final de los
listados, así como las de separación entre polígonos han de ser valores
#GEOC_NAN.
\note Aunque los vectores \em coorX y \em coorY sólo contengan un polígono, los
elementos primero y último han de ser #GEOC_NAN.
\note Los huecos en los polígonos no serán tenidos en cuenta, serán tratados
como polígonos individuales.
\note <b>Esta función puede dar resultados incorrectos para puntos muy alejados
de los polígonos de trabajo. Para intentar mitigar este efecto, puede
seleccionarse mediante una variable del preprocesador la precisión de
algunas variables intermedias. Para más información se recomienda leer el
encabezado de este fichero.</b>
\note Con cálculos internos de 32 bits las coordenadas de los vértices del
polígono no han de estar más lejos de las de los puntos de trabajo de unas
40000 unidades. Con cálculos de 64 bits, los polígonos pueden estar
alejados de los puntos de trabajo unas 3000000000 unidades, lo que
corresponde a coordenadas Y UTM ajustadas al centímetro. Con esto
podríamos chequear un punto en un polo con respecto a un polígono en el
ecuador en coordenadas UTM expresadas en centímetros.
\date 14 de abril de 2011: Creación de la función.
\todo Esta función no está probada.
*/
int PtoEnPoligonoVerticeBordeInd(const long x,
const long y,
const long* coorX,
const long* coorY,
const size_t N,
const size_t incX,
const size_t incY,
const size_t* posNan,
const size_t nNan,
size_t* poli);
/******************************************************************************/
/******************************************************************************/
/**
\brief Comprueba si un punto está contenido en una serie de polígonos
individuales de un número arbitrario de lados. Esta función trata
correctamente los puntos situados en los bordes y/o los vértices del
polígono. Trabaja con datos de tipo real, que convierte a enteros (por
redondeo o truncamiento) intermamente, mediante a aplicación de un factor
de escala.
\param[in] x Coordenada X del punto de trabajo.
\param[in] y Coordenada Y del punto de trabajo.
\param[in] coorX Vector que contiene las coordenadas X de los vértices de los
elementos. Puede contener varios polígonos, pero no huecos (si los
hay, serán tratados como otros polígonos).
\param[in] coorY Vector que contiene las coordenadas Y de los vértices de los
elementos. Puede contener varios polígonos, pero no huecos (si los
hay, serán tratados como otros polígonos).
\param[in] N Número de elementos que contienen los vectores \em coorX y
\em coorY.
\param[in] incX Posiciones de separación entre los elementos del vector
\em coorX. Este argumento siempre ha de ser un número positivo.
\param[in] incY Posiciones de separación entre los elementos del vector
\em coorY. Este argumento siempre ha de ser un número positivo.
\param[in] factor Factor de multiplicación para aplicar a las coordenadas del
punto de trabajo y de los vértices de los polígonos, con el fin de
aumentar su resolución antes de convertirlas en valores de tipo
entero (\p long \p int). El uso de factores muy grandes puede
provocar resultados erróneos. Ver la nota al final de la
documentación de esta función.
\param[in] redondeo Identificador de redondeo o truncamiento en la conversión
interna de variables de tipo \p double en variables de tipo
\p long \p int. Dos posibilidades:
- 0: La conversión se hace por truncamiento.
- Distinto de 0: La conversión se hace por redondeo.
\param[in] posNan Vector que almacena las posiciones en los vectores \em coorX y
\em coorY de los elementos #GEOC_NAN, que separan los polígonos
individuales. Este vector es la salida de la función
\ref BuscaGeocNanEnVectores.
\param[in] nNan Número de elementos del vector \em posNan.
\param[out] poli Número del polígono en que está incluido el punto de trabajo.
Si hay varios polígonos que contienen al punto de trabajo no se
puede asegurar cuál de ellos será el indicado en este argumento.
Este argumento sólo tiene sentido si el valor retornado por la
función es distinto de #GEOC_PTO_FUERA_POLIG.
\return Dos posibilidades:
- #GEOC_PTO_FUERA_POLIG: El punto está fuera de todos los polígonos
listados.
- #GEOC_PTO_DENTRO_POLIG: El punto está dentro de, al menos, un polígono
de entre los listados.
- #GEOC_PTO_VERTICE_POLIG: El punto es un vértice de, al menos, un
polígono de entre los listados.
- #GEOC_PTO_BORDE_POLIG: El punto pertenece a la frontera de, al menos,
un polígono de entre los listados, pero no es un vértice.
\note Esta función se puede ejecutar en paralelo con OpenMP.
\note Esta función no comprueba si el número de elementos de los vectores
\em coorX y \em coorY es congruente con los valores pasados en \em N,
\em incX e \em incY. Tampoco comprueba si \em N es un valor mayor o igual
a 3, que es el número mínimo de vértices que ha de tener un polígono.
\note Esta función no comprueba si el número de elementos del vector \em posNan
es congruente con el valor pasado en \em nNan.
\note Las variables se redondean internamente con la orden
<tt>(long)(round(factor*variable))</tt>, y se truncan con la orden
<tt>(long)(factor*variable)</tt>.
\note La estructura de los vectores de coordenadas es la misma que la de la
función \ref PtoEnPoligono. Las marcas de comienzo y final de los
listados, así como las de separación entre polígonos han de ser valores
#GEOC_NAN.
\note Aunque los vectores \em coorX y \em coorY sólo contengan un polígono, los
elementos primero y último han de ser #GEOC_NAN.
\note Los huecos en los polígonos no serán tenidos en cuenta, serán tratados
como polígonos individuales.
\note <b>Esta función puede dar resultados incorrectos para puntos muy alejados
de los polígonos de trabajo. Para intentar mitigar este efecto, puede
seleccionarse mediante una variable del preprocesador la precisión de
algunas variables intermedias. Para más información se recomienda leer el
encabezado de este fichero.</b>
\note Con cálculos internos de 32 bits las coordenadas de los vértices del
polígono no han de estar más lejos de las de los puntos de trabajo de unas
40000 unidades. Con cálculos de 64 bits, los polígonos pueden estar
alejados de los puntos de trabajo unas 3000000000 unidades, lo que
corresponde a coordenadas Y UTM ajustadas al centímetro. Con esto
podríamos chequear un punto en un polo con respecto a un polígono en el
ecuador en coordenadas UTM expresadas en centímetros. En este caso nos
referimos a las coordenadas una vez aplicado el factor de escala
\em factor.
\date 14 de abril de 2011: Creación de la función.
\todo Esta función no está probada.
*/
int PtoEnPoligonoVerticeBordeDoubleInd(const double x,
const double y,
const double* coorX,
const double* coorY,
const size_t N,
const size_t incX,
const size_t incY,
const double factor,
const int redondeo,
const size_t* posNan,
const size_t nNan,
size_t* poli);
/******************************************************************************/
/******************************************************************************/
#ifdef __cplusplus
}
#endif
/******************************************************************************/
/******************************************************************************/
#endif
/******************************************************************************/
/******************************************************************************/
/** @} */