OK, with no feedback on this, I have removed the copied comments from geo_ops.c, reorganized a little, and removed the GPL copyright notice.

## Advertising

Patch attached as unified diff so you can see the line changes easier. Should this be backpatched to 8.2.X? --------------------------------------------------------------------------- Bruce Momjian wrote: > > I did some research on this item. I downloaded the source code to WN from: > > http://hopf.math.northwestern.edu/index.html > > I could only find the most recent version. wn-2.4.7. I then looked at > its image.c file: > > http://momjian.us/expire/image.c > > I looked at the last two functions in the file and compared it to what > we have in CVS, particularly the version of the code when it was first > added to CVS: > > > http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/utils/adt/geo_ops.c?rev=1.13;content-type=text%2Fplain > > Again, look at the last two functions in the file. > > You will see similarities and differences. Many of the variable names > are the same, and there is an identical comment block. The algorithm > used is very similar as well, but the style and formatting is different. > > I have updated the code comment in CVS to mention the web site, GPL > license, and article describing the algorithm. > > Not sure where to go from here. > > --------------------------------------------------------------------------- > > bruce wrote: > > Tom Lane wrote: > > > [ redirecting to -hackers, as I see no need for this to be a core issue ] > > > > > > Charles Comiskey <[EMAIL PROTECTED]> writes: > > > > Hello, > > > > I've recently looked through the PostgreSQL code and a couple of > > > > questions > > > > surfaced. I was hoping someone here may be able to answer them. Two > > > > have > > > > links to possible GPL sources and the third is just a contribution > > > > question. > > > > > > > item #1: Does the geo_ops.c file contain GPL code? > > > > Embedded within the geo_ops.c file is a John Franks copyright statement > > > > referring to wn/image.c file from WN Server 1.15.1. WN Server appears > > > > to > > > > have been under the GPL license since 0.94 and continues to be offered > > > > under the GPL license today. John's letter to Linux Journal seems to > > > > only > > > > point the user to his WN Server distribution vs granting any specific > > > > license. > > > > The comment is: > > > > /* poly_contain_pt() > > * Test to see if the point is inside the polygon. > > * Code adapted from integer-based routines in > > * Wn: A Server for the HTTP > > * File: wn/image.c > > * Version 1.15.1 > > * Copyright (C) 1995 <by John Franks> > > * (code offered for use by J. Franks in Linux Journal letter.) > > */ > > > > That term "adapted from" isn't something Thomas would idly type, I > > think. I bet it means he looked at John Franks' code and used it as a > > base for our code. I am not concerned. > > > > > > Questions: > > > > 1) Is any John Franks code really in this file? > > > > 2) Did John provide a separate license for PostgreSQL to license it > > > > under > > > > the BSD license? > > > > > > This code seems to have been inserted by Tom Lockhart on 1997-07-29 > > > (geo_ops.c rev 1.13). Tom, any info on the copyright status? > > > > > > > References: > > > > - 1994 e-mail with GPL reference to WN Server v0.94: > > > > http://1997.webhistory.org/www.lists/www-talk.1994q4/1080.html > > > > - 1995 e-mail from John with GPL license text reference: > > > > http://1997.webhistory.org/www.lists/www-talk.1995q1/0482.html > > > > - WN Server url today: http://hopf.math.northwestern.edu/ > > > > - Link to Linux Journal article: > > > > http://www.linuxjournal.com/article/2197 > > > > > > > > -- > Bruce Momjian [EMAIL PROTECTED] > EnterpriseDB http://www.enterprisedb.com > > + If your life is a hard drive, Christ can be your backup. + > > ---------------------------(end of broadcast)--------------------------- > TIP 6: explain analyze is your friend -- Bruce Momjian <[EMAIL PROTECTED]> http://momjian.us EnterpriseDB http://www.enterprisedb.com + If your life is a hard drive, Christ can be your backup. +

