Hola a todos.
Quiero hacerme un script para conocer si un punto geográfico está incluido en un polígono.
He visto una web donde lo hacen en Visual Basic (creo) con coordenadas cartesianas que me podría valer:
http://www.brausoft.com/2007/09/03/punt ... -poligono/
Mi pregunta es si alguien conoce en CPAN módulos para trabajar con vectores y ángulos donde pueda encontrar funciones similares a las de la página que indico arriba.
Gracias anticipadas / saludos / apardo
-
- Publicidad
Módulo para tratar vectores y ángulos
3 mensajes
• Página 1 de 1
Módulo para tratar vectores y ángulos
por apardo » 2009-05-23 07:43 @363
- apardo
- Perlero nuevo
- Mensajes: 17
- Registrado: 2009-03-31 16:58 @748
Publicidad
por explorer » 2009-05-23 12:45 @573
Este problema de la Inclusión de un punto dentro de un polígono, tiene varias soluciones. El enlace que pones lo resuelve por medio del cálculo de los ángulos entre los segmentos del polígono y su relación con el punto. Hay otra forma de hacerlo, y es la que se comenta en el libro Mastering Algorithms with Perl, de Jon Orwant, Jarkko Hietaniemi, y John Macdonald. O'Reilly, agosto 1999, cap. 10, Geometric Algorithms.
Este es el código:
A esta función le pasamos las coordenadas del punto ($x, $y) y luego un arreglo (@xy) con las coordenadas de los vértices que definen el polígono, y nos devuelve 0 si el punto está fuera o 1 si está dentro.
La explicación de cómo funciona y muchos otros algoritmos más quedan en el libro. Un libro muy bueno para enseñar algorítmica de todo tipo, con Perl.
En cuanto a módulos CPAN, hay unos cuantos... a veces, difíciles de encontrar... pero, no hay que desesperar, que seguro que lo encontramos.
Este es el código:
Using perl Syntax Highlighting
# point_in_polygon ( $x, $y, @xy )
#
# Point ($x,$y), polygon ($x0, $y0, $x1, $y1, . . .) in @xy.
# Returns 1 for strictly interior points, 0 for strictly exterior
# points. For the boundary points the situation is more complex and
# beyond the scope of this book. The boundary points are
# exact, however: if a plane is divided into several polygons, any
# given point belongs to exactly one polygon.
#
# Derived from the comp.graphics.algorithms FAQ,
# courtesy of Wm. Randolph Franklin.
#
sub point_in_polygon {
my ( $x, $y, @xy ) = @_;
my $n = @xy / 2; # Number of points in polygon.
my @i = map { 2 * $_ } 0 .. (@xy/2); # The even indices of @xy.
my @x = map { $xy[ $_ ] } @i; # Even indices: x-coordinates.
my @y = map { $xy[ $_ + 1 ] } @i; # Odd indices: y-coordinates.
my ( $i, $j ); # Indices.
my $side = 0; # 0 = outside, 1 = inside.
for ( $i = 0, $j = $n -1 ; $i < $n; $j = $i++ ) {
if (
# If the y is between the (y-) borders . . .
(
( ( $y[ $i ] <= $y ) && ( $y < $y[ $j ] ) ) ||
( ( $y[ $j ] <= $y ) && ( $y < $y[ $i ] ) )
)
and
# ... the (x,y) to infinity line crosses the edge
# from the ith point to the jth point . . .
(
$x
<
( $x[ $j ] - $x[ $i ] ) *
( $y - $y[ $i ] ) /
( $y[ $j ] - $y[ $i ] ) +
$x[ $i ]
)
)
{
$side = not $side; # Jump the fence.
}
}
return $side ? 1 : 0;
}
#
# Point ($x,$y), polygon ($x0, $y0, $x1, $y1, . . .) in @xy.
# Returns 1 for strictly interior points, 0 for strictly exterior
# points. For the boundary points the situation is more complex and
# beyond the scope of this book. The boundary points are
# exact, however: if a plane is divided into several polygons, any
# given point belongs to exactly one polygon.
#
# Derived from the comp.graphics.algorithms FAQ,
# courtesy of Wm. Randolph Franklin.
#
sub point_in_polygon {
my ( $x, $y, @xy ) = @_;
my $n = @xy / 2; # Number of points in polygon.
my @i = map { 2 * $_ } 0 .. (@xy/2); # The even indices of @xy.
my @x = map { $xy[ $_ ] } @i; # Even indices: x-coordinates.
my @y = map { $xy[ $_ + 1 ] } @i; # Odd indices: y-coordinates.
my ( $i, $j ); # Indices.
my $side = 0; # 0 = outside, 1 = inside.
for ( $i = 0, $j = $n -1 ; $i < $n; $j = $i++ ) {
if (
# If the y is between the (y-) borders . . .
(
( ( $y[ $i ] <= $y ) && ( $y < $y[ $j ] ) ) ||
( ( $y[ $j ] <= $y ) && ( $y < $y[ $i ] ) )
)
and
# ... the (x,y) to infinity line crosses the edge
# from the ith point to the jth point . . .
(
$x
<
( $x[ $j ] - $x[ $i ] ) *
( $y - $y[ $i ] ) /
( $y[ $j ] - $y[ $i ] ) +
$x[ $i ]
)
)
{
$side = not $side; # Jump the fence.
}
}
return $side ? 1 : 0;
}
Coloreado en 0.003 segundos, usando GeSHi 1.0.8.4
A esta función le pasamos las coordenadas del punto ($x, $y) y luego un arreglo (@xy) con las coordenadas de los vértices que definen el polígono, y nos devuelve 0 si el punto está fuera o 1 si está dentro.
La explicación de cómo funciona y muchos otros algoritmos más quedan en el libro. Un libro muy bueno para enseñar algorítmica de todo tipo, con Perl.
En cuanto a módulos CPAN, hay unos cuantos... a veces, difíciles de encontrar... pero, no hay que desesperar, que seguro que lo encontramos.
- Math::Geometry::Planar, con la función isinside()
- Math::Geometry::Planar::GPC utiliza la librería GPC, con lo que resuelve el problema de forma rapidísima (es una librería compilada en C). Lo malo es que el manejo es bastante difícil, y no hay mucha documentación
- Math::Geometry::Planar::GPC::Polygon es lo mismo, usa la misma librería GPC
- Math::Polygon, con la función contains(), que implementa la función anterior
- CAD::Calc, con las funciones iswithin() e iswithinc().
JF^D Perl programming & Raku programming. Grupo en Telegram: https://t.me/Perl_ES
-
explorer - Administrador
- Mensajes: 14477
- Registrado: 2005-07-24 18:12 @800
- Ubicación: Valladolid, España
por apardo » 2009-05-23 15:13 @676
Me he quedado
A-L-U-C-I-N-A-D-O
Lo de los módulos CPAN me lo imaginaba aunque no daba con ellos, pero lo del libro:
Una vez más, muchas gracias explorer, ahora me toca estudiar tanta info.
saludos / apardo
A-L-U-C-I-N-A-D-O
Lo de los módulos CPAN me lo imaginaba aunque no daba con ellos, pero lo del libro:
Una vez más, muchas gracias explorer, ahora me toca estudiar tanta info.
saludos / apardo
- apardo
- Perlero nuevo
- Mensajes: 17
- Registrado: 2009-03-31 16:58 @748
3 mensajes
• Página 1 de 1
¿Quién está conectado?
Usuarios navegando por este Foro: No hay usuarios registrados visitando el Foro y 7 invitados