Question

build polygon from point


Badge +3

we need to build polygon, from points, the only problem is the user could enter them not in the right order, is there a way we could build it without intersecting the lines and without woring about the points order ?

Thanks


11 replies

Userlevel 4

If the points describe fairly simple polygons, you could try using the HullReplacer with a Group By on the polygon ID.

Userlevel 4
Badge +25

I agree with @david_r's suggestion (but would like to add that it does require there to be an attribute available on the points that you can use to identify the polygons).

If you don't have that and the polygons are clearly separate from eachother you could buffer all the points and dissolve the buffers to generate those polygon identifiers.

Userlevel 4

I agree with @david_r's suggestion (but would like to add that it does require there to be an attribute available on the points that you can use to identify the polygons).

If you don't have that and the polygons are clearly separate from eachother you could buffer all the points and dissolve the buffers to generate those polygon identifiers.

Great suggestion. The NeighborhoodAggregator might also be helpful for that last bit.

 

 

Badge +3

its work well for 4 points, but for 5 and more still give the same shape as it is for 4 points

take a look at the ws for reference

buildpolygone-from-points.fmwt

Badge +3
@david_r

yes all the polygon will have an id to identify the related point, my question if we have to do this only for one poly and represented by multiple points how to build the polygon without intersecting the lines

Userlevel 4

You don't need to create the lines. Try just the VertexCreator followed by an Aggregator with a Group By on the polygon ID. The finally the HullReplacer.

On the other hand, in your sample Excel sheet there's a "point" attribute that seems to give an incrementing id. Is that the case in your "real" data as well?

Badge +3

You can't, at least not easily..

Only if the polygons are simple can you create a order in any set.

That said,

you can try to create all the lines, Cartesian product.

Then remove all the crossing lines (spatial relator).

Crete a hull. Create a topology. Neighbor finder to match the topology points with the input vertices to transfer the order. Might end up with ordered points.

Works for less simple polygons too.

What the level of complexity would be where it won't work, I guess you would have to test.

Userlevel 2
Badge +16

Hi @boubcher, the shortest path that passes through all the points (the last point is nearly equal to the first point) might be a not-self-intersected polygon boundary. It's the "Travelling salesman problem" and the current ShortestPathFinder supports optimization options to solve the problem.

See the attached experimental workspace: build-points-from-points.fmw (FME 2017.1.2.1)

A result from 20 points:

A result from 50 points:

Userlevel 4

Hi @boubcher, the shortest path that passes through all the points (the last point is nearly equal to the first point) might be a not-self-intersected polygon boundary. It's the "Travelling salesman problem" and the current ShortestPathFinder supports optimization options to solve the problem.

See the attached experimental workspace: build-points-from-points.fmw (FME 2017.1.2.1)

A result from 20 points:

A result from 50 points:

That's a really interesting way to do it and the results look good if there aren't too many points per polygon. It seems that for larger point sets the risk of self-intersections increase, for 100 points I got this:

 

 

 

I would suspect that the results would be (much) better for point sets that visually resemble a polygon rather than some random blob, however.

 

 

For comparison, here's the HullReplacer (using an automatic alpha-value) for the same input points:

 

 

Not perfect either, in the end it will depend on the actual data and the requirements of the client.

 

Userlevel 2
Badge +16
That's a really interesting way to do it and the results look good if there aren't too many points per polygon. It seems that for larger point sets the risk of self-intersections increase, for 100 points I got this:

 

 

 

I would suspect that the results would be (much) better for point sets that visually resemble a polygon rather than some random blob, however.

 

 

For comparison, here's the HullReplacer (using an automatic alpha-value) for the same input points:

 

 

Not perfect either, in the end it will depend on the actual data and the requirements of the client.

 

Yes, you are right. It's a kind of NP-hard problem, so the ShortestPathFinder has some parameters to limit the processing time, and generates an approximate solution (not the true optimal solution) within a reasonable time duration. I expect it could generate a better polygon if you set larger number to the some optimization parameters, even though the number of points was 100.

 

I think it requires trial and error in the actual data conditions to find optimal parameters. That's the reason why I said "experimental" ;-)

 

 

Userlevel 4
Yes, you are right. It's a kind of NP-hard problem, so the ShortestPathFinder has some parameters to limit the processing time, and generates an approximate solution (not the true optimal solution) within a reasonable time duration. I expect it could generate a better polygon if you set larger number to the some optimization parameters, even though the number of points was 100.

 

I think it requires trial and error in the actual data conditions to find optimal parameters. That's the reason why I said "experimental" ;-)

 

 

I agree completely. I'd even classify the HullReplacer as "experimental" for this type of non-trivial problem...

Reply