Re: [HACKERS] [CORE] GPL Source and Copyright Questions - Mailing list pgsql-patches

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.

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 <comiskey@us.ibm.com> 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   bruce@momjian.us
>   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  <bruce@momjian.us>          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;
+        }
     }
 }