The point location problem is to store a set of edges S in a planar subdivision in such a way that we can answer queries of the following type: Given a query point q, report the face in the subdivision that contains q. The trapezoidal map of S is obtained by drawing two vertical extensions from every endpoint p of a segment in S, one extension going upwards and one going downwards. The extensions stop when they meet another segments of S or the boundary. The trapezoidal map of S is simply the subdivision induced by S, the boundary and the vertical extensions. This divides the polygon into trapezoids (which can degenerate into a triangle if any of the horizontal segments of the trapezoid is of zero length). Our demo will report the corresponding trapezoid including the query point (input by mouse or keyboard).
The demo below is based on Seidel's randomized incremental algorithm for line segments. We are currently extending this to monotone chains, which can be more space and time efficient. For a description about this work, which also address the more general problem of fractional cascading, see our CCCG 2001 paper.
Here is a demo
using the TIGER map of Manhattan.
WARNING: this may take a while to download because of the size
of the dataset.
It is a java 1.2 applet, your browser probably needs the
java 1.2 plugin.
If you are behind a firewall, you may not be able to run the applet
because it makes a socket connection to the server.
You can download
the java application directly and run it on your own machine,
and the speed will considerably increase if your machine has more memory
for the application.
Run the downloaded program using
java -jar Demo.jar
This requires the Java 1.2 platform though.
This research is conducted by Yunyue Zhu and Chee Yap.