太線の描画アルゴリズム

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
反転スコープ
記事: 15
登録日時: 6年前
住所: 岐阜

太線の描画アルゴリズム

#1

投稿記事 by 反転スコープ » 5年前

質問失礼します。

3Dゲームで道路(太線)を生成するスクリプトを作成しています。
いきなり3Dで実装するのは難しいので、まずは2D平面上で実装してみたいと考えています。

考えているのは以下の処理です。
(1)任意の数の点群を与える (画像では(10,10),(10,20),(20,20)の三点)
(2)幅Wを指定する
(3)太線の端の部分だけを描画する (画像ではオレンジ色の2つ曲線)

最終的には3Dゲームでの道路ポリゴンの生成に使うので曲線の頂点をいくつか取得できるのが最終目標です。

アルゴリズムのヒントや参考URLでも構わないので教えて頂ける方がいらっしゃいましたら、ご返信よろしくお願いします。
道路質問2.png
道路質問2.png (30.48 KiB) 閲覧数: 16793 回

アバター
usao
記事: 1887
登録日時: 11年前

Re: 太線の描画アルゴリズム

#2

投稿記事 by usao » 5年前

(1)
>幅W
を満たすような折れ線のペアを作る.
手っ取り早い方法としては,
元々与えられた折れ線の頂点群を「各頂点位置における折れ線の法線方向に」W/2だけ移動させたデータを作ればいい.

(2)
できた2つの折れ線データを適当にスプラインとかで曲線化する.

アバター
usao
記事: 1887
登録日時: 11年前

Re: 太線の描画アルゴリズム

#3

投稿記事 by usao » 5年前

データの作成方法がどんな手段でも良いなら,最も楽な方法の1つは
「幅Wの線」を絵として描画してそこからデータ化すれば良いかと.
(カーブ形状が定まれば,そのカーブ上の全点において,直径Wの塗りつぶし円を描画すればいい)

反転スコープ(外出中)

Re: 太線の描画アルゴリズム

#4

投稿記事 by 反転スコープ(外出中) » 5年前

>>usaoさん
ご返信ありがとうございます。
おうちに帰ったらDXライブラリで試作してみます。

littlestream
記事: 48
登録日時: 7年前

Re: 太線の描画アルゴリズム

#5

投稿記事 by littlestream » 5年前

自分は乱数で48回ほどX,Y座標を求めて、前回のX,Y座標との直線を引く事で
カーブ(?)ではないですが、迷路っぽい感じのマップ生成が出来ました。
ソースは後で書きます。

littlestream
記事: 48
登録日時: 7年前

Re: 太線の描画アルゴリズム

#6

投稿記事 by littlestream » 5年前

<iframe width="560" height="315" src="https://www.youtube.com/embed/5YS6zJsFEAE" frameborder="0" allow="autoplay; encrypted-media" allowfullscreen></iframe>

ソースはムービーに書かれています。

反転スコープ
記事: 15
登録日時: 6年前
住所: 岐阜

Re: 太線の描画アルゴリズム

#7

投稿記事 by 反転スコープ » 5年前

>>littlestreamさん
ご返信ありがとうございます。
今回、作りたいのは太線の側の点群の取得ですのでやりたいこととはちょっと違うかもです。
(説明が下手でモウシワケナイ)
てかプチコンって、めちゃくちゃ懐かしいですね!

反転スコープ
記事: 15
登録日時: 6年前
住所: 岐阜

Re: 太線の描画アルゴリズム

#8

投稿記事 by 反転スコープ » 5年前

今日中に書き終わるつもりが終わりませんでした(汗)
ベクトルの計算とか高校生のとき以来なのでWEBを漁りながらでも時間がかかっちゃいますね

とりあえず出来たところまで、続きは明日やる予定です。

コード:

#include "DxLib.h"
#include <math.h>
#include <vector>

#define WIDTH 40

using namespace std;

enum {
	MOUSE_LEFT,
	MOUSE_RIGHT,
	MOUSE_MIDDLE,

	MOUSE_ALL
};

typedef struct {
	double x;
	double y;
}vector2;

int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nCmdShow)
{
	unsigned int mousePressingCount[MOUSE_ALL] = {{ 0 }};
	int mouseX, mouseY;

	vector<vector2> points;
	vector<vector2> plus90;
	vector<vector2> minus90;

	ChangeWindowMode(TRUE);
	SetBackgroundColor(255, 255, 255);

	if (DxLib_Init() == -1){	// DXライブラリ初期化処理
		return -1;				// エラーが起きたら直ちに終了
	}
	SetDrawScreen(DX_SCREEN_BACK);
	
	while (ProcessMessage() == 0 && ScreenFlip() == 0 && ClearDrawScreen() == 0){

		int mouseState = GetMouseInput();
		if(mouseState & MOUSE_INPUT_LEFT){		mousePressingCount[MOUSE_LEFT]++;}	else{mousePressingCount[MOUSE_LEFT] = 0;}
		if (mouseState & MOUSE_INPUT_RIGHT){	mousePressingCount[MOUSE_RIGHT]++;}	else{mousePressingCount[MOUSE_RIGHT] = 0;}
		if (mouseState & MOUSE_INPUT_MIDDLE){	mousePressingCount[MOUSE_MIDDLE]++;}else{mousePressingCount[MOUSE_MIDDLE] = 0;}
	
		DrawFormatString(0, 0, GetColor(0,0,0), "MouseLeftButton = %d", mousePressingCount[MOUSE_LEFT]);
		DrawFormatString(0, 20, GetColor(0, 0, 0), "MouseRightButton = %d", mousePressingCount[MOUSE_RIGHT]);
		DrawFormatString(0, 40, GetColor(0, 0, 0), "MouseMiddleButton = %d", mousePressingCount[MOUSE_MIDDLE]);

		if (mousePressingCount[MOUSE_LEFT] == 1) {
			GetMousePoint(&mouseX, &mouseY);
			vector2 buf = {mouseX, mouseY};
			points.push_back(buf);
			if (points.size() >= 2) {
				vector2 prevPoint = points[ points.size() - 2 ];
				vector2 currentPoint = points[ points.size() - 1 ];

				vector2 distance = {currentPoint.x - prevPoint.x, currentPoint.y - prevPoint.y};
				double magnitude = sqrt( pow(distance.x, 2.0) + pow(distance.y, 2.0) );
				vector2 unit = { distance.x / magnitude, distance.y / magnitude};

				vector2 plusAdd = {currentPoint.x + (-unit.y * (WIDTH / 2)), currentPoint.y + (unit.x * (WIDTH / 2)) };
				vector2 minusAdd = { currentPoint.x + (unit.y * (WIDTH / 2)), currentPoint.y + (-unit.x * (WIDTH / 2)) };
				plus90.push_back(plusAdd);
				minus90.push_back(minusAdd);

			}
		}

		if (mousePressingCount[MOUSE_RIGHT] == 1) {
			points.clear();
			plus90.clear();
			minus90.clear();
		}

		for(int i = 0; i < points.size(); i++){
			DrawCircle(points[i].x, points[i].y, 5, GetColor(0,0,0));
			DrawFormatString(0, i * 20 + 60, GetColor(0,0,0), "Points[%2d] = { %3d , %3d }", i , points[i].x, points[i].y);
		}

		for (int i = 0; i < plus90.size(); i++) {
			DrawCircle(plus90[i].x, plus90[i].y, 5, GetColor(100, 0, 0));
			DrawCircle(minus90[i].x, minus90[i].y, 5, GetColor(100, 0, 0));
		}
	}

	DxLib_End();				// DXライブラリ使用の終了処理

	return 0;				// ソフトの終了 
}
オフトピック
DXライブラリだけで作ろうとすると大変ですね。
unityの有り難味が身に沁みて分かる(unity2Dは使いづらすぎだが)

