I'm trying to create a fast 2D point inside polygon algorithm, for use in hit-testing (e.g. Polygon.contains(p:Point)
). Suggestions for effective techniques would be appreciated.
相关问题
- Faster loop: foreach vs some (performance of jsper
- Why wrapping a function into a lambda potentially
- Ado.net performance:What does SNIReadSync do?
- Device support warning : Google play 2019
- Direct2D Only Partially Linking in C++ Builder
相关文章
- DOM penalty of using html attributes
- Which is faster, pointer access or reference acces
- Behavior of uniforms after glUseProgram() and spee
- Django is sooo slow? errno 32 broken pipe? dcramer
- Understanding the difference between Collection.is
- parallelizing matrix multiplication through thread
- How to determine JS bottlenecks in React Native co
- Difference between SuspendLayout and BeginUpdate
The answer depends on if you have the simple or complex polygons. Simple polygons must not have any line segment intersections. So they can have the holes but lines can't cross each other. Complex regions can have the line intersections - so they can have the overlapping regions, or regions that touch each other just by a single point.
For simple polygons the best algorithm is Ray casting (Crossing number) algorithm. For complex polygons, this algorithm doesn't detect points that are inside the overlapping regions. So for complex polygons you have to use Winding number algorithm.
Here is an excellent article with C implementation of both algorithms. I tried them and they work well.
http://geomalgorithms.com/a03-_inclusion.html
Here is golang version of @nirg answer (inspired by C# code by @@m-katz)
Swift version of the answer by nirg:
There is nothing more beutiful than an inductive definition of a problem. For the sake of completeness here you have a version in prolog which might also clarify the thoughs behind ray casting:
Based on the simulation of simplicity algorithm in http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
Some helper predicates:
The equation of a line given 2 points A and B (Line(A,B)) is:
It is important that the direction of rotation for the line is setted to clock-wise for boundaries and anti-clock-wise for holes. We are going to check whether the point (X,Y), i.e the tested point is at the left half-plane of our line (it is a matter of taste, it could also be the right side, but also the direction of boundaries lines has to be changed in that case), this is to project the ray from the point to the right (or left) and acknowledge the intersection with the line. We have chosen to project the ray in the horizontal direction (again it is a matter of taste, it could also be done in vertical with similar restrictions), so we have:
Now we need to know if the point is at the left (or right) side of the line segment only, not the entire plane, so we need to restrict the search only to this segment, but this is easy since to be inside the segment only one point in the line can be higher than Y in the vertical axis. As this is a stronger restriction it needs to be the first to check, so we take first only those lines meeting this requirement and then check its possition. By the Jordan Curve theorem any ray projected to a polygon must intersect at an even number of lines. So we are done, we will throw the ray to the right and then everytime it intersects a line, toggle its state. However in our implementation we are goint to check the lenght of the bag of solutions meeting the given restrictions and decide the innership upon it. for each line in the polygon this have to be done.
C# version of nirg's answer is here: I'll just share the code. It may save someone some time.
Java Version: