Removing unnecessary polygon points

[PaulG]

Hi,

I have some edited polygons being submitted.

It is entirely possible for those polygons to contain a point which
lie on a straight line.

To illustrate my case : if you imagine a square with 4 lines and 4
points, and on the top line there is a 5th point sitting on that line
with exactly horizontal lines emanating from it - therefore making it
totally useless.

Does anyone know of an algorithm I could use or adapt for detecting
that unnecessary 5th point?

I could detect and remove that either in Javascript on the client or
in PHP as I store that Polygon.

I cannot readily see how I detect the angle that lines come into and
emanate from a point.

Any pointers gratefully received.

[Barry Hunter]

http://www.google.com/search?q=polygon+simplification

is a good start :)

Douglas-Peucker is one of the more common alogorithms, and there are
certainly implementations available in most languages (I've used a PHP
one) - there are even JS ones (I think there was one tailured for v2
not sure about v3)

> --
> You received this message because you are subscribed to the Google Groups "Google Maps JavaScript API v3" group.
> To post to this group, send email to google-map...@googlegroups.com.
> To unsubscribe from this group, send email to google-maps-js-a...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/google-maps-js-api-v3?hl=en.
>
>

[Ben Appleton]

V3 implements something like Douglas-Peucker in JavaScript. Are you sure you need to pre-simplify your polylines?

[PaulG]

@Ben Appleton said: "V3 implements something like Douglas-Peucker in

JavaScript. Are you sure you
need to pre-simplify your polylines? "

Ah, you could be correct there, I will look a bit closer at the return
values, I was just trying to work out in advance a problem I had
noticed in my test data.

Your comment certainly explains why while Mysql needs a Polygon to
have a both a start and and an end point which are exactly the same
this seems not to matter to Gmaps v3, it just dumps the extra data
point (my list of Mysql Geometry Polygon Gotchas is going up).

I will look into that matter now and post back what I find - thanks
for the heads up, most kind!

[bratliff]

Douglas-Peucker is a compute intensive recursive algorithm. It is
also asymmetric. It drops a different set of points in the forward /
reverse directions. It your polys share a common boundary, it will
result in gaps and/or overlaps between adjacent polys.

For quick & dirty point reduction, some simple techniques you might
use are:

Slope comparison:

((x[i]-x[i-1])*(y[i]-y[i+1]))

((y[i]-y[i-1])*(x[i]-x[i+1]))

If the two slopes are are approximately equal, you can drop the middle
point.

Length of sides of triangle:

b=sqrt
(
((x[i]-x[i-1])*(x[i]-x[i-1]))
+
((y[i]-y[i-1])*(y[i]-y[i-1]))
)

c=sqrt
(
((x[i+1]-x[i-1])*(x[i+1]-x[i-1]))
+
((y[i+1]-y[i-1])*(y[i+1]-y[i-1]))
)

d=sqrt
(
((x[i+1]-x[i])*(x[i+1]-x[i]))
+
((y[i+1]-y[i])*(y[i+1]-y[i]))
)

If "c" is approximately equal to "b+d", you can drop the middle point.

Area of implied rectangle:

(x[i+1]-x[i-1])
*
(y[i]-y[i+1]+y[i]-y[i-1])

or

(y[i+1]-y[i-1])
*
(x[i]-x[i+1]+x[i]-x[i-1])

The two expressions are the inverse of each other. The one will be
positive. The other will be negative. If either is approximately
zero, you can drop the middle point.

Finally, to eliminate projection bias & reduce rounding errors, you
ought to convert from floating point Lat/Lon coordinates to integer
pixel coordinates. The three methods are not perfect but are fast &
symmetric in the forward / reverse directions. Both the API &
PolyCluster will perform further point reduction "on the fly"
depending on zoom level.

[PaulG]

Thanks for your reply @bratlif, I shall mull over that during the xmas
break!

I cannot say I know how to implement that but shall have a stab at it
and come back if I cannot work it out, after all, this is how we
learn.

BTW, although I now have the capture and storage of Polygons working,
I note that Gmaps is not automatically removing the unnecessary extra
points, as it did with the first/last overlap when extracted from my
Mysql table.

Thanks again.