CODEWITHSUNDEEP
algorithmgoogle-mapsgispolygon
Baz
Baz

Reputation: 13125

Coordinate Points to Polygons

I have a large set of coordinates, which include the likes of:

59.284 18.42
59.401 18.078
58.894 17.854
59.277 18.742
59.219 18.186
59.472 18.108

The latitude coordinates have a resolution of 0.001 and the longitude 0.002.

Each point is associated with a rectangular area. For a point (x, y) the latitude side of this area ranges from x to x+0.01 with the longitude being y to y+0.02.

Each point is associated with a value between 1 and 10.

What I wish to do is group adjacent areas with the same value in the form of a polygon. The polygon will define the lines that make up its outer boundary, and if it is doughnut like in shape, it will also need to define inner boundaries.

Is there any algorithm or tool which might help me to do this?

I can program in python, csharp, java or c++.

Thanks for your help,

Barry

Upvotes: 0

Views: 1872

Answers (4)

Baz
Baz

Reputation: 13125

Here's the answer:

http://www.cs.man.ac.uk/~toby/alan/software//

Upvotes: 0

Angus Johnson
Angus Johnson

Reputation: 4643

For each set of coordinates associated with the value 1 to 10 do

  1. scale coordinates to integer values (multiply by 1000) to avoid floating point comparisons
  2. convert coordinates to rectangular polygons
  3. 'union' these polygons (using Clipper, Boost Geometry or Boost Polygon) to merge the adjacent ones

Upvotes: 1

James Waldby - jwpat7
James Waldby - jwpat7

Reputation: 8701

You might be able to adapt a contour finding algorithm for your purpose. Numerous articles and several programs are available online.

Answer #11 in an article in a CFD forum summarizes one method as follows:

(1) Assume you have a plot package that can plot straight line segments. (2) Construct a fine grid with (x,y) coordinates over the domain on which you want to plot. (3) Evaluate the function to be coutoured at each node by computing the function or perhaps interpolating some discrete approximation. (4) Select a list of coutour levels to be plotted. (5) For each rectangle of the grid: (a) Find the largest and smallest function values on the corners. (b) Ignore the contour levels outside the range of the largest and smallest values. (c) For each acceptable contour and for each edge, find the coordinate values of the intersection of the contour level and the straight line joining the function values at the corners. (d) Plot the line segments joining coordinates with equal contour values.

Note, answers #6-#10 briefly talk about using gri, PGPLOT, matlab, and Plotmtv for contour plotting.

Upvotes: 0

Steve C
Steve C

Reputation: 647

I don't know an answer to your whole question, but I would suggest scaling your coordinates by 1000 so you deal with integers if possible. For testing adjacency, you will need to do exact arithmetic and comparisons, or else you will have to do all comparisons to be "close enough" (epsilon value).

Upvotes: 0

Related Questions