Geo Fencing - Sample Code

My first blog was about geofencing (read it here). The point-in-polygon algorithm may seem easy enough, but when actually trying to implement it, you will notice that there are some tricky parts to it (like when your point is on the edge of the polygon, or when your polygon contains horizontal lines, etc.). Therefor, I've decided to add some java sample code.

So, here goes...

Points, lines and polygons

First, we'll create some objects to represent our points, lines and polygons:
A point is a position with an x- and an y-coordinate. To apply it to geofencing, you can just think of x-coordinates as longitudes and y-coordinates as latitudes.

A line is a straigth line with a direction (vertex). It has a from-point and a to-point. We will use it to represent the edges of our polygon.

A polygon, obviously, is a multi-sided shape that consists of a number of points.

Objective

Our objective is to create a method for calculating if we are inside the polygon or not.

As described in my first blog post, this method will:

• calculate the lines of the polygon
• filter the lines that intersect with our y-position
• calculate the exact points on which the lines intersect with the y-position
• sort the points by x-position
• use ray casting (out-in-out-in) algorithm for checking if we are inside or outside of the polygon.

In java, it would look something like this:

Now, let's try to implement each sub-method separately...

Calculate the polygon lines

First, the method for calculating the lines of a polygon.

We just take the points of the polygon and connect them together. We then close the polygon by connecting the last point to the first point:
There's no real magic here, it's a very simple method.

Filter the lines that intersect with the y-axis

Next, we need to filter the lines that intersect with our y-axis...

Calculate the x-intersection points at the y-axis

Next we calculate the x-intersection points of the lines at the given y-position, using the following method:

We calculate the x-position of every line, at the provided y, using standard calculus.

Sort the points by x-position

Sorting the points by X-position is easy, we just use a java double comparator:

Check if we are inside or outside of the polygon

And finally, we check if we are inside or outside the polygon, using the ray-casting algorithm:

Initially, we are outside of the polygon. At each point, we invert our status (inside - outside - inside - outside - ...). Until we have reached our x-position. We then know if we're inside or outside of the polygon.

That's it!

We just use simple java code, it can easily be ported to Android, iOS, ...

This code can still be optimized a lot, but the idea was to show how geofencing works (technically).

References:

http://stefanbangels.blogspot.be/2012/12/for-several-years-now-i-have-been.html

http://en.wikipedia.org/wiki/Point_in_polygon

http://en.wikipedia.org/wiki/Slope

http://en.wikipedia.org/wiki/Geo-fence
http://geomalgorithms.com/a03-_inclusion.html

Named placeholders for SQL parameters

JDBC is great.

But there seems to be a useful feature missing:

"Named placeholders for SQL parameters"

PreparedStatement provides a precompiled Statement that can be executed multiple times. The statement can be created by calling the factory method on the java.sql.Connection class:

public PreparedStatement prepareStatement(String sql) 
  throws SQLException;

This method takes an SQL String as an argument, which can contain (?) place holders, for example:

"SELECT name FROM users WHERE id = ?"

You can change the value of the place holders, by parameter index using methods:

public void setString(int parameterIndex, String theString)
  throws SQLException;

public void setLong(int parameterIndex, long theLong) 
  throws SQLException;

...

Very nice indeed.

But shouldn't it be easier if we (additionally) could use NAMED placeholders like this:

"SELECT name FROM users WHERE id = ?{ID}"

And set the place holders values like this:

public void setString(String parameterName, String theString)
  throws SQLException;

public void setLong(String parameterName, int theLong) 
  throws SQLException;

...

Using indexes is error prone. You often need to re-count which index number is used for what parameter. Especially when you're refactoring, bug-fixing or implementing new functionality. Also, when using parameter indexes, you sometimes need to duplicate parameter values, which makes it even less readable.

In my projects, I prefer using my own helper class for adding functionality to Prepared Statements.

Some sample code:

public class PreparedStatementTemplate {

    private enum ParameterType {LONG, STRING}

    private final Pattern placeHolderPattern = Pattern.compile(
        "(\\?\\{([A-Za-z0-9]*)\\})"
    );

    private final PreparedStatement preparedStatement;

    private List<String> placeHolders;

    public PreparedStatementTemplate(
      Connection connection, String sql) throws SQLException {
        this.preparedStatement = connection.prepareStatement(
            extractPlaceHolders(sql)
        );
    }

    private String extractPlaceHolders(String sql) {
        List<String> placeHolders = new LinkedList<String>();
        Matcher matcher = placeHolderPattern.matcher(sql);
        while (matcher.find()) {
            placeHolders.add(matcher.group(2));
        }
        this.placeHolders = placeHolders;
        return matcher.replaceAll("?");
    }

    public void setString(String key, String value) throws SQLException {
        setParameterValue(key, value, ParameterType.STRING);
    }

    public void setLong(String key, long value) throws SQLException {
        setParameterValue(key, value, ParameterType.LONG);
    }
    private void setParameterValue(
        String key, Object value, ParameterType type) throws SQLException {
        for (Integer index : findPlaceHolderIndexes(key)) {
            if (type == ParameterType.LONG) {
                preparedStatement.setLong(index, (Long) value);
            } else if (type == ParameterType.STRING) {
                preparedStatement.setString(index, (String) value);
            } else {
                throw new SQLException("unknown parameter type: " + type);
            }
        }
    }

    public List<Integer> findPlaceHolderIndexes(String key) {
        List<Integer> indexes = new LinkedList<Integer>();
        int n = 1;
        for (String placeHolder : placeHolders) {
            if (key.equalsIgnoreCase(placeHolder)) {
                indexes.add(n);
            }
            n++;
        }
        return indexes;
    }

    public ResultSet executeQuery() throws SQLException {
        return preparedStatement.executeQuery();
    }

    public int executeUpdate() throws SQLException {
        return preparedStatement.executeUpdate();
    }

    public void close() throws SQLException {
        preparedStatement.close();
    }

}

You can use it like this:

PreparedStatementTemplate template = new PreparedStatementTemplate(
    connection, "SELECT name FROM users WHERE id = ?{ID}"
);
try {
    template.setLong("ID", userId);
    ResultSet rs = template.executeQuery();
    try {
        while (rs.next()) {
            System.out.println(rs.getString("NAME"));
        }
    } finally {
        rs.close();
    }
} finally {
    template.close();
}
        
Why isn't this feature embedded in the standard JDBC?  It would make life much easier!

More information about JDBC Prepared Statements can be found here:
http://docs.oracle.com/javase/tutorial/jdbc/basics/prepared.html
http://www.tutorialspoint.com/jdbc/jdbc-statements.htm