the algorithm to judge whether the point is located in polygon
    reference: https://www.ecse.rpi.edu/~wrf/Research/Short_Notes/pnpoly.html#Explanation
340176
def _pnpoly(x, y, coords):
    
    vert = [[0, 0]]

    for coord in coords:
        for node in coord:
            vert.append(node)
        vert.append(coord[0])
        vert.append([0, 0])

    inside = False

    i = 0
    j = len(vert) - 1

    while i < len(vert):
        if ((vert[i][0] > y) != (vert[j][0] > y)) and (x < (vert[j][1] - vert[i][1])
                                                       * (y - vert[i][0]) / (vert[j][0] - vert[i][0]) + vert[i][1]):
            inside = not inside
        j = i
        i += 1

    return inside
971783
def extract_polygon_area(self, pid, polygon_points):
        
        polygon = shapgeo.Polygon(polygon_points)
        xy = self.grid.get_element_centroids()
        in_poly = []
        for nr, point in enumerate(xy):
            if shapgeo.Point(point).within(polygon):
                in_poly.append(nr)

        values = self.parsets[pid][in_poly]
        return np.array(in_poly), values
1242589
@Pure
	boolean containsControlPoint(Point3D p) {
		double x, y, z;
		for(int i=0; i<this.numCoords;) {
			x = this.coords[i++];
			y = this.coords[i++];
			z = this.coords[i++];
			if (x==p.getX() && y==p.getY() && z==p.getZ()) {
				return true;
			}
		}
		return false;
	}
233930
static boolean isPathConvex(MultiPath multi_path, int path_index, ProgressTracker progress_tracker) {
		MultiPathImpl mimpl = (MultiPathImpl) multi_path._getImpl();
		int path_start = mimpl.getPathStart(path_index);
		int path_end = mimpl.getPathEnd(path_index);

		boolean bxyclosed = !mimpl.isClosedPath(path_index) && mimpl.isClosedPathInXYPlane(path_index);

		AttributeStreamOfDbl position = (AttributeStreamOfDbl) (mimpl.getAttributeStreamRef(VertexDescription.Semantics.POSITION));
		int position_start = 2 * path_start;
		int position_end = 2 * path_end;

		if (bxyclosed)
			position_end -= 2;

		if (position_end - position_start < 6)
			return true;

		// This matches the logic for case 1 of the tree hull algorithm. The idea is inductive. We assume we have a convex hull pt_0,...,pt_m, and we see if
		// a new point (pt_pivot) is among the transitive tournament for pt_0, knowing that pt_pivot comes after pt_m.

		// We check three conditions:
		// 1) pt_m->pt_pivot->pt_0 is clockwise (closure across the boundary is convex)
		// 2) pt_1->pt_pivot->pt_0 is clockwise (the first step forward is convex)  (pt_1 is the next point after pt_0)
		// 3) pt_m->pt_pivot->pt_m_prev is clockwise (the first step backwards is convex)  (pt_m_prev is the previous point before pt_m)

		// If all three of the above conditions are clockwise, then pt_pivot is among the transitive tournament for pt_0, and therefore the polygon pt_0, ..., pt_m, pt_pivot is convex.

		Point2D pt_0 = new Point2D(), pt_m = new Point2D(), pt_pivot = new Point2D();
		position.read(position_start, pt_0);
		position.read(position_start + 2, pt_m);
		position.read(position_start + 4, pt_pivot);

		// Initial inductive step
		ECoordinate det_ec = determinant_(pt_m, pt_pivot, pt_0);

		if (det_ec.isFuzzyZero() || !isClockwise_(det_ec.value()))
			return false;

		Point2D pt_1 = new Point2D(pt_m.x, pt_m.y);
		Point2D pt_m_prev = new Point2D();

		// Assume that pt_0,...,pt_m is convex. Check if the next point, pt_pivot, maintains the convex invariant.
		for (int i = position_start + 6; i < position_end; i += 2) {
			pt_m_prev.setCoords(pt_m);
			pt_m.setCoords(pt_pivot);
			position.read(i, pt_pivot);

			det_ec = determinant_(pt_m, pt_pivot, pt_0);

			if (det_ec.isFuzzyZero() || !isClockwise_(det_ec.value()))
				return false;

			det_ec = determinant_(pt_1, pt_pivot, pt_0);

			if (det_ec.isFuzzyZero() || !isClockwise_(det_ec.value()))
				return false;

			det_ec = determinant_(pt_m, pt_pivot, pt_m_prev);

			if (det_ec.isFuzzyZero() || !isClockwise_(det_ec.value()))
				return false;
		}

		return true;
	}
