GNU Astronomy Utilities - Tasks: task #13658, Work on concave polygons too
You are not allowed to post comments on this tracker with your current authentication level.
task #13658: Work on concave polygons too
Submitter: | Mohammad Akhlaghi <makhlaghi> | ||
Submitted: | Thu 25 Jun 2015 02:44:12 AM UTC | ||
Should Start On: | Wed 24 Jun 2015 03:00:00 PM UTC | Should be Finished on: | Wed 24 Jun 2015 03:00:00 PM UTC |
Category: | Crop | Priority: | 5 - Normal |
Item Group: | New feature | Status: | Done |
Privacy: | Public | Assigned to: | sks_15 |
Percent Complete: | 100% | Open/Closed: | Closed |
Effort: | 0.00 |
Jump to the original submission
Thu 09 Apr 2020 04:57:33 PM UTC, comment #48: |
Mohammad Akhlaghi <makhlaghi> |
Thu 09 Apr 2020 07:14:11 AM UTC, comment #47: Done here:-) |
Sachin Kumar Singh <sks_15> |
Thu 09 Apr 2020 03:10:12 AM UTC, comment #46: Thanks Sachin. I just made another merge for task #15567, it would be cleaner if you re-base your commit over the updated master branch, then I'll merge it ;-). You can also make the final touches ;-). I won't make any merge or commits to the master branch till I get your commit (if you do it by the end of Thursday) ;-). |
Mohammad Akhlaghi <makhlaghi> |
Wed 08 Apr 2020 07:16:47 PM UTC, comment #45: Done here. Also, sorry I forgot about the usage of conditional operators for if else in compare functions before rebasing and pushing. But probably you will be doing some more changes in a new commit and hence I didn't rebase again. Can you please fix them when you do the final changes? Thank you;-) |
Sachin Kumar Singh <sks_15> |
Wed 08 Apr 2020 02:01:40 PM UTC, comment #44: Great! Thanks Sachin. A few small points remain, I look forward to merging it afterwards:
|
Mohammad Akhlaghi <makhlaghi> |
Wed 08 Apr 2020 12:22:56 PM UTC, comment #43: All done:-) Documentation is done and rebased here. One minor point, when I tried to declare `struct point p` in polyon_leftmost_point` and used p={..}, there was the error that an expression has to be provided(it came in the beginning and that's why I declared it in the middle to start with). Hence I haven't change it. Other than that it's all good:-) |
Sachin Kumar Singh <sks_15> |
Tue 07 Apr 2020 10:15:46 PM UTC, comment #42: One more minor stylistic point:
|
Mohammad Akhlaghi <makhlaghi> |
Tue 07 Apr 2020 09:56:56 PM UTC, comment #41: Great! Thanks a lot Sachin, you have the green flag :-). Just some minor points are listed below to hopefully implement with the rebase:
|
Mohammad Akhlaghi <makhlaghi> |
Mon 06 Apr 2020 10:37:24 PM UTC, comment #40: All things are done according to the requirements. Also the `gal_polygon_sort_vertex` function, until now, returned the array of output points rather than indexes(as ordinds). The latest commit fixes that and puts point structure in polygon.c.(I also toyed with the idea of a map to sort, but it turned out to be rather redundant and overkilling so was dropped altogether).
|
Sachin Kumar Singh <sks_15> |
Sun 05 Apr 2020 09:08:54 PM UTC, comment #39: Thanks Sachin, it generally looks good, can you please rebase it so I can implement it in the Crop program, and close this task?
|
Mohammad Akhlaghi <makhlaghi> |
Sat 04 Apr 2020 04:56:58 AM UTC, comment #38: Yes, I did get this error and proposed for the same solutions in comment #36 which is now fixed here. Also can you please push all the recent changes of savannah master in GitHub master branch too. It helps in maintaining consistency. |
Sachin Kumar Singh <sks_15> |
Sat 04 Apr 2020 03:20:20 AM UTC, comment #37: I tried the build, but it crashed when building `onecrop.c':
|
Mohammad Akhlaghi <makhlaghi> |
Thu 02 Apr 2020 12:43:37 PM UTC, comment #36: I'll remove whitespaces in the next commit.
|
Sachin Kumar Singh <sks_15> |
Thu 02 Apr 2020 10:13:41 AM UTC, comment #35: The functions for concave sort are merged into polygon library and pushed here. Documentation and rebasing will be done before the final push and review. Also, can you please push changes on savannah on GitHub master branch too. It helps to keep track of the number of commits and promotes uniformity:-) |
Sachin Kumar Singh <sks_15> |
Sun 29 Mar 2020 07:31:21 PM UTC, comment #34: I think so! We have all the other necessary components in place now to use it in Crop.
|
Mohammad Akhlaghi <makhlaghi> |
Sun 29 Mar 2020 07:18:40 PM UTC, comment #33: Is my sorting algorithm for concave polygons ontask-concave-sortready to be used? |
Sachin Kumar Singh <sks_15> |
Sat 28 Mar 2020 06:00:38 PM UTC, comment #32: Previous comment was actually for task #15578, I mistakenly wrote it here! Please reply to it there ;-) |
Mohammad Akhlaghi <makhlaghi> |
Sat 28 Mar 2020 05:40:47 PM UTC, comment #31: I was able to reproduce the problem with the segmentation fault when setting `i' to `size_t'. The problem is in the conditional `i>=0': `size_t' (which is actually `unsigned long') will always be positive, so this test will always pass and it will just read into un-allocated memory until it crashes!
|
Mohammad Akhlaghi <makhlaghi> |
Sat 21 Mar 2020 10:12:24 PM UTC, comment #30: It has been merged with the master branch and pushed to them main repository :-).
|
Mohammad Akhlaghi <makhlaghi> |
Sat 21 Mar 2020 10:52:10 AM UTC, comment #29: The requirements are done and the code is rebased and pushed here. Also, as this task fixes bug #50120 and core implementation of task #14639, can I use them in my proposal:-) |
Sachin Kumar Singh <sks_15> |
Thu 19 Mar 2020 01:31:06 PM UTC, comment #28: I just noticed that you haven't actually used your new `gal_polygon_isconvex' function. If you like, you can use it inside of the `polygonmask' of `onecrop.c' and determine the function to use for finding if a given pixel is within the polygon or not.
|
Mohammad Akhlaghi <makhlaghi> |
Thu 19 Mar 2020 10:25:01 AM UTC, comment #27: I've pushed the code here. I noted that one change in onecrop.c is taking more than 79 columns. If all is okay with other changes I will fix this and rebase and push again. Please review.
|
Sachin Kumar Singh <sks_15> |
Wed 18 Mar 2020 09:42:41 PM UTC, comment #26: I read the paper about the internal algorithm used in astronomy.net. I understood the algorithm and the required thresholds. I realised how this was related to the non-linear warping task. This is a rough summary:
|
Sachin Kumar Singh <sks_15> |
Wed 18 Mar 2020 03:31:04 PM UTC, comment #25: Great! I am happy the problem is solved :-).
|
Mohammad Akhlaghi <makhlaghi> |
Wed 18 Mar 2020 01:08:34 PM UTC, comment #24: The code is fixed and tested now. I've also added the documentation for the book. Review it and confirm so that I can rebase the commits.
|
Sachin Kumar Singh <sks_15> |
Wed 18 Mar 2020 11:11:48 AM UTC, comment #23: Great! I am happy you found the solution ;-).
|
Mohammad Akhlaghi <makhlaghi> |
Wed 18 Mar 2020 07:16:23 AM UTC, comment #22: Also, I contacted `assign@gnu.org` again today. I also send a mail to `copyright-clerk@fsf.org` a few days back but haven't got a reply yet. |
Sachin Kumar Singh <sks_15> |
Wed 18 Mar 2020 07:06:04 AM UTC, comment #21: Two new functions are added in `polygon.c' and pushed to `task-is-in-polygon' branch :
|
Sachin Kumar Singh <sks_15> |
Wed 18 Mar 2020 02:04:47 AM UTC, comment #20: Thanks for the debug! I think we are getting close.
|
Mohammad Akhlaghi <makhlaghi> |
Tue 17 Mar 2020 04:05:56 PM UTC, comment #19: For the function to find if the polygon is convex or concave, we can simply:
|
Sachin Kumar Singh <sks_15> |
Tue 17 Mar 2020 03:23:14 PM UTC, comment #18: When I put
inside the `POLYGON_MASK' macro in onecrop.c inside its `if' statement, after the first 10 correct vertices(in shifted coordinates), it outputs a lot of (0.000, 0.000) after the last correct point ((68.956700, 408.959500) in this case).When I draw the polygon the bend is there due to this (0, 0) coordinate. I think it's a garbage valve. If I try to prevent it using `if' statement, it shows a segmentation fault. How to prevent it? |
Sachin Kumar Singh <sks_15> |
Tue 17 Mar 2020 02:00:29 PM UTC, comment #17: Probably the best way to debug this problem is to actually use it in the Crop program like I described ;-). Once you do that, you'll see that we don't actually do any polygon clipping (which is in the vector-space).
|
Mohammad Akhlaghi <makhlaghi> |
Tue 17 Mar 2020 12:45:07 PM UTC, comment #16: I've tried many points around the problematic region in my `gal_concavesort_isinside_polygon' but there doesn't seem to be any problem at all. But when reproducing the steps I see that the erroneous region still appears. I even applied a rounding error constant as used in `polygon.c`, but the error still persists. I tried a few other points and then there seemed a pattern.
|
Sachin Kumar Singh <sks_15> |
Mon 16 Mar 2020 02:26:39 AM UTC, comment #15: Great! To keep things simple, let's focus on the point-in-polygon part (your `gal_concavesort_isinside_polygon' function). I tried it by copying this function (and its `GAL_CONCAVESORT_TRI_CROSS_PRODUCT' macro) in `lib/polygon.c'.
|
Mohammad Akhlaghi <makhlaghi> |
Sun 15 Mar 2020 06:35:42 PM UTC, comment #14: I've added a new function inside the concavesort.c which uses winding number algorithm to identify points inside a non-convex polygon.
|
Sachin Kumar Singh <sks_15> |
Sun 15 Mar 2020 02:35:26 AM UTC, comment #13: After the last post, and based on the taught that there is possibly no unique concave polygon from a set of points. So I thought it is probably necessary to add an option to avoid sorting and let the program use the same order that the user provided.
|
Mohammad Akhlaghi <makhlaghi> |
Sun 15 Mar 2020 12:50:29 AM UTC, comment #12: Thanks Sachin, the code is very well formatted now and it also prints the final output properly :-).
|
Mohammad Akhlaghi <makhlaghi> |
Sat 14 Mar 2020 09:57:02 PM UTC, comment #11: All bugs related to concave sort are fixed. I've tested it with more inputs and it shows good results. I've pushed the code to my `task_concave_sort` branch.
|
Sachin Kumar Singh <sks_15> |
Sat 14 Mar 2020 05:40:32 PM UTC, comment #10: Thanks a lot Sachin. I just tried it without any change (with the command below), but got all zeros as output:
|
Mohammad Akhlaghi <makhlaghi> |
Thu 12 Mar 2020 09:35:24 PM UTC, comment #9: The program to sort the concave polygons is ready. It is still a crude code to be modified when importing to the library.
|
Sachin Kumar Singh <sks_15> |
Tue 10 Mar 2020 02:10:58 AM UTC, comment #8: That was a great review of some of the existing algorithms, I enjoyed reading it ;-). I am sure you'll find/implement the best solutions and we'll test it in many real-world scenarios :-).
|
Mohammad Akhlaghi <makhlaghi> |
Mon 09 Mar 2020 08:12:32 PM UTC, comment #7: Also, I think this is the time around which I should start working on my proposal for GSoC. I think this task and task #14639 and bug #50120 are interconnected and solving this will very much solve the others too and hence should be included for the task for summers.
|
Sachin Kumar Singh <sks_15> |
Mon 09 Mar 2020 08:00:45 PM UTC, comment #6: 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.
|
Sachin Kumar Singh <sks_15> |
Sat 07 Mar 2020 03:09:06 AM UTC, comment #5: Indeed, we have to find a robust centroid. Maybe the centroid can be chosen from a set of points within the vertices themselve? Generally, this is a good implementation issue which is easier to answer as you test various implementations. So please try different scenarios and see how successful it is with various sets of points.
|
Mohammad Akhlaghi <makhlaghi> |
Fri 06 Mar 2020 03:12:14 PM UTC, comment #4: What if the centroid lies outside the polygon? Will this method will still be valid? If not, I think we can sort the points using polar coordinates and their distance from a fixed point(which can be the point which is the lowermost and rightmost, for example). But I'm not sure about the feasibility of this method. A bit more discussion is required:-)
|
Sachin Kumar Singh <sks_15> |
Thu 05 Mar 2020 11:16:32 PM UTC, comment #3: This seems to be a promising idea! It is an important problem in several astronomical scenarios, not just the Crop program (as mentioned in the first post). I have always been wanting to do this, but never found the time.
|
Mohammad Akhlaghi <makhlaghi> |
Thu 05 Mar 2020 10:42:17 PM UTC, comment #2: I have an idea to sort a concave hull based on their centroid. This answer (https://gamedev.stackexchange.com/a/13232) seems to work. What other things do I need to consider before proceeding? What other problems might arise?
|
Sachin Kumar Singh <sks_15> |
Sun 22 Jan 2017 04:50:51 PM UTC, comment #1: Also see, bug #50120 (Print an error when polygon is concave). |
Mohammad Akhlaghi <makhlaghi> |
Thu 25 Jun 2015 02:44:12 AM UTC, original submission:
Currently the function to sort the vertices of the polygon (orderedpolygoncorners in lib/polygon.c) only works on convex polygons. Because it was originally designed for ImageWarp where we won't be dealing with concave polygons.
|
Mohammad Akhlaghi <makhlaghi> |
Depends on the following items: None found
Items that depend on this one: None found
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 11 latest changes.
Date | Changed by | Updated Field | Previous Value | => | Replaced by |
---|---|---|---|---|---|
2020-04-09 | makhlaghi | Status | Postponed | Done | |
Percent Complete | 70% | 100% | |||
Open/Closed | Open | Closed | |||
2020-03-21 | makhlaghi | Percent Complete | 0% | 70% | |
Assigned to | None | sks_15 | |||
2020-03-17 | sks_15 | Attached File | - | Added Figure_1.png, #48614 | |
2020-03-17 | sks_15 | Attached File | - | Added Screenshot@from@2020-03-16@23-08-03.png, #48612 | |
Attached File | - | Added Screenshot@from@2020-03-17@00-07-19.png, #48613 | |||
2020-03-16 | makhlaghi | Attached File | - | Added point-in-polygon-comment15.png, #48599 | |
2020-03-12 | sks_15 | Attached File | - | Added test.c, #48589 | |
2020-03-09 | sks_15 | Attached File | - | Added geogebra_thumbnail.png, #48570 |
Powered by Savane 3.13-4448.
Corresponding source code
Thanks a lot Sachin, it has been merged and pushed to the main branch :-D.
Just some tips for the future (which I have implemented in the next commit):