polygon = new ArrayList<>();
polygon.add(new Point(1, 1));
polygon.add(new Point(1, 10));
polygon.add(new Point(10, 10));
polygon.add(new Point(5, 5));
polygon.add(new Point(10, 1));
System.out.println(isPointInPolygon(new Point(5, 5), polygon));package com.javarush.task.task40.task4004;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/*
Принадлежность точки многоугольнику
*/
class Point {
public int x;
public int y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Solution {
public static void main(String[] args) {
List<Point> polygon = new ArrayList<>();
polygon.add(new Point(0, 0));
polygon.add(new Point(0, 10));
polygon.add(new Point(10, 10));
polygon.add(new Point(10, 0));
System.out.println(isPointInPolygon(new Point(5, 5), polygon));
System.out.println(isPointInPolygon(new Point(100, 100), polygon));
}
public static boolean isPointInPolygon(Point point, List<Point> polygon) {
//напишите тут ваш код
//if (point!=null && polygon!=null) {
int min_x = Integer.MAX_VALUE, min_y = Integer.MAX_VALUE, max_x = Integer.MIN_VALUE, max_y = Integer.MIN_VALUE;
for (Point p : polygon
) {
if (p==null)return false;
min_x = Math.min(min_x, p.x);
max_x = Math.max(max_x, p.x);
min_y = Math.min(min_y, p.y);
max_y = Math.max(max_y, p.y);
}
if (point.y < min_y || point.y > max_y) return false;
if (point.x < min_x || point.x > max_x) return false;
int intersection=phase2(point, polygon);
return intersection % 2 != 0;
//}
//return false;
}
//intersection
private static int phase2(Point point, List<Point> polygon){
int left_count=0;
int right_count=0;
LinkedList<_line> list=new LinkedList<>();
for (int i = 0; i <polygon.size() ; i++) {
if (i==polygon.size()-1)list.add(new _line(polygon.get(i),polygon.get(0)));
else list.add(new _line(polygon.get(i),polygon.get(i+1)));
}
for (_line rebro:list
) {
if (point.y<rebro.y_min||point.y> rebro.y_max) {
}
else {
if (point.x>rebro.x_min){
right_count++;
}else {
left_count++;
}
}
//
//точка на ребре
//if (rebro.x_max== rebro.x_min)
}
return Math.min(left_count,right_count);
}
private static class _line{
int x_start,y_start,x_end,y_end,x_min,x_max,y_min,y_max;
public _line(Point start, Point end) {
x_start=start.x;
x_end=end.x;
y_start=start.y;
y_end=end.y;
x_min=Math.min(x_start,x_end);
x_max=Math.max(x_start,x_end);
y_min=Math.min(y_start,y_end);
y_max=Math.max(y_start,y_end);
}
}
}