[task #13658] Work on concave polygons too

[Sachin Kumar Singh]

Follow-up Comment #6, task #13658 (project gnuastro):

After a little bit of research, I found that to uniquely sort the concave
polygon we need more than just a set of points as discussed in this
<https://scicomp.stackexchange.com/a/31076/33495> answer. The polar sort
method using centroid discussed earlier is bound to fail in many cases.

If we want the polygon to be constructed using the outermost set of points, we
can use this <https://gamedev.stackexchange.com/a/24589> variation of the gift
wrapping algorithm. I think this algorithm will do as it uses lines(or
splines?) and angles for its sort.

Also, I've had an idea of my own for the sort using polar sort and distances
from a reference point, which will be the point(for anti-clockwise sort) the
leftmost(min x-coordinate) and lowermost(min y-coordinate). Now we can sort
the points using `atan2`(or just use the polar angle and distance for sorting)
and for similar polar angels, the one which is farthest away from it is placed
first in the sorted array. This works in O(n) time. This image shows an
example. This may not be the best edge case but it is minimal to understand
the algorithm. The point O is the reference point. The angle between the
reference point and line parallel to x-axis passing through the reference
point is the polar angle here. 

But first I need to know if there is a criterion for the particular polygon
(like it will need to cover particular areas in the file or not or any such
case). 

(file #48570)
    _______________________________________________________

Additional Item Attachment:

File name: geogebra_thumbnail.png         Size:8 KB
    <https://savannah.gnu.org/file/geogebra_thumbnail.png?file_id=48570>



    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/task/?13658>

_______________________________________________
  Message sent via Savannah
  https://savannah.gnu.org/