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

asked 2021-03-13 21:50:34 +0100

Miroslaw gravatar image

updated 2021-03-14 11:03:14 +0100

Please help in this question. I'm really don't know even how to start in Sage.

*Task: to do *

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:
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 
Gy=  0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
Finally the order n of G and the cofactor are:

 h = 1

Point to check : 

 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 flag offensive close merge delete