Точка, ближайшая к комбинированным геометрическим фигурам (составная фигура)

Question

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

Эти формы могут быть типа:

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

В приведенном ниже примере есть перевернутый круг (самый большой круг с серым вокруг него), кольцо (topleft), квадрат и линия. Если мы не рассматриваем линию, то оранжевая часть является формой, которую нужно ограничить. Если линия принимается во внимание, то насыщенная оранжевая часть линии является формой, которую необходимо ограничить.

Черные маленькие точки представляют точки, которые необходимо ограничить. Синие точки представляют желаемый результат. (a 1, b 2 и т. д.) Точка "f" не имеет соответствующего ограниченного результата, поскольку она уже находится в оранжевой области. Для целей этого примера только точка «e» ограничена линией, все остальные - оранжевой оранжевой областью.

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

Я нашел методы, которые близки к этому, но ни один из них я не смог бы объединить для создания вышеуказанных функций. Несколько похожих вопросов, которые я нашел:

Точки внутри полукруга Какой алгоритм я могу использовать для определения точек внутри полукруга?

Точка, ближайшая к MovieClip Вспышка: ближайшая точка к мувиклипу

Ближайшая точка через сумму Минковского (это сработает, если я смогу преобразовать составную фигуру в многоугольники) http://www.codezealot.org/archives/153

Выберите край полигона, ближайший к точке (аналогично приведенному выше) Для точки в неправильном многоугольнике, какой самый эффективный способ выбрать край, ближайший к точке?

PS: я заметил, что оранжевая область на некоторых экранах может выглядеть желтой. В любом случае это цветная область.

Answer 1

Давайте назовем I пересечением всех фигур, C контуром I, p точкой, которую вы хотите ограничить, и r точкой результата. У нас есть:

• Если p в I, то r = p
• Если p не в I, то r в C. Таким образом, r является ближайшей точкой в ​​C к p.

Так что я думаю, что вы должны сделать следующее:

1. Если p находится внутри всех фигур, вернуть p.
2. Вычислить контур C пересечения всех фигур, он определяется списком деталей (сегменты, дуги, ...).
3. Найдите ближайшую точку к p в каждой части C (вычисленной в 2.) и верните ближайшую точку среди них к p.

Answer 2

Это не очень хороший ответ, но он слишком длинный, чтобы вписаться в комментарий ...

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

НО

Область, в которой вы заинтересованы, строится путем объединения, пересечения и различия других областей, и поэтому не будет общей связи между ближайшими точками исходных фигур и ближайшими точками объединенной фигуры. Если вы понимаете, о чем я. Например, хотя ближайшая точка A union B является ближайшей к набору {closest point of A, closest point of B}, ближайшая точка A intersection B не является простой функцией этого же набора; по крайней мере, не для общего случая.

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

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

Answer 3

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

В случае ограничения круглой формы, перпендикулярная линия равна линии к ее центру.В случае ограничения формы линии, перпендикулярная линия - это (конечно) линия, перпендикулярная самой себе.В случае прямоугольника перпендикулярная линия - это линия, перпендикулярная ближайшему краю.(И то же самое теоретически для сложных ограничений многоугольника.)

Таким образом, новый подход (который мне еще предстоит проверить) будет состоять в следующем:

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

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

Если это не сработает, я еще раз взгляну на метод отсечения полигонов.Для этого подхода я наткнулся на этот полезный пост:
Вычислить объединение двух произвольных фигур
, где обрезка сложных многоугольников значительно упрощается с помощью http://code.google.com/p/gpcas/

Методсправедливо для всех случаев (все точки и их результаты) выше, а также для ряда других сценариев, которые мы тестировали (на бумаге).
Я попробую живую версию завтра на работе.