Вопросы Теги

Как определить, является ли треугольник Delaunay внутренним или внешним?

Благодаря инструкциям, размещенным здесь, а также некоторым другим дополнениям, я создал автоматический скрипт, который компилирует последнюю библиотеку OpenSSL для Android с поддержкой: armeabi, armeabi-v7a, x86, x86_64 и arm64-v8a: 

#!/bin/bash -e
#@author Aleksandar Gotev (alex.gotev@mobimesh.it)
#Hints and code taken also from http://stackoverflow.com/questions/11929773/compiling-the-latest-openssl-for-android

if [ "$#" -ne 6 ]
then
    echo "Usage:"
    echo "./openssl-build    \\"
    echo "                  "
    echo
    echo "Supported target ABIs: armeabi, armeabi-v7a, x86, x86_64, arm64-v8a"
    echo
    echo "Example using GCC 4.8, NDK 10e, OpenSSL 1.0.2d and Android API 21 for armeabi-v7a."
    echo "./openssl-build /home/user/android-ndk-r10e \\"
    echo "                /home/user/openssl-1.0.2d \\"
    echo "                21 \\"
    echo "                armeabi-v7a \\"
    echo "                4.8 \\"
    echo "                /home/user/output/armeabi-v7a"
    exit 1
fi

NDK_DIR=$1
OPENSSL_BASE_FOLDER=$2
OPENSSL_TARGET_API=$3
OPENSSL_TARGET_ABI=$4
OPENSSL_GCC_VERSION=$5
OPENSSL_OUTPUT_PATH=$6

NDK_MAKE_TOOLCHAIN="$NDK_DIR/build/tools/make-standalone-toolchain.sh"
OPENSSL_TMP_FOLDER="/tmp/openssl"
rm -rf "$OPENSSL_TMP_FOLDER"
mkdir -p "$OPENSSL_TMP_FOLDER"
cp -r ${OPENSSL_BASE_FOLDER} ${OPENSSL_TMP_FOLDER}

function build_library {
    mkdir -p ${OPENSSL_OUTPUT_PATH}
    export PATH=$TOOLCHAIN_PATH:$PATH
    make && make install
    rm -rf ${OPENSSL_TMP_FOLDER}
    echo "Build completed! Check output libraries in ${OPENSSL_OUTPUT_PATH}"
}

if [ "$OPENSSL_TARGET_ABI" == "armeabi-v7a" ]
then
    ${NDK_MAKE_TOOLCHAIN} --platform=android-${OPENSSL_TARGET_API} \
                          --toolchain=arm-linux-androideabi-${OPENSSL_GCC_VERSION} \
                          --install-dir="${OPENSSL_TMP_FOLDER}/android-toolchain-arm"
    export TOOLCHAIN_PATH="${OPENSSL_TMP_FOLDER}/android-toolchain-arm/bin"
    export TOOL=arm-linux-androideabi
    export NDK_TOOLCHAIN_BASENAME=${TOOLCHAIN_PATH}/${TOOL}
    export CC=$NDK_TOOLCHAIN_BASENAME-gcc
    export CXX=$NDK_TOOLCHAIN_BASENAME-g++
    export LINK=${CXX}
    export LD=$NDK_TOOLCHAIN_BASENAME-ld
    export AR=$NDK_TOOLCHAIN_BASENAME-ar
    export RANLIB=$NDK_TOOLCHAIN_BASENAME-ranlib
    export STRIP=$NDK_TOOLCHAIN_BASENAME-strip
    export ARCH_FLAGS="-march=armv7-a -mfloat-abi=softfp -mfpu=vfpv3-d16"
    export ARCH_LINK="-march=armv7-a -Wl,--fix-cortex-a8"
    export CPPFLAGS=" ${ARCH_FLAGS} -fpic -ffunction-sections -funwind-tables -fstack-protector -fno-strict-aliasing -finline-limit=64 "
    export CXXFLAGS=" ${ARCH_FLAGS} -fpic -ffunction-sections -funwind-tables -fstack-protector -fno-strict-aliasing -finline-limit=64 -frtti -fexceptions "
    export CFLAGS=" ${ARCH_FLAGS} -fpic -ffunction-sections -funwind-tables -fstack-protector -fno-strict-aliasing -finline-limit=64 "
    export LDFLAGS=" ${ARCH_LINK} "
    cd ${OPENSSL_TMP_FOLDER}
    ./Configure android-armv7 --openssldir=${OPENSSL_OUTPUT_PATH}
    build_library

elif [ "$OPENSSL_TARGET_ABI" == "arm64-v8a" ]
then
    ${NDK_MAKE_TOOLCHAIN} --platform=android-${OPENSSL_TARGET_API} \
                          --toolchain=aarch64-linux-android-4.9 \
                          --install-dir="${OPENSSL_TMP_FOLDER}/android-toolchain-arm64"
    export TOOLCHAIN_PATH="${OPENSSL_TMP_FOLDER}/android-toolchain-arm64/bin"
    export TOOL=aarch64-linux-android
    export NDK_TOOLCHAIN_BASENAME=${TOOLCHAIN_PATH}/${TOOL}
    export CC=$NDK_TOOLCHAIN_BASENAME-gcc
    export CXX=$NDK_TOOLCHAIN_BASENAME-g++
    export LINK=${CXX}
    export LD=$NDK_TOOLCHAIN_BASENAME-ld
    export AR=$NDK_TOOLCHAIN_BASENAME-ar
    export RANLIB=$NDK_TOOLCHAIN_BASENAME-ranlib
    export STRIP=$NDK_TOOLCHAIN_BASENAME-strip
    export ARCH_FLAGS=
    export ARCH_LINK=
    export CPPFLAGS=" ${ARCH_FLAGS} -fpic -ffunction-sections -funwind-tables -fstack-protector -fno-strict-aliasing -finline-limit=64 "
    export CXXFLAGS=" ${ARCH_FLAGS} -fpic -ffunction-sections -funwind-tables -fstack-protector -fno-strict-aliasing -finline-limit=64 -frtti -fexceptions "
    export CFLAGS=" ${ARCH_FLAGS} -fpic -ffunction-sections -funwind-tables -fstack-protector -fno-strict-aliasing -finline-limit=64 "
    export LDFLAGS=" ${ARCH_LINK} "
    cd ${OPENSSL_TMP_FOLDER}
    ./Configure android --openssldir=${OPENSSL_OUTPUT_PATH}
    build_library

elif [ "$OPENSSL_TARGET_ABI" == "armeabi" ]
then
    ${NDK_MAKE_TOOLCHAIN} --platform=android-${OPENSSL_TARGET_API} \
                          --toolchain=arm-linux-androideabi-${OPENSSL_GCC_VERSION} \
                          --install-dir="${OPENSSL_TMP_FOLDER}/android-toolchain-arm"
    export TOOLCHAIN_PATH="${OPENSSL_TMP_FOLDER}/android-toolchain-arm/bin"
    export TOOL=arm-linux-androideabi
    export NDK_TOOLCHAIN_BASENAME=${TOOLCHAIN_PATH}/${TOOL}
    export CC=$NDK_TOOLCHAIN_BASENAME-gcc
    export CXX=$NDK_TOOLCHAIN_BASENAME-g++
    export LINK=${CXX}
    export LD=$NDK_TOOLCHAIN_BASENAME-ld
    export AR=$NDK_TOOLCHAIN_BASENAME-ar
    export RANLIB=$NDK_TOOLCHAIN_BASENAME-ranlib
    export STRIP=$NDK_TOOLCHAIN_BASENAME-strip
    export ARCH_FLAGS="-mthumb"
    export ARCH_LINK=
    export CPPFLAGS=" ${ARCH_FLAGS} -fpic -ffunction-sections -funwind-tables -fstack-protector -fno-strict-aliasing -finline-limit=64 "
    export CXXFLAGS=" ${ARCH_FLAGS} -fpic -ffunction-sections -funwind-tables -fstack-protector -fno-strict-aliasing -finline-limit=64 -frtti -fexceptions "
    export CFLAGS=" ${ARCH_FLAGS} -fpic -ffunction-sections -funwind-tables -fstack-protector -fno-strict-aliasing -finline-limit=64 "
    export LDFLAGS=" ${ARCH_LINK} "
    cd ${OPENSSL_TMP_FOLDER}
    ./Configure android --openssldir=${OPENSSL_OUTPUT_PATH}
    build_library

