📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 3258| 回复: 5
跳转到指定楼层
上一主题 下一主题
收起左侧

Google : 有关google地图实现的一个问题

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
假设有很多多边形,最大的是地球,每一个国家可以认为是一个多边形,
每一个省 ,市,区,小区,楼都可以认为是一个多边形,这些多边形之间要么是相互包含的,
要么是互相没有交集的,(不存在overlap的情况)。给出一个多边形,要求写程序求出最小的包含它的多边形。
已知有现成的函数可以判断两个多边形是否相互包含, iscontained(poly p1, poly p2)

上一篇:Google : Combine intervals
下一篇:Amazon : Inplace rearrange string
🔗
 楼主| wwwyhx 2011-9-12 02:56:45 | 只看该作者
全局:
按多边形包含关系组成一颗树吧, 最小包含多边形就是要求的父节点.
回复

使用道具 举报

🔗
yjyongz 2011-12-12 01:59:19 | 只看该作者
全局:
类似于 Trie的 数据结构
public class GoogleMap {

        /**
         * @param args
         */
        public class POLY{
                POLY array[];
                int id;
        }
       
        //time complexity is O(N^2); I am not sure about it
        //space complexity is O(N); N is # of POLY in the world
        POLY find(POLY root,POLY a,POLY b){
                if(root==null) return null;
                POLY result[] = new POLY[root.array.length];
                for(int i=0;i<root.array.length;i++){
                        result[i] = find(root.array[i],a,b);
                        if(result[i]==a) return a;
                        if(result[i]==b) return b;
                }
                int count = 0;POLY temp = new POLY();
                for(int i=0;i<result.length;i++){
                        if(result[i]!=null){
                                count++;
                                temp = result[i];
                        }
                }
                if(count==2) return root;
                else if(count==1) return temp;
                else  return null;
        }
       
        /*public static void main(String[] args) {
                // TODO Auto-generated method stub
               
        }*/

}
回复

使用道具 举报

🔗
nooneknow 2011-12-12 03:04:58 | 只看该作者
全局:
类似于 Trie的 数据结构
public class GoogleMap {

        /**
         * @param args
         */
        public class POLY{
                POLY array[];
                int id;
        }
       
        //time complexity is O(N^2); I am not sure about it
        //space complexity is O(N); N is # of POLY in the world
        POLY find(POLY root,POLY a,POLY b){
                if(root==null) return null;
                POLY result[] = new POLY[root.array.length];
                for(int i=0;i
yjyongz 发表于 2011-12-12 01:59



讲讲思路?怎么iscontained都没用?

这个数据结构在computational geometry里边类似典型的kd tree或者range tree。
回复

使用道具 举报

🔗
yjyongz 2011-12-12 05:21:11 | 只看该作者
全局:
地球
     亚洲          欧洲           美洲        澳洲   非洲    南极洲
中国  印度   法国  英国    美国  墨西哥

我的方法是 bottom-up (就是post-traverse)方法。。 举个例子
连个input 是 中国和 墨西哥  --》 expected output是地球

如果某个节点的结果集 result[]..有两个节点是不是NULL的 。。那这个节点肯定是包含的最小的POLY
不知道 对不对。。
回复

使用道具 举报

🔗
3vilCoder 2011-12-14 09:17:00 | 只看该作者
全局:
本帖最后由 tsy3602 于 2011-12-17 23:03 编辑

首先遍对所有poly遍历,找出包含给定多边形的所有多边形,记做set a。
然后从set a中找出一个可以包含在所有其它多边形中的多边形,这个多边形就是所求最小多边形。
时间复杂度为O(n)+O(n)=O(n),感觉这种做法挺傻瓜的...
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表