# Point in polygon - ask whether a given point in the curve lies inside, outside, or on the boundary of a polygon

Draw a ray from Point(x,y) to infinity, and count how many times it crosses the curve; if the count is odd, then (x,y) is inside the enclosed region; otherwise, it's outside.

*Solution: *

To turn this into a practical algorithm, first we must build polygonal approximation of the curve and look for all segments that the ray (straight line) from (x,y) intersects. This operation is linear in the number of segments of the polygon. Once we have all the candidate segments, we can use these as the basis for a Newton search to find a more exact point of intersection of the ray (straight line) with the curve.

The elliptic curve domain parameters over Fp associated with a Koblitz curve secp256k1                                          are specified  by the sextuple T = (p,a,b,G,n,h) where the finite field Fp is defined by:
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2
The curve E: y^2 = x^3+ax+b over Fp is defined by:  (short : y^2=x^3 + b)
a = 0
b = 7

Base point:
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
G=(Gx,Gy)
Finally the order n of G and the cofactor are:

n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
h = 1

Point to check :
Px=0xf9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9
Py=0x388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672
P(Px,Py)

result: -> the line of above Point P(Px,Py) cross the curve only one.


how to write in Sage? how to execute the task?

more information at "A Simple and Correct Even-Odd Algorithm for the Point-in-PolygonProblem for Complex Polygons" link to paper: https://arxiv.org/pdf/1207.3502.pdf

**the problem for me is which points I must take to Polygon.
For example the Point which I must check is P3
then to polygn should I take P1,P2,P4,P5 or other? how to understand it?**

edit retag close merge delete