elif [ "$OPENSSL_TARGET_ABI" == "x86" ]
then
    ${NDK_MAKE_TOOLCHAIN} --platform=android-${OPENSSL_TARGET_API} \
                          --toolchain=x86-${OPENSSL_GCC_VERSION} \
                          --install-dir="${OPENSSL_TMP_FOLDER}/android-toolchain-x86"
    export TOOLCHAIN_PATH="${OPENSSL_TMP_FOLDER}/android-toolchain-x86/bin"
    export TOOL=i686-linux-android
    export NDK_TOOLCHAIN_BASENAME=${TOOLCHAIN_PATH}/${TOOL}
    export CC=$NDK_TOOLCHAIN_BASENAME-gcc
    export CXX=$NDK_TOOLCHAIN_BASENAME-g++
    export LINK=${CXX}
    export LD=$NDK_TOOLCHAIN_BASENAME-ld
    export AR=$NDK_TOOLCHAIN_BASENAME-ar
    export RANLIB=$NDK_TOOLCHAIN_BASENAME-ranlib
    export STRIP=$NDK_TOOLCHAIN_BASENAME-strip
    export ARCH_FLAGS="-march=i686 -msse3 -mstackrealign -mfpmath=sse"
    export ARCH_LINK=
    export CPPFLAGS=" ${ARCH_FLAGS} -fpic -ffunction-sections -funwind-tables -fstack-protector -fno-strict-aliasing -finline-limit=64 "
    export CXXFLAGS=" ${ARCH_FLAGS} -fpic -ffunction-sections -funwind-tables -fstack-protector -fno-strict-aliasing -finline-limit=64 -frtti -fexceptions "
    export CFLAGS=" ${ARCH_FLAGS} -fpic -ffunction-sections -funwind-tables -fstack-protector -fno-strict-aliasing -finline-limit=64 "
    export LDFLAGS=" ${ARCH_LINK} "
    cd ${OPENSSL_TMP_FOLDER}
    ./Configure android-x86 --openssldir=${OPENSSL_OUTPUT_PATH}
    build_library

elif [ "$OPENSSL_TARGET_ABI" == "x86_64" ]
then
    ${NDK_MAKE_TOOLCHAIN} --platform=android-${OPENSSL_TARGET_API} \
                          --toolchain=x86_64-4.9 \
                          --install-dir="${OPENSSL_TMP_FOLDER}/android-toolchain-x86_64"
    export TOOLCHAIN_PATH="${OPENSSL_TMP_FOLDER}/android-toolchain-x86_64/bin"
    export TOOL=x86_64-linux-android
    export NDK_TOOLCHAIN_BASENAME=${TOOLCHAIN_PATH}/${TOOL}
    export CC=$NDK_TOOLCHAIN_BASENAME-gcc
    export CXX=$NDK_TOOLCHAIN_BASENAME-g++
    export LINK=${CXX}
    export LD=$NDK_TOOLCHAIN_BASENAME-ld
    export AR=$NDK_TOOLCHAIN_BASENAME-ar
    export RANLIB=$NDK_TOOLCHAIN_BASENAME-ranlib
    export STRIP=$NDK_TOOLCHAIN_BASENAME-strip
    export CPPFLAGS=" ${ARCH_FLAGS} -fpic -ffunction-sections -funwind-tables -fstack-protector -fno-strict-aliasing -finline-limit=64 "
    export CXXFLAGS=" ${ARCH_FLAGS} -fpic -ffunction-sections -funwind-tables -fstack-protector -fno-strict-aliasing -finline-limit=64 -frtti -fexceptions "
    export CFLAGS=" ${ARCH_FLAGS} -fpic -ffunction-sections -funwind-tables -fstack-protector -fno-strict-aliasing -finline-limit=64 "
    export LDFLAGS=" ${ARCH_LINK} "
    cd ${OPENSSL_TMP_FOLDER}
    ./Configure linux-x86_64 --openssldir=${OPENSSL_OUTPUT_PATH}
    build_library

else
    echo "Unsupported target ABI: $OPENSSL_TARGET_ABI"
    exit 1
