aboutsummaryrefslogtreecommitdiff
path: root/arch/casiowin/monochromelib/src/filled_polygon.c
blob: 85f8c3523ed1f79c28be7de397dd0d91b5bae4de (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/* *****************************************************************************
 * filled_polygon.c -- Display a filled polygon.
 * Copyright (C) 2011      Pierre "PierrotLL" Le Gall <legallpierre89@gmail.com>
 * Copyright (C) 2016-2017 Thomas "Cakeisalie5" Touhey <thomas@touhey.fr>
 *
 * This file is part of libcarrot.
 * libcarrot is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 3.0 of the License,
 * or (at your option) any later version.
 *
 * libcarrot is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 * See the GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with the libcarrot; if not, see <http://www.gnu.org/licenses/>.
 * ************************************************************************** */
#include <monochrome.h>

static int ML_filled_polygon_quicksord_partition(int *t, int p, int r)
{
	int i, j, x, tmp;
	j = p - 1;
	x = t[r];
	for(i=p ; i<r ; i++)
	{
		if(x > t[i])
		{
			j++;
			tmp = t[j];
			t[j] = t[i];
			t[i] = tmp;
		}
	}
	t[r] = t[j+1];
	t[j+1] = x;
	return j + 1;
}

static void ML_filled_polygon_quicksord(int* t, int p, int r)
{
	int q;
	if(p < r)
	{
		q = ML_filled_polygon_quicksord_partition(t, p, r);
		ML_filled_polygon_quicksord(t, p, q-1);
		ML_filled_polygon_quicksord(t, q+1, r);
	}
}


void ML_filled_polygon(const int *x, const int *y, int nb_vertices, ML_Color color)
{
	int i, j, dx, dy, ymin, ymax;
	int *cut_in_line, nb_cut;
	if(nb_vertices < 3) return;
	cut_in_line = malloc(nb_vertices*sizeof(int));
	if(!cut_in_line) return;
	ymin = ymax = y[0];
	for(i=1 ; i<nb_vertices ; i++)
	{
		if(y[i] < ymin) ymin = y[i];
		if(y[i] > ymax) ymax = y[i];
	}
	for(i=ymin ; i<=ymax ; i++)
	{
		nb_cut = 0;
		for(j=0 ; j<nb_vertices ; j++)
		{
			if((y[j]<=i && y[(j+1)%nb_vertices]>=i) || (y[j]>=i && y[(j+1)%nb_vertices]<=i))
			{
				dy = abs(y[j]-y[(j+1)%nb_vertices]);
				if(dy)
				{
					dx = x[(j+1)%nb_vertices]-x[j];
					cut_in_line[nb_cut] = x[j] + rnd(abs(i-y[j]+sgn(i-y[j])/2)*dx/dy);
					nb_cut++;
				}
			}
		}
		ML_filled_polygon_quicksord(cut_in_line, 0, nb_cut-1);
		j = 0;
		while(j<nb_cut-2 && cut_in_line[j]==cut_in_line[j+1]) j++;
		while(j < nb_cut)
		{
			if(j == nb_cut-1) ML_horizontal_line(i, cut_in_line[j-1]+1, cut_in_line[j], color);
			else
			{
				dx = 1;
				while(j+dx<nb_cut-1 && cut_in_line[j+dx]==cut_in_line[j+dx+1]) dx++;
				ML_horizontal_line(i, cut_in_line[j], cut_in_line[j+dx], color);
				j += dx;
			}
			j++;
		}
	}
	free(cut_in_line);
}