sc
发帖数: 122 | 1 发信人: oneaddone (我叫倒乱,来自乱岛,我是来捣乱的!), 信区: Algorithm
标 题: Re: 请教一个题,觉得这里肯定有人知道
发信站: 日月光华 (2003年06月12日01:23:32 星期四), 站内信件
判断点是否在多边形中
以点P为端点，向左方作射线L，由于多边形是有界的，所以射线L的左端一定在多边形外
，考虑沿着L从无穷远处开始自左向右移动，遇到和多边形的第一个交点的时候，进入到
了多边形的内部，遇到第二个交点的时候，离开了多边形，……所以很容易看出当L和多
边形的交点数目C是奇数的时候，P在多边形内，是偶数的话P在多边形外。
但是有些特殊情况要加以考虑。如果L和多边形的顶点相交，有些情况下交点只能计算一
个，有些情况下交点不应被计算（你自己画个图就明白了）；如果L和多边形的一条边重
合，这条边应该被忽略不计。为了统一起见，我们在计算射线L和多边形的交点的时候，
1。对于多边形的水平边不作考虑；2。对于多边形的顶点和L相交的情况，如果该顶点是
其所属的边上纵坐标较大的顶点，则计数，否则忽略；3。对于P在多边形边上的情形，
直接可判断P属于多边行。由 |
|
i*******o
发帖数: 7 | 2 【 以下文字转载自 ComputerGraphics 讨论区 】
发信人: iammaomao (毛毛), 信区: ComputerGraphics
标 题: 求助：多边形与锥体的相交问题
发信站: BBS 未名空间站 (Tue Nov 10 18:08:06 2009, 美东)
向大家求助一个题目：
求解多边形与锥体的相交截面， 多边形与锥体均为凸的。
对计算几何完全不懂，问了几个朋友查了点资料，但思路还是混乱，希望大家给些指导
，非常感谢。目前的想法如下：
方法1。 通过求锥形的边与多边形边的交点 来求锥形的边与多边形的交点 然后综合得
到结果
涉及到：线段与线段的交点，繁琐的判断
方法2。 a。映射到一平面，求两个多变形的交 b。映射回去
涉及到：平面上多边形的交（似乎有现成算法），映射（怎么做还在迷糊中）
方法3。 求每一个锥形面同多边形的交。
涉及到：非同一平面上多边形的交 （资料说三角形与多边形的相交比较高效，但锥形
体里面还有一个非三角形的面。。。）
不好意思，写得很杂乱。行家眼里恐怕是很外行，呵呵。请问大家哪一个比较靠谱呢？
复杂度呢？又或者有其他 |
|
i*******o
发帖数: 7 | 3 向大家求助一个题目：
求解多边形与锥体的相交截面， 多边形与锥体均为凸的。
对计算几何完全不懂，问了几个朋友查了点资料，但思路还是混乱，希望大家给些指导
，非常感谢。目前的想法如下：
方法1。 通过求锥形的边与多边形边的交点 来求锥形的边与多边形的交点 然后综合得
到结果
涉及到：线段与线段的交点，繁琐的判断
方法2。 a。映射到一平面，求两个多变形的交 b。映射回去
涉及到：平面上多边形的交（似乎有现成算法），映射（怎么做还在迷糊中）
方法3。 求每一个锥形面同多边形的交。
涉及到：非同一平面上多边形的交 （资料说三角形与多边形的相交比较高效，但锥形
体里面还有一个非三角形的面。。。）
不好意思，写得很杂乱。呵呵。请问大家哪一个比较靠谱呢？
复杂度呢？又或者有其他的算法推荐？非常感谢!! |
|
j**********3
发帖数: 3211 | 4 以前狗家的一个问题：
怎么判断一个点在多边形里？o(n), o(lgn)
这个怎么做啊？
由此，我想到相关的问题：
1. 给你一堆多边形的顶点，无序，你怎么知道某个点的下一个点是哪个点？也就是说
，你怎么从这些点中找到边缘？
2. 怎么判断两个多边形是否有交集？
3. 怎么判断两个多边形合并后的顶点？
4. 怎么求多边形面积
一头雾水，忘有大牛解答。。。 |
|
s***r
发帖数: 500 | 5 你要的多边形应该是共面的吧，非共面的麻烦一点，先triangulate...
你要先搞几个基本的，线段跟线段的交点，线段跟平面的交点。然后分两步：
1) 求锥体跟多边形所在平面的交 （另一凸多边形）
2) 求两个共面凸多边形的交 （有现成的例子）
求1)的话就分情况了，锥体顶点跟底面点在多边形所在平面的两侧 -> 求所有侧边上的
交点。都在一侧 -> 没有交集。一部分底面顶点在一侧 -> 多边形平面跟锥体底面相交
->找converting node，分两种情况处理....
这个很多computer graphics课的作业都有，去各大学搜搜没准能找到现成的... |
|
p******r
发帖数: 43 | 6 给定平面坐标系，给定一些点的坐标，这些点构成一个多边形。然后给出一个点的坐标，
判断这个点是否在多边形内。
或者给出一条直线 x=a, 如何算出这条直线和这个多边形的交点？
哪儿能找到这个问题的算法？ |
|
s*****j
发帖数: 6435 | 7 【 以下文字转载自 Mathematics 讨论区 】
发信人: shanggj (shanggj), 信区: Mathematics
标 题: 问一个多边形外切圆的问题.
发信站: BBS 未名空间站 (Mon Apr 23 11:34:58 2012, 美东)
知道一个多边形的顶点坐标. X[0]Y[0], X[1]Y[1],....,X[n]Y[n].
有什么简单方法算出这个多边形的外切圆半径和中心坐标?
多谢. |
|
o*******7
发帖数: 772 | 8 多边形由多个点组成,不是真正意义上的多边形,比如四个点(0,0),(0,1),(1,1),(1,0),
(0,0)就算组成一个正方形了.
有什么数学定理可以用来判断一个点是否在多边形里?要考虑到像"凹"这样的奇葩形状,
编程需要,谢谢. |
|
j**********3
发帖数: 3211 | 9 大牛，这些点，是按顺序给的么？如果不是，怎么知道多边形的边界呢？
另外，如何把两个多边形拼到一起，找交点呢？ |
|
H****r
发帖数: 16240 | 10 我对Glock最喜欢的几点，其一是零件超级少，其二是多边形膛线。
刚才去维基，发现CZ居然也是，
但感觉我的PCR，阴线阳线清清楚楚，不是多边形膛线啊。
有CZ82的同修，帮忙拍张膛线照片？ |
|
c***c
发帖数: 21374 | 11 想实现一个就像fireworks,photoshop里面那种多边形（或者叫绳索？）的效果
大概就是，用户在屏幕上点一下，出来一个点，然后移动鼠标就有一条线，再
点一下就又是一个点，两点之间自动连成直线。双击结束画图。如果最后一个点和
第一个点重合，则这两个点耦合，然后所有连接点与点之间的直线形成一个多边形
说明白了没？
tks |
|
c******n
发帖数: 4965 | 12 画多边形？
准备用典型MVC 结构， 希望在rendering 部分用尽量简单的办法，画个平面的多边形
， 每个角上
加个可以click 的control,
YUI 好像没有 |
|
s*****j
发帖数: 6435 | 13 知道一个多边形的顶点坐标. X[0]Y[0], X[1]Y[1],....,X[n]Y[n].
有什么简单方法算出这个多边形的外切圆半径和中心坐标?
多谢. |
|
|
j**********3
发帖数: 3211 | 15 这是针对我上边哪个问题？
另外，给多边形的时候，那些点，是按顺序给的么？如果不按outline的顺序给的点，
我都不知道怎么找相邻点。 |
|
|
x**e
发帖数: 96 | 17 已知不规多边形各点的坐标，以及连接他们的顺序，怎样求得重心的坐标？
谢谢 |
|
m******y
发帖数: 41 | 18 不需要形状完全一样，但要所有边都向外扩大
本以为实现了（如图1），蓝色是原图，绿的和红的是不同幅度扩大
用到了convhull命令
可看到图2就傻了，才发现convhull画出来的是convex多边形，没法搞concave
请达人们帮忙一下吧
多谢 |
|
H****h
发帖数: 1037 | 19 你可以算出每条边相对于你的参考点所张的角，取值在(-\pi,\pi),
符号依赖于边的方向。然后把所有角求和。
如果得到2\pi或-2\pi，那么参考点就在多边形里。
如果是0，就在外面。不会有别的值了。
， |
|
x**e
发帖数: 96 | 20 已知不规多边形各点的坐标，以及连接他们的顺序，怎样求得重心的坐标？
谢谢 |
|
H****h
发帖数: 1037 | 21 我自己推导的。注意到多边形的面积等于小三角形OP_kP_{k+1}面积之和。
而小三角形OP_kP_{k+1}的重心在(P_k+P_{k+1})/3。 |
|
|
s*****j
发帖数: 6435 | 23 说的不确切. 就是半径最小的能包含这个多边形的圆. 好象叫什么 equivalent
circle. |
|
s*****j
发帖数: 6435 | 24 说的是能够包含这个多边形的最小圆.
不一定每个顶点都在圆上吧. |
|
s*a
发帖数: 33 | 25 One approach maybe: divide the 多边形 into (n-2) triangulars,
then the mass (area) and the position of the center of mass
of each triangular is known. Now the problem becomes to find
the CM of (n-2) points and could be easily done. |
|
s*a
发帖数: 33 | 26 The division into triangulars is not a problem. Assume 顶点s are labled
as A1, A2, ..., An. Then can always choose A1A2A3, A1A3A4, ..., A1A(n-1)An.
When calculating the area of each triangular, remember it can be either
positive or negative (based on the particular ordering of the three
end points AiAjAk), which means each triangular can either have a positive
mass or a negative mass. This will take care of 凹多边形.
Of course, if catalina's formula is correct, then that is easier. :) |
|
S**I
发帖数: 15689 | 27 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
S**I
发帖数: 15689 | 28 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
c****p
发帖数: 6474 | 29 你这个越来越离谱了。和你说过了，显示器画不出纯圆就是因为像素的问题，现在你都
能发展出多边形就是圆了，你怎么不说之前的直线就是圆了？
用多高的分辩率，用多少像素也解决不了纯圆的问题。我不知道你是啥专业的这么硬气
，我虽然不算完全对口但是多少知道点。我来给你讲讲为什么用折线，为什么多少像素
都不行，为什么这是一个纯技术问题（而不是所谓的“一孔之见”的论据）。
先说位图：
我贴了两个复件，都是一个圆加个圆心，一张是原样，一张是放大的。黑线是圆，红点
是圆心。
圆的概念：圆是一个点集，这个点集的特点是其中所有点的到某一给定点的欧式距离都
相等，这个给定点叫圆心，这个相等的距离叫半径。
像素的概念：像素是数字成像的最小单位，听起来它更像是一个点的概念，但是实际上
它是有面积的；简单起见，我们可以用排在一起的小正方形说明问题。
在放大图里面，可以看到圆从圆周到圆心（含）13格，即13个像素。但是实际上这个圆
的半径是12，因为要从像素（方格）的中心点计算距离。那么怎么确定每个像素是黑（
在圆上）还是白（不在圆上）呢？
先要说明一个概念，真正意义上的圆是有无数个点的，但是实际在计算机处理的时候，
... 阅读全帖 |
|
b****g
发帖数: 4933 | 30 人类离天顶星科技究竟有多远——聊聊模拟声-数码声以及音染和数码音源
模拟声是连续的。数码声是不连续的。声音本身是模拟的，换句话说，声音本身是一个
连续的波形，模拟录音比如LP唱片，记录音频信号的唱片表面纹路也是连续的。而数码
录制声音的过程是把声音的波形截断，用一个个取样点去采集声音并且记录下来的过程
。
如果理解不能的话，打个不恰当的比方来帮助你吧。一个圆周由有无数个点组成。 当
你在这个圆周上均匀的找出10个点的时候，用直线连接这10个点，你所做的实际上是用
一个十边形来近似模拟这个圆周。你也可以在这个圆周上均匀找出100个点来，用线连
起来以后，你所做的是用一个一百边形来近似这个圆周。一个多边形做出来以后，用眼
睛看肯定觉得和真正的圆周是不同的，边缘有很多毛刺。但是均匀分布的点数量也多，
就越近似于圆。
但是这毕竟是多边形不是圆，因此你就用橡皮和笔去描这个多边形的边角，尽量给他描
圆了，把角去掉，把边描圆。你可以有多种不同的方法去描这个圆，不同的方法描出来
的圆是不同的，但是可以给出主观的（人耳）客观的（仪器）评估是好还是坏。主观也
好，客观也好，评估标准不同，评估的结果也不同，... 阅读全帖 |
|
p*****a
发帖数: 147 | 31 这题正解是什么？
- 树结构，O(lgn), how to build tree? 怎么用二分加速？
- 矢量乘法？
- scan all polys, find the min poly that contains the given poly. O(n), easy
to understand and divide to multiple machines.
10) 假设有很多多边形，最大的是地球，每一个国家可以认为是一个多边形，每一个省
，市，区，小区，楼都可以认为是一个多边形，这些多边形之间要么是相互包含的，
要么是互相没有交集的，（不存在overlap的情况）。给出一个多边形，要求写程序求
出最小的包含它的多边形。已知有现成的函数可以判断两个多边形是否相互包含，
iscontained(poly p1, poly p2)。
如何加速？如果在多机的情况下呢？
=> 可以用树结构表示包含的关系。
可以用二分搜索做加速。
多机的话可以range一个机器处理一个区域，另外要考虑前端处理机的负载不要成为瓶
颈，所以让每个机器自己判断此多边形是否包含。 |
|
p*****a
发帖数: 147 | 32 来自主题: JobHunting版 - G家一道题 这题正解是什么？
- 树结构，O(lgn), how to build tree? 怎么用二分加速？
- 矢量乘法？
- scan all polys, find the min poly that contains the given poly. O(n), easy
to understand and divide to multiple machines.
原题见：http://www.mitbbs.com/article_t/JobHunting/31828487.html
10) 假设有很多多边形，最大的是地球，每一个国家可以认为是一个多边形，每一个省
，市，区，小区，楼都可以认为是一个多边形，这些多边形之间要么是相互包含的，
要么是互相没有交集的，（不存在overlap的情况）。给出一个多边形，要求写程序求
出最小的包含它的多边形。已知有现成的函数可以判断两个多边形是否相互包含，
iscontained(poly p1, poly p2)。
如何加速？如果在多机的情况下呢？
=> 可以用树结构表示包含的关系。
可以用二分搜索做加速。
多机的话可以range一个机器处理一个... 阅读全帖 |
|
m**q
发帖数: 189 | 33 经过了三个月的断断续续的面试和准备，最近一阵抓了很多时间努力准备，
本以为最后的一次面试能弥补前面的不足，可惜还是功亏一篑...
想想主要是自己编程水平不行，不能快速的写出bug free code，另外
design和算法方面有差距，一方面是前面的准备不足，后面拼命努力最终
还是无补 :(
一共面了6个人，把面试题给大家分享，希望大家都能拿到满意的offer。
1) 一个range的序列（链表或数组），如[1,3], [2,6], [8,10]，[15,18]
写程序合并有重叠的range，比如上面的序列合并为[1,6], [8,10], [15,18]
如果这个序列不是静态的，而是一个数据流，如何 处理？
2) 利用快速排序的划分方法，把数组分成三部分，< val, = val, > val。
3) 对于google查询的词组成的动态的数据流，在任意时刻取出10个完全随机的查询。
4) 把一个字符串转换成32bit的整数
5) 在一个数组中寻找三个数，使得它们的和为0
6) 大概是用一位数组来表示二维数组，但是每一行的元素个数可以不同，实现get，
set函数
7) 已知每个待查找... 阅读全帖 |
|
g***s
发帖数: 3811 | 34 10) 假设有很多多边形，最大的是地球，每一个国家可以认为是一个多边形，每一个省
，市，区，小区，楼都可以认为是一个多边形，这些多边形之间要么是相互包含的，要
么是互相没有交集的，（不存在overlap的情况）。给出一个多边形，要求写程序求出
最小的包含它的多边形。 |
|
x******g
发帖数: 318 | 35 问题
如果一个多边形的对应边都比另一个同样边数的多边形的长，那么当该多边形满足什
么条件
（充要条件）的时候，它的面积也一定比另一个的大？
另一个等价的说法：
如果一个多边形的面积比任何一个同样边数的对应边都比它小的多边形的大，那么该
多边形应该满足什么条件（充要条件）？ |
|
t********u
发帖数: 44 | 36 如何判断一个点是否在多边形内部还是外部
射线法。
即从待测点向多边形任意方向发出一条射线，若射线与多边形的交点为奇数，则该点在
多边形内部；反之该点在多边形外部。
网上搜的，我擦，小白弱问这算考啥啥能力？ |
|
l*********g
发帖数: 1729 | 37 你们可以找你们的李小林叫兽看看，这个垃圾教授的水平估计也作不出来。所以老将都
是些不学无术的垃圾。
给定一个正方形，现在往正方形内随机丢入10个点，每个点立刻以相同速度向四面八方
膨胀占领周围的区域直到碰到其他的点的膨胀区域才停止。这样最后正方形会被分割出
10个多边形，多边形的边为各个点膨胀后停止下来的边界线。问：最后这些多边形中有
一个3角形的概率？2个三角形？3个？
一个四边形？5边形？等。
来帮助老将们理解一下这个题目：其实就是最简单的，对任何2个点，因为他们以相同
速度向四面八方膨胀，所以最后他们肯定相遇在2个点连线的中垂线上，这个中垂线就
是分界线。对任意2个点都有中垂线，这些中垂线就构成了多边形的边。
把题目稍微便难点：现在往正方形内随机丢入n个点,回答上面的问题。
更难点：如果是立方体，最后形成的都是多面体，其中有4面体的概率？五面体的概率
？等等。
更更难点：如果是一般的k维体，结果又如何？ |
|
发帖数: 1 | 38 大前提：圆不是多边形，这个用三角和圆定义证明。
if π= m/n
圆就等同多边形，或者多边形外接圆的小弧，和多边形对应边等长。
悖论出现。
QED. |
|
t****o
发帖数: 31 | 39 我觉得多边形覆盖的问题可以抽象为一个树的结构，地球作为根节点，仅被地球包含的
多边形作为根节点的子节点，依次递归建立树。找一个包含给定多边形的最小多边形就
变成找一个给定节点的父节点了 |
|
g***s
发帖数: 3811 | 40 来自主题: JobHunting版 - G家一道题 都有了现成的函数，没有必要树结构，也没有必要矢量乘法（这个是用来实现包含函数
的）
× 多core同时对所有多边形判断是否包含给定的多边形，如果包含，得到这个多边形
的最左结点
× 在这些最左结点中找最大的那个，对应的多边形就是了。
easy |
|
i*****t
发帖数: 24265 | 41 说过了，不懂不是错，不懂装懂就是错了。
为什么用直线画圆?
1 不是你说的像素问题，毕竟显示器像素有限，全部用像素点来代替也没有任何问题
2 计算机的圆不一定是圆的，显示器可以直接看出来是直线组成，其实不过只是大家规
定它是圆罢了
3 不承认大家多边形做圆的公理，如何能知道多边形就是圆呢？
4 只要你认为了那多边形是圆，那就没有问题，跟别人交通也无问题了
5 如果一味指责电脑的多边形不是圆，那就进入了牛角尖了，没有任何意义。 |
|
s*****V
发帖数: 21731 | 42 找到的貌似后续 4
我们今天从AS定理的远祖开始来考察一下AS定理的世系演化。
平面三角形的内角和等于180度这一定理，不能算是AS定理最早的祖先，但算得是一个
好的祖先代表。
这个简单例子让我们看到了几何体上有代数，三对边夹角之和是个常数。因此，我们知
道无穷多个三角形之所以能归为一类，用边数为3或角数为3来判断都不够好，而是因为
有一个共同的不变量π。这个不变量是几何不变量。
三角形还有别的不变量吗？当然有。大家可以验算一下：边数-顶点数＝0对所有三角形
也成立（不许笑！），而且与几何不变量π没有关系。
这个不变数对任意多边形（平面的或立体的）都成立：边数-顶点数＝0。有一点点意思
了吧。敏感的同学可能马上看到这个不变数0是由于任意多边形都是一个闭合的东东。
更多一点意思的是，推广到无穷多边形也是成立的，特别是对圆周也成立，虽然边和顶
点已经难以看出来了。
于是我们发现这个不变数0原来是不仅是三角形的，也不仅是多边形的，也不仅是圆周
的，而是任意封闭曲线的性质。任意封闭曲线有一个不变数0。这就是封闭曲线的所谓
拓扑不变量。到这时，我们看不到这个0与边数或顶点数之类的关系，边、顶点、... 阅读全帖 |
|
a**u
发帖数: 99 | 43 能不能这样算一个多边形的重心?
选取一个中心为原点,如,取各点x坐标的平均,y坐标的平均.
把每个端点和该点相连,就形成乐N个三角形.
然后,调用N次计算三角形重心和重量的子程序.
得到(M_1,C_1),(M_2,C_2)，……，(M_N,C_N)
M_i为重量,C_i=(x_i,y_i)为重心位置.
这样,该多边形的重心为
X=∑（M_i*x_i）/∑M_i
Y=∑（M_i*y_i）/∑M_i
同理，可以得到凹多边形的重心。
整个怪异多边形的重心则易得到。 |
|
c***s
发帖数: 70028 | 44 图片说明：从某个角度看，宁波路390号的建筑薄如纸片。
图片说明：绕到楼背后，才发现“纸片楼”其实是多边形建筑。
宁波路异形老宅“薄如纸片” 专家:设计为利用空间
据《东方早报》报道，这是我看错了?这楼只能看不能住吗?……近日，一张“纸片楼”的照片引来网友连连惊呼。之所以被称为“纸片楼”，是因为从照片上看，整栋楼薄如一张纸片。而令人诧异的是，在“纸片”上，竟然还晾晒着衣物被单，俨然有人居住其中。记者在实地走访后发现，薄如纸片的立面只是视线错觉，老宅实际是带有三角的多边形建筑。
建筑师介绍，过去在造楼时往往会将地界利用到最大限度，贴着马路边建楼，也叫做贴界。
居民：已建成七八十年
这样的楼能住人吗?在看到“纸片楼”的照片时，网友不免提出了各种疑问，仅仅就照片上的情形来看，这幢4层楼的楼房显然有些不可思议。
昨日早报记者来到了照片中的“纸片楼”，该楼位于宁波路390号。楼内居民告诉记者，整幢楼一共住着40多户人家，事实上“纸片”的形状仅仅是一种视线错觉，整幢楼三角形的格局使得它在某个角度看起来薄得仿佛一张纸。
“这幢楼有七八十年历史了，我们从来都没觉得有什么稀奇的。”听闻记者来采访，一位居... 阅读全帖 |
|
b*******8
发帖数: 37364 | 45 你这个绝对通不过审稿：
if π= m/n
圆就等同多边形，或者多边形外接圆的小弧，和多边形对应边等长。 |
|
b*******8
发帖数: 37364 | 46 这个证明要能通过发表，能得菲尔兹奖了
if π= m/n
圆就等同多边形，或者多边形外接圆的小弧，和多边形对应边等长。 |
|
S******r
发帖数: 4421 | 47 刚仔细研究了下割圆术
原来是用勾股定理反复迭代
小时候看的科学画报 反复提到画多边形 误以为真要画多边形
是我才疏学浅 2b了
===========================
即便每个边只有两厘米
那圆周也在24k cm 也就是240m
这里有几个问题
1. 这个直径将近80米的大圆是怎么画出来的
2. 这块地得有多平整 才能保证这个精度
3. 这些小木棍 或其他切边的东西 在边与边连接是要多紧密
才能保证7位小数点精度
不黑不吹 做理性探讨
“南北朝数学家祖冲之，并没有发明新的方法计算圆周率[15][16]，而是将刘徽割圆术
的计算，继续分割到12288边形，又用刘徽多边形面积公式，求得24576边形的面积” |
|
t******l
发帖数: 10908 | 48 这个其实说明阿基米德欧几里德都是有漏洞的。如果是 fractal 的形状，那即使空间
在被约束在两个多边形之间，周长也不一定就在两个多边形之间，因为 fractal shape
被两多边形 bound 的时候，其周长不能保证函数单调性。
：娃从目前看来，应该是明显比老爹我聪明。可惜不是天才级别的聪明啊。要是天才，
估计就不需要老爹我劳什么神了。
： |
|
t******l
发帖数: 10908 | 49 我觉得首贴这个有可能 make sense。比如那隔壁楼的拉灯问题求通解作为例子。
如果用 power set 这种 propositional logic on sets，这样的话 brain task 看起
来主要就是靠 phonological thinking，而并不 activate spatial-temporal-
topological thinking。而这样的话，因为超过 "the magic # 7"，导致基本必须笔算
。而这种情况下，因为 brain 只用一块功能，dorsolateral prefrontal cortex 也用
不上。
（logician 那种九九集合逻辑表背得滚瓜烂熟，可以依靠 long-term memory 笔算的
另说，当然可能对心理健康可能没啥帮助）。
但如果用 “在每个灯泡上画点，然后每个灯泡上两两连成多边形，然后数多边形，考
虑独立自主和寄人篱下，再加组合公式，这种把问题给 map 成 spatial-temporal-
topological 问题，然后 recurse down” 的办法，这是需要更多的时间，而且依赖于
al... 阅读全帖 |
|
h****y
发帖数: 9234 | 50 澳大利亚新近成立的公司Euclideon近日发布了最新产品，一款名为“无限细节（Unlim
ited Detail）”引擎。
据称该引擎可将当今图形水准提升十万倍，不采用多边形。利用微粒构建的模型，可呈
现无限点云数据，打造无限细节的强大图形效果，
此前游戏界普遍采用的是多边形构建的模型。
另外，这款仍然在完善的新引擎可让《孤岛危机2》过时，虽然所说仅针对多边形构建模
型的CE3引擎。不过，从发布的图片效果来讲，还
有很长的距离，但Euclideon是一家纯技术公司，非美工设计公司，其所发布的演示效果
也可能对引擎的评价有所影响。
震撼视频：
http://v.youku.com/v_show/id_XMjkxNTA3MjA0.html |
|