fi

Документы сценария: https://github.com/alexbbb/pjsip-android-builder#build-only-openssl

Проверка последней версии: https://github.com/alexbbb/pjsip-android-builder/blob/master/openssl-build

10
задан balint.miklos 26 January 2010 в 09:26
поделиться

4 ответа

This solution assumes that you have a data structure that represents the Delaunay triangulation using a "virtual infinite Delaunay vertex" the way CGAL does it (see details here).

The idea is to find the boundary Delaunay edges: the edges connecting two consecutive sample points; and then "flood" through the Delaunay triangulation to classify the Delaunay faces. One knows that the infinite vertex is exterior so one can classify its neighbors (and neighbors' neighbors, etc.) as exterior as long as one does not cross boundary edges. If one reaches a boundary edge one can simply mark the neighbor triangle as interior and continue similarly.

Input: set of points densely sampling of the boundary of a closed shape, which can even contain holes
Output: Voronoi diagram in the interior of the shape (approximation of the medial axis of the shape)

  1. Compute the Delaunay triangulation of your points
  2. Mark the Delaunay edges which connect two consecutive sample points. (See page 4-5 of this paper how you can do this with a local test on every Delaunay edge)
  3. Classify all infinite Delaunay faces as OUTSIDE and push them to a queue Q.
  4. While Q is not empty
    1. Delaunay face f = Pop from Q
    2. For every unclassified neighbor triangle t of f
      • if the Delaunay edge shared by t and f is marked, classify t as the opposite of f
      • else classify t the same like f
      • push t to Q
  5. For every Delaunay edge e
    • if the two neighbor Delaunay triangles d1, d2 are both classified as INTERIOR, output the segment connecting the circumcenter of d1 and d2.

For an input like this
sample points
the following medial axis approximation can be computed: medial axis

You can check out how this medial axis approximation behaves in practice using the free windows binary of Mesecina. Source code here.

12
ответ дан 3 December 2019 в 23:14
поделиться

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

Использование предложенного ими алгоритма для невыпуклого многоугольника показывает, что он не всегда восстанавливает реальную триангуляцию. http://www.cc.kyoto-su.ac.jp/~atsushi/Jun/Topics/Teddy/images/example2_2.jpg

0
ответ дан 3 December 2019 в 23:14
поделиться

Рассматривали ли вы использование другой формы триангуляции, которая не создает внешних треугольников? Однажды я прошел курс, на котором много времени уделялось обсуждению теоретических аспектов триангуляции полигонов. Может быть, беглый просмотр сайта курса даст вам некоторое представление? http://cgm.cs.mcgill.ca/~godfried/teaching/cg-web.html#triangulation

Редактировать: На самом деле, я просто подумал о другом. Если у вас уже есть многоугольник, который вы пытаетесь триангулировать, вы можете использовать теорему Грина. Теорема Грина использует периметр многоугольника для вычисления его площади! Что еще более важно, в этом случае вы можете определить, находится ли точка на одной стороне линии, или другое, глядя на знак области. На многоугольниках теорема Грина решает простую задачу вычитания. Итак, возьмите любую точку, которая, как вы ЗНАЕТЕ, находится внутри многоугольника, и вычислите площадь относительно каждого края многоугольника. Это говорит вам, на какой стороне каждой линии должна быть ваша точка. Теперь просто возьмите точку внутри каждого треугольника и проделайте то же самое. Если какой-либо из знаков неправильный, то перед вами внешний треугольник. (Примечание: в зависимости от формы вашего многоугольника это может не сработать. Это должно работать нормально для выпуклых многоугольников, но вогнутости могут вызвать дополнительные сложности.)

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

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

2
ответ дан 3 December 2019 в 23:14
поделиться

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

Почему бы просто не триангулировать многоугольник (используя монотонное разложение или что-то подобное), чтобы никогда не создавать никаких внешних треугольников? Я полагаю, что это может увеличить время выполнения (сначала выполнить триангуляцию за время O (nlogn), а затем создать триангуляцию Delaunay за время O (n ^ 2)), но может быть более быстрый способ сделать это.

0
ответ дан 3 December 2019 в 23:14
поделиться
Другие вопросы по тегам:

Похожие вопросы: