taskGNU Astronomy Utilities - Tasks: task #15578, Function to find if polygon...

 
 

You are not allowed to post comments on this tracker with your current authentication level.

task #15578: Function to find if polygon vertices are sorted anti-clockwise

Submitter:  Mohammad Akhlaghi <makhlaghi>
Submitted:  Sat 21 Mar 2020 09:02:30 PM UTC
   
 
Should Start On:  Sat 21 Mar 2020 12:00:00 AM UTC Should be Finished on:  Sat 21 Mar 2020 12:00:00 AM UTC
Category:  Libraries Priority:  5 - Normal
Item Group:  Enhancement Status:  None
Privacy:  Public Assigned to:  sks_15
Percent Complete:  100% Open/Closed:  Closed
Effort:  0.00

Jump to the original submission

Sun 29 Mar 2020 04:21:56 PM UTC, comment #22: 

Thanks Sachin, it has been merged into the master branch and pushed to the main repository.

I also used them implemented in the Crop program and it now works much more reasonable, that has also been pushed. In that commit, I also polished the functions and the documentation a little ;-).

I am marking this task as complete :-D.

Mohammad Akhlaghi <makhlaghi>
Group administrator
Sun 29 Mar 2020 05:04:13 AM UTC, comment #21: 

The code is pushed here. Please have a look:-)

Sachin Kumar Singh <sks_15>
Sun 29 Mar 2020 02:05:12 AM UTC, comment #20: 

Everything looks nice! Your tests were also very good :-).

You can rebase now ;-). Ignore the part in the `crop' program and also all changes in `tests/during-dev.sh'.

Just one small thing in the documentation for `gal_polygon_to_counterclockwise': it didn't have an `@end deftypefun', and in the last sentence, there was a `code{0}' (which should be `@code{0}'). You should have seen these errors when building your branch, please correct such errors also.

Mohammad Akhlaghi <makhlaghi>
Group administrator
Sat 28 Mar 2020 10:47:54 PM UTC, comment #19: 

All the requirements are done and the code is pushed here. Documentation for the `gal_polygon_to_counterclokwise` is added and the bugs regarding size_t are fixed. Names are changes in `is` functions. See the test cases in `tests/during-dev.sh`.

Sachin Kumar Singh <sks_15>
Sat 28 Mar 2020 08:53:09 PM UTC, comment #18: 

Thanks, this explains it ;-).

I agree! We can mention in the documentation of `gal_polygon_iscounterclockwise' that it currently doesn't differentiate between a complex and simple polygon, and will just return the orientation that occurs the most (by area). In fact, now that I think more about it, it is reasonable.

We should later implement the Shamos-Hoey Algorithm and maybe call it `gal_polygon_issimple'.

By the way, it would be better if you rename all the `_is' functions with the `is' part separated, for example `gal_polygon_is_counterclockwise' and `gal_polygon_is_simple'.

In summary, I agree with your suggestion ;-). For now, we won't check for simple/complex, we'll just focus on the orientation (which is incidentally also the title of this task).

You'll just need to make a change to the `gal_polygon_is_counterclockwise' remove the case that returns a `GAL_POLYGON_ORIENTATION_COMPLEX' value, and mention (in the documentation) that when the weight of the orientations is equal, it will just return a counter-clockwise code. Infact, now it doesn't need any macros any more, the return value is just `1' if its counter-clockwise and 0 if its clockwise.

