구현 인테리어 포인트

Question

,

를위한 최고의 자원 무엇

:

분석 + 내부 포인트 알고리즘의 실제 구현?

Answer 1

Boyd의 책을 가지고 있다면 CVXOPT에 대해 알고있을 것입니다. 그것 안에서보세요. 구현 세부 사항에 관심이 있다면 구현을 살펴 보는 것이 매우 중요합니다. 대부분의 복잡한 수치 알고리즘과 마찬가지로, 이전에 작성된 코드를 사용하여 직접 작성하는 것보다 훨씬 나아지게 될 것입니다. 선형 프로그래밍, SOCP, 2 차 프로그래밍, 볼록 프로그래밍 등을 위해 온라인에서 사용할 수있는 다른 많은 내부 포인트 구현이 있습니다. OOQP도 사용했으며 내부를 약간 보았습니다. 그것은 충분히 직설적이었습니다.

나는 Numerical Optimization의 초판을 좋아했다. 나는 후반부에 예측기 - 교정기 방법의 좋은, 아주 실용적인 개요를 가졌다. 두 번째 판은 비슷한 품질의 의심 할 여지가 없습니다.

Answer 2

두 가지 방법으로 그것을 구현할 수 있습니다 만 한 지점이있는 경우

, 당신은 다각형의 영역을 얻을 것이다 다음 확인 만약 verticle에서와 n 개의 삼각형의 면적의 합 점과 두 개의 연속 점에있는 다른 두 점은 다각형의 면적과 같습니다. 그것이 사실이라면 그 요점은 안쪽에 있고, 그렇지 않으면 바깥에 있습니다.

많은 포인트 (M 포인트라고 가정 해 봅시다)가 있고 내부에 있는지 알아야만 폴리곤 내부에 포인트가 생기고 그 지점에 버티클이있는 n 개의 삼각형으로 분할됩니다. 다른 두 개는 폴리곤에서 연속적으로 두 점 (가장자리를 이루는 점)을 가리 킵니다. 앞에서 선택했던 점에 verticle이 있고 다각형의 각 점에 점이있는 n 개의 선이 있습니다. 시계 방향으로 각도별로 정렬합니다. 그런 다음 M 포인트를 선택하고 다른 포인트는 M 포인트 중 하나를 선택합니다. 첫 번째 N과 같이 정렬합니다. 그러면 M의 각 점에 대해 o (N + M)에서 N에서 가장 가까운 왼쪽 및 오른쪽 선을 찾을 수 있습니다 (선이 CenterAx 및 CenterAy라고 가정 해 보겠습니다). , 삼각형 CenterAxAy에있는 점이 있는지 알아야합니다. 삼각형 인 경우 o (1)에서 할 수 있습니다. CenterAxAy가 면적 (CenterAxP) + 면적 (CenterAyP) + 면적 (AxAyP).

난 당신이 내가 여기에 쓴 것을 이해 바랍니다.