markfang2050 发表于 2019-6-25 15:27:16

任意多边形的凹凸性判断与面积计算

编程比赛
输入各顶点坐标，如何程序判断一个任意多边形的凹凸性？并计算面积。
要求给出代码与测试案例。语言不限。

.·.·. 发表于 2019-6-25 15:53:49

看起来不难
只要输入顶点坐标是按顺序输入而非随机输入
对多边形A1A2..An我们只需要用行列式计算三角形A1A2A3,A1A3A4,...,A1An-1An的（有向）面积
之后看看全部面积是否同号就好。
总面积等于刚刚算的全部（有向）面积的和，无论是否为凸多边形都如此

mathe 发表于 2019-6-25 18:21:18

凸性应该判断A1A2A3,A2A3A4,A3A4A5,...,An-1AnA1的有向面积同号才对

一条菜狗 发表于 2020-4-15 17:20:53

.·.·. 发表于 2019-6-25 15:53
看起来不难
只要输入顶点坐标是按顺序输入而非随机输入
对多边形A1A2..An我们只需要用行列式计算三 ...

楼下的大佬（管理）什么来头？:D

.·.·. 发表于 2020-4-15 21:47:50

一条菜狗 发表于 2020-4-15 17:20
楼下的大佬（管理）什么来头？

不知道
但曾经混过CMO银牌的我不会做的题dalao都会做
有点害怕

wayne 发表于 2020-4-16 08:34:45

题目好像没说给的点都是有序的吧?:lol

不过,无序的好像我也想到办法了.

灵树 发表于 2020-4-26 21:04:23

对于随机分布点，可以用计算三角形法向量的办法找出所有边缘点，再用边缘点构成的三角形计算法向量即可求出某个点是内凹。

kastin 发表于 2021-9-25 21:06:51

mathe 发表于 2019-6-25 18:21
凸性应该判断A1A2A3,A2A3A4,A3A4A5,...,An-1AnA1的有向面积同号才对

要先确定不自相交，才能用这个方法进行凹凸性的判断，否则会出现失效。比如一笔画出来的连线自相交的五角星。
页: [1]
查看完整版本: 任意多边形的凹凸性判断与面积计算