gnuastro-devel
[Top][All Lists]
Advanced

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

[task #15578] Function to find if polygon vertices are sorted anti-clock


From: Sachin Kumar Singh
Subject: [task #15578] Function to find if polygon vertices are sorted anti-clockwise
Date: Sat, 28 Mar 2020 16:05:29 -0400 (EDT)
User-agent: Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:73.0) Gecko/20100101 Firefox/73.0

Follow-up Comment #17, task #15578 (project gnuastro):

It seems that the algorithm won't work for intersecting polygons. At most it
may tell when it is mostly clockwise(see last and second last paragraphs here
<https://en.wikipedia.org/wiki/Curve_orientation#Practical_considerations>).
Also, it suggests no such algorithm is possible for intersecting polygon due
to its characteristics. 

But I searched a bit and found that an algorithm, Shamos-Hoey Algorithm
<http://geomalgorithms.com/a09-_intersect-3.html>, exists but it is so very
different from the existing one. It used priority queues and AVL trees. Though
it is robust and fast, it may take a while to implement. Should we just allow
only the counterclockwise direction to be present and ask the user to check
the vertices to find if a non-intersecting polygon is present until the
algorithm is implemented? What do you think?

    _______________________________________________________

Reply to this item at:

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

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




reply via email to

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