0

Dear Stackoverflow community,

I have contours of irregular polygons as unordered datapoints (like on the figure here: https://s16.postimg.org/pum4m0pn9/figure_4.png), and I am trying to order them (ie. to create a polygon).

I cannot use the convex hull envelope because of the non convex shape of the polygon. I cannot ase a minimum distance criterion because some points of other parts of the contour lie closer (example: point A has to be joined with B, but is closer to C). I cannot use a clockwise ordering because of the irregular shape of the contour.

Do anyone knos a way to implement (preferentially in Python) an algorithm that would reorder the datapoints from a starting point?

Community
  • 1
  • 1
BBF
  • 1
  • 2
  • The thing is that the order in which you go through your points can define different polygons so that there is no unique solution in general. – Francis Colas Mar 30 '15 at 11:57
  • Have you had a look at the `shapely` module for python? It features a lot of functions for polygons and the like. Maybe you can find your needs already implemented there... https://pypi.python.org/pypi/Shapely – WWhisperer Mar 30 '15 at 12:22
  • Your problem is similar to the "travelling salesman problem". I had solved this problem with "simulated annealing" many years ago. It should be pretty straight forward to implement it. – fang Mar 31 '15 at 06:09
  • look here [finding holes in 2D point set](http://stackoverflow.com/a/21884021/2521214) for some ideas on how to solve this – Spektre Apr 15 '15 at 07:43

1 Answers1

0

look here finding holes in 2D point set for some ideas on how to solve this

  1. I would create point density map (similar to above linked answer)
  2. create list of all lines
    • so add to it all possible combination of lines (between close points)
    • not intersecting empty area in map
  3. remove all intersecting lines
  4. apply closed loop / connectivity analysis on the lines
  5. then handle the rest of unused points
    • by splitting nearest line by them ...
    • map example
    • depending on you map grid size and point density you may need to blend/smooth the map to cover gaps
    • if grid size is too big then you can miss details like on the image between points A,C
    • if it is too small then significant gaps may occur near low density areas

But as said this has more then one solution so you need to tweak this a bit to make the wanted output perhaps some User input for shaking the solution a bit until wanted solution found...

[notes]

you can handle this as more covex polygons ...

  • add line only if winding rule met
  • stop when no more lines found
  • start again with unused points
  • and in the end try to connect found non closed polygons ...
Community
  • 1
  • 1
Spektre
  • 49,595
  • 11
  • 110
  • 380