Ryan – Page 12 – Ryan Schulze

How to get the intersecting area of two polygons in MySQL

December 3, 2012September 27, 2014RyanGeometric Objects, Intersection, MySQL, polygon, spatial, stored procedure

I was playing around with spatial features of MySQL this weekend and stumbled into a problem where I was looking for the area of two rectangles that overlap. MySQL provides a function to check if they overlap, but no function to extract the region that overlaps.

I’ve never written a stored routine in MySQL before, so I decided it would be a good exercise to try making one. As you can see the function is pretty straightforward and it assumes you are working with rectangles, but other than that it does what it is supposed to.
You pass the function 2 polygons (e.g. Intersection(a.poly,b.poly)), and it returns the intersecting area as a new polygon.

DROP FUNCTION IF EXISTS Intersection;
DELIMITER //
CREATE FUNCTION Intersection(g1 POLYGON, g2 POLYGON) RETURNS POLYGON DETERMINISTIC
BEGIN
  DECLARE minx1, minx2, maxx1, maxx2 DOUBLE;
  DECLARE miny1, miny2, maxy1, maxy2 DOUBLE;
  DECLARE miny,  maxy,  minx,  maxx DOUBLE;
  SET minx1 =    LEAST(X(PointN(ExteriorRing(g1),1)),X(PointN(ExteriorRing(g1),2)),X(PointN(ExteriorRing(g1),3)),X(PointN(ExteriorRing(g1),4)));
  SET maxx1 = GREATEST(X(PointN(ExteriorRing(g1),1)),X(PointN(ExteriorRing(g1),2)),X(PointN(ExteriorRing(g1),3)),X(PointN(ExteriorRing(g1),4)));
  SET miny1 =    LEAST(Y(PointN(ExteriorRing(g1),1)),Y(PointN(ExteriorRing(g1),2)),Y(PointN(ExteriorRing(g1),3)),Y(PointN(ExteriorRing(g1),4)));
  SET maxy1 = GREATEST(Y(PointN(ExteriorRing(g1),1)),Y(PointN(ExteriorRing(g1),2)),Y(PointN(ExteriorRing(g1),3)),Y(PointN(ExteriorRing(g1),4)));
  SET minx2 =    LEAST(X(PointN(ExteriorRing(g2),1)),X(PointN(ExteriorRing(g2),2)),X(PointN(ExteriorRing(g2),3)),X(PointN(ExteriorRing(g2),4)));
  SET maxx2 = GREATEST(X(PointN(ExteriorRing(g2),1)),X(PointN(ExteriorRing(g2),2)),X(PointN(ExteriorRing(g2),3)),X(PointN(ExteriorRing(g2),4)));
  SET miny2 =    LEAST(Y(PointN(ExteriorRing(g2),1)),Y(PointN(ExteriorRing(g2),2)),Y(PointN(ExteriorRing(g2),3)),Y(PointN(ExteriorRing(g2),4)));
  SET maxy2 = GREATEST(Y(PointN(ExteriorRing(g2),1)),Y(PointN(ExteriorRing(g2),2)),Y(PointN(ExteriorRing(g2),3)),Y(PointN(ExteriorRing(g2),4)));
  SET minx = IF ( minx2 > minx1 , minx2 , minx1 );
  SET maxx = IF ( maxx2 > maxx1 , maxx1 , maxx2 );
  SET miny = IF ( miny2 > miny1 , miny2 , miny1 );
  SET maxy = IF ( maxy2 > maxy1 , maxy1 , maxy2 );
  RETURN POLYGON(LINESTRING(POINT(minx,miny),POINT(maxx,miny), POINT(maxx,maxy), POINT(minx,maxy),POINT(minx,miny)));
END //
DELIMITER ;

DROP FUNCTION IF EXISTS Intersection;

DELIMITER //

CREATE FUNCTION Intersection(g1 POLYGON, g2 POLYGON) RETURNS POLYGON DETERMINISTIC

BEGIN

DECLARE minx1, minx2, maxx1, maxx2 DOUBLE;

DECLARE miny1, miny2, maxy1, maxy2 DOUBLE;