反転スコープ
記事: 15
登録日時: 6年前
住所: 岐阜

Re: 太線の描画アルゴリズム

#9

投稿記事 by 反転スコープ » 5年前

usao さんが書きました:
5年前
データの作成方法がどんな手段でも良いなら,最も楽な方法の1つは
「幅Wの線」を絵として描画してそこからデータ化すれば良いかと.
(カーブ形状が定まれば,そのカーブ上の全点において,直径Wの塗りつぶし円を描画すればいい)
あとからテクスチャを張るときに困難になりそう(なイメージ)なので第二候補として考えてみます。

かずま

Re: 太線の描画アルゴリズム

#10

投稿記事 by かずま » 5年前

反転スコープ さんが書きました:
5年前

コード:

			DrawFormatString(0, i * 20 + 60, GetColor(0,0,0), "Points[%2d] = { %3d , %3d }", i , points[i].x, points[i].y);
points[ i].x, points[ i].y は double ですから、
%3d ではなく、%5.1f にしたほうがよいのでは?

かずま

Re: 太線の描画アルゴリズム

#11

投稿記事 by かずま » 5年前

こんなの書いてみましたが、曲がるところの内側がダメですね。

コード:

#include "DxLib.h"
#include <vector>

#define WIDTH 40

using namespace std;

enum { MOUSE_LEFT, MOUSE_RIGHT, MOUSE_MIDDLE, MOUSE_ALL };

typedef struct { double x, y; } vector2;

int WINAPI WinMain(HINSTANCE hi, HINSTANCE pi, LPSTR cl, int cs)
{
	unsigned int mousePressingCount[MOUSE_ALL] = {{ 0 }};
	int color = GetColor(0, 0, 0), color2 = GetColor(255, 255, 255);
	vector<vector2> points;

	ChangeWindowMode(TRUE);
	SetBackgroundColor(255, 255, 255);
	if (DxLib_Init() == -1) return -1;
	SetDrawScreen(DX_SCREEN_BACK);
	
	while (!ProcessMessage() && !ScreenFlip() && !ClearDrawScreen()){
		int mouseState = GetMouseInput();
		if (mouseState & MOUSE_INPUT_LEFT) mousePressingCount[MOUSE_LEFT]++;
		else mousePressingCount[MOUSE_LEFT] = 0;
		if (mouseState & MOUSE_INPUT_RIGHT) mousePressingCount[MOUSE_RIGHT]++;
		else mousePressingCount[MOUSE_RIGHT] = 0;
		if (mouseState & MOUSE_INPUT_MIDDLE) mousePressingCount[MOUSE_MIDDLE]++;
		else mousePressingCount[MOUSE_MIDDLE] = 0;
	
		DrawFormatString(0, 0, color, "MouseLeftButton = %d",
			mousePressingCount[MOUSE_LEFT]);
		DrawFormatString(0, 20, color, "MouseRightButton = %d",
			mousePressingCount[MOUSE_RIGHT]);
		DrawFormatString(0, 40, color, "MouseMiddleButton = %d",
			mousePressingCount[MOUSE_MIDDLE]);

		if (mousePressingCount[MOUSE_LEFT] == 1) {
			int x, y;
			GetMousePoint(&x, &y);
			vector2 buf = { (double)x, (double)y };
			points.push_back(buf);
		}
		if (mousePressingCount[MOUSE_RIGHT] == 1) points.clear();
		for(int i = 0; i < points.size(); i++) {
			if (i > 0)
				DrawLine(points[i-1].x, points[i-1].y,
						points[i].x, points[i].y, color, WIDTH);
			DrawCircle(points[i].x, points[i].y, WIDTH/2-1, color, FALSE);
			DrawCircle(points[i].x, points[i].y, WIDTH/2-3, color2, FALSE);
			if (i > 0)
				DrawLine(points[i-1].x, points[i-1].y,
						points[i].x, points[i].y, color2, WIDTH-2);
			DrawFormatString(0, i * 20 + 60, color,
				"Points[%2d] = { %5.1f , %5.1f }", i, points[i].x, points[i].y);
		}
	}
	DxLib_End();
	return 0;
}

かずま

Re: 太線の描画アルゴリズム

#12

投稿記事 by かずま » 5年前

これでどうでしょうか?

コード:

		for(int i = 0; i < points.size(); i++) {
			DrawCircle(points[i].x, points[i].y, WIDTH/2-1, color, FALSE);
			if (i > 0) {
				DrawLine(points[i-1].x, points[i-1].y,
						points[i].x, points[i].y, color, WIDTH);
				DrawLine(points[i-1].x, points[i-1].y,
						points[i].x, points[i].y, color2, WIDTH-2);
			}
			if (i > 1)
				DrawLine(points[i-2].x, points[i-2].y,
						points[i-1].x, points[i-1].y, color2, WIDTH-2);
			DrawCircle(points[i].x, points[i].y, WIDTH/2-3, color2, FALSE);
			DrawFormatString(0, i * 20 + 60, color,
				"Points[%2d] = { %5.1f , %5.1f }", i, points[i].x, points[i].y);
		}

かずま

Re: 太線の描画アルゴリズム

#13

投稿記事 by かずま » 5年前

かずま さんが書きました:
5年前

コード:

			DrawCircle(points[i].x, points[i].y, WIDTH/2-3, color2, FALSE);
2つめの DrawCircle の最後の引数は、FALSE ではなく、TRUE にしてください。

アバター
usao
記事: 1887
登録日時: 11年前

Re: 太線の描画アルゴリズム

#14

投稿記事 by usao » 5年前

オフトピック
絵を描いてデータ化~ という話はあれですよ,
画像処理的手段で境界線の座標列を取得すればいいよね的な話.

かずま

Re: 太線の描画アルゴリズム

#15

投稿記事 by かずま » 5年前

太線の端の座標列を計算したいのですね。
曲がるところで曲線の座標はどうしましょうか?
とりあえず、曲線なしだとこうなりました。

コード:

#include "DxLib.h"
#include <math.h>
#include <vector>

#define WIDTH 40

using namespace std;

enum { MOUSE_LEFT, MOUSE_RIGHT, MOUSE_MIDDLE, MOUSE_ALL };

typedef struct { double x, y; } vector2;

