Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Point in Face #905

Open
aaronzedwick opened this issue Aug 27, 2024 · 12 comments · May be fixed by #1056
Open

Point in Face #905

aaronzedwick opened this issue Aug 27, 2024 · 12 comments · May be fixed by #1056
Assignees
Labels
new feature New feature or request

Comments

@aaronzedwick
Copy link
Member

Proposed new feature or change:

Add a function to check if a point is inside a polygon. Currently a pole point in polygon is implemented, possibly modify it and make a similar function? That function makes a reference edge using the point and the equator, which wouldn't work with all points.

@aaronzedwick aaronzedwick added the new feature New feature or request label Aug 27, 2024
@aaronzedwick aaronzedwick self-assigned this Aug 27, 2024
@github-project-automation github-project-automation bot moved this to 📚 Backlog in UXarray Development Aug 27, 2024
@philipc2
Copy link
Member

We need to make sure that we implement the point-in-polygon algorithm for spherical geometry. There are dozens of implementations for standard planar geometry (shapely is the most obvious one), but these wouldn't be ideal.

@aaronzedwick
Copy link
Member Author

aaronzedwick commented Aug 27, 2024

We need to make sure that we implement the point-in-polygon algorithm for spherical geometry. There are dozens of implementations for standard planar geometry (shapely is the most obvious one), but these wouldn't be ideal.

That’s why I mentioned @hongyuchen1030 I believe it works on spherical geometry.

@hongyuchen1030
Copy link
Contributor

We need to make sure that we implement the point-in-polygon algorithm for spherical geometry. There are dozens of implementations for standard planar geometry (shapely is the most obvious one), but these wouldn't be ideal.

That’s why I mentioned @hongyuchen1030 I believe it works on spherical geometry.

Unfortunately, they don't. And it is a complicated problem to solve on the spherical geometry. I remember we have already had such a discussion a long time ago. For the recent one, please see my comments here #898 (comment)

How to detect if a point is inside a face on the spherical surface. (I know the immediate answer is ray-casting, but we are on the spherical surface, so the ray will go back!)

for now, I can only come up with the pole_in_polygon that checks pole point only. With some modification, it might be used for a general case. Again this problem is more complicate on the sphere than on the planar surface

@aaronzedwick
Copy link
Member Author

We need to make sure that we implement the point-in-polygon algorithm for spherical geometry. There are dozens of implementations for standard planar geometry (shapely is the most obvious one), but these wouldn't be ideal.

That’s why I mentioned @hongyuchen1030 I believe it works on spherical geometry.

Unfortunately, they don't. And it is a complicated problem to solve on the spherical geometry. I remember we have already had such a discussion a long time ago. For the recent one, please see my comments here #898 (comment)

How to detect if a point is inside a face on the spherical surface. (I know the immediate answer is ray-casting, but we are on the spherical surface, so the ray will go back!)

for now, I can only come up with the pole_in_polygon that checks pole point only. With some modification, it might be used for a general case. Again this problem is more complicate on the sphere than on the planar surface

They don’t? I thought your pole inside polygon worked on a sphere. Would it not work in the general case? Any ideas on how to make it general?

@hongyuchen1030
Copy link
Contributor

We need to make sure that we implement the point-in-polygon algorithm for spherical geometry. There are dozens of implementations for standard planar geometry (shapely is the most obvious one), but these wouldn't be ideal.

That’s why I mentioned @hongyuchen1030 I believe it works on spherical geometry.

Unfortunately, they don't. And it is a complicated problem to solve on the spherical geometry. I remember we have already had such a discussion a long time ago. For the recent one, please see my comments here #898 (comment)

How to detect if a point is inside a face on the spherical surface. (I know the immediate answer is ray-casting, but we are on the spherical surface, so the ray will go back!)

for now, I can only come up with the pole_in_polygon that checks pole point only. With some modification, it might be used for a general case. Again this problem is more complicate on the sphere than on the planar surface

They don’t? I thought your pole inside polygon worked on a sphere. Would it not work in the general case? Any ideas on how to make it general?

Yes, the pole point inside worked on the sphere. Previously we only needed to query the pole point. I will create a new PR for the general case and put my algorithm there.

@aaronzedwick
Copy link
Member Author

aaronzedwick commented Oct 21, 2024

@hongyuchen1030 @philipc2 I think I will start to go ahead and implement something similar as to what is described in this paper here.

@hongyuchen1030
Copy link
Contributor

hongyuchen1030 commented Oct 21, 2024

@hongyuchen1030 @philipc2 I think I will start to go ahead and implement something similar as to what is described in this paper here.

Me and Paul already talked about this paper and didn't think it's suitable for the Uxarray. Please keep in mind that it uses exact computation (CGAL). It will build a tree diagram as well
Image

Before you go into any workaround method (like this one), I suggest learning from the computational geometry, especially the mesh arrangement.

@aaronzedwick
Copy link
Member Author

@hongyuchen1030 @philipc2 I think I will start to go ahead and implement something similar as to what is described in this paper here.

Me and Paul already talked about this paper and didn't think it's suitable for the Uxarray. Please keep in mind that it uses exact computation (CGAL). It will build a tree diagram as well Image

Before you go into any workaround method (like this one), I suggest learning from the computational geometry, especially the mesh arrangement.

Can you elaborate further on what you mean by learning from the computation geometry? I’m happy to pursue any method you think is best. I just need to start working on this (or steps to lead towards completing this) for my remapping algorithm.

@hongyuchen1030
Copy link
Contributor

