How to check the coastline polygon is ordered correctly

[sexton]

Setting up ANUGA tsunami models, eg: a coastline polygon is defined that consists of coastline dataset stitched to the outer domain.

We need to ensure that the ordering of points is correct. The attached file shows an example of where points are out of order and the resultant polygon is not ordered propetly, and we are seeing crossovers in the polygon.

We need a check for this to ensure it's correct.

[sexton]

Mandurah coastline + stitched to polygon

[hudson]

NOTE: This is the same bug as #257. We need a fast algorithm to convert complex polygons to concave ones, or raise an exception on complex polygons with an algorithm such as this:

​http://www.lems.brown.edu/~wq/projects/cs252.html

I've already implemeted a brute-force check that has found some pathological data in the unit tests.

[hudson]

This is an intractable problem, in my opinion. I have looked into a couple of different "healing" algorithms, and there is no guarantee that a usable mesh will be produced each time that reflects what the user wanted. As this is is a scientific application, I don't think there is a place for rough heirstics. How do we decide what the threshold is to say that a polygon is "broken"?

I think the best solution is to output a warning for the user to fix the polygon file using their tools.

Comments?

[hudson]

Rev 7690 - exception is raised on a pathological poly. An O(n log n) algorithm is used.

Also, one of the files used for the unit tests, mainland_only.csv, had a bad poly, and this has been fixed by hand.