int WINAPI WinMain(HINSTANCE hi, HINSTANCE pi, LPSTR cl, int cs)
{
	unsigned int mousePressingCount[MOUSE_ALL] = { 0 };

	vector<vector2> points, plus90, minus90;
	int color = GetColor(0, 0, 0), color2 = GetColor(100, 0, 0);

	ChangeWindowMode(TRUE);
	SetBackgroundColor(255, 255, 255);

	if (DxLib_Init() == -1) return -1;
	SetDrawScreen(DX_SCREEN_BACK);
	
	while (!ProcessMessage() && !ScreenFlip() && !ClearDrawScreen()) {
		int mouseState = GetMouseInput();
		if (mouseState & MOUSE_INPUT_LEFT) mousePressingCount[MOUSE_LEFT]++;
		else mousePressingCount[MOUSE_LEFT] = 0;
		if (mouseState & MOUSE_INPUT_RIGHT) mousePressingCount[MOUSE_RIGHT]++;
		else mousePressingCount[MOUSE_RIGHT] = 0;
		if (mouseState & MOUSE_INPUT_MIDDLE) mousePressingCount[MOUSE_MIDDLE]++;
		else mousePressingCount[MOUSE_MIDDLE] = 0;
	
		DrawFormatString(0, 0, color, "MouseLeftButton = %d",
				mousePressingCount[MOUSE_LEFT]);
		DrawFormatString(0, 20, color, "MouseRightButton = %d",
				mousePressingCount[MOUSE_RIGHT]);
		DrawFormatString(0, 40, color, "MouseMiddleButton = %d",
				mousePressingCount[MOUSE_MIDDLE]);

		if (mousePressingCount[MOUSE_LEFT] == 1) {
			int mouseX, mouseY;
			GetMousePoint(&mouseX, &mouseY);
			vector2 buf = { (double)mouseX, (double)mouseY };
			points.push_back(buf);
			int n = points.size();
			if (n == 1) {
				plus90.push_back(buf), minus90.push_back(buf);
			}
			if (n >= 2) {
				vector2 p1 = points[n - 1], p2 = points[n - 2];

				double dx = p1.x - p2.x, dy = p1.y - p2.y;

				double dist = sqrt(dx * dx + dy * dy);

				double ux = dx / dist * (WIDTH / 2);
				double uy = dy / dist * (WIDTH / 2);

				vector2 plus1 = { p1.x - uy, p1.y + ux };
				vector2 minus1 = { p1.x + uy, p1.y - ux };
				plus90.push_back(plus1);
				minus90.push_back(minus1);

				vector2 plus = { plus1.x - dx, plus1.y - dy };

				if (n == 2) {
					plus90[n-2] = plus;
					minus90[n-2] = { p2.x*2 - plus.x, p2.y*2 - plus.y };
				}
				else {  // n >= 3
					double x, y;
					vector2 plus2 = plus90[n - 2];
					vector2 plus3 = plus90[n - 3];
					if (plus3.x == plus2.x || plus1.x == plus.x) {
						x = (plus.x + plus2.x) / 2;
						y = (plus.y + plus2.y) / 2;
					}
					else  {
						double m2 = (plus3.y - plus2.y) / (plus3.x - plus2.x);
						double m0 = (plus1.y - plus.y) / (plus1.x - plus.x);
						if (m2 == m0) {
							x = (plus.x + plus2.x) / 2;
							y = (plus.y + plus2.y) / 2;
						}
						else {
							x = (plus.y - plus2.y
								+ m2 * plus2.x - m0 * plus.x) / (m2 - m0);
							y = m0 * (x - plus.x) + plus.y;
						}
					}
					plus90[n-2] = { x, y };
					minus90[n-2] = {
						p2.x*2 - plus90[n-2].x, p2.y*2 - plus90[n-2].y };
				}
			}
		}
		if (mousePressingCount[MOUSE_RIGHT] == 1) {
			points.clear(), plus90.clear(), minus90.clear();
		}
		for(int i = 0; i < points.size(); i++){
			DrawCircle(points[i].x, points[i].y, 5, color);
			DrawFormatString(0, i * 20 + 60, color,
				"Points[%2d] = { %5.1f, %5.1f }", i , points[i].x, points[i].y);
		}
		for (int i = 0; i < points.size(); i++) {
			DrawCircle(plus90[i].x, plus90[i].y, 5, color2);
			DrawCircle(minus90[i].x, minus90[i].y, 5, color2);
			if (i > 0) {
				DrawLine(plus90[i-1].x, plus90[i-1].y,
					plus90[i].x, plus90[i].y, color);
				DrawLine(minus90[i-1].x, minus90[i-1].y,
					minus90[i].x, minus90[i].y, color);
			}
		}
	}
	DxLib_End();
	return 0;
}

反転スコープ
記事: 15
登録日時: 6年前
住所: 岐阜

Re: 太線の描画アルゴリズム

#16

投稿記事 by 反転スコープ » 5年前

>>かずまさん
なんかもう出来てる! 
そうです! 作りたかった動作はまさにコレです!

意味が分かる処理にはコメントをつけて自分なりに理解したのですが、
途中からどんな処理をしているのかさっぱりになってしまいました。
私は法線や単位ベクトルなどを昨日、知ったばかりのズブの素人です。

もしよろしければどんな処理をしているのか教えてもらえませんか?
(「正規化」などの数学用語?みたいな検索の足掛かりが欲しいなと)

コード:

		if (mousePressingCount[MOUSE_LEFT] == 1) {
			int mouseX, mouseY;
			GetMousePoint(&mouseX, &mouseY);
			vector2 buf = { (double)mouseX, (double)mouseY };
			points.push_back(buf);	//クリックした点を太線中心線の点群に加える
			int n = points.size();	//点群の数

			//点が1個しか無かったら、とりあえずクリックしたとこと同じ点をぶちこんどく
			if (n == 1) {
				plus90.push_back(buf), minus90.push_back(buf);
			}

			//点が2個以上あったら
			if (n >= 2) {
				//今クリックした点をp1とする。 前回クリックした点をp2とする。
				vector2 p1 = points[n - 1], p2 = points[n - 2];
				//x座標とy座標の差をそれぞれ求める。
				double dx = p1.x - p2.x, dy = p1.y - p2.y;
				//三平方の定理で2点間の距離を出す。
				double dist = sqrt(dx * dx + dy * dy);
				//正規化した後、道幅の分だけ長くする。
				double ux = dx / dist * (WIDTH / 2);
				double uy = dy / dist * (WIDTH / 2);
				//p1の±90度回転した点を太線外形線の点群に加える
				vector2 plus1 = { p1.x - uy, p1.y + ux };
				vector2 minus1 = { p1.x + uy, p1.y - ux };
				plus90.push_back(plus1);
				minus90.push_back(minus1);

				//ここから先が分からない(;_;)
				vector2 plus = { plus1.x - dx, plus1.y - dy };

				if (n == 2) {
					plus90[n - 2] = plus;
					minus90[n - 2] = { p2.x * 2 - plus.x, p2.y * 2 - plus.y };
				}
				else {  // n >= 3
					double x, y;
					vector2 plus2 = plus90[n - 2];
					vector2 plus3 = plus90[n - 3];
					if (plus3.x == plus2.x || plus1.x == plus.x) {
						x = (plus.x + plus2.x) / 2;
						y = (plus.y + plus2.y) / 2;
					}
					else {
						double m2 = (plus3.y - plus2.y) / (plus3.x - plus2.x);
						double m0 = (plus1.y - plus.y) / (plus1.x - plus.x);
						if (m2 == m0) {
							x = (plus.x + plus2.x) / 2;
							y = (plus.y + plus2.y) / 2;
						}
						else {
							x = (plus.y - plus2.y
								+ m2 * plus2.x - m0 * plus.x) / (m2 - m0);
							y = m0 * (x - plus.x) + plus.y;
						}
					}
					plus90[n - 2] = { x, y };
					minus90[n - 2] = {
						p2.x * 2 - plus90[n - 2].x, p2.y * 2 - plus90[n - 2].y };
				}
			}
		}

