Простой алгоритм для пересечения полигона

Это может быть огромным приближением в зависимости от ваших полигонов, но вот один из вариантов:

• Вычислите центр масс для каждого многоугольника.
• Вычислите минимальное, максимальное или среднее расстояние от каждой точки многоугольника до центра масс.
• Если C1C2 (где C1/2 - центр первого/второго многоугольника) >= D1 + D2 (где D1/2 - расстояние, вычисленное для первого/второго многоугольника), то два многоугольника "пересекаются".

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

Вы не дали нам своего представления многоугольника. Поэтому я выбираю (скорее предлагаю) его для вас :)

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

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

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

Вы получите новый многоугольник по тому же представлению.

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

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

Вот простой и глупый подход: на входе дискретизируйте полигоны в битовую карту. Чтобы пересечься, AND битмапы вместе. Чтобы получить выходные полигоны, обведите неровные границы битмапа и сгладьте их с помощью алгоритма аппроксимации полигонов. (Я не помню, дает ли эта ссылка наиболее подходящие алгоритмы, это просто первая ссылка в Google. Вы можете проверить один из инструментов для преобразования растровых изображений в векторные. Может быть, вы сможете использовать их, не переделывая алгоритм?)

Самой сложной частью будет трассировка границ, я думаю.

Кстати, в начале 90-х я столкнулся с чем-то похожим на эту проблему на работе. Я ее замял: Я придумал (совершенно другой) алгоритм, который работал бы на координатах вещественных чисел, но, похоже, столкнулся с совершенно неисправимым множеством вырожденных случаев перед лицом реалий плавающей точки (и шумного ввода). Возможно, с помощью интернета у меня получилось бы лучше!

Если вы используете C++ и не хотите создавать алгоритм самостоятельно, вы можете использовать Boost.Geometry. В нем используется адаптированная версия алгоритма Вейлера-Атертона, упомянутого выше.

Не храните его вообще. Там много средств обработки кредитных карт. Если вы абсолютно не должны иметь эту функциональность в доме, не делайте этого.

• Amazon Payment Services: http://aws.amazon.com/fps/
• Платежные решения BrainTree: http://www.braintreepaymentsolutions.com/
• Начисление платы: http://chargify.com/
• Paypal: https://merchant.paypal.com/
• Авторизование.Net реселлеры: http://www.authorize.net/solutions/merchantsolutions/resellerdirectory/

Серьезно, примите решение.

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

Этот, определенно.

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

Кроме того, что последний использует дополнительную таблицу,

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

Пример использования кода аутентификации сообщений на основе HMAC (fancy hashing):

details= user_id+' '+token_expiry_timestamp
mac= hmac_sha2(server_secret, details)
token= details+' '+mac

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

user_id, token_expiry_timestamp, mac= token split on ' '
details= user_id+' '+token_expiry_timestamp
if hmac_sha2(server_secret, details)!=mac
    complain
else if token_expiry_timestamp<now
    complain
else
    allow password for user_id to be changed

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

Вот подход, основанный на триангуляции, который довольно прост в реализации и может быть сделан для запуска в O (N ² ).

BTW, O (N ² ) оптимален для этой проблемы. Представьте себе два многоугольника в форме лопастей вилки, пересекающихся под прямым углом. Каждый имеет число сегментов, пропорциональных числу зубцов; число многоугольников в пересечении пропорционально квадрату числа зубцов.

1. Сначала триангулируйте каждый многоугольник.

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

3. Вычислите соседей каждого треугольника, сравнивая их попарно, и создайте граф смежности. Этот граф будет содержать один связанный подграф для каждого многоугольника в пересечении P и Q.

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

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

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

У Алана Мерта есть полная реализация обрезки полигонов GPC.

Редактировать:

Другой подход заключается в том, чтобы сначала разделить каждый многоугольник на множество треугольников, с которыми легче работать. Теорема двух ушей Гэри Х. Мейстерса делает этот трюк. Эта страница в McGill хорошо объясняет деление на треугольники.