659101
private static boolean checkVerticesForIntersection_(
			MultiVertexGeometryImpl geom, RasterizedGeometry2D rgeom) {
		// Do a quick raster test for each point. If any point is inside, then
		// there is an intersection.
		int pointCount = geom.getPointCount();
		Point2D pt = new Point2D();
		for (int ipoint = 0; ipoint < pointCount; ipoint++) {
			geom.getXY(ipoint, pt);
			RasterizedGeometry2D.HitType hit = rgeom.queryPointInGeometry(pt.x,
					pt.y);
			if (hit == RasterizedGeometry2D.HitType.Inside) {
				return true;
			}
		}

		return false;
	}
915300
function writePointGeometry_(geometry) {
  if (geometry instanceof olGeomPoint) {
    const flatCoordinates = geometry.getFlatCoordinates();
    const stride = geometry.getStride();
    const end = flatCoordinates.length;
    return `p(${this.encodeCoordinates_(flatCoordinates, stride, 0, end)})`;
  }
  return null;
}
650968
private static boolean polygonContainsEnvelope_(Polygon polygon_a,
			Envelope envelope_b, double tolerance,
			ProgressTracker progress_tracker) {
		// Quick envelope rejection test

		Envelope2D env_a = new Envelope2D(), env_b = new Envelope2D();
		polygon_a.queryEnvelope2D(env_a);
		envelope_b.queryEnvelope2D(env_b);

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

		// Quick rasterize test to see whether the the geometries are disjoint,
		// or if one is contained in the other.
		int relation = tryRasterizedContainsOrDisjoint_(polygon_a, envelope_b,
				tolerance, false);

		if (relation == Relation.disjoint || relation == Relation.within)
			return false;

		if (relation == Relation.contains)
			return true;

		if (env_b.getWidth() <= tolerance && env_b.getHeight() <= tolerance) {// treat
																				// as
																				// point
			Point2D pt_b = envelope_b.getCenterXY();
			return polygonContainsPointImpl_(polygon_a, pt_b, tolerance,
					progress_tracker);
		}

		if (env_b.getWidth() <= tolerance || env_b.getHeight() <= tolerance) {// treat
																				// as
																				// polyline
			Polyline polyline_b = new Polyline();
			Point p = new Point();
			envelope_b.queryCornerByVal(0, p);
			polyline_b.startPath(p);
			envelope_b.queryCornerByVal(2, p);
			polyline_b.lineTo(p);
			return polygonContainsPolylineImpl_(polygon_a, polyline_b,
					tolerance, null);
		}

		// treat as polygon
		Polygon polygon_b = new Polygon();
		polygon_b.addEnvelope(envelope_b, false);
		return polygonContainsPolygonImpl_(polygon_a, polygon_b, tolerance,
				null);
	}
1345720
static boolean polygonRelateMultiPoint_(Polygon polygon_a,
			MultiPoint multipoint_b, double tolerance, String scl,
			ProgressTracker progress_tracker) {
		RelationalOperationsMatrix relOps = new RelationalOperationsMatrix();
		relOps.resetMatrix_();
		relOps.setPredicates_(scl);
		relOps.setAreaPointPredicates_();

		Envelope2D env_a = new Envelope2D(), env_b = new Envelope2D();
		polygon_a.queryEnvelope2D(env_a);
		multipoint_b.queryEnvelope2D(env_b);

		boolean bRelationKnown = false;
		boolean b_disjoint = RelationalOperations.envelopeDisjointEnvelope_(
				env_a, env_b, tolerance, progress_tracker);

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

		if (!bRelationKnown) {
			// Quick rasterize test to see whether the the geometries are
			// disjoint, or if one is contained in the other.
			int relation = RelationalOperations
					.tryRasterizedContainsOrDisjoint_(polygon_a, multipoint_b,
							tolerance, false);

			if (relation == RelationalOperations.Relation.disjoint) {
				relOps.areaPointDisjointPredicates_(polygon_a);
				bRelationKnown = true;
			} else if (relation == RelationalOperations.Relation.contains) {
				relOps.areaPointContainsPredicates_(polygon_a);
				bRelationKnown = true;
			}
		}

		if (!bRelationKnown) {
			EditShape edit_shape = new EditShape();
			int geom_a = edit_shape.addGeometry(polygon_a);
			int geom_b = edit_shape.addGeometry(multipoint_b);
			relOps.setEditShapeCrackAndCluster_(edit_shape, tolerance,
					progress_tracker);
			relOps.computeMatrixTopoGraphClusters_(geom_a, geom_b);
			relOps.m_topo_graph.removeShape();
		}

		boolean bRelation = relationCompare_(relOps.m_matrix, relOps.m_scl);
		return bRelation;
	}
