[OSM-dev] Osmosis Replication Statistics

[David Siegel]

On 29.08.2007, at 09:41, Martijn van Oosterhout wrote:

> On 8/29/07, Brett Henderson <brett at bretth.com> wrote:
>> There is already a --bounding-box filter task.  Presumably you're
>> looking for something more accurate than a square ...  If so, I have
>> some research to do, I don't know how to figure out if a point fits
>> inside a shape.  Hopefully the algorithm isn't too difficult.
>
> Don't write code you don't need to, see:
> http://java.sun.com/j2se/1.4.2/docs/api/java/awt/Polygon.html
> You can create a Polygon object and then call the contains() function.
>

I agree with Martijn. Don't write it yourself. AFAIK finding points  
in a general polygon (not convex and with holes) is absolutly non- 
trivial. It becomes a lot easier for convex polygons without holes  
but it still requires very clever data structures and algorithms to  
get it efficient. If you find that awt/Polygon is too slow you might  
want to take a look at the Java Topology Suite:

http://www.jump-project.org/project.php?PID=JTS&SID=OVER

I'd also like to recommend the following book to everyone who is  
interested in spatial algorithms:

de Berg; van Kreveld; Overmars; Schwarzkopf
Computational Geometry
Algorithms and Applications
ISBN 3-540-65620-0

http://www.amazon.com/Computational-Geometry-Algorithms-Applications- 
Second/dp/3540656200/ref=pd_bbs_sr_1/002-2494453-4962429? 
ie=UTF8&s=books&qid=1188394001&sr=8-1

It's an excellent introduction to the topic. It's easy to read and  
contains a lot of mapping related examples.

cheers,
    david