计算二维空间某点的最近k 个点

计算多维空间——主要是二维空间——中最近点问题是GIS、游戏、计算机图形学中常遇到的问题。最近点问题包含但不局限于下面问题:

  1. 一维空间中距离点A 最近的一个点
  2. 一维空间中距离点A 最近的K 个点
  3. 一维空间中距离点A 小于D 的所有点
  4. 二维空间中距离点A 最近的一个点
  5. 二维空间中距离点A 最近的K 个点
  6. 二维空间中距离点A 小于D 的所有点

下面以问题 5. 二维空间中距离点A 最近的K 个点 为例,谈谈我的思路:

绘图1

 首先将二维距离变为一维距离,得到距离该点(红点)在一个坐标系上最近的1→i 个点,所对应的点的集合为Sx。下图是当i=3 时,距离最近的点:

绘图2

同理,得到y轴上最近的1→i 个点,点的集合为Sy。

绘图3

i 的大小从1 逐渐递增,每次计算集合Sx和集合Sy 的交集(Sx∩Sy),如果交集中的点w 是x、y坐标距离红点之和(△x+△y)第k 小的那个点,且满足约束条件:

△x+△y < max(Sx∪Sy)

那么停止i 的递增,在Sx和集合Sy 的交集(Sx∩Sy)中距离红点之和(△x+△y)中最小的k 个点即是平面上距离红点之和(△x+△y)最小的k 个点。当然约束条件可以进一步优化为:

△x+△y ≤ max(min(Sx)+max(Sy),min(Sy)+max(Sx))

因为二维平面距离之和(△x+△y)与距离(\sqrt{\bigtriangleup x^2+\bigtriangleup y^2})满足:

△x+△y ≥  \sqrt{\bigtriangleup x^2+\bigtriangleup y^2}

 那么距离红点最近的k 个点距离上限小于△x+△y。

最终,只需要在一个较小的集合Sx∪Sy 中遍历找到距离红点最近的k 个点就可以咯~~~

计算某一点到连接两点的直线距离(矢量方法)

方法一:计算两点形成直线的斜率,斜率的负倒数是某点到该直线的斜率,通过计算垂足到该点距离得到某点到两点形成的直线距离。

方法二:矢量方法,好处是对于任意斜率都可以计算。

问题:已知点A (ax, ay),求到连接点B(bx, by)  和C(cx, cy) 的直线距离。

假设:建立坐标系,向量\vec{a}\vec{b} \vec{c}  分别对应三点的向量,如下图:

绘图1

图中C到直线AB 的垂线是紫色那根(假设垂足为D,图中未标注)。分别求得A 到B 的向量和C 到B的向量:

\vec{AB} = \vec{b}-\vec{a}    \vec{CB} = \vec{b}-\vec{c}

通过计算\vec{AB} \times \vec{CB} 可以推导出红色线段长度为$\mid\vec{CB}\mid \cos\theta $,因为

\vec{AB} \times \vec{CB}  = \mid\vec{AB}\mid \cdot \mid\vec{CB}\mid $ \cos\theta $

再通过勾股定理得到垂线距离:

$\mid CD\mid = \sqrt{\mid\vec{CB}\mid ^2 - (\frac{\vec{AB} \times \vec{CB})^2}{\mid\vec{AB}\mid}}$

$ = \sqrt{(cy-by)^2+(cx-bx)^2-\frac{((bx-ax)(bx-cx)+(by-ay)(by-cy))^2}{(ay-by)^2+(ax-bx)^2}}$

 

Android 开发笔记(SDK)

Android 为开发者提供的SDK(Software Development Kit,软件开发包)提供了一系列API,通过调用这些API 即可写出各具形态的app 了,所以我们应该对SDK 有一定的了解。

SDK 中Java 类以树层次结构打包,最上层的是android package,它主要包含了app 的资源类和对安卓系统的权限。如:Manifest  |  Manifest.permission  |  R  |  R.anim  |  R.array  |  R.attr  |  R.color  |  R.dimen  |  R.drawable  |  R.id  |  R.layout  |  R.string  |  R.style  |  R.xml 等。

android.app 中包含了android已封装好的一些高级类,如: Activity  |  Service  |  Fragment

Activity 类表示人机交互的一个界面。

Service 类表示一个后台长时间运行的组件,无UI,比如处理网络通信,音乐播放,或者是与一个content provider 交互。

Fragment 类在平板等大屏显示时表示activity 行为的一部分,并且关联相应的UI(可以看做是一部分UI,类似于activity)。

adroid.app 中还包含了其他类和接口:Dialog  |  ActionBar  |  Notification 等。

 

提供基础的操作系统级别的服务:services, message passing,IPC(Inter-Process Communication)。

BatteryManager 电池状态信息。

Bundle  一个字符各种可打包类型映射

 

包含了可以访问android 提供content providers 的类。

 

包含app 外观设计的一些资源类:  R  |  R.anim  |  R.attr  |  R.bool  |  R.color  |  R.dimen  |  R.drawable  |  R.id  |  R.integer  |  R.layout  |  R.string  |  R.style  |  R.styleable 等。

 

