Quantcast

Best way to turn arbitrary Geometries into multi-point approximation

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Best way to turn arbitrary Geometries into multi-point approximation

mark harwood
I have a search technology that can store and index information
presented as WKT multi-points and can then quickly retrieve records that
have points in a defined search area (ranking records by the number of
points contained in the search area).

What I would like to do is use JTS to translate any given geometry
(lines/polygons etc) into a multi-point approximate reprentation for
storing in this index. Each output geometry would use a limited number
of points to express the shape - a line for example would be translated
to a series of points whereas a polygon might look like a polka-dot
print with evenly spaced points.

Does anyone have any guidelines as to how to most efficiently achieve
this using the JTS api?

Many thanks for a wonderful project!

Cheers,
Mark


_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Best way to turn arbitrary Geometries into multi-point approximation

mbedward
Hi Mark

Interesting question - the polygon case is a bit like the recent
discussion of concave hulls, only in reverse :)

For line strings maybe the LengthIndexedLine class is your friend.

For polygons, an easy hack would be to get the bounding box, generate
points on a regular grid within that and then test for point in
polygon, though you might need some elaboration of that if you're
dealing with long, narrow polygons.

Michael
_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Best way to turn arbitrary Geometries into multi-point approximation

mark harwood
Hi Michael,
Thanks for the response.


> , generate
> points on a regular grid within that and then test for point in
> polygon, though you might need some elaboration of that if you're
> dealing with long, narrow polygons.
>  
Yes, that is an issue. I was coming round to this idea:

1) Get Bounding box for given geometry
2) Generate a grid of evenly sized boxes (e.g. 16x16) that fit into the
bounding box
3) For each box in 2 check to see if it is contained by the original
geometry -if it is, generate a regular grid of points in the box (number
of points is proportionate to box size)
4) If a box in 3) is not contained but overlaps, further subdivide that
box and repeat step 3) with this grid layer

This recursion would repeat until you reach a level of box that meets a
pre-defined level of resolution (otherwise it could repeat subdivisions
forever).

Cheers
Mark



> Michael
> _______________________________________________
> jts-devel mailing list
> [hidden email]
> http://lists.refractions.net/mailman/listinfo/jts-devel
> ------------------------------------------------------------------------
>
>
> No virus found in this incoming message.
> Checked by AVG - www.avg.com
> Version: 8.0.237 / Virus Database: 270.11.5/1978 - Release Date: 03/01/09 07:04:00
>
>  


_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Best way to turn arbitrary Geometries into multi-point approximation

mbedward
Hi Mark,

Yes, I think that's a reasonable approach.

Michael
_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Loading...