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

SAY · 发表于 2024-4-15 15:47:49

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

inabilezami · 发表于 2024-4-15 15:48:03

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

urinowiq · 发表于 2024-4-15 15:48:39

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

Kristslots · 发表于 2024-4-15 15:49:30

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

Zpasarbola · 发表于 2024-4-15 15:49:52

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

ozjazit · 发表于 2024-4-15 15:50:02

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

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

saluozu · 发表于 2024-4-15 15:50:42

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

singqing · 发表于 2024-4-15 15:50:52

要先确定不自相交，才能用这个方法进行凹凸性的判断，否则会出现失效。比如一笔画出来的连线自相交的五角星。

		自动登录	找回密码
密码			立即注册