this linear crossover can also be considered as two-point crossover
333707
private static void linearCrossover(Program gp1, Program gp2, LGP manager, RandEngine randEngine) {
      // length(gp1) <= length(gp2)
      if (gp1.length() > gp2.length())
      {
         gp1 = gp2;
         gp2 = gp1;
      }

      // select i1 from gp1 and i2 from gp2 such that abs(i1-i2) <= max_crossover_point_distance
      // max_crossover_point_distance=min{length(gp1) - 1, m_max_distance_of_crossover_points}
      int i1 = randEngine.nextInt(gp1.length());
      int i2 = randEngine.nextInt(gp2.length());
      int cross_point_distance = (i1 > i2) ? (i1 - i2) : (i2 - i1);
      int max_crossover_point_distance = (gp1.length() - 1 > manager.getMaxDistanceOfCrossoverPoints() ? manager.getMaxDistanceOfCrossoverPoints() : gp1.length() - 1);
      while (cross_point_distance > max_crossover_point_distance)
      {
         i1 = randEngine.nextInt(gp1.length());
         i2 = randEngine.nextInt(gp2.length());
         cross_point_distance = (i1 > i2) ? (i1 - i2) : (i2 - i1);
      }

      int s1_max = (gp1.length() - i1) > manager.getMaxDifferenceOfSegmentLength() ? manager.getMaxDifferenceOfSegmentLength() : (gp1.length() - i1);
      int s2_max = (gp2.length() - i2) > manager.getMaxDifferenceOfSegmentLength() ? manager.getMaxDifferenceOfSegmentLength() : (gp2.length() - i2);

      // select s1 from gp1 (start at i1) and s2 from gp2 (start at i2)
      // such that length(s1) <= length(s2)
      // and abs(length(s1) - length(s2)) <= m_max_difference_of_segment_length)
      int ls1 = 1 + randEngine.nextInt(s1_max);
      int ls2 = 1 + randEngine.nextInt(s2_max);
      int lsd = (ls1 > ls2) ? (ls1 - ls2) : (ls2 - ls1);
      while ((ls1 > ls2) && (lsd > manager.getMaxDifferenceOfSegmentLength()))
      {
         ls1 = 1 + randEngine.nextInt(s1_max);
         ls2 = 1 + randEngine.nextInt(s2_max);
         lsd = (ls1 > ls2) ? (ls1 - ls2) : (ls2 - ls1);
      }

      if(((gp2.length() - (ls2-ls1)) < manager.getMinProgramLength() || ((gp1.length()+(ls2-ls1)) > manager.getMaxProgramLength())))
      {
         if(randEngine.uniform() < 0.5)
         {
            ls2=ls1;
         }
         else
         {
            ls1=ls2;
         }
         if((i1+ls1) > gp1.length())
         {
            ls1 = gp1.length() - i1;
         }
         if((i2 + ls2) > gp2.length()) {
            ls2 = gp2.length() - i2;
         }
      }



      List<Instruction> instructions1=gp1.getInstructions();
      List<Instruction> instructions2=gp2.getInstructions();

      List<Instruction> instructions1_1=new ArrayList<>();
      List<Instruction> instructions1_2=new ArrayList<>();
      List<Instruction> instructions1_3=new ArrayList<>();

      List<Instruction> instructions2_1=new ArrayList<>();
      List<Instruction> instructions2_2=new ArrayList<>();
      List<Instruction> instructions2_3=new ArrayList<>();

      for(int i=0; i < i1; ++i)
      {
         instructions1_1.add(instructions1.get(i));
      }
      for(int i=i1; i < i1+ls1; ++i)
      {
         instructions1_2.add(instructions1.get(i));
      }
      for(int i=i1+ls1; i < instructions1.size(); ++i)
      {
         instructions1_3.add(instructions1.get(i));
      }

      for(int i=0; i < i2; ++i)
      {
         instructions2_1.add(instructions2.get(i));
      }
      for(int i=i2; i < i2+ls2; ++i)
      {
         instructions2_2.add(instructions2.get(i));
      }
      for(int i=i2+ls2; i < instructions2.size(); ++i)
      {
         instructions2_3.add(instructions2.get(i));
      }

      instructions1.clear();
      instructions2.clear();

      for(int i=0; i < i1; ++i)
      {
         instructions1.add(instructions1_1.get(i));
      }
      for(int i=0; i < ls2; ++i)
      {
         instructions1.add(InstructionHelper.reassign2Program(instructions2_2.get(i), gp1));
      }
      for(int i=0; i < instructions1_3.size(); ++i)
      {
         instructions1.add(instructions1_3.get(i));
      }

      for(int i=0; i < i2; ++i)
      {
         instructions2.add(instructions2_1.get(i));
      }
      for(int i=0; i < ls1; ++i)
      {
         instructions2.add(InstructionHelper.reassign2Program(instructions1_2.get(i), gp2));
      }
      for(int i=0; i < instructions2_3.size(); ++i)
      {
         instructions2.add(instructions2_3.get(i));
      }

      gp1.invalidateCost();
      gp2.invalidateCost();
   }