DECLARE miny, maxy, minx, maxx DOUBLE;

SET minx1 = LEAST(X(PointN(ExteriorRing(g1),1)),X(PointN(ExteriorRing(g1),2)),X(PointN(ExteriorRing(g1),3)),X(PointN(ExteriorRing(g1),4)));

SET maxx1 = GREATEST(X(PointN(ExteriorRing(g1),1)),X(PointN(ExteriorRing(g1),2)),X(PointN(ExteriorRing(g1),3)),X(PointN(ExteriorRing(g1),4)));

SET miny1 = LEAST(Y(PointN(ExteriorRing(g1),1)),Y(PointN(ExteriorRing(g1),2)),Y(PointN(ExteriorRing(g1),3)),Y(PointN(ExteriorRing(g1),4)));

SET maxy1 = GREATEST(Y(PointN(ExteriorRing(g1),1)),Y(PointN(ExteriorRing(g1),2)),Y(PointN(ExteriorRing(g1),3)),Y(PointN(ExteriorRing(g1),4)));

SET minx2 = LEAST(X(PointN(ExteriorRing(g2),1)),X(PointN(ExteriorRing(g2),2)),X(PointN(ExteriorRing(g2),3)),X(PointN(ExteriorRing(g2),4)));

SET maxx2 = GREATEST(X(PointN(ExteriorRing(g2),1)),X(PointN(ExteriorRing(g2),2)),X(PointN(ExteriorRing(g2),3)),X(PointN(ExteriorRing(g2),4)));

SET miny2 = LEAST(Y(PointN(ExteriorRing(g2),1)),Y(PointN(ExteriorRing(g2),2)),Y(PointN(ExteriorRing(g2),3)),Y(PointN(ExteriorRing(g2),4)));

SET maxy2 = GREATEST(Y(PointN(ExteriorRing(g2),1)),Y(PointN(ExteriorRing(g2),2)),Y(PointN(ExteriorRing(g2),3)),Y(PointN(ExteriorRing(g2),4)));

SET minx = IF ( minx2 > minx1 , minx2 , minx1 );

SET maxx = IF ( maxx2 > maxx1 , maxx1 , maxx2 );

SET miny = IF ( miny2 > miny1 , miny2 , miny1 );

SET maxy = IF ( maxy2 > maxy1 , maxy1 , maxy2 );

RETURN POLYGON(LINESTRING(POINT(minx,miny),POINT(maxx,miny), POINT(maxx,maxy), POINT(minx,maxy),POINT(minx,miny)));

END //

DELIMITER ;

Example comparing some rectangles in 2 tables using the function:

CREATE TABLE `poly1` (
  `id` int(10) unsigned NOT NULL,
  `poly` polygon NOT NULL,
  PRIMARY KEY (`id`),
  SPATIAL KEY `poly` (`poly`)
) ENGINE=MyISAM;

CREATE TABLE `poly2` (
  `id` int(10) unsigned NOT NULL,
  `poly` polygon NOT NULL,
  PRIMARY KEY (`id`),
  SPATIAL KEY `poly` (`poly`)
) ENGINE=MyISAM;

-- Insert some test data into the tables
insert into poly1 (id,poly) VALUES (1, GEOMFROMWKB(POLYGON(LINESTRING(POINT(1,0),POINT(4,0), POINT(4,2), POINT(1,2),POINT(1,0)))));
insert into poly1 (id,poly) VALUES (2, GEOMFROMWKB(POLYGON(LINESTRING(POINT(6,0),POINT(10,0),POINT(10,2),POINT(6,2),POINT(6,0)))));
insert into poly1 (id,poly) VALUES (3, GEOMFROMWKB(POLYGON(LINESTRING(POINT(10,10),POINT(20,10),POINT(20,5),POINT(10,5),POINT(10,10)))));

