COMP9021tangram

发表于 | 分类于

2. Background


The game of tangram consists in creating shapes out of pieces. We assume that each piece has its own colour,
different to the colour of any other piece in the set we are working with. Just for reference, here is the list of
colours that are available to us (you will not make use of this list):

1.1. Aims. The purpose of the assignment is to:

  • design and implement an interface based on the desired behaviour of an application program;
  • practice the use of Python syntax;
  • develop problem solving skills.

2.1. Pieces. Here is an example of the contents of the file pieces_A.xml, typical of the contents of any file of
this kind (so only the number of pieces, the colour names, and the various coordinates can differ from one such
file to another–we do not bother with allowing for variations, in the use of space in particular).

1
2
3
4
5
6
7
8
9
<svg version="1.1" xmlns="http://www.w3.org/2000/svg">
<path d="M 50 50 L 50 90 L 90 90 z" fill="red"/>
<path d="M 160 170 L 160 130 L 120 130 z" fill="green"/>
<path d="M 200 30 L 180 30 L 180 50 L 220 50 z" fill="blue"/>
<path d="M 40 100 L 40 140 L 60 140 L 60 120 z" fill="yellow"/>
<path d="M 210 70 L 230 90 L 270 90 L 270 50 L 230 50 z" fill="purple"/>
<path d="M 180 130 L 180 170 L 220 210 L 240 190 z" fill="olive"/>
<path d="M 100 200 L 120 180 L 80 140 L 80 180 z" fill="magenta"/>
</svg>

3. First task (3 marks)


You have to check that the pieces represented in an .xml file satisfy our constraints. So you have to check
that each piece is convex, and if it represents a polygon with n sides (n ≥ 3) then the representation consists
of an enumeration of the n vertices, either clockwise or anticlockwise. Here is the expected behaviour of your
program.

该题主要是对图形方面的一些数学知识的考察。如点是否在一个图形内部，图形的凸凹性质，线是否相交等等。

对于判断图形的凸凹性，可以判断对于每一个点来说，其余的边均在它的相同一侧。所以需要用向量来表示边。

然后用点与边的向量积来确定该点在边的哪一侧。以下为核心代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def onside(line, point):
   x1 = line[0]
   x2 = line[2]
   y1 = line[1]
   y2 = line[3]
   x = point[0]
   y = point[1]

   # y-y1/x-x1=y2-y1/x2-x1
   result = x * (y2 - y1) + y * (x1 - x2) - x1 * y2 + x2 * y1
   # print(result)
   if result == 0:
       # point on the line
       return False
   if result > 0:
       return 1
   else:
       return -1

判断点是否在图形的内部，则需要使用射线法来。也就是说假设点在图形内部，改点在非特殊情况下只和凸多边形有一个焦点

至于计算多边形的面积，则可以直接使用公式。s=1/2[(x1y2-x2y1)+(x2y3-x3y2)+…… +(xny1 - x1*yn)],代码如下

1
2
3
4
5
6
7
def calculate_area(points):
   area = 0
   for i in range(len(points) - 1):
       area += 0.5 * (points[i][0] * points[i + 1][1] - points[i + 1][0] * points[i][1])

   area += 0.5 * (points[-1][0] * points[0][1] - points[-1][1] * points[0][0])
   return abs(area)
Jie wechat
学就完事