> -----Original Message----- > From: Kenneth Chan [mailto:[EMAIL PROTECTED]] > Sent: Wednesday, May 22, 2002 12:24 PM > To: [EMAIL PROTECTED] > Subject: [HACKERS] A more precise polygon_overlap() > > > Gents, > > 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.
For convex polygons, it is very simple. Unfortunately, most polygon's don't fall into that category. For polygons of arbitrary shape, it is an incredibly complex problem. This is a very good article on the subject: "On Local Heuristics to Speed Up Polygon-Polygon Intersection Tests" by: Wael M. Badawy Center for Advanced Computer Studies University of Southwestern Louisiana Lafayette, LA 70504 [EMAIL PROTECTED] Walid G. Aref Department of Computer Sciences Purdue University West Lafayette, IN 47907 [EMAIL PROTECTED] A link to the above paper is here: http://www.cs.purdue.edu/homes/aref/spdb.html The big problems come from: 1. polygons which are self intersecting 2. polygons that have holes Here is a paper one one sort of idea: http://www.me.cmu.edu/faculty1/shimada/gm97/24700b/project/venkat/projec t/ Here is a list of links that may prove helpful: http://citeseer.nj.nec.com/aref95window.html The most general method I know of is the Weiler-Atherton polygon-polygon clipping algorithm. Here is some stuff on it: http://www.cs.buffalo.edu/faculty/walters/cs480/NewLect10.pdf Here is a fun one: +-------------------+ | /| | +--------------+ | | | /\ | | | | / \ | | | | /____\ | | | | | | | +--------------+ | | | +-------------------+ A triangle lives in a box. The upper right hand corner of the box has an enclave. Detail: ---------------------+ + / /| / / | / / | / / | / / | / / | / / | / / | / / | / / | / / | / / | / / | -------+ + | | | | | | | The point of the triangle on the top nearly touches one line of the enclosing box. To answer questions about interesection are tricky even with a simple example like this. When the polygons are self-intersecting, it can be even more outrageous. ---------------------------(end of broadcast)--------------------------- TIP 4: Don't 'kill -9' the postmaster