提供了app 布局的一些小部件,如Bar 等。  AppBarLayout  |  NavigationView  等。

 

关于文字的类。有关接口和类: Editable  |  GetChars  |  Annotation  |  AutoText  |  Html  |  Layout

 

人如其名,包含一些小工具类,如时间、base64编码、字符串和数字处理方法等。

 

安卓app 上常用的一些UI 组件类。接口:Menu  |  ContextMenu  |  MenuItem  类:Display  |  Gravity  |  LayoutInflater (在对应的View 对象中实例化某个XML布局) |  MenuInflater  |  View(UI最基本的组件)

 

包含屏幕上使用的UI 组件,你也可以自己设计一些组件(实现View 的子类)。类:  Button  |  CheckBox  |  CheckedTextView  |  EditText  |  GridView  |  ImageButton  |  ImageView  |  LinearLayout  |  ListView  |  MediaController  |  ProgressBar  |  RadioButton  |  RadioGroup  |  RelativeLayout  |  Scroller  |  TableLayout  |  Toast  等。

 

包含了在设备上访问和写入数据的类,主要包括:1.内容分享 (android.content  中的 ContentProvider 、 ContentResolver 、Intent 和 IntentFilter);2. 包管理(访问一个安卓包.apk的信息) 3. 资源管理(获取应用app 相关的资源数据,如strings,drawables,media等)。

 

包含用于处理从content provider 返回来的数据。如果需要管理一个私有的数据库,请使用 android.database.sqlite 类。

 

管理Sqlite 的类。接口和类:SQLiteCursorDriver  |  SQLiteClosable  |   SQLiteCursor  |  SQLiteDatabase  |  SQLiteQuery  |  SQLiteStatement  等。

 

提供可以在屏幕上直接画图的低级工具,如画布、滤镜、点和矩形。

 

提供管理可视化元素(图、灰度等)的类,这些类经常被widgets 作为背景图片或者指示器。

 

管理音频和视频的类。AsyncPlayer  |  AudioManager  |  MediaPlayer  |  Ringtone

 

java.net.* 之上的网络访问类。

 

使用OpenGL 画图。

 

 

 

 

Ubuntu14.04 上安装pygame

因为在一台ubuntu 服务器上跑个pygame 的程序,在ubuntu14.04 上安装pygame 了一天,之前在windows 上安装很顺利,换做ubuntu 上就有点傻傻的。总结来说尽量不要手动下源包,通过configure 和 make install 来安装,因为存在很多依赖(32-bit,64-bit 等)的问题。应该采用正确的安装姿势:

sudo apt-get install python-game

我的过程如下:

在pygame 官网下载了最新(2009年的(⊙﹏⊙)b,因为基于的SDL 从1.2换做2.0版本了,无法做兼容了)的pygame 源码,解压, python setup.py install  安装。

安装后的结果是可以在程序中 import pygame 并使用基本的函数(如pygame.draw.line 等),但如果要使用相关其他模块时,如 import pygame.font 则会出现 font module not found的问题. 我尝试采用 http://stackoverflow.com/a/15368766/1424948 中的方法安装相关的模块:

$ sudo apt-get install python-dev libsdl-image1.2-dev libsdl-mixer1.2-dev  
libsdl-ttf2.0-dev   libsdl1.2-dev libsmpeg-dev python-numpy subversion 
libportmidi-dev ffmpeg libswscale-dev libavformat-dev libavcodec-dev

但是还是会存在  font module not found 的问题,我也尝试使用自动安装pygame的方法来解决:

$ sudo apt-get install python-pygame

但这个问题应该是之前的手动安装已经无法覆盖,而手动的安装依赖问题无法解决。最终我的解决方法是:

  1. sudo python setup.py clean
  2. 删除 python/site-packages 下的pygame 包
  3. sudo apt-get install python-pygame

完成这三步后,一切OK。

 

 

Android 开发笔记(准备工作)

一、开发工具

  • Java 

Android 开发基于Java 语言,所以Java 语言环境必须安装。

  • Android SDK

Android SDK (Software Development Kit) 是开发Android 软件开发包,为开发者提供调用Android API调用,并负责将编译源码。功能类似于传统C++/MFC中开发的库文件加编译器。

从理论上讲,有Java 和Android SDK 就可以开发出结果为apk 的安卓应用了,但在目录、文件管理上比较困难,和其他工具(如模拟器)的扩展也需要手动操作,因此一般开发人员还需要一个开发平台。

  • Android Studio 或者Eclipse 开发平台

开发平台主要功能有三点:1.组织文件和目录;2.自动生成代码;3.扩展其他工具、插件。类似于Visual Studio平台中的管理功能,平台根据类型和作用分目录存放不同文件,比如res 存放静态文件。类似于使用MFC 新建项目时,VS 会自动生成一些通用代码。平台的另外一个好处就是很方便的能够扩展一些工具,比如模拟器,或者是在编译较老的SDK 时,需要从网上下载,平台都能够自动处理。总之,平台好处就是自动化处理一些原本需要人工操作的过程。

  • gradle

