Нахождение точек внутри фигуры

@Luca Brasi · Регистрация: 06.11.2015

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

Не хотелось бы изобретать велосипед, может есть более внятные способы нежели многократный проход циклами по точкам...
Есть два набора точек. По одним строится график, а вторые просто в пространстве.
По первому набору построить график, сделать пересечение графика с горизонтальной прямой.

Далее внутри обьектов fig1 и fig2 - найти точки со второго набора.

@Alli_Lupin · 17.10.2019, 10:42

Luca Brasi, а как вы хотите решать задачу? просто или сложно? т.е. просто сперва посчитаете, сколько у вас фигур и какими точками они описаны, а потом будете каждую точку проверять по n условиям, или сперва сгруппируете точки по.. кхм, кучкам и потом уже будете анализировать эти кучки на вхождение в фигуру?

@Luca Brasi · 17.10.2019, 21:20 **[ТС]**

Alli_Lupin, ну хотелось бы полегче, только не всегда выбранный путь "полегче" им и будет))). Если найти точки которые описывают фигурки, то по ним можно построить полигон.
Внутри полигона уже искать точки из общего набора.

Python
1
2
3
4
5
6
from shapely.geometry import Point
from shapely.geometry.polygon import Polygon
 
point = Point(0.5, 0.5)
polygon = Polygon([(0, 0), (0, 1), (1, 1), (1, 0)])
print(polygon.contains(point))

@Alli_Lupin · 17.10.2019, 22:35

Luca Brasi, у меня этот пакет не ставится сходу. Поздно уже экспериментировать.. Я бы просто математикой решал, но как-то лаконичного решения не получается.

@vrm2 · 17.10.2019, 23:16

Сообщение от Luca Brasi

Не хотелось бы изобретать велосипед, может есть более внятные способы нежели многократный проход циклами по точкам...
Есть два набора точек. По одним строится график, а вторые просто в пространстве.
По первому набору построить график, сделать пересечение графика с горизонтальной прямой.

Проходим по второму набору точек. Для каждой точки (x,y) вычисляем соответствующую ей точку графика (x,y_g). Затем проверяем, что точка находится выше линии (y > y_line) и ниже графика (y < y_g).

Для вычисления точек графика - сортируем точки первого набора по оси X, затем получаем уравнения прямых для каждого отрезка, соединяющего соседние точки.

Итого: O(M*logM) + O(N), где M - количество точек графика (первый набор), N - количество точек под графиком (второй набор)

@Luca Brasi · 17.10.2019, 23:30 **[ТС]**

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

но как-то лаконичного решения не получается.

знакомо... Мое решение уж как-то сильно примитивно. Да и хз, прокатит ли в таком виде

1. Сначала ищем габариты прямоугольника для первой фигуры.
2. Рисуем фигуру
3. Выделяем точки кривой которые попали в этот прямоугольник.
4. Смещаемся к другой фигуре...

@Alli_Lupin · 17.10.2019, 23:58

Luca Brasi, а какая функция у прямоугольника?

@Luca Brasi · 18.10.2019, 07:33 **[ТС]**

Alli_Lupin, функция прямоугольника? Честно говоря не особо понял, ведь фунция следует привязыавть к конкретной кривой. Или Вы клоните в сторону какого то тайного метода вычисления...

@Alli_Lupin · 18.10.2019, 09:48

Сообщение от Luca Brasi

1. Сначала ищем габариты прямоугольника для первой фигуры.

Нет, я всего лишь об этом)

@Luca Brasi · 19.10.2019, 12:02 **[ТС]**

Честно говоря вчера я повозился нормально. Но по последним данным, габариты ищет... Причем даже для нескольких треугольников

В целом обошелся лишь одним циклом с перебором точек, что по мне куда годнее первого моего решения.
Хочу переписать всё в объектном стиле, чтобы не стыдно было показывать)))

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

у меня этот пакет не ставится сходу

я кажется понял о чем Вы... У меня дома Убунта, а вот на работе win10. Там тоже не хотело ставитсья, пришось искать решение, в принципе оно просто

@Alli_Lupin · 19.10.2019, 19:19

Luca Brasi, решили задачу? Это хорошо)

@Luca Brasi · 21.10.2019, 21:57 **[ТС]**

Alli_Lupin, сделал некоторую объектную модель.
Пришлось решать баанльными способами, т.к. они работают проще и точнее нежели эта методология shapely
mdesign.zip
Моя нынешняя задача свелась к нахождению лишь точек поверх кривой

@vrm2 · 21.10.2019, 23:21

Сообщение от Luca Brasi

сделал некоторую объектную модель.
Пришлось решать банальными способами, т.к. они работают проще и точнее нежели эта методология shapely

