How do I find points that are NOT within a list of polygons using MS SQL?

Question

I have a table of points, and and a table of polygons. I have managed to build queries (MS SQL) to get the containing polygon for a given point, as well as listing all the points within a specified polygon, but I cannot work out how to find all points that are not within any polygon.

The following query lists all points with the containing polygon. My initial thought was to just look points that are not contained (i.e. STContains() <> 1), but this returns all points too, seem there are always polygons that do not contain a given point.

 SELECT points.name, polygons.name
 FROM points CROSS JOIN
 polygons
 WHERE (polygons.shape.STContains(points.shape) = 1) 

How do I find those points that are not within any polygons?

• tr3v: Ah! Many thanks. I had spent way too long on this and knew the answer was staring me in the face. I need to do your course :-) I have copied you reply, so you can delete it now but I guess there is always a possibility of someone else providing the same answer.
• Blerg: Glad you solved it.

Answer 1

At least in PostgreSQL it is much faster to do a left or right join on st_intersects instead and use

"where id is null"

to find those that "don't have a friend"

edit:

Ok, here comes an example tested in SQL Server 2014 express:

There is 2 polygons and 4 points. 2 of them is inside the one of the polygons and oine point on the border of the other polygon. By doing a right join we get back all points, but only those inside a polygon gets a polygon id. So we filter away all points that gets a polygon id and left is the points outside all polygons. In this case only one, point(0 3)

This is, at least in PostGIS a fast way of doing it because the spatial index is used on the intersects operation.

with polygons as
(
 select 'p1' id , geometry::STGeomFromText('polygon ((1 1, 1 5, 5 5, 1 1))', 0) poly
 union all
 select 'p2' id , geometry::STGeomFromText('polygon ((0 0, 1 1, 0 1, 0 0))', 0) poly
)
,
points as
(
 select 1 id, geometry::STGeomFromText('point (0 0)', 0) P
 union all
 select 2 id, geometry::STGeomFromText('point (3 4)', 0) P
 union all
 select 3 id, geometry::STGeomFromText('point (2 3)', 0) P
 union all
 select 4 id, geometry::STGeomFromText('point (0 3)', 0) P
)
select points.id, points.p.STAsText() 
from polygons 
right join 
points 
on polygons.poly.STIntersects(points.p) = 1
where polygons.id is NULL;

• tr3v: You beat me to it - this is exactly what I did, and I have just posted my final solution.
• Inactivated Account: Isn't exactly the same as what you're doing as you can't do a right join with STIntersects in MSSQL... you're doing a right join on two temp tables of numbers... one temp table is generated using the STIntersects function
• tr3v: I just tried your edited solution, and performance was consistently ~20% slower than my solution. Maybe this has more to do with other joins in my query than the spatial join. My solution uses a spatial index according to the execution plan.
• Nicklas Avén: Interesting. I haven't done any testing about performance in MS Sql. But some years ago I found the "not in" method slower in PostGIS. I might try it with the same data set in PostGIS and MS sql if I find time.
• Inactivated Account: nice finally got this to work... thank you for this!!!

Answer 2

My eventual solution after much trial and error was the following simplified (hopefully not oversimplified!) code. This lists all points from allpoints that do not have matches in containedpoints (i.e. those points that are in at least one polygon).

 SELECT allpoints.id, allpoints.name 
 FROM
 (
 SELECT points.id, points.name
 FROM points CROSS JOIN 
 polygons
 WHERE (polygons.geom.STContains(points.geom) = 1) 
 ) AS containedpoints RIGHT OUTER JOIN
 ( 
 SELECT points.id, points.name
 FROM points 
 ) AS allpoints ON containedpoints.id=allpoints.id
 WHERE containedpoints.id IS NULL

• Inactivated Account: since the accepted answer is for another software (postgresql) and actually doesn't work in SQL server, you should mark your own solution as the answer...
• Inactivated Account: Good to have this method - potentially COULD be doing more work depending on the size of the inputs, but will keep this in my toolbox as we deal with this from time to time!
• Nicklas Avén: @mapBaker Interesting. Is it only right join that has limitations like this in Sql Server? Or is it all outer joins? Do you have a link about it?
• Inactivated Account: @NicklasAvén RIGHT JOIN works but I think the problem is how the ST_Intersects function expects a boolen, ie. STIntersects = 1 (gives the intersecting features), or STIntersects = 0 (which should give the NON intersecting, but doesn't) , and I can't see how this works in a select statement or a where clause either...
• Nicklas Avén: @mapBaker, But in this case you will be joining on those actually intersecting, and then finding the ones that doesn't intersect any polygon at all because they don't get any polygon id in the join but instead just null. I will try it when I get to a SQL Server installation.

Answer 3

Assuming you can generate an ID for the points you're trying to isolate, you can (as suggested) use a sub-query to generate a list of points that DO intersect the polygons, then use the ID of those points in the where clause NOT IN statement:

select 
pointID
from points
where pointID not in 
 (
 select distinct
 pointID
 from points
 join polygons
 on points.geom.STIntersects(polygons.geom) = 1
 where polygon.id = '941' -- if you have a particular ID from the polygons you're looking to isolate, but optional if your entire polygon dataset is to be analyzed
 ) 

• tr3v: Thanks, that is more or less what I did (no need for distinct) and used polygon.Contains() instead of point.Intersects() - not sure what is more efficient. I found this to be quite slow, and my final solution was to use all points in polygons outer joined with all points.