Changeset 6fd83c4 in git

Timestamp:

Jan 5, 2012, 1:03:48 PM (11 years ago)

Author:

Martin Lee <martinlee84@…>

Branches:

(u'spielwiese', '828514cf6e480e4bafc26df99217bf2a1ed1ef45')

Children:

34e062be492e096661b73e4bf540240303bdc2ec

Parents:

f9b796e144ec0a1fae5662e82e689bdaa9c6727f

git-author:

Martin Lee <martinlee84@web.de>2012-01-05 13:03:48+01:00

git-committer:

Oleksandr Motsak <motsak@mathematik.uni-kl.de>2012-02-10 14:16:43+01:00

Message:

chg/fix: remove redundant points from polygon
add: new function to obtain the slopes of the right edges of a polygon

Location:

factory

Files:

• cfNewtonPolygon.cc (modified) (2 diffs)
• cfNewtonPolygon.h (modified) (1 diff)

factory/cfNewtonPolygon.cc

@@ -145 +145 @@
     i++;
   }
-  if (i + 1 < sizePoints)
+  if (i + 1 <= sizePoints || i == sizePoints)
   {
     int relArea=
@@ -681 +681 @@
 }
 #endif
+
+//assumes the input is a Newton polygon of a bivariate polynomial which is
+//primitive wrt. x and y, i.e. there is at least one point of the polygon lying
+//on the x-axis and one lying on the y-axis
+int* getRightSide (int** polygon, int sizeOfPolygon, int& sizeOfOutput)
+{
+  int maxY= polygon [0][0];
+  int indexY= 0;
+  for (int i= 1; i < sizeOfPolygon; i++)
+  {
+    if (maxY < polygon [i][0])
+    {
+      maxY= polygon [i][0];
+      indexY= i;
+    }
+    else if (maxY == polygon [i][0])
+    {
+      if (polygon [indexY][1] < polygon[i][1])
+        indexY= i;
+    }
+    if (maxY > polygon [i][0])
+      break;
+  }
+
+  int count= -1;
+  for (int i= indexY; i < sizeOfPolygon; i++)
+  {
+    if (polygon[i][0] == 0)
+    {
+      count= i - indexY;
+      break;
+    }
+  }
+
+  int * result;
+  int index= 0;
+  if (count < 0)
+  {
+    result= new int [sizeOfPolygon - indexY];
+    sizeOfOutput= sizeOfPolygon - indexY;
+    count= sizeOfPolygon - indexY - 1;
+    result [0]= polygon[sizeOfPolygon - 1][0] - polygon [0] [0];
+    index= 1;
+  }
+  else
+  {
+    sizeOfOutput= count;
+    result= new int [count];
+  }
+
+  for (int i= indexY + count; i > indexY; i--, index++)
+    result [index]= polygon [i - 1] [0] - polygon [i] [0];
+
+  return result;
+}

factory/cfNewtonPolygon.h

@@ -49 +49 @@
                  );
 
+/// get the y-direction slopes of all edges with positive slope in y-direction
+/// of a convex polygon with at least one point of the polygon lying on the
+/// x-axis and one lying on the y-axis
+///
+/// @return an array containing the slopes as described above
+int* getRightSide (int** polygon,     ///<[in] vertices of a polygon
+                   int sizeOfPolygon, ///<[in] number of vertices
+                   int& sizeOfOutput  ///<[in,out] size of the output
+                  );
+
 #ifdef HAVE_NTL
 /// Algorithm 5 as described in Convex-Dense Bivariate Polynomial Factorization