Объектная модель в данном случае только все усложняет. С помощью pandas задача решается в 5-10 строчек, без циклов и классов.

К коду много вопросов - начиная от алгоритма в целом и неэффективного использования pandas, заканчивая нарушениями стилистики python кода. Я бы рекомендовал доработать код, чтобы "не стыдно было показывать".

@Luca Brasi · 22.10.2019, 15:11 **[ТС]**

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

неэффективного использования pandas, заканчивая нарушениями стилистики python кода.

буду рад послушать Ваши коментарии

@vrm2 · 22.10.2019, 23:59

Сообщение от Luca Brasi

буду рад послушать Ваши коментарии

Нарушения PEP-8:
- лишние пустые строки после названия метода и перед определением класса
- коментарии к классу и методу должны писаться после класса или метода
- docstring должен содержать краткое описание в первой строке, и только затем описание параметров
- названия переменных и методов должны быть в это_название_переменной, а не названиеПеременной

В классе Point:
- в питоне не принято прятать поля объекта (можно просто назвать поля - x и y, а не _x и _y)
- в питоне не принято делать геттеры и сеттеры. В дальнейшем, если понадобвится переопределить геттер или сеттер можно добавить property
- для форматирования существуют f-строки: f'x: {self._x}, y: {self._y}'
- вообще, класс Point лучше реализовать с помощью NamedTuple

В классе PointSet:
- реализован с помощью списка (self._pointSet является списком), эффективнее делать на основе set
- надо кидать исключение не NameError, а ValueError
- переменная sum переопределяет встроенную функцию sum, лучше заменить название на sum_ или total

В классе PointSetFactory:
- PointSetFactory на самом деле не Factory (он ничего не создает), а скорее Service. Поэтому - PointSetService. А еще лучше, что-то типа PointSplitService
- findPosPointSets скорее должен называться split_points_above_treshold
- findPosPointSets скорее должны быть функциями, а не методами

В модуле how_to_use:
- нет полноценного примера, который можно запустить. Нужно определить какие-нибудь dataframe, иначе непонятно как они должны выглядеть
- комментарий `#iterate over files and calc average value` - какие файлы? зачем вычисляем среднее?

Некоторые ошибки алгоритма:
- почему-то не учитываются точки график (первое множество точек, которое указано в задании), сранивается только с treshold
- переменные _x и _y определены как переменные класса, а должны объявляться в __init__
- операция + не определена в классе PointSet, код из how_to_use просто не запустится
- неверная реализация findPosPointSets - при повторном появлении точки меньше treshold будет каждый раз создаваться новое пустое множество точек. Аналогично для findNegPointSets

Прочее:
- нет необходимости указывать coding: utf-8 в начале файла
- лучше объединить все классы в один модуль, нет смысла для каждого класса создавать модуль

А также:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# импортировать все не рекомендуется
from mdesign.Point import *
from mdesign.PointSet import *
# лучше так
from mdesign.Point import Point
from mdesign.PointSet import PointSet
 
# цикл в PointSet
for point in self._pointSet:
    sum = sum + point.getY()
# лучше использовать list comprehension и встроенную функцию sum
total = sum([p.getY() for p in self._pointSet])
# или даже использовать генератор вместо списка
total = sum(p.getY() for p in self._pointSet)

Использование datafame принятут за уши - используется как двумерный массив - создаете dataframe и потом в цикле идете по нему. Pandas и numpy предназначены для того, чтобы избегать циклов - так во-первых проще описывать алгоритм, а во-вторых ускоряется быстродействие, т.к. используется код numpy, написанный на C вместо питоне.

Про pandas в данной задаче отдельно надо много писать.

Добавлено через 12 минут
Решение с помощью dataframe должно выглядеть как-то так (не проверял код):

Python
1
2
3
4
5
6
7
8
9
10
import pandas as pd
import numpy as np
 
graph_df = ... dataframe со столбцами x и y, описывающий точки на графике
plane_df = ... dataframe со столбцами x и y, описывающий точки на плоскости
 
# для каждой искомой точки определяем соответствующую точку на графике (линейной интерполяцией)
y = np.interp(plane_df.x, graph_df.x, graph_df.y)
# отбираем точки, лежащие ниже графика и выше линии threshold
result = plane_df[(plane_df.y < y) & (plane_df.y > threshold)]

@vrm2 · 23.10.2019, 08:23

А если надо разбивать точки на области, ограниченные графиком и threshold, то так:

Python
1
2
3
4
5
6
7
8
9
# для каждой искомой точки определяем соответствующую точку на графике (линейной интерполяцией)
y = np.interp(plane_df.x, graph_df.x, graph_df.y)
# определяем, что точка лежит ниже графика и выше линии threshold
desired = (plane_df.y < y) & (plane_df.y > threshold)
# нумеруем группы точек
group_number = (desired != desired.shift()).cumsum()
# с каждой группой точек (group) делаем что-то полезное
for name, group in plane_df.groupby(group_number):
  ...

