1 |
|
2 | const tolerance = 1e-6;
|
3 |
|
4 | function dcmp(x: number) {
|
5 | if (Math.abs(x) < tolerance) {
|
6 | return 0;
|
7 | }
|
8 |
|
9 | return x < 0 ? -1 : 1;
|
10 | }
|
11 |
|
12 |
|
13 | function onSegment(p1: number[], p2: number[], q: number[]) {
|
14 | if (
|
15 | (q[0] - p1[0]) * (p2[1] - p1[1]) === (p2[0] - p1[0]) * (q[1] - p1[1]) &&
|
16 | Math.min(p1[0], p2[0]) <= q[0] &&
|
17 | q[0] <= Math.max(p1[0], p2[0]) &&
|
18 | Math.min(p1[1], p2[1]) <= q[1] &&
|
19 | q[1] <= Math.max(p1[1], p2[1])
|
20 | ) {
|
21 | return true;
|
22 | }
|
23 | return false;
|
24 | }
|
25 |
|
26 |
|
27 | export function isPointInPolygon(points: number[][], x: number, y: number) {
|
28 | let isHit = false;
|
29 | const n = points.length;
|
30 | if (n <= 2) {
|
31 |
|
32 | return false;
|
33 | }
|
34 | for (let i = 0; i < n; i++) {
|
35 | const p1 = points[i];
|
36 | const p2 = points[(i + 1) % n];
|
37 | if (onSegment(p1, p2, [x, y])) {
|
38 |
|
39 | return true;
|
40 | }
|
41 |
|
42 |
|
43 | if (
|
44 | dcmp(p1[1] - y) > 0 !== dcmp(p2[1] - y) > 0 &&
|
45 | dcmp(x - ((y - p1[1]) * (p1[0] - p2[0])) / (p1[1] - p2[1]) - p1[0]) < 0
|
46 | ) {
|
47 | isHit = !isHit;
|
48 | }
|
49 | }
|
50 | return isHit;
|
51 | }
|