So can you just check some polygons that are given fully in counter-clockwise (and keep the checks in `tests/during-dev.sh'), implement these corrections and commit it so I try it out ;-)?

Mohammad Akhlaghi <makhlaghi>
Group administrator
Sat 28 Mar 2020 08:05:29 PM UTC, comment #17: 

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). 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, 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?

Sachin Kumar Singh <sks_15>
Sat 28 Mar 2020 06:01:59 PM UTC, comment #16: 

I mistakenly posted the comment in task #13658 (comment 31). Please see it there and reply here ;-).

Mohammad Akhlaghi <makhlaghi>
Group administrator
Sat 28 Mar 2020 04:39:03 PM UTC, comment #15: 

Here is the region file containing the vertices of the polygon.

(file #48693)

Sachin Kumar Singh <sks_15>
Sat 28 Mar 2020 04:38:00 PM UTC, comment #14: 

Added debugging procedures is inserted and the previous requirements are done here. Documentation will be pushed in(probably) next commit when everything works fine. 

One nagging problem I encountered is when `i` in `gal_polygon_to_counterclockwise` is declared as unsigned long(or size_t) it prints -ve values and causes segmentation faults but such problems do not arise when using long. How to overcome it?

Sachin Kumar Singh <sks_15>
Thu 26 Mar 2020 06:46:59 PM UTC, comment #13: 

Some small points:

  • I see that the returned type of the declaration of `gal_polygon_to_counterclockwise' is still `void', but it has been fixed in the definition. Do you try compiling these? There should have been a compilation warning. Note that in Gnuastro, we aim to have no compilation warnings ;-).


  • To help in readability (this is just stylistic), I usually write these statements like below (so the `sum' conditions are right under each other and more clear to the eye.



  if      (sum <0) return GAL_POLYGON_ORIENTATION_CCW;
  else if (sum==0) return GAL_POLYGON_ORIENTATION_COMPLEX;
  else             return GAL_POLYGON_ORIENTATION_CW;


But even a cleaner implementation would be like this, avoiding all the dirty `if's and `else's and `returns':


  return ( sum
           ? ( sum < 0
               ? GAL_POLYGON_ORIENTATION_CCW
               : GAL_POLYGON_ORIENTATION_CW )
           : GAL_POLYGON_ORIENTATION_COMPLEX );


  • Given that the natural sign of `sum' is negative when the orientation is counter-clockwise, it may be better and more clear if the values of `GAL_POLYGON_ORIENTATION_CCW' and `GAL_POLYGON_ORIENTATION_CW' are interchanged so they are natural.


After these changes, I think it is good enough for testing. Please correct the documentation.

Then add a test usage of these library functions in the Crop program (just before the line `if(crp->p->polygonnosort)' in `polygonmask' of `onecrop.c'): with a few checking `printf's after it, followed by an `exit 0;'.

Then please add a few example calls to the `--polygon' option in `tests/during-dev.sh' and commit/push it so I can also try them easily.

The basic idea is that the newly added `polygonnosort' option should be reversed (replaced): we should be able to automatically see if the given polygon is sorted or not. If it is, we won't change/touch it. If it isn't we'll sort it. But the user can manually request a sorting with a new `--polygonsort' option, in which case, we won't do any sorting checks at all, and will directly call the `gal_polygon_ordered_corners'.

Mohammad Akhlaghi <makhlaghi>
Group administrator
Thu 26 Mar 2020 06:12:18 PM UTC, comment #12: 

The required changes are made and pushed here. The document is not changed yet.

About comment #7, yes, I'd seen that wiki page prior to the elements 84's article. The orientation matrix as shown in the wiki is just twice the matrix used in calculating the area of a polygon by the shoelace formula. And indeed this is what the 84's article was all about, checking the area of the polygon to find the orientation. Hence both these are fundamentally similar.

Sachin Kumar Singh <sks_15>
Wed 25 Mar 2020 11:43:03 PM UTC, comment #11: 

Some points:

  • It is better if `gal_polygon_iscounterclockwise' returns 0 when the polygon is complex/intersecting. The reason is this: in a simple `if' statement, both the values of `-1' and `1' are true (they aren't zero), but zero means false. So it would really help in the later usage of this function if the return value is 0 when we have the worst scenario (intersecting). For example this scenario:



if( gal_polygon_iscounterclockwise(polygon, num) )
  { .... operation if sorted ... }