@Luca Brasi · 23.10.2019, 19:04 **[ТС]**

вопросов много, буду по немногу...

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

PointSetFactory на самом деле не Factory (он ничего не создает), а скорее Service. Поэтому - PointSetService. А еще лучше, что-то типа PointSplitService

чем отличается Service от тогоже Utils класса? по сути они оба статические...

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

- переменные _x и _y определены как переменные класса, а должны объявляться в __init__

а что не так с объявлением чеерз конструктор? Вообще убрать их как переменные класса?

Python
1
2
3
4
    def __init__(self, x, y):
 
        self._x = x
        self._y = y

@vrm2 · 23.10.2019, 21:40

Сообщение от Luca Brasi

чем отличается Service от тогоже Utils класса? по сути они оба статические...

Есть такой паттерн проектирования - Factory (фабрика), он описывает класс, которой создает объекты определенного типа на основе некоторых условий. Ваш класс такой фабрикой не является, поэтому не надо называть его фабрикой. Можно назвать Utils.

Сообщение от Luca Brasi

а что не так с объявлением чеерз конструктор? Вообще убрать их как переменные класса?

Через конструктор - все нормально (поля объекта). Но переменные x и y определены не только в конструкторе, но и на уровне класса (поля класса, это как статические поля класса в java). Не нужно объявлять одинаковые переменные и там, и там.

@vrm2 · 24.10.2019, 13:58

Python
1
2
3
4
5
6
7
class Point:
    _x = 0   # вот эти строчки лишние, они определяют поля
    _y = 0   # общие для всего класса (имеют одинаковые значения во всех объектах)
 
    def __init__(self, x, y):
        self._x = x   # а это "нормальные" поля (различаются для каждого объекта)
        self._y = y

Новые блоги и статьи Все статьи Все блоги /
Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .
Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .	Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при создании или изменении элементов справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной записи электронной. . .

@Luca Brasi 892 / 204 / 55 Регистрация: 06.11.2015 Сообщений: 2,288 Записей в блоге: 2

	Нахождение точек внутри фигуры 16.10.2019, 19:58. Показов 12980. Ответов 18 Метки нет (Все метки) Не хотелось бы изобретать велосипед, может есть более внятные способы нежели многократный проход циклами по точкам... Есть два набора точек. По одним строится график, а вторые просто в пространстве. По первому набору построить график, сделать пересечение графика с горизонтальной прямой. Далее внутри обьектов fig1 и fig2 - найти точки со второго набора. 0

@Alli_Lupin 5042 / 1069 / 149 Регистрация: 29.01.2013 Сообщений: 6,242
	17.10.2019, 10:42
	Luca Brasi, а как вы хотите решать задачу? просто или сложно? т.е. просто сперва посчитаете, сколько у вас фигур и какими точками они описаны, а потом будете каждую точку проверять по n условиям, или сперва сгруппируете точки по.. кхм, кучкам и потом уже будете анализировать эти кучки на вхождение в фигуру? 0

@Alli_Lupin 5042 / 1069 / 149 Регистрация: 29.01.2013 Сообщений: 6,242
	17.10.2019, 22:35
	Luca Brasi, у меня этот пакет не ставится сходу. Поздно уже экспериментировать.. Я бы просто математикой решал, но как-то лаконичного решения не получается. 0

@Alli_Lupin 5042 / 1069 / 149 Регистрация: 29.01.2013 Сообщений: 6,242
	17.10.2019, 23:58
	Luca Brasi, а какая функция у прямоугольника? 0

@Luca Brasi 892 / 204 / 55 Регистрация: 06.11.2015 Сообщений: 2,288 Записей в блоге: 2
	18.10.2019, 07:33 [ТС]
	Alli_Lupin, функция прямоугольника? Честно говоря не особо понял, ведь фунция следует привязыавть к конкретной кривой. Или Вы клоните в сторону какого то тайного метода вычисления... 0

@Alli_Lupin 5042 / 1069 / 149 Регистрация: 29.01.2013 Сообщений: 6,242
	19.10.2019, 19:19
	Luca Brasi, решили задачу? Это хорошо) 0

@Luca Brasi 892 / 204 / 55 Регистрация: 06.11.2015 Сообщений: 2,288 Записей в блоге: 2
	21.10.2019, 21:57 [ТС]
	Alli_Lupin, сделал некоторую объектную модель. Пришлось решать баанльными способами, т.к. они работают проще и точнее нежели эта методология shapely mdesign.zip Моя нынешняя задача свелась к нахождению лишь точек поверх кривой 0