поиск действительных точек в 2d-пространстве с ограничениями на произвольные области

Question

У меня есть двумерное пространство двойной точности с областями (произвольно определенными, в основном, кружками), которые, так сказать, «недействительны», и я хотел бы получить ближайшую действительную точку, учитывая желаемый пункт назначения (который не ' должен быть действительным). Итак, до сих пор я пытался отойти от случая к случаю, избегая этих областей, но когда есть несколько ограничений (например, необходимость избегать 2-3 областей, которые близки / смешаны вместе), этот подход не работает. Я думал о каком-то поиске, но другая проблема - дискретизация пространства, так как эти регионы не будут им соответствовать.

Я надеялся, что вы, ребята, могли бы дать мне несколько советов о том, как решать такую ​​проблему, как эта. Связанный, но гораздо более простой случай будет this .

Спасибо!

Answer 1

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

Если регионы не пересекаются, вы можете объединить их в регионы. CGAL предоставляет библиотеки для двумерных логических значений (в частности, союзы).

Answer 2

Это в принципе невозможно, если только вы не можете наложить некоторые ограничения на эти недопустимые области.

Рассмотрите недопустимую область (или объединение областей) в форме большого нерегулярного шарика с крошечной крошечной валидой где-то внутри.,И предположим, что ваш пункт назначения находится внутри капли, рядом с точечным отверстием, так что желаемая точка фактически находится в точечном отверстии.Если единственный способ проверить этот BLOB-объект - это метод да / нет, чтобы проверить точку на достоверность, то единственный способ найти точечное отверстие - это исчерпывающий поиск, который будет длиться вечно.