Skip site navigation (1) Skip section navigation (2)

A more precise polygon_overlap()

From: "Kenneth Chan" <kkchan(at)technologist(dot)com>
To: pgsql-hackers(at)postgresql(dot)org
Subject: A more precise polygon_overlap()
Date: 2002-05-22 19:23:35
Message-ID: (view raw, whole thread or download thread mbox)
Lists: pgsql-hackers

I am looking for a more precise polygon overlap test and any comment/pointers/suggestions are appreciated.  Attached is the modified poly_overlap in geoops.c.  

If the polygons pass the bounding box check, the following tests will be carried out.  The tests are terminated as soon as one of them returns true:

1) At least one of the vertex in polygon a is inside polygon b
2) At least one of the vertex in polygon b is inside polygon a
3) At least one edge of polygon a intersects with an edge on polygon b

All these tests could be expensive for polygons with lots of vertices.  Would anyone know where I can find information on a more efficient way of determining polygon overlap.  

Efficiency aside, is there anything obivious I have missed which could lead to an incorrect result?

The end game for me is to be able to test if a path enters a polygon and this is a first step as I am new to postgresql.  Looks like postgresql converts the path to a polygon and call poly_overlap(), which could lead to incorrect result.  At some stage, I might add an overlap operator that accepts a path and a polygon.

Kenneth Chan.
Sign-up for your own FREE Personalized E-mail at

Attachment: geo_ops.c.change
Description: application/octet-stream (2.0 KB)

pgsql-hackers by date

Next:From: Manfred KoizarDate: 2002-05-22 20:00:30
Subject: Re: Killing dead index tuples before they get vacuumed
Previous:From: Neil ConwayDate: 2002-05-22 19:11:56
Subject: ksqo?

Privacy Policy | About PostgreSQL
Copyright © 1996-2017 The PostgreSQL Global Development Group