insert into poly2 (id,poly) VALUES (1, GEOMFROMWKB(POLYGON(LINESTRING(POINT(1,0),POINT(4,0), POINT(4,2), POINT(1,2),POINT(1,0)))));
insert into poly2 (id,poly) VALUES (2, GEOMFROMWKB(POLYGON(LINESTRING(POINT(3,0),POINT(7,0), POINT(7,2), POINT(3,2),POINT(3,0)))));
insert into poly2 (id,poly) VALUES (3, GEOMFROMWKB(POLYGON(LINESTRING(POINT(5,0),POINT(7,0), POINT(7,2), POINT(5,2),POINT(5,0)))));
insert into poly2 (id,poly) VALUES (4, GEOMFROMWKB(POLYGON(LINESTRING(POINT(8,0),POINT(10,0),POINT(10,2),POINT(8,2),POINT(8,0)))));
insert into poly2 (id,poly) VALUES (5, GEOMFROMWKB(POLYGON(LINESTRING(POINT(3,0),POINT(6,0), POINT(6,2), POINT(3,2),POINT(3,0)))));
insert into poly2 (id,poly) VALUES (6, GEOMFROMWKB(POLYGON(LINESTRING(POINT(5,0),POINT(11,0),POINT(11,2),POINT(5,2),POINT(5,0)))));
insert into poly2 (id,poly) VALUES (7, GEOMFROMWKB(POLYGON(LINESTRING(POINT(12,8),POINT(18,8),POINT(18,4),POINT(12,4),POINT(12,8)))));

SELECT
 a.id as 'poly1',
 b.id as 'poly2',
 cast(100/Area(a.poly)*Area(Intersection(a.poly,b.poly)) as decimal(4,2)) as '% of poly2 in poly1'
FROM
 poly1 a,
 poly2 b
WHERE
 MBROverlaps(b.poly,a.poly);

CREATE TABLE `poly1` (

`id` int(10) unsigned NOT NULL,

`poly` polygon NOT NULL,

PRIMARY KEY (`id`),

SPATIAL KEY `poly` (`poly`)

) ENGINE=MyISAM;

CREATE TABLE `poly2` (

`id` int(10) unsigned NOT NULL,

`poly` polygon NOT NULL,

PRIMARY KEY (`id`),

SPATIAL KEY `poly` (`poly`)

) ENGINE=MyISAM;

-- Insert some test data into the tables

insert into poly1 (id,poly) VALUES (1, GEOMFROMWKB(POLYGON(LINESTRING(POINT(1,0),POINT(4,0), POINT(4,2), POINT(1,2),POINT(1,0)))));

insert into poly1 (id,poly) VALUES (2, GEOMFROMWKB(POLYGON(LINESTRING(POINT(6,0),POINT(10,0),POINT(10,2),POINT(6,2),POINT(6,0)))));

insert into poly1 (id,poly) VALUES (3, GEOMFROMWKB(POLYGON(LINESTRING(POINT(10,10),POINT(20,10),POINT(20,5),POINT(10,5),POINT(10,10)))));

insert into poly2 (id,poly) VALUES (1, GEOMFROMWKB(POLYGON(LINESTRING(POINT(1,0),POINT(4,0), POINT(4,2), POINT(1,2),POINT(1,0)))));

insert into poly2 (id,poly) VALUES (2, GEOMFROMWKB(POLYGON(LINESTRING(POINT(3,0),POINT(7,0), POINT(7,2), POINT(3,2),POINT(3,0)))));

insert into poly2 (id,poly) VALUES (3, GEOMFROMWKB(POLYGON(LINESTRING(POINT(5,0),POINT(7,0), POINT(7,2), POINT(5,2),POINT(5,0)))));

insert into poly2 (id,poly) VALUES (4, GEOMFROMWKB(POLYGON(LINESTRING(POINT(8,0),POINT(10,0),POINT(10,2),POINT(8,2),POINT(8,0)))));

insert into poly2 (id,poly) VALUES (5, GEOMFROMWKB(POLYGON(LINESTRING(POINT(3,0),POINT(6,0), POINT(6,2), POINT(3,2),POINT(3,0)))));

insert into poly2 (id,poly) VALUES (6, GEOMFROMWKB(POLYGON(LINESTRING(POINT(5,0),POINT(11,0),POINT(11,2),POINT(5,2),POINT(5,0)))));