linux/C 项目开发中,如果你有了C语言环境(compiler,linker),有了项目所需要的库文件,你还需要通过一定的方法、规则将源文件生成安装程序,这些方法和规则一般写在Makefile 中,不同硬件设备有所区别,所以在安装源码时常通过configure 等脚本生成makefile,最后才make生成最终程序。Android 开发同理,一个Android 项目也需要通过SDK 的一些命令、工具生成中间文件,最后才生成安装程序,而管理这个过程最流行的工具就是gradle。当然不用gradle 也是可以的,只是需要手工敲得命令有些复杂和单调而已。

  • 模拟器(Emulator)

如果你没有真实的设备运行你的Android 程序,模拟器是不错的选择, 但平台中自带的模拟器效率较低,可以考虑其他模拟器,如Genymotion等。

二、安装过程

  1. 安装JDK(Java Development Kit)
  2. 安装Android SDK
  3. 安装Android Studio (下面全部以AS为例,需要VPN支持,或者使用SS并在AS 配置代理)
  4. 安装Android Emulator

三、Android体系结构

Android 基于Linux 操作系统的一个重要原因就是Linux 内核具有良好的硬件设备的支持,比如用于存储的磁盘,用于无线网连接的wifi。通过公共库(Libraries)对底层硬件的封装,为应用框架(Application Framework)和Android Runtime 提供了更具有特色的功能,比如SQLite 提供结构化数据库存储,OpenGL 提供高性能画图等。Android Runtime 基于优化的Java 虚拟机,称作Dalvik Virtuak Machine,任何Android 应用都是运行在这个虚拟机之上,虚拟机可以为应用分配内存和处理进程和进程间通信。应用框架(Application Framework)为程序提供更高层次的工功能服务,比如资源的访问和进程间消息传递等。

anst

四、应用组件

Android 每个应用包含四类组件:

  • Activities        与用户交互
  • Services         与应用有关的后台服务
  • Broadcast Receiver      Android 系统和应用的通信
  • Content Provider       与其他应用的通信

每一个Activity 对应着一块屏幕和一个与用户交互的事件,比如一个Android 邮件应用,有一个activity 是列出所有邮件,一个activity 读邮件,一个activity 写邮件等。所有的activities 都是源自于应用启动时的一个activity,类似于所有函数都是源于main() 函数调用。

一个Service 对应着一个后台持续运行的线程,比如一个后台播放音乐,在比如不中断用户操作的方式从网络上获取数据。

Broadcast Receiver用于回应其他应用或者系统广播的消息。比如一个应用可能发起广播给其他程序某些数据已经下载完毕了,那么Broadcast Receiver 则会截获这则消息并发起相应的动作。

Content Provider 通过请求用于向其他应用提供数据,例如第三方应用请求读取你的通信录。这类请求通过ContentResolver 类处理。一个Content Provider 可以连接多个Content Rsolver。他们关系如下图所示:

Android Training Bangalore

Android 还有其他一些组件,如Manifest 是应用的配置文件,Resources是外部元素,如变量和静态图片等。

五、文件组织结构

以Android Studio 为例,新建一个项目时,会在C:\Users\[your name]\AndroidStudioProjects 下创建你的项目对应的文件夹,而在Android Studio 视图中则有至少manifests、java 和res 三个目录。这三者分别保存配置文件,源代码和资源静态文件。

Screen Shot 2015-11-16 at 10.37.04 PM

  • manifests 目录下有AndroidManifests.xml 文件保存应用的配置信息,它告诉了系统需要哪些资源,以及如何构建起这个应用。
  • java 或src 目录下保存系统的 java 源文件
  • res 保存了用户交互所需要的资源,可能有子文件夹
    • drawable  保存图片
    • layout  保存屏幕布局
    • menu  保存屏幕菜单
    • values 保存为屏幕预定义的值

可能还可能有其他文件夹:

  • gen 是平台IDE 环境在编译时产生的中间文件
  • libs  外部的库文件

六、Android application package (APK) 生成过程

andriod的安装文件.apk如下图所示生成:

apk-structure

  1. .java源文件javac 编译为.class 二进制文件
  2. 项目.class 和其他外部库.class 通过dx编译为classes.dex 二进制可执行文件
  3. aapt 将classes.dex 二进制可执行文件、配置文件AndroidManifest.xml 和Resources 文件打包为apk 文件

知道了这个过程,那么你也可以通过将apk 反编译为xml、资源文件和源码等了。

 

 

 

TeXworks 快捷方式

以前一直用pspreview+xelatex+Notepad++,最近TeXlive2013 也试着安装了下,感觉TeXworks 的速度快,使用方便,有些特性非常实用。比如TeXworks 提供从pdf 源文件跳转到源码位置,只需要右键->跳至源文件,或者Ctrl+pdf上的位置,就可以跳转到源文件对应的位置了。TeXworks 有Preview window(显示pdf)和source window(显示源码)两个界面,在两个界面的快捷方式有:

继续阅读