else
  error(EXIT_FAILURE, 0, "polygon not sorted")


  • Define macros for the values, so users don't have to memorize the return values and the code becomes more cleaner to read. For example: `GAL_POLYGON_ORIENTATION_CCW', `GAL_POLYGON_ORIENTATION_CW' and ``GAL_POLYGON_ORIENTATION_COMPLEX'.


  • You didn't say anything about that Wikipedia article I cited in Comment #7. Please let me know what you think about it?


  • In `gal_polygon_to_counterclockwise', I see that you have called `gal_polygon_iscounterclockwise' several times! This is very bad practice! A function should only be called once. A much more elegant solution is to use a `switch' statement like this:



orientation=gal_polygon_iscounterclockwise(polygon, num)
switch(orientation)
 {
 case GAL_POLYGON_ORIENTATION_CCW:
   ...;
   break;
 case GAL_POLYGON_ORIENTATION_CW:
   ...;
   break;
 case GAL_POLYGON_ORIENTATION_COMPLEX:
   ...;
   break;
 default:
   error(EXIT_FAILURE, 0, "%s: a bug! Please contact us at %s"
         "polygon orientation code %d not recognized",
         __func__, PACKAGE_BUGREPORT, orientation);
 }


  • Begin the comments in the code with a "Capital" letter ;-)! It should be standard English where sentences start with a capital letter ;-).


  • The return value of `gal_polygon_to_counterclockwise' should also be an integer: `1' if it succeeds and `0' if it doesn't. This way, a user of the library will be able to deal with intersecting polygons in their own way with a simple `if' statement like before.
Mohammad Akhlaghi <makhlaghi>
Group administrator
Wed 25 Mar 2020 08:01:58 PM UTC, comment #10: 

I've added the 'gal_polygon_to_counterclockwise' in polygon.c. Required changes were also done on 'gal_polygon_iscounterclockwise', but the documentation for neither of those is updated. I'll do so after the review and testing. I've tested the individual parts of the function separately but wasn't able to test it on the whole. I've provided comments showing the working of the individual parts of code.

Please check the new commit here. I'll rebase it after all changes are done.

Sachin Kumar Singh <sks_15>
Wed 25 Mar 2020 05:35:40 PM UTC, comment #9: 

Yes, this is the correct way to put an array into a `gal_data_t' container. Just note that you aren't converting (copying the data into another allocated space) when you use this method.

Also, you don't need any special value to `minmapsize' because the first argument is not NULL: its an already allocated array (`v'). `minmapsize' is only relevant when you want this function to allocate memory. As a place-holder you can just give it `-1' (largest `size_t' value).

Just note that the `ndim' argument of `gal_data_t' is the number of dimensions, not the number of elements. So in this context, `ndim' should be `1'. The number of elements (along each dimension) is set through the `dsize' array (which you have set to NULL in the example!). Since the number of elements is already in `n' and the dataset is one-dimensional (only needing a one-elemnent array), you can simply give it a value of `&n'.

Just don't forget that when you define the permutation, keep the X and Y value of each point to be touching.

After the permutation is done, nothing changes (`v' will still point to your permuted array). But before freeing the `temp' with `gal_data_free', be sure to set `temp->array=NULL', otherwise the allocated space will be freed.

Mohammad Akhlaghi <makhlaghi>
Group administrator
Wed 25 Mar 2020 02:22:41 PM UTC, comment #8: 

If I need to use `gal_permutation_apply`, I need to use `gal_data_t` as input. Should I use

temp=gal_data_alloc(v,  GAL_TYPE_FLOAT64, n, NULL, NULL, 0, minmapsize, 0, NULL, NULL, NULL);

to make `temp` a temporary store the vertices `v` to be reversed. What should be the value of minmapsize and is this the correct way to convert `double*` to `gal_data_t*`? I plan to make a `permutation` array having the reverse indexes than the clockwise vertices and then using `gal_permutation_apply(temp, n)` to reverse that order.

I also thought of swapping the vertices using a swap function but it seems to be an overkill given that the permutation feature already exists.

Sachin Kumar Singh <sks_15>
Tue 24 Mar 2020 10:55:05 PM UTC, comment #7: 

I was just looking a little close into it and came up with the Curve orientation wikipedia page. Had you looked into it? Its solution also seems to be nice (and possibly more generic?).

