|
Last updated on:
10 November 2008 06:00:17 PM
I'm not really familiar with
Computational Geometry...
but I'm going to fill in something here later...
1.
Introduction to Computational
Geometry
2. Geometrical objects
and its properties
3. Convex Hull
4. Line Intersection
5. Plane Sweep algorithm
6. Triangulation
1.
Introduction to Computational
Geometry
Computational Geometry is an important subject.
Mastering this subject can actually help you in programming contests since
every contest usually include 1-2 geometrical problems.
Unfortunately I myself also very weak in this
field... Nevertheless... let me start filling in more and more stuffs here...
2.
Geometrical objects and
its properties
Earth coordinate system
People use latitudes (horizontal lines)
and longitudes (vertical lines) in Earth coordinate system.
Longitude spans from 0 degrees (Greenwich)
to +180* East and -180* West.
Latitude spans from 0 degrees (Equator) to +90* (North pole) and -90* (South
pole).
The most interesting question is what is the
spherical / geographical distance between two cities p and q on earth with
radius r, denoted by (p_lat,p_long) to (q_lat,q_long). All coordinates are
in radians. (i.e. convert [-180..180] range of longitude and [-90..90] range
of latitudes to [-pi..pi] respectively.
After deriving the mathematical equations.
The answer is as follow:
spherical_distance(p_lat,p_long,q_lat,q_long)
=
acos( sin(p_lat) * sin(q_lat) + cos(p_lat) * cos(q_lat) * cos(p_long - q_long)
) * r
since cos(a-b) = cos(a)*cos(b) + sin(a)*sin(b),
we can simplify the above formula to:
spherical_distance(p_lat,p_long,q_lat,q_long)
=
acos( sin(p_lat) * sin(q_lat) +
cos(p_lat) * cos(q_lat) * cos(p_long)
* cos(q_long) +
cos(p_lat) * cos(q_lat) * sin(p_long)
* sin(q_long)
) * r
|
TEST YOUR EARTH COORDINATE SYSTEM KNOWLEDGE
Solve UVa
problems related with Earth Coordinate System:
535 - Globetrotter
10075 - Airlines
- combined with all-pairs shortest path
|
3. Convex Hull
Basically, Convex Hull is the most basic and
most popular computational geometry problem. Many algorithms are available
to solve this efficiently, with the best lower bound O(n log n). This lower
bound is already proven.
Convex Hull problem (2-D version):
Input: A set of points in Euclidian plane
Output: Find the minimum set of points that enclosed all other points.
Convex Hull algorithms:
a. Jarvis March / Gift Wrapping
b. Graham Scan
c. Quick Hull
d. Divide and Conquer
Will be written later... -_-''' (I will need
a lot of figures...)
This document, 10_computational_geometry.html, has been accessed 8345 times since 26-Jul-04 20:31:42 SGT.
This is the 1st time it has been accessed today.
A total of 4069 different hosts have accessed this document in the
last 1932 days; your host, 38.107.191.108, has accessed it 1 times.
If you're interested, complete statistics for
this document are also available, including breakdowns by top-level
domain, host name, and date.
|
