Point in Polygon Algorithm

by

The algorithm is ray-casting to the right. Each iteration of the loop, the test point is checked against one of the polygon’s edges. The first line of the if-test succeeds if the point’s y-coord is within the edge’s scope. The second line checks whether the test point is to the left of the line (I think – I haven’t got any scrap paper to hand to check). If that is true the line drawn rightwards from the test point crosses that edge.

By repeatedly inverting the value of c, the algorithm counts how many times the rightward line crosses the polygon. If it crosses an odd number of times, then the point is inside; if an even number, the point is outside.

I would have concerns with a) the accuracy of floating-point arithmetic, and b) the effects of having a horizontal edge, or a test point with the same y-coord as a vertex, though.

More Related Contents:

  1. Pattern Programmings
  2. the problem is from a algorithm problem I do recently,but I can't gain the right answer [duplicate]
  3. Algorithm to find the smallest number in an array in C [closed]
  4. Recursive C function
  5. How to generate numbers upto 18 digits, sum of whose reciprocals is a whole number [closed]
  6. Finding target sum of two numbers in array
  7. The most efficient way to implement an integer based power function pow(int, int)
  8. What is the fastest/most efficient way to find the highest set bit (msb) in an integer in C?
  9. hash function for string
  10. Building a logarithm function in C without using float type
  11. How can I simplify this working Binary Search code in C?
  12. Matrix multiplication: Small difference in matrix size, large difference in timings
  13. Project Euler Question 14 (Collatz Problem)
  14. How do you print the EXACT value of a floating point number?
  15. Time complexity of a recursive algorithm
  16. How to find largest triangle in convex hull aside from brute force search
  17. C – How to implement Set data structure?
  18. Print all the permutations of a string in C
  19. Correctness of Sakamoto’s algorithm to find the day of week
  20. Why prefer start + (end – start) / 2 over (start + end) / 2 when calculating the middle of an array?
  21. Generating a uniform distribution of INTEGERS in C
  22. Rolling median in C – Turlach implementation
  23. Rolling median algorithm in C
  24. Floating point linear interpolation
  25. Finding the intersecting node from two intersecting linked lists
  26. Finding out the duplicate element in an array
  27. Does C have any tools for doing string addition?
  28. a working non-recursive floodfill algorithm written in C?
  29. Algorithm to pick values from array that sum closest to a target value?
  30. Avoid Overflow when Calculating π by Evaluating a Series Using 16-bit Arithmetic?

Leave a Comment