Python – How to Find if Two Polygons Intersect

algorithmintersectionpython

I'm looking for an algorithm, a high level solution, or even a library which can help me determine if two polygons intersect, in Python.

I have the vertices of the two polygons (These are single part polygons without any holes) in two different arrays. The polygons are 2D (i.e. just X and Y coordinates)

I'll like to make an function which will return a boolean indicating whether these two polygons intersect.

Please note that I cannot use arcpy, or any arcgis components in this.

Can you suggest an algorithm or library for doing this?

Best Answer

You could try shapely.

They describe spatial relationships and it work on windows

The spatial data model is accompanied by a group of natural language relationships between geometric objects – contains, intersects, overlaps, touches, etc. – and a theoretical framework for understanding them using the 3x3 matrix of the mutual intersections of their component point sets

The following code shows how you can test for intersection:

from shapely.geometry import Polygon
p1 = Polygon([(0,0), (1,1), (1,0)])
p2 = Polygon([(0,1), (1,0), (1,1)])
print(p1.intersects(p2))

Related Solutions

[GIS] Checking for number of shapefiles in directory using Python

Check the glob library:

import os
import glob
path = "c:\\my\\dir"

flist = glob.glob(os.path.join(path,"shapefile*"))  <- Notice the *

>>> flist 
["c:\\my\\dir\shapefile.prj","c:\\my\\dir\shapefile.shp",...]

If you want just the fname without the path attached:

 os.path.basename(flist[0]) 
 >>> shapefile.prj

if you want just the file name without the extension:

os.path.basename(flist[0]).split(".")[0]
>>> shapefile

Also if the list is empty, then the file doesn't exist:

if flist not:
    print "File not found"
    break #or os.exit(1)

Edit: Also to check for the only filename in path :

import os
import glob
path = "c:\\my\\dir"

flist = glob.glob(os.path.join(path,"shapefile*"))  <- Notice the *
mlist = []
for file in flist:
    if os.path.basename(file).split(".")[0] not in mlist:
        mlist.append(os.path.basename(file).split(".")[0])
if len(mlist)>1: #(More than filename)
    break

To check if only one shapefile in the dir:

 def file_check(path):
      """Returns true if in path there is only one basename"""
      import os
      mlist = [] 
      for file in os.listdir(path):
          if os.path.basename(file).split(".")[0] not in mlist:
                mlist.append(os.path.basename(file).split(".")[0]
   if len(mlist)>1:
            return True
    else:
            return False

[GIS] How to apply Dijkstra’s algorithm in Python with PostGIS data

What you need is a directed graph. The table osm2po creates for pgRouting is not directed. Nevertheless you can derive one forward and one backward edge from each segment (table-row). The result is an adjacency list - a little different from your representation:

graph = {
  'A': {'B': 10, 'D': 4, 'F': 10},
}

osm2po (and I think pgRouting does also) uses this layout:

'A', 10 , 'B'
'A',  4 , 'D'
'A', 10 , 'F'

Best Answer

Related Solutions

[GIS] Checking for number of shapefiles in directory using Python

[GIS] How to apply Dijkstra’s algorithm in Python with PostGIS data

Related Question