Can you elaborate further on what you mean by learning from the computation geometry? I’m happy to pursue any method you think is best. I just need to start working on this (or steps to lead towards completing this) for my remapping algorithm.

Have you tried to look into the mesh arrangement materials that been posted on #983?

I just need to start working on this (or steps to lead towards completing this) for my remapping algorithm.

Have you looked into the source codes and the detailed implementation of such algorithms in this paper? There are lots of state-of-art algorithms. However, not every one of them fits the requirement of Uxarray. We are looking for algorithms that works on the spherical surface, accurate enough but without loosing much performance. Again, this packages utilize CGAL exact computation so I don't think it will work for us. If you are interested, you can also learn about the CGAL library.

@aaronzedwick
Copy link
Member Author

@hongyuchen1030 I have, however it seems like a large scale project to tackle, that would stall finishing bilinear remapping for awhile. If you think it is worth it however, I would be happy to start working on that.

Yes I have been looking at the source code for the paper, although I have only had a day to go through it so I don’t have a complete and thorough understanding of how it works yet. However in the paper they seemed to suggest their solution was robust and efficient speed wise.

Ok! Sounds good, I will look into CGAL. Just for clarity, is there a specific reason you think CGAL is incompatible with our project?

@hongyuchen1030
Copy link
Contributor

hongyuchen1030 commented Oct 22, 2024

@hongyuchen1030 I have, however it seems like a large scale project to tackle, that would stall finishing bilinear remapping for awhile. If you think it is worth it however, I would be happy to start working on that.

I understand that it's a large-scale project, and tackling it now could delay the completion of bilinear remapping. However, I encourage you to read the MeshArrangement paper — you'll realize that we're essentially reinventing the wheel right now but in an unsystematic way. Point-in-polygon on a sphere is a complex problem, and that paper calls it "robust" because of CGAL's exact computation, and "efficient" due to using a tree structure to reduce query complexity to logN. But these claims come from a geoscience perspective, not from computational geometry, so they might not be as solid as they seem.

That said, do you know how long their algorithm would take to run?

In the meantime, if you need a quicker solution for your bilinear mapping, here are two options we’ve discussed before:

  1. Write a helper function that converts each point to the "pole point" and adjusts other node coordinates. Then, call the pole_point_in_polygon function, which is robust for pole points.

  2. Use what Paul has in TempestRemap, but keep in mind that it's not robust. You can test different cases and patch as needed.

Ultimately, I expect we'll have to sort everything out with MeshArrangement. Uxarray is already redoing much of this work. It's a big task, and you could wait until we decide to use it systematically in the future.

Ok! Sounds good, I will look into CGAL. Just for clarity, is there a specific reason you think CGAL is incompatible with our project?

As we've highlighted many times in our meetings, Uxarray does not favor using C++ or any compiled code, and performance is absolutely critical for this project. While CGAL offers robustness, its slow performance doesn’t align with the speed requirements we need, especially for handling large-scale datasets efficiently.

@aaronzedwick
Copy link
Member Author

@hongyuchen1030 I have, however it seems like a large scale project to tackle, that would stall finishing bilinear remapping for awhile. If you think it is worth it however, I would be happy to start working on that.

I understand that it's a large-scale project, and tackling it now could delay the completion of bilinear remapping. However, I encourage you to read the MeshArrangement paper — you'll realize that we're essentially reinventing the wheel right now but in an unsystematic way. Point-in-polygon on a sphere is a complex problem, and that paper calls it "robust" because of CGAL's exact computation, and "efficient" due to using a tree structure to reduce query complexity to logN. But these claims come from a geoscience perspective, not from computational geometry, so they might not be as solid as they seem.

That said, do you know how long their algorithm would take to run?

In the meantime, if you need a quicker solution for your bilinear mapping, here are two options we’ve discussed before:

  1. Write a helper function that converts each point to the "pole point" and adjusts other node coordinates. Then, call the pole_point_in_polygon function, which is robust for pole points.
  2. Use what Paul has in TempestRemap, but keep in mind that it's not robust. You can test different cases and patch as needed.

Ultimately, I expect we'll have to sort everything out with MeshArrangement. Uxarray is already redoing much of this work. It's a big task, and you could wait until we decide to use it systematically in the future.

Ok! Sounds good, I will look into CGAL. Just for clarity, is there a specific reason you think CGAL is incompatible with our project?

As we've highlighted many times in our meetings, Uxarray does not favor using C++ or any compiled code, and performance is absolutely critical for this project. While CGAL offers robustness, its slow performance doesn’t align with the speed requirements we need, especially for handling large-scale datasets efficiently.

Okay! That makes sense! Thanks for the clarification! I was looking into doing something similar to Paul's, but it didn't seem robust like you said, especially as I started trying different implementations. That's why I went looking for something else. Using pole_in_point_polygon sounds like it could be a good solution for now. I will look into that, along with the mesh arrangement. Thanks for the discussion and time!

@aaronzedwick aaronzedwick moved this from 📚 Backlog to 🏗 In progress in UXarray Development Oct 23, 2024
@aaronzedwick aaronzedwick linked a pull request Nov 5, 2024 that will close this issue
10 tasks
@aaronzedwick aaronzedwick moved this from 🏗 In progress to 👀 In review in UXarray Development Nov 27, 2024
@aaronzedwick aaronzedwick changed the title Point in Polygon Point in Face Dec 18, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
new feature New feature or request
Projects
Status: 👀 In review
3 participants