On Dec 22, 11:14 am, PaulG <[email protected]> wrote:
> 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.
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.
--
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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/google-maps-js-api-v3?hl=en.
