ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 13 Mar 2021 21:50:34 +0100Point in polygon - ask whether a given point in the curve lies inside, outside, or on the boundary of a polygonhttps://ask.sagemath.org/question/56164/point-in-polygon-ask-whether-a-given-point-in-the-curve-lies-inside-outside-or-on-the-boundary-of-a-polygon/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:
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
Gy= 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
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?**Sat, 13 Mar 2021 21:50:34 +0100https://ask.sagemath.org/question/56164/point-in-polygon-ask-whether-a-given-point-in-the-curve-lies-inside-outside-or-on-the-boundary-of-a-polygon/