typedef std::pair<Point, Point> LineSegment;

/**

 * Make line segments from a polygon defined by points, translated by an offset.

 * Entirely horizontal lines (start and end at same Y coordinate) are skipped, as they are irrelevant to scanline conversion algorithms.

 * Generated line segments always have the lowest Y coordinate point first, i.e. original direction is lost.

 * @param shape The polygon to convert.

 * @param offset Offset vector subtracted from all coordinates in the shape.

 * @return Vector of undirected line segments.

 */

static std::vector<LineSegment> MakePolygonSegments(const std::vector<Point> &shape, Point offset)

{

	std::vector<LineSegment> segments;

	if (shape.size() < 3) return segments; // fewer than 3 will always result in an empty polygon

	segments.reserve(shape.size());

	/* Connect first and last point by having initial previous point be the last */

	Point prev = shape.back();

	prev.x -= offset.x;

	prev.y -= offset.y;

	for (Point pt : shape) {

		pt.x -= offset.x;

		pt.y -= offset.y;

		/* Create segments for all non-horizontal lines in the polygon.

		 * The segments always have lowest Y coordinate first. */

		if (prev.y > pt.y) {

			segments.emplace_back(pt, prev);

		} else if (prev.y < pt.y) {

			segments.emplace_back(prev, pt);

		}

		prev = pt;

	}

	return segments;

}

/**

 * Fill a polygon with colour.

 * The odd-even winding rule is used, i.e. self-intersecting polygons will have holes in them.

 * Left and top edges are inclusive, right and bottom edges are exclusive.

 * @note For rectangles the GfxFillRect function will be faster.

 * @pre dpi->zoom == ZOOM_LVL_NORMAL

 * @param shape List of points on the polygon.

 * @param colour An 8 bit palette index (FILLRECT_OPAQUE and FILLRECT_CHECKER) or a recolour spritenumber (FILLRECT_RECOLOUR).

 * @param mode

 *         FILLRECT_OPAQUE:   Fill the polygon with the specified colour.

 *         FILLRECT_CHECKER:  Fill every other pixel with the specified colour, in a checkerboard pattern.

 *         FILLRECT_RECOLOUR: Apply a recolour sprite to every pixel in the polygon.

 */

void GfxFillPolygon(const std::vector<Point> &shape, int colour, FillRectMode mode)

{

	Blitter *blitter = BlitterFactory::GetCurrentBlitter();

	const DrawPixelInfo *dpi = _cur_dpi;

	if (dpi->zoom != ZOOM_LVL_NORMAL) return;

	std::vector<LineSegment> segments = MakePolygonSegments(shape, Point{ dpi->left, dpi->top });

	/* Remove segments appearing entirely above or below the clipping area. */

	segments.erase(std::remove_if(segments.begin(), segments.end(), [dpi](const LineSegment &s) { return s.second.y <= 0 || s.first.y >= dpi->height; }), segments.end());

	/* Check that this wasn't an empty shape (all points on a horizontal line or outside clipping.) */

	if (segments.empty()) return;

	/* Sort the segments by first point Y coordinate. */

	std::sort(segments.begin(), segments.end(), [](const LineSegment &a, const LineSegment &b) { return a.first.y < b.first.y; });

	/* Segments intersecting current scanline. */

	std::vector<LineSegment> active;

	/* Intersection points with a scanline.

	 * Kept outside loop to avoid repeated re-allocations. */

	std::vector<int> intersections;

	/* Normal, reasonable polygons don't have many intersections per scanline. */

	active.reserve(4);

	intersections.reserve(4);

	/* Scan through the segments and paint each scanline. */

	int y = segments.front().first.y;

	std::vector<LineSegment>::iterator nextseg = segments.begin();

	while (!active.empty() || nextseg != segments.end()) {

		/* Clean up segments that have ended. */

		active.erase(std::remove_if(active.begin(), active.end(), [y](const LineSegment &s) { return s.second.y == y; }), active.end());

		/* Activate all segments starting on this scanline. */

		while (nextseg != segments.end() && nextseg->first.y == y) {

			active.push_back(*nextseg);

			++nextseg;

		}

		/* Check clipping. */

		if (y < 0) {

			++y;

			continue;

		}

		if (y >= dpi->height) return;

		/*  Intersect scanline with all active segments. */

		intersections.clear();

		for (const LineSegment &s : active) {

			const int sdx = s.second.x - s.first.x;

			const int sdy = s.second.y - s.first.y;

			const int ldy = y - s.first.y;

			const int x = s.first.x + sdx * ldy / sdy;

			intersections.push_back(x);

		}

		/* Fill between pairs of intersections. */

		std::sort(intersections.begin(), intersections.end());

		for (size_t i = 1; i < intersections.size(); i += 2) {

			/* Check clipping. */

			const int x1 = max(0, intersections[i - 1]);

			const int x2 = min(intersections[i], dpi->width);

			if (x2 < 0) continue;

			if (x1 >= dpi->width) continue;

			/* Fill line y from x1 to x2. */

			void *dst = blitter->MoveTo(dpi->dst_ptr, x1, y);

			switch (mode) {

				default: // FILLRECT_OPAQUE

					blitter->DrawRect(dst, x2 - x1, 1, (uint8)colour);

					break;

				case FILLRECT_RECOLOUR:

					blitter->DrawColourMappingRect(dst, x2 - x1, 1, GB(colour, 0, PALETTE_WIDTH));

					break;

				case FILLRECT_CHECKER:

					/* Fill every other pixel, offset such that the sum of filled pixels' X and Y coordinates is odd.

					 * This creates a checkerboard effect. */

					for (int x = (x1 + y) & 1; x < x2 - x1; x += 2) {

						blitter->SetPixel(dst, x, 0, (uint8)colour);

					}

					break;

			}

		}

		/* Next line */

		++y;

	}

}

void GfxFillPolygon(const std::vector<Point> &shape, int colour, FillRectMode mode = FILLRECT_OPAQUE);