[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[task #13658] Work on concave polygons too

From: Sachin Kumar Singh
Subject: [task #13658] Work on concave polygons too
Date: Mon, 9 Mar 2020 16:00:45 -0400 (EDT)
User-agent: Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:73.0) Gecko/20100101 Firefox/73.0

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
<> 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 <> 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

(file #48570)

Additional Item Attachment:

File name: geogebra_thumbnail.png         Size:8 KB


Reply to this item at:


  Message sent via Savannah

reply via email to

[Prev in Thread] Current Thread [Next in Thread]