Алгоритм определения попадания точки в контур многоугольника (дублирование кода с C++)

@v1a_sacra · Регистрация: 10.03.2016

Студворк — интернет-сервис помощи студентам

Всем привет. Переписал код C++ из из данной статьи на Java. Но почему-то при любом вхождении метод возвращает true. Тестирую на геоданных (широта и долгота).
Код C++:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
template <class T>
bool pt_in_polygon(const T &test,const std::vector &polygon)
{
if (polygon.size()<3) return false; 
std::vector::const_iterator end=polygon.end();
T last_pt=polygon.back(); 
last_pt.x-=test.x;
last_pt.y-=test.y;
double sum=0.0;
for(
std::vector::const_iterator iter=polygon.begin();
iter!=end;
++iter
)
{
T cur_pt=*iter;
cur_pt.x-=test.x;
cur_pt.y-=test.y;
double del= last_pt.x*cur_pt.y-cur_pt.x*last_pt.y;
double xy= cur_pt.x*last_pt.x+cur_pt.y*last_pt.y;
sum+=
(
atan((last_pt.x*last_pt.x+last_pt.y*last_pt.y - xy)/del)+
atan((cur_pt.x*cur_pt.x+cur_pt.y*cur_pt.y- xy )/del)
);
last_pt=cur_pt;
}
return fabs(sum)>eps;
}
 
 
//T – тип точки, например:
struct PointD
{
double x,y;
};

Вот мой код на Java:

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public static boolean pointInPoligon(Point point) {
            double exp = 1E-5;
            ArrayList<Point> polygon = poligonVectorPoints;
            
            if (polygon.size() < 3)
                return false;
            
            Point lastPt = polygon.get(polygon.size() - 2); 
     
            double lastPtX = lastPt.x - point.x;
            double lastPtY = lastPt.y - point.y;
     
            double sum = 0.0;
            double iterX = 0.0;
            double iterY = 0.0;
            
            
            for(Point iter : polygon) {
                iterX = iter.x - point.x;
                iterY = iter.y - point.y;
     
                double del = lastPtX * iterY - iterX * lastPtY;
                double xy = iterX * lastPtX + iterY * lastPtY;
     
                sum += (Math.atan((lastPtX * lastPtX + lastPtY * lastPtY - xy) / del)+
                        Math.atan((iterX * iterX + iterY * iterY - xy) / del));
                
                lastPtX = iterX;
                lastPtY = iterY;
            }
            System.out.println(sum);
            return Math.abs(sum) > exp;
        }

Помогите пожалуйста разобраться в чем проблема. Код с C++ вроде как работает.
P. S.
Там есть еще один пример кода, но не могу разобраться со следующей строкой. Я просто не пойму, что за бред там написан)
Если кто знает, помогите разобраться и привести пример на Java, как это реализовано:

C++
1
int pred_q=q_patt[pred_pt.y<0][pred_pt.x<0];

Вот полный код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
template bool pt_in_polygon2(const T &test,const std::vector &polygon)
{
static const int q_patt[2][2]= { {0,1}, {3,2} };
if (polygon.size()<3) return false;
std::vector::const_iterator end=polygon.end();
T pred_pt=polygon.back(); 
pred_pt.x-=test.x;
pred_pt.y-=test.y;
int pred_q=q_patt[pred_pt.y<0][pred_pt.x<0];
int w=0;
for(std::vector::const_iterator iter=polygon.begin();iter!=end;++iter)
{
T cur_pt = *iter; 
cur_pt.x-=test.x;
cur_pt.y-=test.y;
int q=q_patt[cur_pt.y<0][cur_pt.x<0];
switch (q-pred_q)
{
case -3:++w;break;
case 3:--w;break;
case -2:if(pred_pt.x*cur_pt.y>=pred_pt.y*cur_pt.x) ++w;break;
case 2:if(!(pred_pt.x*cur_pt.y>=pred_pt.y*cur_pt.x)) --w;break;
}
pred_pt = cur_pt;
pred_q = q;
}
return w!=0;
}

@Aviz__ · 10.05.2018, 13:37

Сообщение от v1a_sacra

Тестирую

а дебагером проходил?

@v1a_sacra · 11.05.2018, 11:36 **[ТС]**

Aviz__, да, я попробовал создать квадрат, с простыми вершинами (1,1)(1,3)(3,3)(3,1). И точку (2,2) определяет, (5,5) нет. Т.е на простейшем работает, так же и со вторым кодом (я его тоже реализовал). На вышеперечисленных данных работает. Пробегал дебагером и лично наблюдал за всем процессом.
Когда начинаю закидывать фигуру с геоданными и проверять на них, всегда возвращает true. Не понятно, почему. Второй метод вообще всегда false возвращает.

@Aviz__ · 11.05.2018, 19:04

вот, набросал, поиграйся с этим, может поможет понять траблу

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class CyberPoint {
 
    static class  Point {
        private double x;
        private double y;
 
        Point(double x, double y) {
            this.x = x;
            this.y = y;
        }
    }
 
    static class  Square {
        private Point [] peaks = new Point[2];
 
        Square(Point... peak) {
            System.arraycopy(peak, 0, this.peaks, 0, 2);
        }
 
        boolean isPointInSquare(Point outPoint) {
            int flagIn = 0;
            if (Math.max(outPoint.x, peaks[0].x) == outPoint.x
                    && Math.min(outPoint.x, peaks[1].x) == outPoint.x)
                flagIn++;
            // у - растет вниз, как на экране
            if (Math.max(outPoint.y, peaks[0].y) == outPoint.y
                    && Math.min(outPoint.y, peaks[1].y) == outPoint.y)
                flagIn++;
            return flagIn == 2;
        }
 
    }
 
    public static void main(String[] args) {
        Point p1 = new Point(3.0000001,1.7);
        Point p2 = new Point(3.0,1.7);
        Square sq1 = new Square(new Point(1,1), new Point(3,3));
        System.out.println(sq1.isPointInSquare(p1));
        System.out.println(sq1.isPointInSquare(p2));
    }
 
}

да, как ты догадался, это для квадратной области.

@v1a_sacra · 15.05.2018, 10:43 **[ТС]**

Aviz__, но в теме указано, что определяет попадание в сколь угодно сложный многоугольник, не так ли?

@Aviz__ · 15.05.2018, 11:31

Сообщение от v1a_sacra

не так ли

нет, ты не понимал в чем проблема, возможно, в формате геоданных. я те дал путь, чтобы понять это)).

Новые блоги и статьи Все статьи Все блоги /
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .

@v1a_sacra 2 / 2 / 0 Регистрация: 10.03.2016 Сообщений: 64
	11.05.2018, 11:36 [ТС]
	Aviz__, да, я попробовал создать квадрат, с простыми вершинами (1,1)(1,3)(3,3)(3,1). И точку (2,2) определяет, (5,5) нет. Т.е на простейшем работает, так же и со вторым кодом (я его тоже реализовал). На вышеперечисленных данных работает. Пробегал дебагером и лично наблюдал за всем процессом. Когда начинаю закидывать фигуру с геоданными и проверять на них, всегда возвращает true. Не понятно, почему. Второй метод вообще всегда false возвращает. 0

@v1a_sacra 2 / 2 / 0 Регистрация: 10.03.2016 Сообщений: 64
	15.05.2018, 10:43 [ТС]
	Aviz__, но в теме указано, что определяет попадание в сколь угодно сложный многоугольник, не так ли? 0