318005
private static boolean linearPathIntersectsLinearPath_(
			MultiPath multipathA, MultiPath multipathB, double tolerance) {
		MultiPathImpl multi_path_impl_a = (MultiPathImpl) multipathA._getImpl();
		MultiPathImpl multi_path_impl_b = (MultiPathImpl) multipathB._getImpl();

		SegmentIteratorImpl segIterA = multi_path_impl_a.querySegmentIterator();
		SegmentIteratorImpl segIterB = multi_path_impl_b.querySegmentIterator();

        PairwiseIntersectorImpl intersector = new PairwiseIntersectorImpl(multi_path_impl_a, multi_path_impl_b, tolerance, false);

		while (intersector.next()) {
			int vertex_a = intersector.getRedElement();
			int vertex_b = intersector.getBlueElement();

			segIterA.resetToVertex(vertex_a);
			segIterB.resetToVertex(vertex_b);
			Segment segmentA = segIterA.nextSegment();
			Segment segmentB = segIterB.nextSegment();

			int result = segmentB.intersect(segmentA, null, null, null,
					tolerance);

			if (result > 0) {
				return true;
			}
		}

		return false;
	}
473762
private static boolean multiPointWithinEnvelope_(MultiPoint multipoint_a,
			Envelope envelope_b, double tolerance,
			ProgressTracker progress_tracker) {
		Envelope2D env_a = new Envelope2D(), env_b = new Envelope2D();
		multipoint_a.queryEnvelope2D(env_a);
		envelope_b.queryEnvelope2D(env_b);

		if (!envelopeInfContainsEnvelope_(env_b, env_a, tolerance))
			return false;

		if (env_b.getHeight() <= tolerance && env_b.getWidth() <= tolerance)
			return envelopeEqualsEnvelope_(env_a, env_b, tolerance,
					progress_tracker); // treat as point

		if (env_b.getHeight() <= tolerance || env_b.getWidth() <= tolerance) {// treat
																				// as
																				// line

			boolean b_interior = false;

			Envelope2D env_b_deflated = new Envelope2D(), env_b_inflated = new Envelope2D();
			env_b_deflated.setCoords(env_b);
			env_b_inflated.setCoords(env_b);

			if (env_b.getHeight() > tolerance)
				env_b_deflated.inflate(0, -tolerance);
			else
				env_b_deflated.inflate(-tolerance, 0);

			env_b_inflated.inflate(tolerance, tolerance);

			Point2D pt_a = new Point2D();

			for (int i = 0; i < multipoint_a.getPointCount(); i++) {
				multipoint_a.getXY(i, pt_a);

				if (!env_b_inflated.contains(pt_a))
					return false;

				if (env_b.getHeight() > tolerance) {
					if (pt_a.y > env_b_deflated.ymin
							&& pt_a.y < env_b_deflated.ymax)
						b_interior = true;
				} else {
					if (pt_a.x > env_b_deflated.xmin
							&& pt_a.x < env_b_deflated.xmax)
						b_interior = true;
				}
			}

			return b_interior;
		}

		// treat as area

		boolean b_interior = false;

		Envelope2D env_b_deflated = new Envelope2D(), env_b_inflated = new Envelope2D();
		env_b_deflated.setCoords(env_b);
		env_b_inflated.setCoords(env_b);
		env_b_deflated.inflate(-tolerance, -tolerance);
		env_b_inflated.inflate(tolerance, tolerance);

		Point2D pt_a = new Point2D();

		// we loop to find a proper interior intersection (i.e. something inside
		// instead of just on the boundary)
		for (int i = 0; i < multipoint_a.getPointCount(); i++) {
			multipoint_a.getXY(i, pt_a);

			if (!env_b_inflated.contains(pt_a))
				return false;

			if (env_b_deflated.containsExclusive(pt_a))
				b_interior = true;
		}

		return b_interior;
	}
1374321
private static boolean polylineRelateMultiPoint_(Polyline polyline_a,
			MultiPoint multipoint_b, double tolerance, int relation,
			ProgressTracker progress_tracker) {
		switch (relation) {
		case Relation.disjoint:
			return polylineDisjointMultiPoint_(polyline_a, multipoint_b,
					tolerance, progress_tracker);

		case Relation.contains:
			return polylineContainsMultiPoint_(polyline_a, multipoint_b,
					tolerance, progress_tracker);

		case Relation.touches:
			return polylineTouchesMultiPoint_(polyline_a, multipoint_b,
					tolerance, progress_tracker);

		case Relation.crosses:
			return polylineCrossesMultiPoint_(polyline_a, multipoint_b,
					tolerance, progress_tracker);

		default:
			break; // warning fix
		}

		return false;
	}
527915
private static double[] crossProduct(double[] u, double[] v) {
        return new double[]{(u[1] * v[2]) - (v[1] * u[2]), (u[2] * v[0]) - (v[2] * u[0]), (u[0] * v[1]) - (v[0] * u[1])};
    }
154070
private void linearizeState(final FSA fsa, IntStack nodes, IntArrayList linearized, BitSet visited, int node) {
    linearized.add(node);
    visited.set(node);
    for (int arc = fsa.getFirstArc(node); arc != 0; arc = fsa.getNextArc(arc)) {
      if (!fsa.isArcTerminal(arc)) {
        final int target = fsa.getEndNode(arc);
        if (!visited.get(target))
          nodes.push(target);
      }
    }
  }
95024
def _linear_selection(self, non_empty_slices, num_slices):
        """"""

        num_non_empty = len(non_empty_slices)

        # # trying to skip 5% slices at the tails (bottom clipping at 0)
        # skip_count = max(0, np.around(num_non_empty * 0.05).astype('int16'))
        # # only when possible
        # if skip_count > 0 and (num_non_empty - 2 * skip_count > num_slices):
        #     non_empty_slices = non_empty_slices[skip_count: -skip_count]
        #     num_non_empty = len(non_empty_slices)

        sampled_indices = np.linspace(0, num_non_empty, num=min(num_non_empty, num_slices),
                                      endpoint=False)
        slices_in_dim = non_empty_slices[np.around(sampled_indices).astype('int64')]

        return slices_in_dim
425965
function linear_extrude(p,s) {
   //console.log("linear_extrude() not yet implemented");
   //return;
   var h = 1, off = 0, /* convexity = 10,*/ twist = 0, slices = 10;
   if(p.height) h = p.height;
   //if(p.convexity) convexity = p.convexity;      // abandoned
   if(p.twist) twist = p.twist;
   if(p.slices) slices = p.slices;
   var o = s.extrude({offset:[0,0,h], twistangle:twist, twiststeps:slices});
   if(p.center==true) {
      var b = new Array;
      b = o.getBounds();      // b[0] = min, b[1] = max
      off = b[1].plus(b[0]);
      off = off.times(-0.5);
      o = o.translate(off);
   }
   return o;
}
234004
private static boolean envelopeCrossesEnvelope_(Envelope2D env_a,
			Envelope2D env_b, double tolerance, ProgressTracker progress_tracker) {
		if (envelopeInfContainsEnvelope_(env_a, env_b, tolerance)
				|| envelopeInfContainsEnvelope_(env_b, env_a, tolerance))
			return false;

		if (env_a.getHeight() <= tolerance && env_a.getWidth() <= tolerance)
			return false; // points cannot cross

		if (env_b.getHeight() <= tolerance && env_b.getWidth() <= tolerance)
			return false; // points cannot cross

		if (env_b.getHeight() > tolerance && env_b.getWidth() > tolerance) {
			if (env_a.getHeight() > tolerance && env_a.getWidth() > tolerance)
				return false; // areas cannot cross
		}

		Envelope2D _env_a;
		Envelope2D _env_b;

		if (env_a.getHeight() > tolerance && env_a.getWidth() > tolerance) {
			// swap b and a
			_env_a = env_b;
			_env_b = env_a;
		} else {
			_env_a = env_a;
			_env_b = env_b;
		}

		if (_env_b.getHeight() > tolerance && _env_b.getWidth() > tolerance) {// treat
																				// env_b
																				// as
																				// an
																				// area
																				// (env_a
																				// as
																				// a
																				// line);

			Envelope2D env_inter = new Envelope2D(), env_b_deflated = new Envelope2D();
			env_b_deflated.setCoords(_env_b);
			env_b_deflated.inflate(-tolerance, -tolerance);
			env_inter.setCoords(env_b_deflated);
			env_inter.intersect(_env_a);

			if (env_inter.isEmpty())
				return false;

			if (env_inter.getHeight() <= tolerance
					&& env_inter.getWidth() <= tolerance)
				return false; // not a line

			assert (!envelopeInfContainsEnvelope_(env_inter, _env_a, tolerance));
			return true;
		}

		// treat both as lines

		Line line_a = new Line(), line_b = new Line();
		double[] scalars_a = new double[2];
		double[] scalars_b = new double[2];
		Point2D pt = new Point2D();
		_env_a.queryLowerLeft(pt);
		line_a.setStartXY(pt);
		_env_a.queryUpperRight(pt);
		line_a.setEndXY(pt);
		_env_b.queryLowerLeft(pt);
		line_b.setStartXY(pt);
		_env_b.queryUpperRight(pt);
		line_b.setEndXY(pt);

		line_a.intersect(line_b, null, scalars_a, scalars_b, tolerance);
		int count = line_a.intersect(line_b, null, null, null, tolerance);

		if (count != 1)
			return false;

		return scalars_a[0] > 0.0 && scalars_a[1] < 1.0 && scalars_b[0] > 0.0
				&& scalars_b[1] < 1.0;
	}
155306
private static boolean multiPointRelateEnvelope_(MultiPoint multipoint_a,
			Envelope envelope_b, double tolerance, int relation,
			ProgressTracker progress_tracker) {
		switch (relation) {
		case Relation.disjoint:
			return multiPointDisjointEnvelope_(multipoint_a, envelope_b,
					tolerance, progress_tracker);

		case Relation.within:
			return multiPointWithinEnvelope_(multipoint_a, envelope_b,
					tolerance, progress_tracker);

		case Relation.contains:
			return multiPointContainsEnvelope_(multipoint_a, envelope_b,
					tolerance, progress_tracker);

		case Relation.equals:
			return multiPointEqualsEnvelope_(multipoint_a, envelope_b,
					tolerance, progress_tracker);

		case Relation.touches:
			return multiPointTouchesEnvelope_(multipoint_a, envelope_b,
					tolerance, progress_tracker);

		case Relation.crosses:
			return multiPointCrossesEnvelope_(multipoint_a, envelope_b,
					tolerance, progress_tracker);

		default:
			break; // warning fix
		}

		return false;
	}
1029170
private static boolean linearPathIntersectsEnvelope_(MultiPath multipath_a,
			Envelope2D env_b, double tolerance, ProgressTracker progress_tracker) {
		if (!multipath_a.hasNonLinearSegments()) {
			Envelope2D env_b_inflated = new Envelope2D();
			env_b_inflated.setCoords(env_b);
			env_b_inflated.inflate(tolerance, tolerance);
			MultiPathImpl mimpl_a = (MultiPathImpl) multipath_a._getImpl();
			AttributeStreamOfDbl xy = (AttributeStreamOfDbl) (mimpl_a
					.getAttributeStreamRef(VertexDescription.Semantics.POSITION));
			Point2D pt = new Point2D();
			Point2D pt_prev = new Point2D();
			Point2D pt_1 = new Point2D();
			Point2D pt_2 = new Point2D();
			for (int ipath = 0, npath = mimpl_a.getPathCount(); ipath < npath; ipath++) {
				boolean b_first = true;
				for (int i = mimpl_a.getPathStart(ipath), n = mimpl_a
						.getPathEnd(ipath); i < n; i++) {
					if (b_first) {
						xy.read(2 * i, pt_prev);
						b_first = false;
						continue;
					}

					xy.read(2 * i, pt);
					pt_1.setCoords(pt_prev);
					pt_2.setCoords(pt);
					if (env_b_inflated.clipLine(pt_1, pt_2) != 0)
						return true;

					pt_prev.setCoords(pt);
				}
			}
		} else {
			Line line_1 = new Line(env_b.xmin, env_b.ymin, env_b.xmin,
					env_b.ymax);
			Line line_2 = new Line(env_b.xmin, env_b.ymax, env_b.xmax,
					env_b.ymax);
			Line line3 = new Line(env_b.xmax, env_b.ymax, env_b.xmax,
					env_b.ymin);
			Line line4 = new Line(env_b.xmax, env_b.ymin, env_b.xmin,
					env_b.ymin);
			SegmentIterator iter = multipath_a.querySegmentIterator();
			while (iter.nextPath()) {
				while (iter.hasNextSegment()) {
					Segment polySeg = iter.nextSegment();
					if (polySeg.isIntersecting(line_1, tolerance))
						return true;

					if (polySeg.isIntersecting(line_2, tolerance))
						return true;

					if (polySeg.isIntersecting(line3, tolerance))
						return true;

					if (polySeg.isIntersecting(line4, tolerance))
						return true;
				}
			}
		}

		return false;
	}
