Tech – Page 10 – 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

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"

Wireshark Version 1.8.0 released

June 22, 2012June 22, 2012Ryantcpdump, wireshark

A new version of Wireshark was released yesterday (1.8.0), head on over to http://www.wireshark.org/download.html to download it for your OS.

New and updated features since version 1.6:

Wireshark supports capturing from multiple interfaces at once.
You can now add, edit, and save packet and capture file annotations.
Wireshark, TShark, and their associated utilities now save files using the pcap-ng file format by default. (Your copy of Wireshark might still use the pcap file format if pcap-ng is disabled in your preferences.)
Decryption key management for IEEE 802.11, IPsec, and ISAKMP is easier.
OID resolution is now supported on 64-bit Windows.
The “Save As” menu item has been split into “Save As”, which lets you save a file using a different filename and “Export Specified Packets”, which lets you have more control over which packets are saved.
TCP fast retransmissions are now indicated as an expert info note, rather than a warning, just as TCP retransmissions are.
TCP window updates are no longer colorized as “Bad TCP”.
TShark’s command-line options have changed. The previously undocumented -P option is now -2 option for performing a two-pass analysis; the former -S option is now the -P option for printing packets even if writing to a file, and the -S option is now used to specify a different line separator between packets.
GeoIP IPv6 databases are now supported.

New Virtualbox version, script for easy update of extension pack

March 14, 2012March 14, 2012Ryan2 Commentsbash, extpack, virtualbox

VirtualBox 4.1.10 was released yesterday with a few nice things in the changelog. Updating virtualbox itself is easy, just download the package and update it. Since I seem to stumble over the update of the extension pack every time (on my headless system) I thought I’d write a small script this time so I don’t have to rethink it next time (automatically downloads and installs the current extpack):

#!/bin/bash
URL="$(wget -qO - https://www.virtualbox.org/wiki/Downloads|grep "Oracle VM VirtualBox Extension Pack"|sed "s/.\+\(http:\/\/download.virtualbox.org.\+.vbox-extpack\).\+/\1/")"
File=${URL##*/}

if [[ "${URL}" != "" &amp;&amp; "${File}" != "" ]]
then
  echo "Downloading and installing ${File}" &amp;&amp; \
  wget -qO ${File} ${URL} &amp;&amp; \
  VBoxManage extpack install --replace ${File}
fi

#!/bin/bash

URL="$(wget -qO - https://www.virtualbox.org/wiki/Downloads|grep "Oracle VM VirtualBox Extension Pack"|sed "s/.\+$http:\/\/download.virtualbox.org.\+.vbox-extpack$.\+/\1/")"

File=${URL##*/}

if [[ "${URL}" != "" && "${File}" != "" ]]

then

echo "Downloading and installing ${File}" && \

wget -qO ${File} ${URL} && \

VBoxManage extpack install --replace ${File}