Thinking in terms of usefulness, you can also add another function like `gal_polygon_to_counterclockwise'.

This higher-level function would call `gal_polygon_iscounterclockwise'. If the given polygon is already counter clockwise, it won't do anything, but if its clockwise, it will permute its elements to be counter clockwise (you can use gnuastro's permutation library for this if you like).

By the way, I also noticed that in the book, the name of the function wasn't updated ;-).

I think you have a good point: if `gal_polygon_iscounterclockwise' can define a crossing of the polygon edges, we can give it a third output integer to use as an indicator that the polygon edges aren't sorted: we want simple polygons after all ;-). For example `1' can be for a CCW orientation, `-1' for a CW orientation and `0' for a crossing of edges (as a sign that its not sorted). What do you think?

Mohammad Akhlaghi <makhlaghi>
Group administrator
Tue 24 Mar 2020 08:02:20 AM UTC, comment #6: 

I think for non-convex polygons this should do as, for example, if the figure is intersecting this might lead to +ve value or 0 (as the case you suggested). But still, I need to find any edge cases.

The code is rebased and pushed here.

As for the URL for the reference page, it belongs to a third party website (element 84)(Is it okay?). I've put it in commas as it isn't possible to wrap it in 79 columns.

Sachin Kumar Singh <sks_15>
Tue 24 Mar 2020 12:02:52 AM UTC, comment #5: 

It would also be good if you add the URL of that reference page to the comments of the function, it can help people understand/debug/expand it better ;-).

Mohammad Akhlaghi <makhlaghi>
Group administrator
Tue 24 Mar 2020 12:00:30 AM UTC, comment #4: 

Thanks a lot Sachin, this is a very clean commit and I enjoyed reading the `git log -1 -p' :-).

But as I read more into it I recognized that this is only one part of this task's aim: finding if the ordered set of points are clock-wise or counter clock-wise.

Before that, we should make sure if the polygon is indeed ordered or not. For example say I have the simple polygon of (0,0), (0,1), (1,1) and (1,0) which is ordered counter-clockwise. But what if the user gives the points like this: (0,0), (1,1), (1,0) and (0,1). We need a function to see if the given set of points is already sorted or not (to possibly pass onto the sorting algorithm and avoid sorting if its not necessary (especially since there isn't a unique sort for concave polygons).

However, this function (and its nice documentation!) is part of the job and is ready. So I can merge it, but it would just be good if you correct its name to something like `gal_polygon_iscounterclockwise': it can return 1 if the ordered set has a counterclockwise direction and 0 if it is clockwise. What do you think? If you agree, make the corrections and I'll merge this part for now.

Mohammad Akhlaghi <makhlaghi>
Group administrator
Mon 23 Mar 2020 12:38:25 PM UTC, comment #3: 

The function for the same is pushed in the `task-is-sorted' branch here. Documentation for the same is also added. Please test it and review.

Sachin Kumar Singh <sks_15>
Sun 22 Mar 2020 08:02:06 PM UTC, comment #2: 

That webpage has such a complete explanation! It seems promising, try it out and if it works, add it as a new function in the `polygon' libraries, maybe called `gal_polygon_issorted'?

Mohammad Akhlaghi <makhlaghi>
Group administrator
Sun 22 Mar 2020 05:49:27 PM UTC, comment #1: 

The winding number method seems to be a good fit for this and is also easy to implement. This should do it:-)

Sachin Kumar Singh <sks_15>
Sat 21 Mar 2020 09:02:30 PM UTC, original submission:  

When dealing with polygons it can be useful to know if the input set of vertices are sorted counter-clockwise or not. This is particularly the case for concave polygons where there is no unique sorting (see the discussion in task #13658).

So a simple function to do this check can be very useful (maybe called `gal_polygon_issorted'): if the given set of vertices are already sorted anti-clockwise, it should return 1, and if not, it should return 0.

With such a function, in Crop, we can decide if the given polygon vertices should be sorted or not (and avoid confusing results when the polygon is concave).

Mohammad Akhlaghi <makhlaghi>
Group administrator

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attached Files
file #48693:  ds9.reg added by sks_15 (324B - text/x-ms-regedit)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by sks_15 (Posted a comment)
  • -email is unavailable- added by makhlaghi (Submitted the item)
  • -email is unavailable- added by makhlaghi
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

     

    Follow 7 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2020-03-29 makhlaghi Percent Complete0% 100%
        Assigned toNone sks_15
        Open/ClosedOpen Closed
    2020-03-28 sks_15 Attached File- Added ds9.reg, #48693
    2020-03-24 sks_15 Assigned tosks_15 None
    2020-03-23 sks_15 Assigned toNone sks_15
    2020-03-21 makhlaghi Carbon-Copy- Added -email is unavailable-

    Back to the top

    Powered by Savane 3.13-f8d8.
    Corresponding source code