check if a polygon diagonal is locally inside the polygon
763349
function locallyInside(a, b) {
       return area(a.prev, a, a.next) < 0 ?
           area(a, b, a.next) >= 0 && area(a, a.prev, b) >= 0 :
           area(a, b, a.prev) < 0 || area(a, a.next, b) < 0;
   }
1321820
function(csg) {
            if ((this.polygons.length === 0) || (csg.polygons.length === 0)) {
                return false;
            } else {
                var mybounds = this.getBounds();
                var otherbounds = csg.getBounds();
                if (mybounds[1].x < otherbounds[0].x) return false;
                if (mybounds[0].x > otherbounds[1].x) return false;
                if (mybounds[1].y < otherbounds[0].y) return false;
                if (mybounds[0].y > otherbounds[1].y) return false;
                if (mybounds[1].z < otherbounds[0].z) return false;
                if (mybounds[0].z > otherbounds[1].z) return false;
                return true;
            }
        }
1312735
function isValidDiagonal(a, b) {
       return a.next.i !== b.i && a.prev.i !== b.i && !intersectsPolygon(a, b) &&
              locallyInside(a, b) && locallyInside(b, a) && middleInside(a, b);
   }
451921
private static boolean polygonContainsPolyline_(Polygon polygon_a,
			Polyline polyline_b, double tolerance,
			ProgressTracker progress_tracker) {
		Envelope2D env_a = new Envelope2D(), env_b = new Envelope2D();
		polygon_a.queryEnvelope2D(env_a);
		polyline_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, polyline_b,
				tolerance, false);

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

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

		return polygonContainsPolylineImpl_(polygon_a, polyline_b, tolerance,
				progress_tracker);
	}
1204512
private static boolean polygonDisjointEnvelope_(Polygon polygon_a,
			Envelope envelope_b, double tolerance,
			ProgressTracker progress_tracker) {
		// 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)
			return true;

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

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

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

		PolygonUtils.PiPResult pipres;
		Point2D pt_b = new Point2D();
		env_b.queryLowerLeft(pt_b);
		pipres = PolygonUtils.isPointInPolygon2D(polygon_a, pt_b, tolerance);
		if (pipres != PolygonUtils.PiPResult.PiPOutside)
			return false;

		env_b.queryLowerRight(pt_b);
		pipres = PolygonUtils.isPointInPolygon2D(polygon_a, pt_b, tolerance);
		if (pipres != PolygonUtils.PiPResult.PiPOutside)
			return false;

		env_b.queryUpperRight(pt_b);
		pipres = PolygonUtils.isPointInPolygon2D(polygon_a, pt_b, tolerance);
		if (pipres != PolygonUtils.PiPResult.PiPOutside)
			return false;

		env_b.queryUpperLeft(pt_b);
		pipres = PolygonUtils.isPointInPolygon2D(polygon_a, pt_b, tolerance);
		if (pipres != PolygonUtils.PiPResult.PiPOutside)
			return false;

		MultiPathImpl mimpl_a = (MultiPathImpl) polygon_a._getImpl();
		AttributeStreamOfDbl pos = (AttributeStreamOfDbl) (mimpl_a
				.getAttributeStreamRef(VertexDescription.Semantics.POSITION));

		Envelope2D env_b_inflated = new Envelope2D();
		env_b_inflated.setCoords(env_b);
		env_b_inflated.inflate(tolerance, tolerance);
		for (int ptIndex = 0, n = mimpl_a.getPointCount(); ptIndex < n; ptIndex++) {
			double x = pos.read(2 * ptIndex);
			double y = pos.read(2 * ptIndex + 1);
			if (env_b_inflated.contains(x, y))
				return false;
		}

		return !linearPathIntersectsEnvelope_(polygon_a, env_b, tolerance,
				progress_tracker);
	}
1126710
function isPointInsidePoly(point, polygon) {
    let i,
        nvert = polygon.length,
        j = nvert - 1,
        c = false;
    for (i = 0; i < nvert; j = i++) {
        if (((polygon[i].lon > point.lon) !== (polygon[j].lon > point.lon)) &&
            (point.lat < (polygon[j].lat - polygon[i].lat) * (point.lon - polygon[i].lon) /
            (polygon[j].lon - polygon[i].lon) + polygon[i].lat)) {
            c = !c;
            //console.log(i, j, polygon[i].lon, '>', point.lon, c);
        }
    }
    return c;
}
1306972
private static boolean polygonContainsPolygon_(Polygon polygon_a,
			Polygon polygon_b, double tolerance,
			ProgressTracker progress_tracker) {
		Envelope2D env_a = new Envelope2D(), env_b = new Envelope2D();
		polygon_a.queryEnvelope2D(env_a);
		polygon_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, polygon_b,
				tolerance, false);

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

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

		return polygonContainsPolygonImpl_(polygon_a, polygon_b, tolerance,
				progress_tracker);
	}
