Revision history [back]

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 = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
 h = 01

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

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 = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
 h = 01
1

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

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)

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

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

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?**