772262
def _validate_planar_fault_geometry(self, node, _float_re):
        
        valid_spacing = node["spacing"]
        for key in ["topLeft", "topRight", "bottomLeft", "bottomRight"]:
            lon = getattr(node, key)["lon"]
            lat = getattr(node, key)["lat"]
            depth = getattr(node, key)["depth"]
            valid_lon = (lon >= -180.0) and (lon <= 180.0)
            valid_lat = (lat >= -90.0) and (lat <= 90.0)
            valid_depth = (depth >= 0.0)
            is_valid = valid_lon and valid_lat and valid_depth
            if not is_valid or not valid_spacing:
                raise LogicTreeError(
                    node, self.filename,
                    "'planarFaultGeometry' node is not valid")
255794
function polygon( $p, $np, $f = 0 )
    {
        $this->objects[$this->currentContents]['c'].= "\n";
        $this->objects[$this->currentContents]['c'].= sprintf('%.3F',$p[0]).' '.sprintf('%.3F',$p[1]).' m ';
        for ( $i = 2; $i < $np*2; $i = $i + 2 )
        {
            $this->objects[$this->currentContents]['c'].= sprintf('%.3F',$p[$i]).' '.sprintf('%.3F',$p[$i+1]).' l ';
        }
        if ( $f == 1 )
        {
            $this->objects[$this->currentContents]['c'].= ' f';
        }
        else
        {
            $this->objects[$this->currentContents]['c'].= ' S';
        }
    }
993035
def get_windzone(conn, geometry):
    ''
    # TODO@Günni
    if geometry.geom_type in ['Polygon', 'MultiPolygon']:
        coords = geometry.centroid
    else:
        coords = geometry
    sql = """
        SELECT zone FROM oemof_test.windzones
        WHERE st_contains(geom, ST_PointFromText('{wkt}', 4326));
        """.format(wkt=coords.wkt)
    zone = conn.execute(sql).fetchone()
    if zone is not None:
        zone = zone[0]
    else:
        zone = 0
    return zone
344981
public Result<float[]> closestPointOnPolyBoundary(long ref, float[] pos) {

        Result<Tupple2<MeshTile, Poly>> tileAndPoly = m_nav.getTileAndPolyByRef(ref);
        if (tileAndPoly.failed()) {
            return Result.of(tileAndPoly.status, tileAndPoly.message);
        }
        MeshTile tile = tileAndPoly.result.first;
        Poly poly = tileAndPoly.result.second;
        if (tile == null) {
            return Result.invalidParam("Invalid tile");
        }

        if (Objects.isNull(pos) || !vIsFinite(pos)) {
            return Result.invalidParam();
        }
        // Collect vertices.
        float[] verts = new float[m_nav.getMaxVertsPerPoly() * 3];
        float[] edged = new float[m_nav.getMaxVertsPerPoly()];
        float[] edget = new float[m_nav.getMaxVertsPerPoly()];
        int nv = poly.vertCount;
        for (int i = 0; i < nv; ++i) {
            System.arraycopy(tile.data.verts, poly.verts[i] * 3, verts, i * 3, 3);
        }

        float[] closest;
        if (distancePtPolyEdgesSqr(pos, verts, nv, edged, edget)) {
            closest = vCopy(pos);
        } else {
            // Point is outside the polygon, dtClamp to nearest edge.
            float dmin = edged[0];
            int imin = 0;
            for (int i = 1; i < nv; ++i) {
                if (edged[i] < dmin) {
                    dmin = edged[i];
                    imin = i;
                }
            }
            int va = imin * 3;
            int vb = ((imin + 1) % nv) * 3;
            closest = vLerp(verts, va, vb, edget[imin]);
        }
        return Result.success(closest);
    }