723068
function polygonCanSee(polygon, a,b) {
    var p, dist, l1=tmpLine1, l2=tmpLine2;

    if (isLeftOn(polygonAt(polygon, a + 1), polygonAt(polygon, a), polygonAt(polygon, b)) && isRightOn(polygonAt(polygon, a - 1), polygonAt(polygon, a), polygonAt(polygon, b))) {
        return false;
    }
    dist = sqdist(polygonAt(polygon, a), polygonAt(polygon, b));
    for (var i = 0; i !== polygon.length; ++i) { // for each edge
        if ((i + 1) % polygon.length === a || i === a){ // ignore incident edges
            continue;
        }
        if (isLeftOn(polygonAt(polygon, a), polygonAt(polygon, b), polygonAt(polygon, i + 1)) && isRightOn(polygonAt(polygon, a), polygonAt(polygon, b), polygonAt(polygon, i))) { // if diag intersects an edge
            l1[0] = polygonAt(polygon, a);
            l1[1] = polygonAt(polygon, b);
            l2[0] = polygonAt(polygon, i);
            l2[1] = polygonAt(polygon, i + 1);
            p = lineInt(l1,l2);
            if (sqdist(polygonAt(polygon, a), p) < dist) { // if edge is blocking visibility to b
                return false;
            }
        }
    }

    return true;
}
1036206
function (otherCsg, csg) {
  if ((otherCsg.polygons.length === 0) || (csg.polygons.length === 0)) {
    return false
  } else {
    let mybounds = bounds(otherCsg)
    let otherbounds = bounds(csg)
    if (mybounds[1].x < otherbounds[0].x) return false
    if (mybounds[0].x > otherbounds[1].x) return false
    if (mybounds[1].y < otherbounds[0].y) return false
    if (mybounds[0].y > otherbounds[1].y) return false
    if (mybounds[1].z < otherbounds[0].z) return false
    if (mybounds[0].z > otherbounds[1].z) return false
    return true
  }
}
1211668
def point_in_multipolygon(point, multipoly):
    
    coords_array = [multipoly['coordinates']] if multipoly[
        'type'] == "MultiPolygon" else multipoly['coordinates']

    for coords in coords_array:
        if _point_in_polygon(point, coords):
            return True

    return False
653110
def _where(self, cond, other=np.nan, inplace=False, axis=None, level=None,
               errors='raise', try_cast=False):
        
        inplace = validate_bool_kwarg(inplace, 'inplace')

        # align the cond to same shape as myself
        cond = com.apply_if_callable(cond, self)
        if isinstance(cond, NDFrame):
            cond, _ = cond.align(self, join='right', broadcast_axis=1)
        else:
            if not hasattr(cond, 'shape'):
                cond = np.asanyarray(cond)
            if cond.shape != self.shape:
                raise ValueError('Array conditional must be same shape as '
                                 'self')
            cond = self._constructor(cond, **self._construct_axes_dict())

        # make sure we are boolean
        fill_value = bool(inplace)
        cond = cond.fillna(fill_value)

        msg = "Boolean array expected for the condition, not {dtype}"

        if not isinstance(cond, pd.DataFrame):
            # This is a single-dimensional object.
            if not is_bool_dtype(cond):
                raise ValueError(msg.format(dtype=cond.dtype))
        elif not cond.empty:
            for dt in cond.dtypes:
                if not is_bool_dtype(dt):
                    raise ValueError(msg.format(dtype=dt))

        cond = -cond if inplace else cond

        # try to align with other
        try_quick = True
        if hasattr(other, 'align'):

            # align with me
            if other.ndim <= self.ndim:

                _, other = self.align(other, join='left', axis=axis,
                                      level=level, fill_value=np.nan)

                # if we are NOT aligned, raise as we cannot where index
                if (axis is None and
                        not all(other._get_axis(i).equals(ax)
                                for i, ax in enumerate(self.axes))):
                    raise InvalidIndexError

            # slice me out of the other
            else:
                raise NotImplementedError("cannot align with a higher "
                                          "dimensional NDFrame")

        if isinstance(other, np.ndarray):

            if other.shape != self.shape:

                if self.ndim == 1:

                    icond = cond.values

                    # GH 2745 / GH 4192
                    # treat like a scalar
                    if len(other) == 1:
                        other = np.array(other[0])

                    # GH 3235
                    # match True cond to other
                    elif len(cond[icond]) == len(other):

                        # try to not change dtype at first (if try_quick)
                        if try_quick:

                            try:
                                new_other = com.values_from_object(self)
                                new_other = new_other.copy()
                                new_other[icond] = other
                                other = new_other
                            except Exception:
                                try_quick = False

                        # let's create a new (if we failed at the above
                        # or not try_quick
                        if not try_quick:

                            dtype, fill_value = maybe_promote(other.dtype)
                            new_other = np.empty(len(icond), dtype=dtype)
                            new_other.fill(fill_value)
                            maybe_upcast_putmask(new_other, icond, other)
                            other = new_other

                    else:
                        raise ValueError('Length of replacements must equal '
                                         'series length')

                else:
                    raise ValueError('other must be the same shape as self '
                                     'when an ndarray')

            # we are the same shape, so create an actual object for alignment
            else:
                other = self._constructor(other, **self._construct_axes_dict())

        if axis is None:
            axis = 0

        if self.ndim == getattr(other, 'ndim', 0):
            align = True
        else:
            align = (self._get_axis_number(axis) == 1)

        block_axis = self._get_block_manager_axis(axis)

        if inplace:
            # we may have different type blocks come out of putmask, so
            # reconstruct the block manager

            self._check_inplace_setting(other)
            new_data = self._data.putmask(mask=cond, new=other, align=align,
                                          inplace=True, axis=block_axis,
                                          transpose=self._AXIS_REVERSED)
            self._update_inplace(new_data)

        else:
            new_data = self._data.where(other=other, cond=cond, align=align,
                                        errors=errors,
                                        try_cast=try_cast, axis=block_axis,
                                        transpose=self._AXIS_REVERSED)

            return self._constructor(new_data).__finalize__(self)
