[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/
- [task #15578] Function to find if polygon vertices are sorted anti-clockwise, (continued)
- [task #15578] Function to find if polygon vertices are sorted anti-clockwise, Mohammad Akhlaghi, 2020/03/23
- [task #15578] Function to find if polygon vertices are sorted anti-clockwise, Sachin Kumar Singh, 2020/03/24
- Message not available
- [task #15578] Function to find if polygon vertices are sorted anti-clockwise, Sachin Kumar Singh, 2020/03/25
- [task #15578] Function to find if polygon vertices are sorted anti-clockwise, Mohammad Akhlaghi, 2020/03/25
- [task #15578] Function to find if polygon vertices are sorted anti-clockwise, Sachin Kumar Singh, 2020/03/25
- Message not available
- [task #15578] Function to find if polygon vertices are sorted anti-clockwise, Sachin Kumar Singh, 2020/03/26
- [task #15578] Function to find if polygon vertices are sorted anti-clockwise, Mohammad Akhlaghi, 2020/03/26
- [task #15578] Function to find if polygon vertices are sorted anti-clockwise, Sachin Kumar Singh, 2020/03/28
- [task #15578] Function to find if polygon vertices are sorted anti-clockwise, Sachin Kumar Singh, 2020/03/28
- [task #15578] Function to find if polygon vertices are sorted anti-clockwise, Mohammad Akhlaghi, 2020/03/28
- [task #15578] Function to find if polygon vertices are sorted anti-clockwise,
Sachin Kumar Singh <=
- [task #15578] Function to find if polygon vertices are sorted anti-clockwise, Mohammad Akhlaghi, 2020/03/28
- [task #15578] Function to find if polygon vertices are sorted anti-clockwise, Sachin Kumar Singh, 2020/03/28
- [task #15578] Function to find if polygon vertices are sorted anti-clockwise, Mohammad Akhlaghi, 2020/03/28
- [task #15578] Function to find if polygon vertices are sorted anti-clockwise, Sachin Kumar Singh, 2020/03/29
- [task #15578] Function to find if polygon vertices are sorted anti-clockwise, Mohammad Akhlaghi, 2020/03/29