Index: geo_ops.c =================================================================== RCS file: /cvsroot/pgsql/src/backend/utils/adt/geo_ops.c,v retrieving revision 1.95 retrieving revision 1.96 diff -u -r1.95 -r1.96 --- geo_ops.c 27 Feb 2007 23:48:08 -0000 1.95 +++ geo_ops.c 5 Mar 2007 23:29:14 -0000 1.96 @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/utils/adt/geo_ops.c,v 1.95 2007/02/27 23:48:08 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/utils/adt/geo_ops.c,v 1.96 2007/03/05 23:29:14 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -5063,128 +5063,126 @@ ***********************************************************************/ /* - * Test to see if the point is inside the polygon. - * Code adapted from integer-based routines in WN: A Server for the HTTP + * Test to see if the point is inside the polygon, returns 1/0, or 2 if + * the point is on the polygon. + * Code adapted but not copied from integer-based routines in WN: A + * Server for the HTTP * version 1.15.1, file wn/image.c - * GPL Copyright (C) 1995 by John Franks * http://hopf.math.northwestern.edu/index.html * Description of algorithm: http://www.linuxjournal.com/article/2197 + * http://www.linuxjournal.com/article/2029 */ -#define HIT_IT INT_MAX +#define POINT_ON_POLYGON INT_MAX static int point_inside(Point *p, int npts, Point *plist) { double x0, y0; - double px, - py; - int i; + double prev_x, + prev_y; + int i = 0; double x, y; - int cross, - crossnum; - -/* - * We calculate crossnum, which is twice the crossing number of a - * ray from the origin parallel to the positive X axis. - * A coordinate change is made to move the test point to the origin. - * Then the function lseg_crossing() is called to calculate the crossnum of - * one segment of the translated polygon with the ray which is the - * positive X-axis. - */ + int cross, total_cross = 0; - crossnum = 0; - i = 0; if (npts <= 0) return 0; + /* compute first polygon point relative to single point */ x0 = plist[0].x - p->x; y0 = plist[0].y - p->y; - px = x0; - py = y0; + prev_x = x0; + prev_y = y0; + /* loop over polygon points and aggregate total_cross */ for (i = 1; i < npts; i++) { + /* compute next polygon point relative to single point */ x = plist[i].x - p->x; y = plist[i].y - p->y; - if ((cross = lseg_crossing(x, y, px, py)) == HIT_IT) + /* compute previous to current point crossing */ + if ((cross = lseg_crossing(x, y, prev_x, prev_y)) == POINT_ON_POLYGON) return 2; - crossnum += cross; - - px = x; - py = y; + total_cross += cross; + + prev_x = x; + prev_y = y; } - if ((cross = lseg_crossing(x0, y0, px, py)) == HIT_IT) + + /* now do the first point */ + if ((cross = lseg_crossing(x0, y0, prev_x, prev_y)) == POINT_ON_POLYGON) return 2; - crossnum += cross; - if (crossnum != 0) + total_cross += cross; + + if (total_cross != 0) return 1; return 0; } /* lseg_crossing() - * The function lseg_crossing() returns +2, or -2 if the segment from (x,y) - * to previous (x,y) crosses the positive X-axis positively or negatively. - * It returns +1 or -1 if one endpoint is on this ray, or 0 if both are. - * It returns 0 if the ray and the segment don't intersect. - * It returns HIT_IT if the segment contains (0,0) + * Returns +/-2 if line segment crosses the positive X-axis in a +/- direction. + * Returns +/-1 if one point is on the positive X-axis. + * Returns 0 if both points are on the positive X-axis, or there is no crossing. + * Returns POINT_ON_POLYGON if the segment contains (0,0). + * Wow, that is one confusing API, but it is used above, and when summed, + * can tell is if a point is in a polygon. */ static int -lseg_crossing(double x, double y, double px, double py) +lseg_crossing(double x, double y, double prev_x, double prev_y) { double z; - int sgn; - - /* If (px,py) = (0,0) and not first call we have already sent HIT_IT */ + int y_sign; if (FPzero(y)) - { - if (FPzero(x)) - { - return HIT_IT; - - } + { /* y == 0, on X axis */ + if (FPzero(x)) /* (x,y) is (0,0)? */ + return POINT_ON_POLYGON; else if (FPgt(x, 0)) - { - if (FPzero(py)) - return FPgt(px, 0) ? 0 : HIT_IT; - return FPlt(py, 0) ? 1 : -1; - + { /* x > 0 */ + if (FPzero(prev_y)) /* y and prev_y are zero */ + /* prev_x > 0? */ + return FPgt(prev_x, 0) ? 0 : POINT_ON_POLYGON; + return FPlt(prev_y, 0) ? 1 : -1; } else - { /* x < 0 */ - if (FPzero(py)) - return FPlt(px, 0) ? 0 : HIT_IT; + { /* x < 0, x not on positive X axis */ + if (FPzero(prev_y)) + /* prev_x < 0? */ + return FPlt(prev_x, 0) ? 0 : POINT_ON_POLYGON; return 0; } } - - /* Now we know y != 0; set sgn to sign of y */ - sgn = (FPgt(y, 0) ? 1 : -1); - if (FPzero(py)) - return FPlt(px, 0) ? 0 : sgn; - - if (FPgt((sgn * py), 0)) - { /* y and py have same sign */ - return 0; - - } else - { /* y and py have opposite signs */ - if (FPge(x, 0) && FPgt(px, 0)) - return 2 * sgn; - if (FPlt(x, 0) && FPle(px, 0)) - return 0; - - z = (x - px) * y - (y - py) * x; - if (FPzero(z)) - return HIT_IT; - return FPgt((sgn * z), 0) ? 0 : 2 * sgn; + { /* y != 0 */ + /* compute y crossing direction from previous point */ + y_sign = FPgt(y, 0) ? 1 : -1; + + if (FPzero(prev_y)) + /* previous point was on X axis, so new point is either off or on */ + return FPlt(prev_x, 0) ? 0 : y_sign; + else if (FPgt(y_sign * prev_y, 0)) + /* both above or below X axis */ + return 0; /* same sign */ + else + { /* y and prev_y cross X-axis */ + if (FPge(x, 0) && FPgt(prev_x, 0)) + /* both non-negative so cross positive X-axis */ + return 2 * y_sign; + if (FPlt(x, 0) && FPle(prev_x, 0)) + /* both non-positive so do not cross positive X-axis */ + return 0; + + /* x and y cross axises, see URL above point_inside() */ + z = (x - prev_x) * y - (y - prev_y) * x; + if (FPzero(z)) + return POINT_ON_POLYGON; + return FPgt((y_sign * z), 0) ? 0 : 2 * y_sign; + } } }

---------------------------(end of broadcast)--------------------------- TIP 9: In versions below 8.0, the planner will ignore your desire to choose an index scan if your joining column's datatypes do not match