insert into poly2 (id,poly) VALUES (7, GEOMFROMWKB(POLYGON(LINESTRING(POINT(12,8),POINT(18,8),POINT(18,4),POINT(12,4),POINT(12,8)))));

SELECT

a.id as 'poly1',

b.id as 'poly2',

cast(100/Area(a.poly)*Area(Intersection(a.poly,b.poly)) as decimal(4,2)) as '% of poly2 in poly1'

FROM

poly1 a,

poly2 b

WHERE

MBROverlaps(b.poly,a.poly);

Result:

poly1	poly2	% of poly2 in poly1
1	2	33.33
1	5	33.33
2	2	25.00
2	3	25.00
3	7	36.00

poly1 poly2 % of poly2 in poly1

1 2 33.33

1 5 33.33

2 2 25.00

2 3 25.00

3 7 36.00

Picture galleries from trips this summer

September 13, 2012Ryannew york, oldtimer, pictures, renaissance, summer

Since we are going on a small vacation tomorrow I wanted to get a couple picture galleries up before I start filling my drive up with new pictures. These are all from small trips/excursions we took over the summer. Unfortunately no pictures from the canoe on the st. croix river.

[album id=31 template=dopefish]

[album id=32 template=dopefish]

[album id=33 template=dopefish]

How to find the fingerprints of public keys in authorized_keys

August 15, 2012September 27, 2014Ryanauth, authorized_keys, bash, fingerprint, ssh, ssh keys

If you use keys for SSH authentication (and you should) then you have probably run into the situation that the auth.log shows that someone logged in, even which local user was used (e.g. root), but you have no idea which of the keys in ~/.ssh/autorized_keys was used. The first step you can do to see what is going on, is increasing the log level of the SSH daemon:

/etc/ssh/sshd_config

LogLevel VERBOSE

1	LogLevel VERBOSE

That will spit out the fingerprint of the SSH key used to log in. Example log entry for a successful login:

Aug 15 11:47:40 security sshd[1924]: Connection from 192.168.199.1 port 39648
Aug 15 11:47:41 security sshd[1924]: Found matching DSA key: df:45:12:ea:d2:92:a2:42:aa:ba:25:1a:90:82:1a:1c
Aug 15 11:47:41 security sshd[1924]: Postponed publickey for root from 192.168.199.1 port 39648 ssh2 [preauth]
Aug 15 11:47:42 security sshd[1924]: Found matching DSA key: df:45:12:ea:d2:92:a2:42:aa:ba:25:1a:90:82:1a:1c
Aug 15 11:47:42 security sshd[1924]: Accepted publickey for root from 192.168.199.1 port 39648 ssh2
Aug 15 11:47:42 security sshd[1924]: pam_unix(sshd:session): session opened for user root by (uid=0)

Aug 15 11:47:40 security sshd[1924]: Connection from 192.168.199.1 port 39648

Aug 15 11:47:41 security sshd[1924]: Found matching DSA key: df:45:12:ea:d2:92:a2:42:aa:ba:25:1a:90:82:1a:1c

Aug 15 11:47:41 security sshd[1924]: Postponed publickey for root from 192.168.199.1 port 39648 ssh2 [preauth]

Aug 15 11:47:42 security sshd[1924]: Found matching DSA key: df:45:12:ea:d2:92:a2:42:aa:ba:25:1a:90:82:1a:1c

Aug 15 11:47:42 security sshd[1924]: Accepted publickey for root from 192.168.199.1 port 39648 ssh2

Aug 15 11:47:42 security sshd[1924]: pam_unix(sshd:session): session opened for user root by (uid=0)

Now that we have the fingerprint of the ssh key used to login, we will need ssh-keygen to spit out the fingerprints of the public keys in ~/.ssh/authorized_keys to be able to compare them. So I wrote a little wrapper called ssh-fingerprint.sh around ssh-keygen to feed it all the public keys from authorized_keys (if you want you can even fit the whole while loop as a oneliner):

#!/bin/bash 
initialize() { #{{{
	# Treat unset variables as an error
	set -o nounset
	tempfile=$(mktemp)
	authorized_keys="${HOME}/.ssh/authorized_keys"
	trap cleanup TERM EXIT # clean up if script exits
} #}}}

