分类目录归档：其他

其他有些什么其他东西呢

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

Posted on by
回复

计算多维空间——主要是二维空间——中最近点问题是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 个点就可以咯~~~

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

Posted on by
回复

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

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

问题：已知点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）

Posted on by
回复

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

Posted on by
回复

因为在一台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 开发笔记（准备工作）

Posted on by
回复

一、开发工具

  • 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 快捷方式

Posted on by
回复

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

继续阅读 →