int is_inside_region()

in src/tuner/nccl_ofi_regions.cpp [154:215]

• 46 lines of code
• 14 McCabe index (conditional complexity)

int is_inside_region(nccl_ofi_tuner_point_t point, nccl_ofi_tuner_region_t *region)
{
	assert(region->num_vertices > 1);

	size_t i, k;
	nccl_ofi_tuner_point_t *pv;
	double min_x, max_x, min_y, max_y;
	const double eps = 1e-10;

	for (i = 0; i < region->num_vertices; i++) {
		k = (i + 1) % region->num_vertices;
		min_x = distance(point, region->vertices[i], region->vertices[k], eps);
		if (min_x < eps) {
			/* Point on the edge */
			return 0;
		}
	}

	min_x = max_x = region->vertices[0].x;
	min_y = max_y = region->vertices[1].y;

	/*
	 * This is a pre-screening step to quickly mark as external all points
	 * outside the bounding box (a rectangle drawn around the polygon).
	 */
	for (i = 0, pv = region->vertices; i < region->num_vertices; i++, pv++) {
		if (pv->x > max_x) {
			max_x = pv->x;
		}
		if (pv->x < min_x) {
			min_x = pv->x;
		}
		if (pv->y > max_y) {
			max_y = pv->y;
		}
		if (pv->y < min_y) {
			min_y = pv->y;
		}
	}
	if (point.x < min_x || point.x > max_x || point.y < min_y || point.y > max_y) {
		/* Point outside the bounding box */
		return -1;
	}

	/* Pick a point far enough to be outside any polygon */
	nccl_ofi_tuner_point_t e = {.x = 2.0 * TUNER_MAX_SIZE, .y = 2.0 * TUNER_MAX_RANKS};

	int crosses = 0;
	int intersectResult = -1;
	for (i = 0; i < region->num_vertices; i++) {
		k = (i + 1) % region->num_vertices;
		intersectResult = intersect(point, e, region->vertices[i], region->vertices[k], eps, 0);

		assert(intersectResult == 1 || intersectResult == -1);

		if (intersectResult == 1) {
			crosses++;
		}
	}

	return (crosses & 1) ? 1 : -1;
}