cleanup() { #{{{
	rm -f ${tempfile}
	exit 0
} #}}}

#===============================================================================
# Main
#===============================================================================
initialize

if [ ! -e ${authorized_keys} ]
then
	echo -e "\nERROR: ${authorized_keys} file not found\n"
	exit 
fi

while read line
do 
	echo "${line}" &gt;  ${tempfile}
	ssh-keygen -l -f ${tempfile}
done &lt; ${authorized_keys}

#!/bin/bash

initialize() { #{{{

# Treat unset variables as an error

set -o nounset

tempfile=$(mktemp)

authorized_keys="${HOME}/.ssh/authorized_keys"

trap cleanup TERM EXIT # clean up if script exits

} #}}}

cleanup() { #{{{

rm -f ${tempfile}

exit 0

} #}}}

#===============================================================================

# Main

#===============================================================================

initialize

if [ ! -e ${authorized_keys} ]

then

echo -e "\nERROR: ${authorized_keys} file not found\n"

exit

while read line

echo "${line}" > ${tempfile}

ssh-keygen -l -f ${tempfile}

done < ${authorized_keys}

How to check if a IP (ipv4) address is valid in pure Bash

July 25, 2012August 26, 2013Ryanbash, ipv4

Here is a small bash function to check if a IP is valid (4 octets, each octet < 256). I find it somewhat elegant since instead of using a lot of case/if/then constructs or a crazy long regex it splits the IP into each octet (and stores them in an array, and then uses a combination of regex and bit shifting to check each octet.

is_valid_ipv4() {
  local -a octets=( ${1//\./ } )
  local RETURNVALUE=0

  # return an error if the IP doesn't have exactly 4 octets
  [[ ${#octets[@]} -ne 4 ]] &amp;&amp; return 1

  for octet in ${octets[@]}
  do
    if [[ ${octet} =~ ^[0-9]{1,3}$ ]]
    then # shift number by 8 bits, anything larger than 255 will be > 0
      ((RETURNVALUE += octet>>8 ))
    else # octet wasn't numeric, return error
      return 1
    fi
  done
  return ${RETURNVALUE}
}

is_valid_ipv4() {

local -a octets=( ${1//\./ } )

local RETURNVALUE=0

# return an error if the IP doesn't have exactly 4 octets

[[ ${#octets[@]} -ne 4 ]] && return 1

for octet in ${octets[@]}

if [[ ${octet} =~ ^[0-9]{1,3}$ ]]

then # shift number by 8 bits, anything larger than 255 will be > 0

((RETURNVALUE += octet>>8 ))

else # octet wasn't numeric, return error

return 1

done

return ${RETURNVALUE}

}

The function will return 0 if the IP is valid, and 1 or higher if it encountered an error (you can check with the $? variable directly after calling the function)
Example:

is_valid_ipv4 ${ip}
if [[ $? -gt 0 ]]
then 
	echo "invalid IP"
else
	echo "valid IP"
fi

is_valid_ipv4 ${ip}

if [[ $? -gt 0 ]]

then

echo "invalid IP"

else

echo "valid IP"

silica.dopefish.de – catching data leaks

July 11, 2012July 11, 2012Ryan

I was testing a PHP script for security flaws today and needed a way to check if it was possible to “accidently” leak sensitive data to an external server. So I threw together a small script to save the contents of the $_SERVER $_COOKIE $POST and $_GET arrays and dump them in a file. Since it worked so good I decided to leave the site online.

Why did I call it silica? Because silica gel absorbs and stores fluids like this website absorbs information thrown at it. How to use it? Just get your application to connect to silica.dopefish.de instead of where it intended to connect to (by overwriting variables, DNS foo, be creative) and see what happens.

Base Domain: silica.dopefish.de
The webserver will catch any URL (regardless what path or filename) and log the environment. The only exception is the logfile.

Logfile: http://silica.dopefish.de/access.log
The log is automatically emptied every 10 minutes, so save the output if you need it.