Проверка на то что точка лежит внутри многоугольника: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
(Новая страница: «==Идея== Если зафиксировать какую-либо вершину, то относительно нее углы будут расположе...»)
 
Строка 3: Строка 3:
 
Если зафиксировать какую-либо вершину, то относительно нее углы будут расположены против часовой стрелки или против часовой стрелки, при этом несложно заметить, что сначала угол к вершине будет меньше/больше угла к нашей точке, а затем наоборот, следовательно, мы можем сделать бинпоиск и найти первую вершину угол от которой больше/меньше нашего.
 
Если зафиксировать какую-либо вершину, то относительно нее углы будут расположены против часовой стрелки или против часовой стрелки, при этом несложно заметить, что сначала угол к вершине будет меньше/больше угла к нашей точке, а затем наоборот, следовательно, мы можем сделать бинпоиск и найти первую вершину угол от которой больше/меньше нашего.
  
 +
==Код==
 +
 +
<syntaxhighlight lang="C++">
 +
point zero;//какая-то точка, которую мы сохранили как 0, для того, чтобы определять по или против
 +
//a = vector_angles;
 +
point my = { q.y-zero.y, q.x-zero.x };
 +
auto it = upper_bound (a.begin(), a.end(), my);
 +
if (it == a.end() && my.a == a[n - 1].a && my.b == a[n - 1].b) {
 +
    it = a.end() - 1;
 +
}
 +
if (it != a.end() && it != a.begin()) {
 +
    int p1 = int(it - a.begin());
 +
    if (in(p[p1], p[p1 - 1], q) <= 0) {//проверка то что внутри
 +
in = true;
 +
    }
 +
}
 
</syntaxhighlight>
 
</syntaxhighlight>
 +
 
{{Автор|Глеб Лобанов|glebodin}}
 
{{Автор|Глеб Лобанов|glebodin}}
  
 
[[Категория:Конспект]]
 
[[Категория:Конспект]]

Версия 17:25, 9 января 2021

Идея

Если зафиксировать какую-либо вершину, то относительно нее углы будут расположены против часовой стрелки или против часовой стрелки, при этом несложно заметить, что сначала угол к вершине будет меньше/больше угла к нашей точке, а затем наоборот, следовательно, мы можем сделать бинпоиск и найти первую вершину угол от которой больше/меньше нашего.

Код

point zero;//какая-то точка, которую мы сохранили как 0, для того, чтобы определять по или против
//a = vector_angles;
point my = { q.y-zero.y, q.x-zero.x };
auto it = upper_bound (a.begin(), a.end(), my);
if (it == a.end() && my.a == a[n - 1].a && my.b == a[n - 1].b) {
    it = a.end() - 1;
}
if (it != a.end() && it != a.begin()) {
    int p1 = int(it - a.begin());
    if (in(p[p1], p[p1 - 1], q) <= 0) {//проверка то что внутри
	in = true;
    }
}



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin