Определить, если область пространства пуста

Question

У меня есть область пространства, 2 измерения, от (0,0) в (MAX_X, MAX_Y),

Внутри этой области пространства я рисую некоторые линии, они пересекают периметр области и могут пересекаться друг с другом. Таким образом, эти линии разделяют мою область пространства на субрегионы, которые, если их суммировать, дают всю область пространства.

Внутри этой области пространства есть несколько точек (x,y), Я должен определить

1. координаты всех вершин, составляющих все подобласти пространства, созданные линиями
2. если данный субрегион пространства содержит или нет одну или несколько точек

Я пытаюсь кодировать это в Java, но язык не очень важен. Я понятия не имею о том, как выполнить эти две задачи. Если кто-нибудь может дать мне подсказку, я действительно ценю это.

Answer 1

Это действительно довольно математический вопрос. Размышляя о проблеме, я предполагаю, что решение будет довольно сложным и / или дорогим (с точки зрения вычислений).

Вы начинаете со списка R субрегионов, начиная с одного элемента: всего региона. Затем вы перебираете список строк. Для каждой строки вы повторяете каждый R. Если линия пересекает область, вы делите ее на две части. Помощь по проверке пересечения линии и области должна быть легко доступна в сети. Просто найдите пересечения между линией и выпуклой областью. Проблема с этим алгоритмом состоит в том, что он будет иметь время выполнения около O(n^3). O(n) для n строк, умноженных на O (n), для областей, умноженных на O (n), для проверок пересечения (однако вы можете значительно ускорить эту последнюю часть, приведя вас к O(n^2) в конец).

Проверка того, какая из ваших областей содержит конкретную точку, является классической проблемой выпуклого анализа. Для этого должны быть доступны алгоритмы. Я думаю, что вы захотите сделать, это перебрать ваши линии и проверить, находится ли ваша точка "слева или справа" от этой линии. Если вы на первом шаге свяжете свои субрегионы со своими линиями, это даст вам соответствующий субрегион в O(n).

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

В основном, если вы хотите получить больше информации по предмету, который вы смотрите на выпуклый анализ.

Тем не менее, если все это вам не поможет, вы, вероятно, не в своей тарелке (не обижайтесь, здесь вы решаете очень сложную математику).

Answer 2

Это довольно сложная проблема вычислительной геометрии. Возможный подход может состоять в том, чтобы представить результирующие регионы посредством плоского подразделения исходного прямоугольника. Подразделение будет представлено двусвязным краевым списком (DCEL). Он состоит из списка направленных половин, списка областей (граней) и списка вершин (пересечений линий). Все эти данные полностью не связаны между собой, так что поиск любых данных по некоторым другим данным очень эффективен.

DCEL будет построен итеративно, начиная с одной области, которая является исходным прямоугольником, и добавляя одну строку за другой. Добавление линии означает сокращение текущего DCEL по этой линии и получение более усовершенствованного DCEL.

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

Хорошая книга по DCEL - это М. де Берг и др. Вычислительная геометрия. Вы также можете найти много ресурсов в Интернете. Вы также найдете реализации и различные пакеты программного обеспечения.