[TL][讨论]如何由N点之间的距离来确定相应的拓扑关系

1 view
Skip to first unread message

yingfei diao

unread,
Dec 24, 2009, 10:15:25 PM12/24/09
to pon...@googlegroups.com
已知   2维空间上 N点之间的两两距离 （N大于3）
求      这N点之间的拓扑关系

这里称拓扑关系不知是否合适
我的意思是指这些点之间的几何关系或者所构成的图形

不知道这一问题在图论之类的学科里是否已经有成熟的解法？
或者有没有算法能解决这一问题？

Hongzhang Liu

unread,
Dec 24, 2009, 10:20:52 PM12/24/09
to pon...@googlegroups.com
这个应该问题不大吧？任意选择三个点，取其中一点作为原点，与另外一点的连线作为x轴，已知两两之间的距离的话，这个三角形是固定的。之后不断的加点就可以了。需要考虑的是各个距离是否是相容的。

2009/12/25 yingfei diao <yfd...@gmail.com>

yingfei diao

unread,
Dec 25, 2009, 2:11:05 AM12/25/09
to pon...@googlegroups.com
觉得这样做好像有点麻烦

能有更轻便的算法么？

2009/12/25 Hongzhang Liu <hongzh...@gmail.com>

jun lin

unread,
Dec 25, 2009, 2:33:32 AM12/25/09
to pon...@googlegroups.com
在满足不了性能的时候再用其他的算法吧。

2009/12/25 yingfei diao <yfd...@gmail.com>

Simon Liu

unread,
Dec 29, 2009, 6:00:47 AM12/29/09
to pon...@googlegroups.com
记得以前做过一个IOI的题，给N个点坐标，判断是凸多边形还是凹多边形。本题我没太看懂需求，不知道那个题目的解法适用不适用

2009/12/25 jun lin <linjun...@gmail.com>



--
刘金雨(云涛)
Email/MSN/GTalk: yuntao.liu(AT)gmail.com

Shuo Chen

unread,
Dec 29, 2009, 6:27:24 AM12/29/09
to TopLanguage
这个，沿着定点走，每次都向左拐或向右拐就是凸的，否则是凹的。

On Dec 29, 7:00 pm, Simon Liu <yuntao....@gmail.com> wrote:
> 记得以前做过一个IOI的题，给N个点坐标，判断是凸多边形还是凹多边形。本题我没太看懂需求，不知道那个题目的解法适用不适用
>

> 2009/12/25 jun lin <linjunhal...@gmail.com>


>
>
>
> > 在满足不了性能的时候再用其他的算法吧。
>
> > 2009/12/25 yingfei diao <yfd...@gmail.com>
>
> >> 觉得这样做好像有点麻烦
>
> >> 能有更轻便的算法么？
>

> >> 2009/12/25 Hongzhang Liu <hongzhang....@gmail.com>

Mikster.Z

unread,
Dec 29, 2009, 6:35:19 AM12/29/09
to pon...@googlegroups.com

@Shuochen ： 沿着才是问题吧~拐不是问题。

@楼主：任取三点固定一个坐标系，求坐标，然后凸包，就可以确定了。

2009/12/29 Shuo Chen <gian...@gmail.com>



--
EX - EMBEDDED SYSTEM DEVELOPER
SOFTWARE ENGINEER
Name : Mikster  

Shuo Chen

unread,
Dec 29, 2009, 8:31:35 AM12/29/09
to TopLanguage
那要看题目给的N个点是否有序了，有序的话就沿着走，否则就求凸壳。

On Dec 29, 7:35 pm, "Mikster.Z" <chinamix...@gmail.com> wrote:
> @Shuochen ： 沿着才是问题吧~拐不是问题。
>
> @楼主：任取三点固定一个坐标系，求坐标，然后凸包，就可以确定了。
>

> 2009/12/29 Shuo Chen <giantc...@gmail.com>

Mikster.Z

unread,
Dec 29, 2009, 9:34:45 AM12/29/09
to pon...@googlegroups.com
有序是你给加的条件~~

2009/12/29 Shuo Chen <gian...@gmail.com>

Simon Liu

unread,
Dec 30, 2009, 5:11:36 AM12/30/09
to pon...@googlegroups.com
嗯。。原题是无序的，是我没说清楚

2009/12/29 Mikster.Z <china...@gmail.com>



--
刘金雨(云涛)
Email/MSN/GTalk: yuntao.liu(AT)gmail.com

CatDog

unread,
Dec 31, 2009, 6:57:10 AM12/31/09
to TopLanguage
我觉得这很有可能不相容，二维空间并不意味着是二维平面，如果是球面或者锥面的话建立二维笛卡尔坐标系是不可能的。
可不可以考虑从四面体开始建立三维的坐标系，这样的话不论是球面还是锥面的点集一定可以映射到三维笛卡尔坐标系，然后楼主再搞个蒙皮，吹气球之类的拓扑
操作试试吧。

数学上来说这个东西可能和张量分析有关，建议楼主参考。

李貌

unread,
Jan 2, 2010, 2:49:59 AM1/2/10
to pon...@googlegroups.com
MDS算法就是做这个的。

2009/12/25 yingfei diao <yfd...@gmail.com>:

yingfei diao

unread,
Jan 13, 2010, 4:34:55 AM1/13/10
to pon...@googlegroups.com
convex optimization 和 MDS的方法的确可行，用的人也比较多了，还有没有别的更好的呢？

2009/12/29 Shuo Chen <gian...@gmail.com>

yingfei diao

unread,
Jan 13, 2010, 4:35:03 AM1/13/10
to pon...@googlegroups.com
的确有人用MDS来做，也有人用convex optimization的方法来做，

2010/1/2 李貌 <stca...@gmail.com>
Reply all
Reply to author
Forward
0 new messages