かずま

Re: 太線の描画アルゴリズム

#17

投稿記事 by かずま » 5年前

コード:

	vector2 plus = { plus1.x - dx, plus1.y - dy };
これは次のように書いても同じです。
	vector2 plus = { p2.x - uy, p2.y + ux };
さらに
	vector2 mins = { minus1.x - dx, minus1.y - dy };
または
	vector2 minus = { p2.x + uy, p2.y - ux };
と書くと、線分[p1,p2] を太線にした長方形[plus1,plus,minus,minus1] ができます。

線分[p2,p3] を太線にした台形[plus2,plus3,minus3,minus2] は既にあります。
台形というのは、線分[plus3,minus3] は線分[p2,p3]とは直交しないからです。
図を書いてくださいね。

さて、点p2 のところで、plus と plus2 を統合して新たな plus2 にしないといけません。

コード:

	if (n == 2) {
		plus90[n-2] = plus;
		minus90[n-2] = { p2.x*2 - plus.x, p2.y*2 - plus.y };
	}
これは、次のように書いても同じです。
	if (n == 2) {
		plus90[0] = plus;
		minus90[0] = minus;
	}
n == 2 なら、線分[p1,p2] は最初の 1本の線です。

p2 は 線分[plus,minus] の中点ですから、
    p2.x = (plus.x + minus.x) / 2
    p2.y = (plus.y + minus.y) / 2

点p2 と点plus が分かっていたら、点minusの座標は次の式で求まります。
    minus.x = p2.x * 2 - plus.x
    minus.y = p2.y * 2 - plus.y