1084713
function checkFeature(point) {
  var feature;
  // Check if there is already a feature object for the given point
  for (var i = 0; i < feature_list.length; i++) {
    feature = feature_list[i];
    if (feature.location.latitude === point.latitude &&
        feature.location.longitude === point.longitude) {
      return feature;
    }
  }
  var name = '';
  feature = {
    name: name,
    location: point
  };
  return feature;
}
64295
function intersectPolygon(node, polyPoints, point) {
  var x1 = node.x;
  var y1 = node.y;

  var intersections = [];

  var minX = Number.POSITIVE_INFINITY,
      minY = Number.POSITIVE_INFINITY;
  polyPoints.forEach(function(entry) {
    minX = Math.min(minX, entry.x);
    minY = Math.min(minY, entry.y);
  });

  var left = x1 - node.width / 2 - minX;
  var top =  y1 - node.height / 2 - minY;

  for (var i = 0; i < polyPoints.length; i++) {
    var p1 = polyPoints[i];
    var p2 = polyPoints[i < polyPoints.length - 1 ? i + 1 : 0];
    var intersect = intersectLine(node, point,
      {x: left + p1.x, y: top + p1.y}, {x: left + p2.x, y: top + p2.y});
    if (intersect) {
      intersections.push(intersect);
    }
  }

  if (!intersections.length) {
    console.log("NO INTERSECTION FOUND, RETURN NODE CENTER", node);
    return node;
  }

  if (intersections.length > 1) {
    // More intersections, find the one nearest to edge end point
    intersections.sort(function(p, q) {
      var pdx = p.x - point.x,
          pdy = p.y - point.y,
          distp = Math.sqrt(pdx * pdx + pdy * pdy),

          qdx = q.x - point.x,
          qdy = q.y - point.y,
          distq = Math.sqrt(qdx * qdx + qdy * qdy);

      return (distp < distq) ? -1 : (distp === distq ? 0 : 1);
    });
  }
  return intersections[0];
}
109537
def contains_point?(pt)
      pt.x.between?(left, left + width - 1) &&
        pt.y.between?(top, top + height - 1)
    end
1096843
private static boolean polygonContainsMultiPoint_(Polygon polygon_a,
			MultiPoint multipoint_b, double tolerance,
			ProgressTracker progress_tracker) {
		Envelope2D env_a = new Envelope2D(), env_b = new Envelope2D();
		polygon_a.queryEnvelope2D(env_a);
		multipoint_b.queryEnvelope2D(env_b);

		// Quick envelope rejection test for false equality.
		if (!envelopeInfContainsEnvelope_(env_a, env_b, tolerance))
			return false;

		// Quick rasterize test to see whether the the geometries are disjoint,
		// or if one is contained in the other.
		int relation = tryRasterizedContainsOrDisjoint_(polygon_a,
				multipoint_b, tolerance, false);

		if (relation == Relation.disjoint)
			return false;

		if (relation == Relation.contains)
			return true;

        boolean b_interior = false;
        Point2D ptB;

        MultiPathImpl polygon_a_impl = (MultiPathImpl)polygon_a._getImpl();

        Polygon pa = null;
        Polygon p_polygon_a = polygon_a;

        boolean b_checked_polygon_a_quad_tree = false;

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

            if (!env_a.contains(ptB))
                return false;

            PolygonUtils.PiPResult result = PolygonUtils.isPointInPolygon2D(p_polygon_a, ptB, tolerance);

            if (result == PolygonUtils.PiPResult.PiPInside)
                b_interior = true;
            else if (result == PolygonUtils.PiPResult.PiPOutside)
                return false;

            if (!b_checked_polygon_a_quad_tree) {
                if (PointInPolygonHelper.quadTreeWillHelp(polygon_a, multipoint_b.getPointCount() - 1) && (polygon_a_impl._getAccelerators() == null || polygon_a_impl._getAccelerators().getQuadTree() == null)) {
                    pa = new Polygon();
                    polygon_a.copyTo(pa);
                    ((MultiPathImpl) pa._getImpl())._buildQuadTreeAccelerator(Geometry.GeometryAccelerationDegree.enumMedium);
                    p_polygon_a = pa;
                } else {
                    p_polygon_a = polygon_a;
                }

                b_checked_polygon_a_quad_tree = true;
            }
        }

        return b_interior;
	}
465143
function pointRectangleSimple(p, a1, a2) {
    if (!(a1.x > p.x ||
        a2.x < p.x ||
        a1.y > p.y ||
        a2.y < p.y))
        return {result: collision.INSIDE};
    return {result: collision.OUTSIDE};
}