59265
def is_inside(point, region):
    
    points = region.vertices
    extrame = models.Point(x=1000000, y=point.y)

    points = points + [points[0]]
    intersect_count = 0
    for i in range(len(points) - 1):
        if is_intersect(models.Line(point, extrame),
                        models.Line(points[i], points[i+1])):
            intersect_count += 1
    return intersect_count % 2 == 1
674123
private static boolean polygonDisjointPolygon_(Polygon polygon_a,
			Polygon polygon_b, double tolerance,
			ProgressTracker progress_tracker) {
		// Quick rasterize test to see whether the the geometries are disjoint,
		// or if one is contained in the other.
		int relation = tryRasterizedContainsOrDisjoint_(polygon_a, polygon_b,
				tolerance, true);

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

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

		return polygonDisjointMultiPath_(polygon_a, polygon_b, tolerance,
				progress_tracker);
	}
1181095
function polygonCanSee2(polygon, a,b) {
    // for each edge
    for (var i = 0; i !== polygon.length; ++i) {
        // ignore incident edges
        if (i === a || i === b || (i + 1) % polygon.length === a || (i + 1) % polygon.length === b){
            continue;
        }
        if( lineSegmentsIntersect(polygonAt(polygon, a), polygonAt(polygon, b), polygonAt(polygon, i), polygonAt(polygon, i+1)) ){
            return false;
        }
    }
    return true;
}
285116
private boolean checkDimensions(CLIQUEUnit other, int e) {
    for(int i = 0, j = 0; i < e; i++, j += 2) {
      if(dims[i] != other.dims[i] || bounds[j] != other.bounds[j] || bounds[j + 1] != bounds[j + 1]) {
        return false;
      }
    }
    return true;
  }
650721
def neighbors(self, node, diagonal_movement=DiagonalMovement.never):
        
        x = node.x
        y = node.y
        neighbors = []
        s0 = d0 = s1 = d1 = s2 = d2 = s3 = d3 = False

        # ↑
        if self.walkable(x, y - 1):
            neighbors.append(self.nodes[y - 1][x])
            s0 = True
        # →
        if self.walkable(x + 1, y):
            neighbors.append(self.nodes[y][x + 1])
            s1 = True
        # ↓
        if self.walkable(x, y + 1):
            neighbors.append(self.nodes[y + 1][x])
            s2 = True
        # ←
        if self.walkable(x - 1, y):
            neighbors.append(self.nodes[y][x - 1])
            s3 = True

        if diagonal_movement == DiagonalMovement.never:
            return neighbors

        if diagonal_movement == DiagonalMovement.only_when_no_obstacle:
            d0 = s3 and s0
            d1 = s0 and s1
            d2 = s1 and s2
            d3 = s2 and s3
        elif diagonal_movement == DiagonalMovement.if_at_most_one_obstacle:
            d0 = s3 or s0
            d1 = s0 or s1
            d2 = s1 or s2
            d3 = s2 or s3
        elif diagonal_movement == DiagonalMovement.always:
            d0 = d1 = d2 = d3 = True

        # ↖
        if d0 and self.walkable(x - 1, y - 1):
            neighbors.append(self.nodes[y - 1][x - 1])

        # ↗
        if d1 and self.walkable(x + 1, y - 1):
            neighbors.append(self.nodes[y - 1][x + 1])

        # ↘
        if d2 and self.walkable(x + 1, y + 1):
            neighbors.append(self.nodes[y + 1][x + 1])

        # ↙
        if d3 and self.walkable(x - 1, y + 1):
            neighbors.append(self.nodes[y + 1][x - 1])

        return neighbors
896912
function isNestedRingClosed(simplePolygon) {
  // check if first and last vertex are the same
  const p0 = simplePolygon[0];
  const p1 = simplePolygon[simplePolygon.length - 1];

  return p0[0] === p1[0] && p0[1] === p1[1] && p0[2] === p1[2];
}