80963
private static boolean polylineDisjointMultiPoint_(Polyline polyline_a,
			MultiPoint multipoint_b, double tolerance,
			ProgressTracker progress_tracker) {
		// Quick rasterize test to see whether the the geometries are disjoint.
		if (tryRasterizedContainsOrDisjoint_(polyline_a, multipoint_b,
				tolerance, false) == Relation.disjoint)
			return true;

		return !linearPathIntersectsMultiPoint_(polyline_a, multipoint_b,
				tolerance, false);
	}
1099777
private static boolean multiPointExactlyEqualsMultiPoint_(
			MultiPoint multipoint_a, MultiPoint multipoint_b, double tolerance,
			ProgressTracker progress_tracker) {
		if (multipoint_a.getPointCount() != multipoint_b.getPointCount())
			return false;

		Point2D ptA = new Point2D(), ptB = new Point2D();
		boolean bAllPointsEqual = true;
		double tolerance_sq = tolerance * tolerance;

		for (int i = 0; i < multipoint_a.getPointCount(); i++) {
			multipoint_a.getXY(i, ptA);
			multipoint_b.getXY(i, ptB);

			if (Point2D.sqrDistance(ptA, ptB) > tolerance_sq) {
				bAllPointsEqual = false;
				break;
			}
		}

		if (!bAllPointsEqual)
			return false;

		return true;
	}
1278100
static boolean multiPointRelatePoint_(MultiPoint multipoint_a,
			Point point_b, double tolerance, String scl,
			ProgressTracker progress_tracker) {
		RelationalOperationsMatrix relOps = new RelationalOperationsMatrix();
		relOps.resetMatrix_();
		relOps.setPredicates_(scl);
		relOps.setPointPointPredicates_();

		Envelope2D env_a = new Envelope2D();
		multipoint_a.queryEnvelope2D(env_a);
		Point2D pt_b = point_b.getXY();

		boolean bRelationKnown = false;
		boolean b_disjoint = RelationalOperations.pointDisjointEnvelope_(pt_b,
				env_a, tolerance, progress_tracker);

		if (b_disjoint) {
			relOps.pointPointDisjointPredicates_();
			bRelationKnown = true;
		}

		if (!bRelationKnown) {
			boolean b_intersects = false;
			boolean b_multipoint_contained = true;
			double tolerance_sq = tolerance * tolerance;

			for (int i = 0; i < multipoint_a.getPointCount(); i++) {
				Point2D pt_a = multipoint_a.getXY(i);

				if (Point2D.sqrDistance(pt_a, pt_b) <= tolerance_sq)
					b_intersects = true;
				else
					b_multipoint_contained = false;

				if (b_intersects && !b_multipoint_contained)
					break;
			}

			if (b_intersects) {
				relOps.m_matrix[MatrixPredicate.InteriorInterior] = 0;

				if (!b_multipoint_contained)
					relOps.m_matrix[MatrixPredicate.InteriorExterior] = 0;
				else
					relOps.m_matrix[MatrixPredicate.InteriorExterior] = -1;

				relOps.m_matrix[MatrixPredicate.ExteriorInterior] = -1;
			} else {
				relOps.m_matrix[MatrixPredicate.InteriorInterior] = -1;
				relOps.m_matrix[MatrixPredicate.InteriorExterior] = 0;
				relOps.m_matrix[MatrixPredicate.ExteriorInterior] = 0;
			}
		}

		boolean bRelation = relationCompare_(relOps.m_matrix, scl);
		return bRelation;
	}
1201372
private static double cross(Coordinate a1, Coordinate a2, Coordinate b1, Coordinate b2) {
		return (a2.getX() - a1.getX()) * (b2.getY() - b1.getY()) - (a2.getY() - a1.getY()) * (b2.getX() - b1.getX());
	}
374843
def cross_product(self, p1, p2):
        """"""
        return (p1.x * p2.y - p1.y * p2.x)
984181
def CrossProd(self, other):
    
    return Point(
        self.y * other.z - self.z * other.y,
        self.z * other.x - self.x * other.z,
        self.x * other.y - self.y * other.x)