コード:

	else {  // n >= 3
		double x, y;    // ★ これから求める plus2 の座標。
		vector2 plus2 = plus90[n - 2];  // ★ 既に存在する plus2
		vector2 plus3 = plus90[n - 3];
		if (plus3.x == plus2.x || plus1.x == plus.x) {
			x = (plus.x + plus2.x) / 2;
			y = (plus.y + plus2.y) / 2;
		}
		else  {
			double m2 = (plus3.y - plus2.y) / (plus3.x - plus2.x);
			double m0 = (plus1.y - plus.y) / (plus1.x - plus.x);
m2 は、直線[plus2,plus3]の傾き
m0 は、直線[plus,plus1]の傾き

コード:

傾きを求めるとき、分母が 0 では困るので、
		if (plus3.x == plus2.x || plus1.x == plus.x) {
でチェックしています。でも、このとき plus と plus2 の中点を
求めていますが、これは間違いです。説明は後で。

			if (m2 == m0) {
				x = (plus.x + plus2.x) / 2;
				y = (plus.y + plus2.y) / 2;
			}
傾きが同じ場合は、実は、plus と plus2 は同じ点なので
				x = plus.x;
				y = plus.y;
と書けば済んだのですが、書いたとき気が付かず、中点にしてしまいました。
直線[plus,plus1] と直線[plus2,plus3] の交点(x,y)を求めましょう。

直線[plus,plus1] と直線[plus2,plus3] の方程式は、

コード:

    y = m0 * (x - plus.x) + plus.y
    y = m2 * (x - plus2.x) + plus2.y
これを解いて、

コード:

	else {
		x = (plus.y - plus2.y
			+ m2 * plus2.x - m0 * plus.x) / (m2 - m0);
		y = m0 * (x - plus.x) + plus.y;
	}

	plus90[n-2] = { x, y };   // ★ plus2 が更新されました。

点p2 は、点plus2 と点minus2 の中点ですから。
	minus90[n-2] = {
		p2.x*2 - plus90[n-2].x, p2.y*2 - plus90[n-2].y };
これは、次のように書いても同じでした。
	minus90[n-2] = { p2.x*2 - x, p2.y*2 - y };

かずま

Re: 太線の描画アルゴリズム

#18

投稿記事 by かずま » 5年前

直線の方程式の形を変えて、場合分けを減らしてみました。

コード:

		if (mousePressingCount[MOUSE_LEFT] == 1) {
			int mouseX, mouseY;
			GetMousePoint(&mouseX, &mouseY);
			vector2 buf = { (double)mouseX, (double)mouseY };
			points.push_back(buf);

			int n = points.size();
			if (n == 1)
				plus90.push_back(buf), minus90.push_back(buf);
			else if (n >= 2) {
				vector2 p1 = points[n - 1], p2 = points[n - 2];

				double dx = p1.x - p2.x, dy = p1.y - p2.y;
				double dist = sqrt(dx * dx + dy * dy);

				double ux = dx / dist * (WIDTH / 2);
				double uy = dy / dist * (WIDTH / 2);

				vector2 P1 = { p1.x - uy, p1.y + ux };
				vector2 M1 = { p1.x + uy, p1.y - ux };
				vector2 P0 = { p2.x - uy, p2.y + ux };
				vector2 M0 = { p2.x + uy, p2.y - ux };

				plus90.push_back(P1), minus90.push_back(M1);

				if (n == 2)
					plus90[0] = P0, minus90[0] = M0;
				else {  // n >= 3
					vector2 P2 = plus90[n - 2], P3 = plus90[n - 3];

					double x10 = P1.x - P0.x, y10 = P1.y - P0.y;
					double x32 = P3.x - P2.x, y32 = P3.y - P2.y;

					double k0 = P0.y * x10 - P0.x * y10;
					double k2 = P2.y * x32 - P2.x * y32;
					double x, y, k = x10 * y32 - x32 * y10;

					if (k == 0)
						x = P0.x, y = P0.y;
					else
						x = (x32 * k0 - x10 * k2) / k,
						y = (y32 * k0 - y10 * k2) / k;
					plus90[n - 2] = { x, y };
					minus90[n - 2] = { p2.x*2 - x, p2.y*2 - y };
				}
			}
		}

コード:

点P0(x0,y0), P1(x1,y1), p2(x2,y2), P3(x3,y3) があると、
直線[P1,P0] と 直線[P3,P2] の方程式は、
	(y - y0)(x1 - x0) = (x - x0)(y1 - y0)
	(y - y2)(x3 - x2) = (x - x2)(y3 - y2)
連立方程式の解は、交点の座標で、
	x = {k0(x3 - x2) - k2(x1 - x0)} / k
	y = {k0(y3 - y2) - k2(y1 - y0)} / k
ただし、
	k0 = y0(x1 - x0) - x0(y1 - y0)
	k2 = y2(x3 - x2) - x2(y3 - y2)
	k = (x1 - x0)(y3 - y2) - (x3 - x2)(y1 - y0)

かずま

Re: 太線の描画アルゴリズム

#19

投稿記事 by かずま » 5年前

曲がるとき、外側の角を落とすようにしました。
曲線にはしていません。

コード:

#include "DxLib.h"
#include <math.h>
#include <vector>

#define WIDTH 40

using namespace std;

enum { MOUSE_LEFT, MOUSE_RIGHT, MOUSE_MIDDLE, MOUSE_ALL };

struct vector2 { double x, y; };
struct Node { vector2 P, A, B, C, D, E, F; };

int WINAPI WinMain(HINSTANCE hi, HINSTANCE pi, LPSTR cl, int cs)
{
	unsigned int mousePressingCount[MOUSE_ALL] = { 0 };

	vector<Node> nodes;
	int color = GetColor(0, 0, 0), color2 = GetColor(100, 0, 0);

	ChangeWindowMode(TRUE);
	SetBackgroundColor(255, 255, 255);

	if (DxLib_Init() == -1) return -1;
	SetDrawScreen(DX_SCREEN_BACK);
	
	while (!ProcessMessage() && !ScreenFlip() && !ClearDrawScreen()) {
		int mouseState = GetMouseInput();
		if (mouseState & MOUSE_INPUT_LEFT) mousePressingCount[MOUSE_LEFT]++;
		else mousePressingCount[MOUSE_LEFT] = 0;
		if (mouseState & MOUSE_INPUT_RIGHT) mousePressingCount[MOUSE_RIGHT]++;
		else mousePressingCount[MOUSE_RIGHT] = 0;
		if (mouseState & MOUSE_INPUT_MIDDLE) mousePressingCount[MOUSE_MIDDLE]++;
		else mousePressingCount[MOUSE_MIDDLE] = 0;
	
		DrawFormatString(0, 0, color, "MouseLeftButton = %d",
				mousePressingCount[MOUSE_LEFT]);
		DrawFormatString(0, 20, color, "MouseRightButton = %d",
				mousePressingCount[MOUSE_RIGHT]);
		DrawFormatString(0, 40, color, "MouseMiddleButton = %d",
				mousePressingCount[MOUSE_MIDDLE]);

		if (mousePressingCount[MOUSE_LEFT] == 1) {
			int mouseX, mouseY;
			GetMousePoint(&mouseX, &mouseY);
			Node node = { (double)mouseX, (double)mouseY, };
			nodes.push_back(node);

			int n = nodes.size();
			if (n >= 2) {
				Node &n1 = nodes[n - 1], &n2 = nodes[n - 2];
				double dx = n1.P.x - n2.P.x, dy = n1.P.y - n2.P.y;
				double dist = sqrt(dx * dx + dy * dy);
				double ux = dx / dist * (WIDTH / 2);
				double uy = dy / dist * (WIDTH / 2);
				n1.A = { n1.P.x - uy, n1.P.y + ux };
				n1.B = { n1.P.x + uy, n1.P.y - ux };
				n2.C = { n2.P.x - uy, n2.P.y + ux };
				n2.D = { n2.P.x + uy, n2.P.y - ux };

				if (n == 2) {
					n1.E = n1.A, n1.F = n1.B;
					n2.A = n2.E = n2.C, n2.B = n2.F = n2.D;
				}
				else  {  // n >= 3
					n1.E = n1.C = n1.A, n1.F = n1.D = n1.B;
					Node &n2 = nodes[n - 2], &n3 = nodes[n - 3];
					double x12 = n1.A.x - n2.C.x, y12 = n1.A.y - n2.C.y;
					double x32 = n3.C.x - n2.C.x, y32 = n3.A.y - n2.A.y;
					double k1 = n2.C.y * x12 - n2.C.x * y12;
					double k3 = n2.A.y * x32 - n2.A.x * y32;
					double x, y, k = x12 * y32 - x32 * y12;
					if (k == 0)
						x = n1.C.x, y = n1.C.y;
					else {
						x = (x32 * k1 - x12 * k3) / k;
						y = (y32 * k1 - y12 * k3) / k;
					}
					n2.E = { x, y };
					n2.F = { n2.P.x*2 - x, n2.P.y*2 - y };
				}
			}
		}
		if (mousePressingCount[MOUSE_RIGHT] == 1) nodes.clear();

		for(int i = 0; i < nodes.size(); i++){
			DrawCircle(nodes[i].P.x, nodes[i].P.y, 5, color);
			DrawFormatString(0, i * 20 + 60, color,
				"P[%2d] = { %5.1f, %5.1f }", i, nodes[i].P.x, nodes[i].P.y);
		}
		for (int i = 0; i < nodes.size(); i++) {
			Node &n0 = nodes[i], &n1 = nodes[i-1];

			DrawCircle(n0.E.x, n0.E.y, 5, color2);
			DrawCircle(n0.F.x, n0.F.y, 5, color2);

			if (i > 0) {
				vector2 a1, b1, a0, b0, c1, d1;

				if ((n1.B.y - n1.A.y) * (n1.D.x - n1.C.x) >
						(n1.B.x - n1.A.x) * (n1.D.y - n1.C.y))
					a1 = n1.C, b1 = n1.F, c1 = n1.A, d1 = n1.C;
				else
					a1 = n1.E, b1 = n1.D, c1 = n1.B, d1 = n1.D;

				if ((n0.B.y - n0.A.y) * (n0.D.x - n0.C.x) >
						(n0.B.x - n0.A.x) * (n0.D.y - n0.C.y))
					a0 = n0.A, b0 = n0.F;
				else
					a0 = n0.E, b0 = n0.B;

				DrawLine(a1.x, a1.y, a0.x, a0.y, color);
				DrawLine(b1.x, b1.y, b0.x, b0.y, color);
				DrawLine(c1.x, c1.y, d1.x, d1.y, color);
			}
		}
	}
	DxLib_End();
	return 0;
}

かずま

Re: 太線の描画アルゴリズム

#20

投稿記事 by かずま » 5年前

かずま さんが書きました:
5年前
曲がるとき、外側の角を落とすようにしました。

コード:

					double x32 = n3.C.x - n2.C.x, y32 = n3.A.y - n2.A.y;
すみません。間違いがありました。次のように訂正します。

コード:

					double x32 = n3.C.x - n2.A.x, y32 = n3.C.y - n2.A.y;
さらに、点が線分の端に表示されるように修正しました。

コード:

#include "DxLib.h"
#include <math.h>
#include <vector>

#define WIDTH 40

using namespace std;

enum { MOUSE_LEFT, MOUSE_RIGHT, MOUSE_MIDDLE, MOUSE_ALL };

struct vector2 { double x, y; };
struct Node { vector2 P, A, B, C, D, E, F; };

int WINAPI WinMain(HINSTANCE hi, HINSTANCE pi, LPSTR cl, int cs)
{
	unsigned int mousePressingCount[MOUSE_ALL] = { 0 };

	vector<Node> nodes;
	int color = GetColor(0, 0, 0);

	ChangeWindowMode(TRUE);
	SetBackgroundColor(255, 255, 255);

	if (DxLib_Init() == -1) return -1;
	SetDrawScreen(DX_SCREEN_BACK);
	
	while (!ProcessMessage() && !ScreenFlip() && !ClearDrawScreen()) {
		int mouseState = GetMouseInput();
		if (mouseState & MOUSE_INPUT_LEFT) mousePressingCount[MOUSE_LEFT]++;
		else mousePressingCount[MOUSE_LEFT] = 0;
		if (mouseState & MOUSE_INPUT_RIGHT) mousePressingCount[MOUSE_RIGHT]++;
		else mousePressingCount[MOUSE_RIGHT] = 0;
		if (mouseState & MOUSE_INPUT_MIDDLE) mousePressingCount[MOUSE_MIDDLE]++;
		else mousePressingCount[MOUSE_MIDDLE] = 0;
	
		DrawFormatString(0, 0, color, "MouseLeftButton = %d",
				mousePressingCount[MOUSE_LEFT]);
		DrawFormatString(0, 20, color, "MouseRightButton = %d",
				mousePressingCount[MOUSE_RIGHT]);
		DrawFormatString(0, 40, color, "MouseMiddleButton = %d",
				mousePressingCount[MOUSE_MIDDLE]);

		if (mousePressingCount[MOUSE_LEFT] == 1) {
			int mouseX, mouseY;
			GetMousePoint(&mouseX, &mouseY);
			Node node = { (double)mouseX, (double)mouseY, };
			nodes.push_back(node);

			int n = nodes.size();
			if (n >= 2) {
				Node &n1 = nodes[n - 1], &n2 = nodes[n - 2];
				double dx = n1.P.x - n2.P.x, dy = n1.P.y - n2.P.y;
				double dist = sqrt(dx * dx + dy * dy);
				double ux = dx / dist * (WIDTH / 2);
				double uy = dy / dist * (WIDTH / 2);
				n1.A = { n1.P.x - uy, n1.P.y + ux };
				n1.B = { n1.P.x + uy, n1.P.y - ux };
				n2.C = { n2.P.x - uy, n2.P.y + ux };
				n2.D = { n2.P.x + uy, n2.P.y - ux };

				if (n == 2) {
					n1.E = n1.A, n1.F = n1.B;
					n2.A = n2.E = n2.C, n2.B = n2.F = n2.D;
				}
				else  {  // n >= 3
					n1.E = n1.C = n1.A, n1.F = n1.D = n1.B;
					Node &n2 = nodes[n - 2], &n3 = nodes[n - 3];
					double x12 = n1.A.x - n2.C.x, y12 = n1.A.y - n2.C.y;
					double x32 = n3.C.x - n2.A.x, y32 = n3.C.y - n2.A.y;
					double k1 = n2.C.y * x12 - n2.C.x * y12;
					double k3 = n2.A.y * x32 - n2.A.x * y32;
					double x, y, k = x12 * y32 - x32 * y12;
					if (k == 0)
						x = n1.C.x, y = n1.C.y;
					else {
						x = (x32 * k1 - x12 * k3) / k;
						y = (y32 * k1 - y12 * k3) / k;
					}
					n2.E = { x, y };
					n2.F = { n2.P.x*2 - x, n2.P.y*2 - y };
				}
			}
		}
		if (mousePressingCount[MOUSE_RIGHT] == 1) nodes.clear();

		for (int i = 0; i < nodes.size(); i++) {
			int color2 = GetColor(100, 0, 0), color3 = GetColor(224, 128, 0);
			Node &n0 = nodes[i], &n1 = nodes[i-1];
			DrawFormatString(0, i * 20 + 60, color,
				"P[%2d] = { %5.1f, %5.1f }", i, n0.P.x, n0.P.y);
			DrawCircle(n0.P.x, n0.P.y, 3, color);

			if (i > 0) {
				vector2 a0, b0, a1, b1, c1, d1;

				if ((n1.B.y - n1.A.y) * (n1.D.x - n1.C.x) >
						(n1.B.x - n1.A.x) * (n1.D.y - n1.C.y))
					a1 = n1.C, b1 = n1.F, c1 = n1.A, d1 = n1.C;
				else
					a1 = n1.E, b1 = n1.D, c1 = n1.B, d1 = n1.D;

				if ((n0.B.y - n0.A.y) * (n0.D.x - n0.C.x) >
						(n0.B.x - n0.A.x) * (n0.D.y - n0.C.y))
					a0 = n0.A, b0 = n0.F;
				else
					a0 = n0.E, b0 = n0.B;

				DrawLine(a1.x, a1.y, a0.x, a0.y, color3, 2);
				DrawLine(b1.x, b1.y, b0.x, b0.y, color3, 2);
				DrawLine(c1.x, c1.y, d1.x, d1.y, color3, 2);
				DrawCircle(a0.x, a0.y, 3, color2);
				DrawCircle(b0.x, b0.y, 3, color2);
				DrawCircle(a1.x, a1.y, 3, color2);
				DrawCircle(b1.x, b1.y, 3, color2);
				DrawCircle(c1.x, c1.y, 3, color2);
			}
		}
	}
	DxLib_End();
	return 0;
}

アバター
usao
記事: 1887
登録日時: 11年前

Re: 太線の描画アルゴリズム

#21

投稿記事 by usao » 5年前

元の折れ線データ(緑)からスプライン曲線(赤)作って,
それを適当に両側に移動(青と紫)…
添付ファイル GoodPtn.png がありません
…とか思ってたら,こういうことかー!
GoodPtn.png
一見,まぁ良さそうだが…
GoodPtn.png (10.28 KiB) 閲覧数: 16480 回

アバター
usao
記事: 1887
登録日時: 11年前

Re: 太線の描画アルゴリズム

#22

投稿記事 by usao » 5年前

サイト重すぎの影響か?
文章と添付ファイルが中途半端にしか投稿されてないやん.なんだこれ.

ダメなパターンはこうなる.
BadPtn.png
BadPtn.png (10.27 KiB) 閲覧数: 16478 回

アバター
usao
記事: 1887
登録日時: 11年前

Re: 太線の描画アルゴリズム

#23

投稿記事 by usao » 5年前

ヒャッハー! プランBだー!
画像処理していいなら,なんとなく丸められるよね.
ImgProc.png
OpenCVでおk
ImgProc.png (10.15 KiB) 閲覧数: 16475 回

アバター
usao
記事: 1887
登録日時: 11年前

Re: 太線の描画アルゴリズム

#24

投稿記事 by usao » 5年前

カーブが極端にきつい個所の内側はどうなるのが正解なのだろう?
HairpinCurve.png
滑らかさを求めるとすごく幅広になるよね
HairpinCurve.png (6.42 KiB) 閲覧数: 16473 回

アバター
いわん
記事: 30
登録日時: 8年前

Re: 太線の描画アルゴリズム

#25

投稿記事 by いわん » 5年前

曲率の限界を決めて鋭角のところは外に広がるようにすれば自然な形になるかも。
どうやって計算したらいいか分かりませんけど(;^_^A

結城紬
記事: 42
登録日時: 6年前

Re: 太線の描画アルゴリズム

#26

投稿記事 by 結城紬 » 5年前

聞いた話では、道路の曲線は直線と円弧をクロソイド曲線でつないだ形になっているそうですね。
https://ja.wikipedia.org/wiki/%E3%82%AF ... 2%E7%B7%9A

反転スコープ
記事: 15
登録日時: 6年前
住所: 岐阜

Re: 太線の描画アルゴリズム

#27

投稿記事 by 反転スコープ » 5年前

風邪でダウンしてて返信遅れました。

>>かずまさん
解説ありがとうございます。
図を二枚ほど描いてようやっと理解しました。
中点とか直線の公式とかそうやって計算できるのは知りませんでした。

私が3日前の時点で考えていたやり方は直線[p1,p2]と直線[p2,p3]のベクトルを
合成してp2の±90度の点を生成するやり方だったので、かずまさんのやり方とは
ちょっと違いますね。

てか座標の絡むアルゴリズムを考えてるときって直線とベクトルの扱い方とか
言葉の使い分けができてないので頭の中ぐちゃぐちゃになります。

曲線バージョンの方は例の如くまだ理解できていないのですが、これはBスプライン曲線ですか?
それと実行するとクリックした瞬間にエラーがでるのですが私の環境だけでしょうか?

コード:

Node &n0 = nodes[i], &n1 = nodes[i - 1];
88行目のここでエラー終了しているようです。

反転スコープ
記事: 15
登録日時: 6年前
住所: 岐阜

Re: 太線の描画アルゴリズム

#28

投稿記事 by 反転スコープ » 5年前

usao さんが書きました:
5年前
元の折れ線データ(緑)からスプライン曲線(赤)作って,
それを適当に両側に移動(青と紫)…
これが3次スプライン曲線ですか?

wikipediaとか見た感じ自分では手に負えそうもないですね。
ネットでスプライン曲線クラスみたいなのを掲載してくださってるサイトがあったので
今からいじいじする予定。

アバター
usao
記事: 1887
登録日時: 11年前

Re: 太線の描画アルゴリズム

#29

投稿記事 by usao » 5年前

スプラインは,数式が簡単で実装容易なCatmull-Romスプラインを使いました.

アバター
usao
記事: 1887
登録日時: 11年前

Re: 太線の描画アルゴリズム

#30

投稿記事 by usao » 5年前

「アルゴリズム」という件名なので,一応,プランB(画像処理なアプローチ)でやった事柄も記しておく.


(B1)初めに,与えられた折れ線をスプラインで曲線的な形に加工したが,
 これはMustではない.元の折れ線のままでもいい.
(B2)「道路の絵」を描くのに十分な広さの画像領域を準備し,テキトーな背景色で塗りつぶしておく.
 (B1)の折れ線上の全ての位置(実際は適当な間隔でサンプリングした位置で良いが)に関して,
 その位置を中心とし直径を(道の幅)とした塗りつぶし円を描画する.
 (要は,めちゃくちゃ太いペンで折れ線を描いた)
(B3)カーブ内側の外周形状を丸めるために,
 (B2)の絵を(ある程度でかいカーネルサイズの)ガウシアンフィルタでぼかし,
 その結果を( (画像の背景輝度+描画輝度)/2 を閾値に用いて )2値化する.
(B4)このままだと,「道路の両端」も丸いので,ズバッと直線的に切る.
 折れ線の端点から方向を計算して要らない箇所を算出してその画素値を背景色に変えればいい.
 (ここまでで#23の絵における暗い赤の領域ができあがる)
 ※この処理は「単に,絵的な見栄えのため」という面が大きい.
  両端が丸いままの状態でも(B5)の処理に影響がないならば,この処理は不要.
(B5)あとは両側輪郭を,素朴な輪郭追跡処理でも行って取得すれば良い.
 (#23で言うところの,黄色い箇所の座標群を取得する)
 最後に,適当にデータを間引けばよいかな.

かずま

Re: 太線の描画アルゴリズム

#31

投稿記事 by かずま » 5年前

反転スコープ さんが書きました:
5年前
それと実行するとクリックした瞬間にエラーがでるのですが私の環境だけでしょうか?

コード:

Node &n0 = nodes[i], &n1 = nodes[i - 1];
88行目のここでエラー終了しているようです。
すみません。i = 0 のとき node[i-1] を参照できないからでしょう。
次のように、n1 の宣言を if (i > 0) { の後に移動してください。

コード:

			Node &n0 = nodes[i];

			DrawCircle(n0.E.x, n0.E.y, 5, color2);
			DrawCircle(n0.F.x, n0.F.y, 5, color2);

			if (i > 0) {
				Node &n1 = nodes[i-1];
				vector2 a1, b1, a0, b0, c1, d1;
反転スコープ さんが書きました:
5年前
曲線バージョンの方は例の如くまだ理解できていないのですが、これはBスプライン曲線ですか?
曲線バージョンは書いていません。
#19 は、角を落として、短い直線で結んだものです。
#20 は、角の頂点を、短い直線の両端に移したものです。

では、曲線バージョンを次に示します。
でも、曲線というのは嘘で、正十二角形で近似しています。

コード:

#include "DxLib.h"
#include <math.h>
#include <vector>

#define WIDTH 40

using namespace std;

enum { MOUSE_LEFT, MOUSE_RIGHT, MOUSE_MIDDLE, MOUSE_ALL };

struct Point { double x, y; };
struct Node {
	Point P, A, B, C, D, E, F;
	vector<Point> arc;
	bool turn;
};

int WINAPI WinMain(HINSTANCE hi, HINSTANCE pi, LPSTR cl, int cs)
{
	unsigned int mousePressingCount[MOUSE_ALL] = { 0 };

	vector<Node> nodes;
	int color = GetColor(0, 0, 0);

	ChangeWindowMode(TRUE);
	SetBackgroundColor(255, 255, 255);

	if (DxLib_Init() == -1) return -1;
	SetDrawScreen(DX_SCREEN_BACK);
	
	while (!ProcessMessage() && !ScreenFlip() && !ClearDrawScreen()) {
		int mouseState = GetMouseInput();
		if (mouseState & MOUSE_INPUT_LEFT) mousePressingCount[MOUSE_LEFT]++;
		else mousePressingCount[MOUSE_LEFT] = 0;
		if (mouseState & MOUSE_INPUT_RIGHT) mousePressingCount[MOUSE_RIGHT]++;
		else mousePressingCount[MOUSE_RIGHT] = 0;
		if (mouseState & MOUSE_INPUT_MIDDLE) mousePressingCount[MOUSE_MIDDLE]++;
		else mousePressingCount[MOUSE_MIDDLE] = 0;
	
		DrawFormatString(0, 0, color, "MouseLeftButton = %d",
				mousePressingCount[MOUSE_LEFT]);
		DrawFormatString(0, 20, color, "MouseRightButton = %d",
				mousePressingCount[MOUSE_RIGHT]);
		DrawFormatString(0, 40, color, "MouseMiddleButton = %d",
				mousePressingCount[MOUSE_MIDDLE]);

		if (mousePressingCount[MOUSE_LEFT] == 1) {
			int mouseX, mouseY;
			GetMousePoint(&mouseX, &mouseY);
			Node node = { (double)mouseX, (double)mouseY, };
			nodes.push_back(node);

			int n = nodes.size();
			if (n >= 2) {
				Node &n1 = nodes[n - 1], &n2 = nodes[n - 2];
				double dx = n1.P.x - n2.P.x, dy = n1.P.y - n2.P.y;
				double dist = sqrt(dx * dx + dy * dy);
				double ux = dx / dist * (WIDTH / 2);
				double uy = dy / dist * (WIDTH / 2);
				n1.A = { n1.P.x - uy, n1.P.y + ux };
				n1.B = { n1.P.x + uy, n1.P.y - ux };
				n2.C = { n2.P.x - uy, n2.P.y + ux };
				n2.D = { n2.P.x + uy, n2.P.y - ux };

				if (n == 2) {
					n1.E = n1.A, n1.F = n1.B;
					n2.A = n2.E = n2.C, n2.B = n2.F = n2.D;
				}
				else  {  // n >= 3
					n1.E = n1.C = n1.A, n1.F = n1.D = n1.B;
					Node &n2 = nodes[n - 2], &n3 = nodes[n - 3];
					double x12 = n1.A.x - n2.C.x, y12 = n1.A.y - n2.C.y;
					double x32 = n3.C.x - n2.A.x, y32 = n3.C.y - n2.A.y;
					double k1 = n2.C.y * x12 - n2.C.x * y12;
					double k3 = n2.A.y * x32 - n2.A.x * y32;
					double x, y, k = x12 * y32 - x32 * y12;
					if (k == 0)
						x = n1.C.x, y = n1.C.y;
					else {
						x = (x32 * k1 - x12 * k3) / k;
						y = (y32 * k1 - y12 * k3) / k;
					}
					n2.E = { x, y };
					n2.F = { n2.P.x*2 - x, n2.P.y*2 - y };
					n2.turn = (n2.B.y - n2.A.y) * (n2.D.x - n2.C.x) >
							(n2.B.x - n2.A.x) * (n2.D.y - n2.C.y);
					Point s1, s2;
					if (n2.turn)
						s1 = n2.A, s2 = n2.C;
					else
						s1 = n2.B, s2 = n2.D;

					const double PI = 3.141592653589793238;
					x = s1.x - n2.P.x, y = s1.y - n2.P.y;
					double t1 = atan2(y, x);
					x = s2.x - n2.P.x, y = s2.y - n2.P.y;
					double t2 = atan2(y, x);
					if (abs(t2 - t1) > PI)
						if (t1 < 0) t1 += 2*PI;
						else if (t2 < 0) t2 += 2*PI;
					if (t1 > t2) swap(t1, t2), swap(s1, s2);

					for (int i = 0; i < 8 && t1 < t2; t1 += PI / 6, i++)
						n2.arc.push_back({ WIDTH / 2 * cos(t1) + n2.P.x,
						                   WIDTH / 2 * sin(t1) + n2.P.y });
					n2.arc.push_back(s2);
				}
			}
		}
		if (mousePressingCount[MOUSE_RIGHT] == 1) nodes.clear();

		for (int i = 0; i < nodes.size(); i++) {
			int color2 = GetColor(100, 0, 0), color3 = GetColor(224, 128, 0);
			Node &n0 = nodes[i];
			DrawFormatString(10, i * 20 + 60, color,
				"P[%2d] = { %3.0f, %3.0f }", i, n0.P.x, n0.P.y);
			DrawCircle(n0.P.x, n0.P.y, 3, color);

			if (i > 0) {
				Node &n1 = nodes[i-1];
				Point a0, b0, a1, b1, c1, d1;

				if (n1.turn)
					a1 = n1.C, b1 = n1.F, c1 = n1.A, d1 = n1.C;
				else
					a1 = n1.E, b1 = n1.D, c1 = n1.B, d1 = n1.D;

				if (n0.turn)
					a0 = n0.A, b0 = n0.F;
				else
					a0 = n0.E, b0 = n0.B;

				DrawLine(a1.x, a1.y, a0.x, a0.y, color3, 2);
				DrawLine(b1.x, b1.y, b0.x, b0.y, color3, 2);
				int n = n1.arc.size();
				for (int i = 1; i < n; i++)
					DrawLine(n1.arc[i-1].x, n1.arc[i-1].y,
						n1.arc[i].x, n1.arc[i].y, color3, 2);
				DrawCircle(a0.x, a0.y, 3, color2);
				DrawCircle(b0.x, b0.y, 3, color2);
				DrawCircle(a1.x, a1.y, 3, color2);
				DrawCircle(b1.x, b1.y, 3, color2);
				DrawCircle(c1.x, c1.y, 3, color2);
			}
		}
	}
	DxLib_End();
	return 0;
}

アバター
usao
記事: 1887
登録日時: 11年前

Re: 太線の描画アルゴリズム

#32

投稿記事 by usao » 5年前

元の折れ線データの各中間ノードにおいて4点(カーブ外側3点,内側1点)を算出することをやってみた.
SidePoly.png
算出結果
SidePoly.png (6.25 KiB) 閲覧数: 14042 回
計算内容は長々と文章で書くより図を見た方が早いかと.
* 赤青2本の矢印は元の折れ線のエッジの法線
* 緑の線はその2本の矢印が成す角を2等分する線
Fig1.png
図1
Fig1.png (7.15 KiB) 閲覧数: 14042 回
* カーブ内側の点(緑線の下端)は,図2のオレンジ色の直角三角形で二重線で示した角のcosに関する式を立てればおk.
 (このcos値は矢印と緑線の内積から算出可能)
Fig2.png
図2
Fig2.png (8.98 KiB) 閲覧数: 14042 回

反転スコープ
記事: 15
登録日時: 6年前
住所: 岐阜

Re: 太線の描画アルゴリズム

#33

投稿記事 by 反転スコープ » 5年前

すいません。 また返信遅れました。
usao さんが書きました:
5年前
スプラインは,数式が簡単で実装容易なCatmull-Romスプラインを使いました.
ありがとうございます!ネットで公開されていたクラスを使っただけですが、
Catmull-Romスプラインで曲線の実装ができました!
今、手元にunityの環境がないので完成したものは掲載できませんが、
掲示板に記録として残しときたいので、今度画像貼りますね。

画像処理的なやり方の方はまだ試してませんが
unityでopenCVが使えるのか、そこから調べないとです。

反転スコープ
記事: 15
登録日時: 6年前
住所: 岐阜

Re: 太線の描画アルゴリズム

#34

投稿記事 by 反転スコープ » 5年前

あっ、ここの掲示板のスレって2ページ目とかあったんですね。
これから目を通します。

アバター
usao
記事: 1887
登録日時: 11年前

Re: 太線の描画アルゴリズム

#35

投稿記事 by usao » 5年前

オフトピック
折れ線から単純にスプライン計算すると激しく暴れる
→制御点の数を増やしつつ,形も修正する感じで…
→つまり折れ線を再分割しつつ形もいい感じに丸めていけばどうの
→あーだこーだ方法を考えて実装して動かしたところ…

 *Bezier を再発明している!*

=終=

返信

“C言語何でも質問掲示板” へ戻る